The first-generation IMPACT predication technology has made a strong contribution in the area of branch handling and predication-based code scheduling. The second-generation IMPACT predication technology is designed to allow much more aggressive exploitation of instruction-level parallelism within the predicated compilation framework. The compiler techniques being developed in this project include accurate global flow analysis of predicated code, partial reverse if-conversion, advanced predication-based code optimizations, fully resolved predicates, and advanced predication-based dependence height reduction. The architecture techniques being developed include predication-based branch prediction and new predication manipulation instructions.

The objective is to provide architecture expertise and compiler prototypes required for the microprocessor industry to understand the cost and effectiveness of each level of hardware support. First, the design complexity of architecture support, including silent instructions, sentinel hardware, conditional move instructions, conditional store instructions, and conditional execution of all instructions, is studied. Second, compiler software is developed: if-conversion, reverse if-conversion, optimizers, and schedulers that become increasingly aggressive as the level of architecture support increases. Third, an integrated approach is defined to coordinate speculative execution and predicated execution to best improve program execution performance.

Compilers for instruction-level parallel (ILP) processors often use profile information to make critical optimization decisions. As new techniques to support fast profiling continue to emerge, profile-based optimizations will soon become commercially feasible. However, open questions remain regarding the stability of profile-based optimizations in the presence of conflicting execution profile due to different input sets. This project deals with static program analysis and code transformation techniques re- quired to minimize the potential performance variation when using profile information in advanced compiler transformations.

Improvements in memory speeds have not kept pace with increasing processor clock frequency and improved exploitation of instruction-level parallelism. Consequently, the gap between processor and memory speeds is expected to grow, increasing the number of execution cycles spent waiting for memory accesses to complete. One solution to this growing problem is to reduce the number of cache misses by increasing the effectiveness of the cache hierarchy. The objective of this project is to develop techniques for dynamic analysis of program data access behavior, which is then used to guide proactively the placement of data within the cache hierarchy in a location-sensitive manner.

The objective of this project is to develop advanced code parallelization and optimization techniques to take advantage of the wide issue capabilities of the coming generations of X86 processors. Techniques investigated include profile-driven optimizations, height reduction, region compilation, code scheduling for reduction in register pressure, and register allocation. The project deals with real system performance and industry standard benchmark programs such as SPEC. Techniques must deal with real-world constraints imposed by the X86 architecture.

The Illinois Computing Laboratory for Aerospace Systems and Software (ICLASS) is a NASA center for excellence in aerospace computing. Its research focus is in the areas of parallel architectures and algorithms, reliable and fault-tolerant computing, distributed and real-time systems, and software engineering and artificial intelligence. Problems being addressed include system-level functional test generation, measurement and simulation of parallel I/O environments, advanced compilation technology for high-performance digital signal processing systems, development and analysis of parallel simulation algorithms, a design environment for fault-tolerant systems, dependability of validation-performance systems, reliable streams in ad hoc networks, predictable, high-speed communication for workstation clusters, performance analysis, virtual reality, and parallel I/O, systems support for high-performance parallel applications, and support environments for process and artifact design.

This project will investigate the development of automated design environments to validate performance and dependability of high-availability systems. Methods that allow detailed performance and reliability design via automatic fault injection and analysis will be investigated. Fault injection geared to evaluate the system under high-stress conditions will be developed. The analysis will be supported by various on-line dependability analysis tools that can quantify performability bottlenecks in the system. Graphical environments to display performance parameters, such as resource utilizations, queue length, and resource contention in an animated form, will also be developed to allow the designer to make effective reliability/speed trade-offs.

The diagnosis of a persistent problem that may surface intermittently is often difficult. For the diagnosis to be effective, it is imperative that the system be able to relate errors occurring in the different components/functions and at different times. The purpose of this study is to develop effective techniques for recognizing the symptoms of persistent problems and investigate the feasibility of this approach for failure/error prediction. The goal is to automate and formalize a process to relate errors occurring in different parts of a system. Thus, given a problem we will determine whether it is an intermittent manifestation of a common fault or an isolated incident. The approach will be based on the recognition of error symptoms, the history of system behavior, and the level and type of system activity.

There is a need for a high level of dependability in computer systems such as aircraft and aerospace systems, medical and automotive equipment, and high-speed network switching devices. This research will develop an integrated design framework in which developers of these systems can eliminate dependability risks early in the design process. Using relatively simple descriptions of the system's behavior, designers can test for dependability in a hierarchical manner, from the chip level to the system level, long before the system is built. This approach helps ensure the dependability of critical systems while reducing the time, effort, and cost of developing them. This is a joint project with Stanford University.

This project will investigate new design and validation techniques that are critical for predictably dependable highly networked systems. The research will develop an interactive dependability evaluation methodology embodied in a portable automatic tool and a design methodology for rapid recovery and preemptive diagnosis for hetero geneous high-performance computing networks. Creating system-independent and easily scalable techniques for comparing different designs and prototypes from a fault tolerance perspective will provide a key solution to where and when to introduce fault tolerance for maximum effectiveness and cost benefit, which will help ensure that highly networked systems can maintain a sustained period of robust and responsive operation.

The objective of this research is to develop tools and methodologies for design of VLSI systems for testability, reliability, and manufacturability. The complexity of VLSI systems has increased the need for the development of chip design methodologies that emphasize easily prov- able and manufacturable functionality, performance, and reliability. This program addresses a wide range of design issues, each dealing with various aspects of reliable VLSI design, including research in fault simulation, test generation, design and synthesis for testability, and fault diagnosis.

The objective of this work is to develop an automatic test generation and diagnosis system for the large chips envisioned by the high-performance computing (HPC) and communications industry. Testing is a major roadblock in the design and manufacture of large complex chips, and the problem of testing is getting more difficult with the increasing size and complexity of chips. Genetic algorithms (GAs) have been demonstrated to provide an effective framework for test generation. Our goal is to extend this GA framework to allow for the complex circuitry envisioned in the next generation of HPC systems.

The objective of this work is to extend existing and develop new performance and dependability evaluation algorithms, including new methods to speed up simulation, reduce the rate of state-space growth in analytical state-based methods, and extend the domain of models for which analytical methods may be applied. Existing methods are unable to solve for combined performance/dependability (performability) measures, needed in complex, degradable, satellite networks. The impact of this work will be shown through prototype implementations in UltraSAN, a stochastic activity network-based software package for performance/dependability evaluation.

The objective of this work is to develop new model-based analysis techniques having applications to bioinformatics. We are particularly interested in developing methods for simulating systems with rare events, using a method known as importance sampling. One avenue of research will be to find good ``biasing schemes'' for systems represented as stochastic activity networks within particular application domains. Another area is in methods for numerically solving models that have mixes of exponential and deterministic timings. Prototype implementations of the developed methods will be made and incorporated in UltraSAN, a stochastic activity network-based software package for performability evaluation.

The goal of this work is to study the robust transport of multiclass traffic, with differing quality-of-service constraints, in the presence of failures. In particular, the focus will be to develop efficient methods to route co-existing real-time applications such as video and voice. A judicious method for admitting and routing multiclass traffic is important to provide an acceptable quality of service as well as to maximize network throughput and revenue. Both transient and steady-state behavior will be considered in the choice of appropriate routing schemes.

The goal of this work, conducted jointly with Purdue University and the U.S. Navy, is to develop new approaches to dependability design and analysis that are failure-, application-, and system-comprehensive. The work at the University of Illinois will focus on assessment techniques, developing an application-independent model specification language and techniques to solve the specified models. Together with the work at Purdue and the navy, this work will provide tools for analysis that guarantee rapid real-time recovery, consider the highly networked nature of current military C2 computing environments, and provide for the impact of degraded services on command decisions.

The aim of this work is to develop new technques for large-scale discrete event simulation, including new algo rithms for parallel simulation, measure-based sequential simulation, and analysis of simulation results. We are developing parallel simulation algorithms that adapt to the dynamic behavior of a model for improved performance. We are also developing methods to simulate only those parts of a model that contribute to evaluation of the set of measures for improved speedup. Finally, we are developing techniques to use the structure of a model to provide more meaningful statements about accuracy. The impact of this work will be shown through prototype implementations in UltraSAN.

Current large distributed applications cannot specify the dependability they require from remote objects and subsystems and cannot adapt to changes in resource availability. The objective of this project is to make dramatic improvements in the specification of dependability requirements in the prediction of dependability under varying conditions, and in the adaptability of the applications and resource management strategies by providing infrastructure mechanisms to support dynamic behavior. The goal is to specify an application's availability requirements through defining a set of acceptable operating regions and adapting when we predict that various thresholds of predicted dependability will not be met.

The goal of this research is to address two important problems in computer system modeling with the purpose of providing practical algorithms for the analytical/numerical solution of systems represented as stochastic activity networks. In particular, we are (1) investigating methods to reduce the memory necessary to solve numerically systems represented as stochastic activity networks while still obtaining solutions in a reasonable amount of time and (2) investigating numerically stable and memory-efficient methods to solve for the reward accumulated during a finite mission time. Solutions to these problems are necessary to make practical the evaluation of complex space and aerospace systems.

The objective of this research is to develop an integrated services network architecture across hybrid ad hoc packet cellular and wireline networks. We propose a new type of quality of service called adaptive service, which addresses the unique requirements of a mobile computing environment, while also being compatible with traditional integrated services in wireline networks. This research develops the network architecture and resource management algorithms required for providing adaptive service in hybrid mobile computing environments.

The objective of this research is to develop a distributed computing platform across hybrid wireline/wireless networks to support seamless user mobility across different networks. As a result of mobility between different networks with vastly different resources, the applications need to adapt gracefully to dynamic changes in perceived network quality of service. We are building the PRAYER distributed system, which features systems support for both seamless mobility and adaptive computing.

We have developed a new probabilistic measure called probability of win, which can handle changes in distribution of performance values from one problem domain to another. Our results have been implemented in TEACHER, a prototype learning system under development for the past few years. We have applied our learning system to learn better heuristics for (1) process placement on massively parallel processing systems, (2) branch-and-bound search in solving combinatorial search problems, (3) load balancing in networks of workstations, (4) designing more robust blind equalizers in cellular communication, (5) tuning parameters in VLSI circuit testing, placement, and routing, (6) designing artificial neural networks automatically, and (7) tuning parameters in stereo vision.

We utilize emerging VLSI technologies that allow tens to hundreds of vector pipelines to be implemented in one chip. Instead of competing for precious area in the same chip as regular instruction-set architectures, we design and evaluate a supervector processor in a separate chip. This is feasible as vector instructions, once initiated, can continue to execute until completion without close supervision by the instruction-set architecture. We are studying three interrelated issues: (1) architecture of coprocessor, (2) software for exploiting parallelism, and (3) system simulation and evaluation. Our design will allow computation-intensive loops to be executed at a rate far exceeding that provided by current co-processors.

In this project, we develop a method called NOVEL (Nonlinear Optimization Via External Lead) for solving continuous and discrete global optimization problems. These problems are characterized by a nonlinear objective function, with or without a collection of nonlinear constraints. Such problems exist in many engineering applications that include operations research, signal processing, and function optimization. NOVEL addresses the balance between global search and local search, using a trace to aid in identifying promising regions before committing to local searches. We have applied NOVEL to find significantly better solutions than existing ones in filter-bank design, neural network learning, and constraint-satisfaction problems in operations research and combinatorial optimization.

In this project, we study issues related to the efficient operation and resource scheduling of local area and mobile networks. We study three related issues in resource scheduling: (1) efficient contention of shared network channels using a window-based multiaccess protocol, (2) intelligent filtering of statistical status information to aid in resource scheduling and network monitoring, and (3) efficient placement and migration of data and information to reduce network traffic. We are developing a prototype system to integrate solutions developed for each of these issues.