Retiming is a very promising transformation of circuits which preserves functionality and improves performance. Its benefits are especially promising in automatic synthesis of circuits from higher-level descriptions. However, retiming has not been widely included in current design tools and methodologies. One of the main obstacles is the problem of finding an equivalent initial state for the retimed circuit. In this paper, we introduce a simple modification of the retiming algorithm of Leiserson and Saxe. The modified algorithm helps minimize the effort required to find equivalent initial states and reduces the chance that the network needs to be modified in order to find an equivalent initial state. This algorithm is the kernel of a new efficient retiming method, which searches for optimal retimings while preserving the initial state condition. The paper also presents an improved method to perform the initial state calculation.

A Decoded INstruction Cache (DINC) is a buffer between the instruction decoder and other instruction pipeline stages. In this paper, we explain how techniques that reduce the branch penalty on a DINC, can improve CPU performance. We also analyze the impact of some of the design parameters of DINC's on variable instruction length computers. Our study indicates that tuning the mapping of the instructions into the cache can improve performance substantially. Tuning must be based on the instruction length distribution for a specific architecture. In addition, the associativity degree has a greater effect on the DINC's performance than on the performance of regular caches. We discuss the difference between the performance of DINC's and other caches, when longer cache lines are used. We present a model to estimate the miss rate based on its characteristics, that are discussed and analyzed throughout this paper. Our conclusions are based on both analytical study and trace driven simulations of several integer UNIX applications.>

A Decoded INstruction Cache (DINC) serves as a buffer between the instruction decoder and the other instruction-pipeline stages. In this paper we explain how techniques that reduce the branch penalty based on such a cache, can improve CPU performance. We analyze the impact of some of the design parameters of DINCs on variable instruction-length computers, e.g., CISC machines.

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.>

An approach to test for delay faults is presented. A variable size delay fault model is used to represent these failures. The nominal gate delays with the manufacturing tolerances are an integral part of the model and are used in the propagation of simplified waveforms through the logic network. The faulty waveforms are functions of the variable-size delay fault. For each fault and test pattern, a threshold is computed such that this fault is detected if its size exceeds epsilon . This threshold is used (along with the minimum slack at the fault site) to determine a metric called quality. The quality of detection for a fault measures how close the test came to exposing the ideally smallest-size fault at that point. This metric (together with the traditional fault coverage) gives a complete measure of the goodness of the test.>

For pt.I see ibid., p.857-66 (1988). A novel algebra is introduced for delay test generation. The algebra combines the nine natural logic values (00 , 01, 0X, 10, 11, 1X, X1, XX) with special attributes that record both heuristic choices and whatever information about waveforms is deducible algebraically (i.e. without numerical computations using actual gate delays). A test generator uses this algebra in an efficiently organized backtrack search. The test generator is linked to a delay fault simulator. Previous event-driven simulators have considered different types of events; one type of event is a change in faultless values from one test to another test, and the other type of event is a difference between faulty and faultless values. The presented simulator is driven by both types of events. Each generated test is simulated to determine the quality of detection.>

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.>

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.