We describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. The algorithms, based on novel parallelization techniques for Very Long Instruction Word (VLIW) architectures, find and place together independently executable operations that may be far apart in the original code. i.e., they may be separated by many conditional branches or belong to different iterations of a loop. As a result, the functional units in the superscalar are presented with more work that can proceed in parallel, thus achieving higher performance than the approach of using hardware instruction dispatch techniques alone.While general scheduling techniques improve performance by removing idle pipeline cycles, to further improve performance on a superscalar with only a few functional units requires a reduction in the pathlength. We have designed a set of new algorithms for reducing pathlength and removing stalls due to branches, namely speculative load-store motion out of loops, unspeculation, limited combining, basic block expansion, and prolog tailoring. These algorithms were implemented in a prototype version of the IBM RS/6000 xlc compiler and have shown significant improvement in SPEC integer benchmarks on the IBM POWER machines.Also, we describe a new technique to obtain profiling information with low overhead, and some applications of profiling directed feedback, including scheduling heuristics, code reordering and branch reversal.

We describe a novel architectural framework that allows software applications written for a given Complex Instruction Set Computer (CISC) to migrate to a different, higher performance architecture, without a significant investment on the part of the application user or developer. The framework provides a hardware mechanism for seamless switching between two instruction sets, resulting in a machine that enhances application performance while keeping the same program behavior (from a user perspective). High execution speed on migrated applications is achieved through automated translation of the object code of one machine to that of the other, using advanced global optimization and scheduling techniques. Issues affecting application behavior, such as precise exceptions, as well as self-modifying code, are addressed. Relaxation of full compatibility on these issues lead to further possible performance gains, encouraging applications to adopt the newer architecture.

An approach to the generation of test patterns for implementation-level faults is presented. The approach involves fault simulation on a functional-level description of a combinational VLSI design, together with an appropriate functional fault model. The methodology uses the difference fault model (DFM), a formal abstraction of the faults at the implementation level, as the basis for fault simulation at the functional level. Incremental information from fault simulation results provides guidance for the generation of nonuniformly random test patterns using a backtracing process. The quality of the generated patterns is measured in terms of their coverage of implementation faults.>

A formal approach to the analysis of a combinational circuit described at the high level is presented. It produces information conducive to the acceleration of test generation algorithms. This analysis yields, as its main product, information which can be used to reduce the amount of effort expended during backtracing, by guiding this process towards decisions (assignments) less likely to cause conflicts and minimizing the amount of work between backtracks. RIDDLE, an algorithm which performs this analysis in time linear in the number of signals, is introduced. Experimental results for the special case of combinational gate-level designs are also given.>

An approach to estimate the fault coverage of the implementation of a VLSI design obtained by fault simulation at the function level is presented. The proposed methodology begins by defining a fault model for the functional level, the difference fault model (DFM), which reflects all of the faults in the implementation level. Functional fault detection is recorded by performing a functional simulation of the design, with faults injected as determined by the DFM. The last step is to use the correspondence between the functional faults (in the DFM) and those of the implementation level to yield an estimate of the implementation fault coverage. The results obtained show a very good correlation between the estimated fault coverage, based on fault simulation at the functional level, and the actual fault coverage obtained by fault simulation on a gate-level implementation.>

A formal approach to the analysis of combinatorial gate-level designs is presented which produces information conducive to the acceleration of test generation algorithms. This analysis yields, as its main product, information which can be used to reduce the amount of effort expended during backtracing by guiding this process towards decision (assignments) less likely to cause conflicts and by minimizing the amount of work between backtracks. The G-RIDDLE approach is introduced for performing this analysis, as a refinement of the more general case which handles designs consisting of multi-input/multioutput combinatorial blocks. Experimental results are given for a popular benchmark of combinatorial gate-level designs.>

SLS, a large-capacity, high-performance switch-level simulator developed to run on an IBM System/370 architecture is described. SLS uses a model which closely reflects the behavior of MOS circuits. The high performance is the result of mixing a compiled model with the more traditional approach of event-driven simulation control, together with very efficient algorithms for evaluating the steady-state response of the circuit. SLS is used for design verification/checking applications and for estimating fault coverage.>

With the advent of VLSI, relatively large processing arrays may be realized in a single VLSI chip. Such regularly structured arrays take considerably less time to design and test, and fault-tolerance can easily be introduced into them. However, only a few computational algorithms which can effectively use such regular arrays have been developed so far.

The effect of incorporating a priority scheme into a data flow computer is studied in this paper. Specifically, we deal with the scheduling of instructions in a data flow program, and the mechanisms by which such scheduling may be implemented within a data flow computer. We show that the assignment of priorities to data flow operations is a special case of a problem in scheduling theory, and also belongs to the NP-complete class of problems. Therefore, we develop a heuristic approach, based on the well-known Critical Path algorithm, as a basis for determining instruction priorities. Our conclusions, based on the simulation of programs executed in a modified data flow computer, show that adding a priority mechanism is not justifiable in the general case. This is due mostly to the inability to reach the potential improvement offered by scheduling operations, because of implementation restrictions. Nevertheless, certain algorithms (e. g., DFT) can still benefit from the proposed scheme, mainly because of their highly regular, static structure.

We describe SLS, a large capacity, high performance switch level simulator, developed to run on an IBM System/370 architecture, that uses a model which closely reflects the behavior of MOS circuits. This performance is the result of mixing a compiled model with the more traditional approach of event-driven simulation control, together with very efficient algorithms for evaluating the steady state response of the circuit. SLS is used for design verification/checking applications and for estimating fault coverage.

This work deals with some performance aspects of the implementation of an algorithm to simulate MOS electronic circuits, modeled at the transistor level. The target architecture is a special purpose logic simulation machine, the Yorktown Simulation Engine (YSE), which has no direct support for loop mechanisms or conditional flow control. Since the simulation algorithm requires such mechanisms to determine whether and when a circuit reaches a steady state, we must calculate prior to simulation time, the number of iterations required for the algorithm to converge. We show how to arrange the order in which transistors are processed, aiming at a reduced number of such iterations, and therefore, an improved simulation performance. The results presented here show the optimal way to deal with acyclic circuits and some heuristic criteria to handle cyclic circuits. Also, we show a method to calculate the number of iterations required for the convergence of the simulation algorithm. These methods, originally developed for the YSE, have been also incorporated in a switch level simulator running on an IBM/370 architecture.

Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology. Such an implementation requires an area-economical mapping of a tree on a plane. Novel mapping schemes for trees onto hexagonal arrays (or grids) and appropriate algorithms are proposed here and shown to be superior over known mappings on square arrays (or grids).

A geometric programming model is developed to optimize delayed-staging (DS) storage hierarchies. These hierarchies have direct paths between the CPU and the k fastest storage levels (k = 1 in a linear hierarchy), allowing for some concurrency in the flow of data through the hierarchy. The criterion for optimization is the minimization of average hierarchy access time subject to budgetary limitations, given the cache access time and the backing-store capacity.

A procedure to efficiently obtain fault ratios for all levels in multilevel delayed-staging (D-S) storage hierarchies without recurring to simulation runs for each configuration desired is presented. The procedure is based on the applicability of stack processing techniques to D-S configurations and requires simulation runs for two-level hierarchies only.