In deep sub-micron (DSM) designs, performance will depend critically on the latency of long wires. We propose a new synthesis methodology for synchronous systems that makes the design functionally insensitive to the latency of long wires. Given a synchronous specification of a design, we generate a functionally equivalent synchronous implementation that can tolerate arbitrary communication latency between latches. By using latches we can break a long wire in short segments which can be traversed while meeting a single clock cycle constraint. The overall goal is to obtain a design that is robust with respect to delays of long wires, in a shorter time by reducing the multiple iterations between logical and physical design, and with performance that is optimized with respect to the speed of the single components of the design. We describe the details of the proposed methodology as well as report on the latency insensitive design of PDLX, an out-of-order microprocessor with speculative-execution.

It is widely believed that any true (or sensitizable) critical path of length /spl ges/2 T must be speeded up in order for a circuit to have a delay

We address the problem of encoding the state variables of a finite state machine such that the BDD representing its characteristic function has the minimum number of nodes. We present an exact formulation of the problem. Our formulation characterizes the two BDD reduction rules by deriving conditions under which these reduction rules can be applied. We then provide an algorithm that finds these conditions and solves the problem by formulating it as a 2-CNF formula and extracting all its prime implicants. In addition to this, we implemented a simulated annealing algorithm for this problem and provide a thorough experiment of the impact of encoding on a BDD representing an FSM with different orderings.

Asynchronous circuits operate correctly only under timing assumptions. Hence testing those circuits for delay faults is crucial. Previous work has shown that full-scan delay-fault testing of asynchronous circuits is feasible. In this work, we tackle the problem of partial-scan testing, which requires test-pattern generation on a sequential circuit. We show how this problem can be effectively reduced to a classical problem of stuck-at test-pattern generation for a related combinational circuit. The reduction is done in three steps. The first step reduces testing of an asynchronous sequential circuit, by using a partial-scan approach, to testing an object called an asynchronous net, in which feedback is allowed only inside asynchronous memory elements. We then decompose the problem of testing asynchronous nets into that of initializing memory elements (the second step), followed by robust path delay fault testing (the third step). We provide effective procedures to solve both the initialization and the test-pattern generation problem. The technique is complete, automated, and requires only partial scan of some memory element outputs.

A trace driven methodology for logic synthesis and optimization is proposed. Given a logic description of a digital circuit C and an expected trace of input vectors T, an implementation of C that optimizes a cost function under application of T is derived. This approach is effective in capturing and utilizing the correlations that exist between input signals on an application specific design. The idea is novel since it proposes synthesis and optimization at the logic level where the goal is to optimize the average case rather than the worst case for a chosen cost metric. The paper focuses on the development of algorithms for trace driven optimization to minimize the switching power in multi level networks. The average net power reduction (internal plus I/O power) obtained on a set of benchmark FSMs is 14%, while the average reduction in internal power is 25%. We also demonstrate that the I/O transition activity provides an upper bound on the power reduction that can be achieved by combinational logic synthesis.

Asynchronous circuits operate correctly only under timing assumptions. Hence testing those circuits for delay faults is crucial. The paper describes a three step method to detect possible delay faults in a sequential asynchronous circuit. The delays that are to be tested must be provided by the synthesis system. By using this information a set of paths in the circuit that must be tested is identified (step 1). For these paths the circuit is made acyclic by inserting at least one scan latch in every cycle (step 2). Then test patterns are generated for these paths (step 3). These test patterns consist of setup and initialization vectors and the final test vector. We provide effective procedures to solve both the initialization and the test pattern generation problem. The latter problem is solved by reduction to a classical problem of stuck-at test pattern generation for a related combinational circuit. Finally, a heuristic is proposed to determine which state variables must become part of a scan chain, or for which input variables the positive and negative phase must be driven independently in test mode. Experimental results shows that a high level of path delay fault testability can be achieved with partial scan.

This paper is concerned with approximate delay computation algorithms for combinational circuits. As a result of intensive research in the early 90's efficient tools exist which can analyze circuits of thousands of gates in a few minutes or even in seconds for many cases. However, the computation time of these tools is not so predictable since the internal engine of the analysis is either a SAT solver or a modified ATPG algorithm, both of which are just heuristic algorithms for an NP-complete problem. Although they are highly tuned for CAD applications, there exists a class of problem instances which exhibits the worst-case exponential CPU time behavior. In the context of timing analysis, circuits with a high amount of reconvergence, e.g. C6288 of the ISCAS benchmark suite, are known to be difficult to analyze under sophisticated delay models even with state-of-the-art techniques. To make timing analysis of such corner case circuits feasible we propose an approximate computation scheme to the timing analysis problem as an extension to the exact analysis method proposed previously. Sensitization conditions are conservatively approximated in a selective fashion so that the size of SAT problems solved during analysis is controlled. Experimental results show that the approximation technique is effective in reducing the total analysis time without losing accuracy for the case where the exact approach takes much time or cannot complete.

In this paper, we present a symbolic minimization procedure to obtain optimal two-level implementations of finite-state machines. Encoding based on symbolic minimization consists of optimizing the symbolic representation, and then transforming the optimized symbolic description into a compatible two-valued representation by satisfying encoding constraints (bitwise logic relations) imposed on the binary codes that replace the symbols. Our symbolic minimization procedure captures the sharing of product terms due to ORing effects in the output part of a two-level implementation of the symbolic cover. Face, dominance, and disjunctive constraints are generated. Product terms are accepted in a symbolic minimized cover only when they induce compatible encoding constraints. At the end, a set of codes that satisfy all constraints is computed. The quality of this synthesis procedure is shown by the fact that the cardinality of the cover obtained by symbolic minimization and of the cover obtained by replacing the codes in the initial cover and then minimizing it with ESPRESSO are very close. Experiments show that in some cases, our procedure improves on the best results of state-of-art tools.

ion, which eliminates details that are of no importance when checking whether a design satisfies a particular property. ffl Decomposition, which consists of breaking the design at a given level of the hierarchy into components that can be designed and verified almost independently. These mechanisms can be applied to different classes of designs: from embedded controllers to computers, from microprocessors to digital-to-analog converters. They are not only useful in the verification process but also in the design process per se making verification itself unnecessary in some cases. For example, formalization of the design specifications is required for formal verification but it also helps in design transfer between different organizations eliminating the risk of losing knowledge about the design and its specifications, thus making verification before and after the transfer unnecessary. We argue that almost all advances in verification stem from the application of these three basic con...

We propose a novel procedure for testing all multiple stuck-faults in a logic circuit using two complementary algorithms. The first algorithm finds pairs of input vectors to detect the occurrence of target single stuck-faults independent of the occurrence of other faults. The second uses a sophisticated branch and bound procedure to complete the test set generation on the faults undetected by the first algorithm. The technique is complete and applies to all circuits. Experimental results presented in this paper demonstrate that compact and complete test sets can be quickly generated for standard benchmark circuits.

Article Timed shared circuits: a power-efficient design style and synthesis tool Share on Authors: Luciano Lavagno Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CA Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CAView Profile , Patrick C. McGeer Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CA Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CAView Profile , Alexander Saldanha Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CA Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CAView Profile , Alberto L. Sangiovanni-Vincentelli Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CA Cadence Berkeley Laboratories, 1919 Addison Street, Suite 301, Berkeley-CAView Profile Authors Info & Claims DAC '95: Proceedings of the 32nd annual ACM/IEEE Design Automation ConferenceJanuary 1995 Pages 254–260https://doi.org/10.1145/217474.217538Online:01 January 1995Publication History 21citation231DownloadsMetricsTotal Citations21Total Downloads231Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An approach for fast discrete function evaluation based on multi-valued decision diagrams (MDD) is proposed. The MDD for a logic function is translated into a table on, which function evaluation is performed by a sequence of address lookups. The value of a function for a given input assignment is obtained with at most one lookup per input. The main application is to cycle-based logic simulation of digital circuits, where the principal difference from other logic simulators is that only values of the output and latch ports are computed. Theoretically, decision-diagram based function evaluation offers orders-of-magnitude potential speedup over traditional logic simulation methods. In practice, memory bandwidth becomes the dominant consideration on large designs. We describe techniques to optimize usage of the memory hierarchy.

The main disadvantage of the path delay fault model is that to achieve 100% testability every path must be tested. Since the number of paths is usually exponential in circuit size, this implies very large test sets for most circuits. Not surprisingly, all known analysis and synthesis techniques for 100% path delay fault testability are computationally infeasible on large circuits. We prove that 100% delay fault testability is not necessary to guarantee the speed of a combinational circuit. There exist path delay faults which can never impact the circuit delay (computed using any correct timing analysis method) unless some other path delay faults also affect it. These are termed robust dependent delay faults and need not be considered in delay fault testing. Necessary and sufficient conditions under which a set of path delay faults is robust dependent are proved; this yields more accurate and increased delay fault coverage estimates than previously used. Next, assuming only the existence of robust delay fault tests for a very small set of paths, we show how the circuit speed (clock period) can be selected such that 100% robust delay fault coverage is achieved. This leads to a quantitative tradeoff between the testing effort (measured by the size of the test set) for a circuit and the verifiability of its performance. Finally, under a bounded delay model, we show that the test set size can be reduced while maintaining the delay fault coverage for the specified circuit speed. Examples and experimental results are given to show the effect of these three techniques on the amount of delay fault testing necessary to guarantee correct operation.>

A common approach to performance optimization of circuits focuses on re-synthesis to reduce the length of all paths greater than the desired delay .We describe a new delay optimization procedure that optimizes only sensitizable paths greater than .Unlike previous methods that use topological analysis only, this method accounts for both functional and topological interactions in the circuit.Comprehensive experimental results comparing the proposed technique to a state-of-the-art performance optimization procedure are presented for combinational and sequential logic circuits.

The existence of redundant stuck-faults in a logic circuit is potentially detrimental to high-speed operation, especially when there are false paths that are longer than the circuit delay. Keutzer, Malik, and Saldanha (KMS) in IEEE transactions of Computer Aided Design, vol. 10, no. 4, p. 427, April 1991 have proved that redundancy is not necessary to reduce delay by presenting an algorithm that derives an equivalent irredundant circuit from a given redundant circuit, with no increase in delay. The KMS algorithm consists of an iterative loop of timing analysis, gate duplications, and redundancy removal to successively eliminate long false paths. In this paper we resolve the main bottlenecks of the KMS algorithm by providing an efficient single-pass algorithm to simultaneously remove all long false paths from a given circuit. We achieve this by relating a circuit structure property based on path lengths to the testability (redundancy) and delay. The application of this algorithm to a variety of related logic synthesis problems is described.>

Three encoding problems relevant to the synthesis of digital circuits are input, output, and state encoding. Several encoding strategies have been proposed in the past that decompose the encoding problem into a two step process of constraint generation and constraint satisfaction. The latter requires the assignment of binary codes to symbols subject to the satisfaction of constraints on the codes. This paper focuses on the constraint satisfaction problem. We prove that constraint satisfaction is NP-complete. We develop a framework for the satisfaction of both input and output encoding constraints, and describe a polynomial time (in the number of symbols to be encoded) algorithm to check for the existence of a solution for a set of input and output constraints. An exact algorithm to determine the minimum number of encoding bits required to satisfy all the given constraints is provided, and a heuristic algorithm is also described. The application of this framework to a variety of encoding problems with different cost functions is illustrated. Experimental results on standard benchmarks are given for the exact and heuristic algorithms.>

The main disadvantage of the path delay fault model is that to achieve 100% testability every path must be tested.Since the number of paths is usually exponential in circuit size, atl known analysis and synthesis techniques for 100% path delay fault testability are infeasible on most circuits.In this paper, we show that 100'%odelay fault testability is not necessary to guarantee the speed of a combinational circuit.There exist path delay faults which can never impact the circuit delay (computed using arty correct timing analysis method) unless some other path delay faults also affect i~hence these delay faults need not be considered in delay fault testing.Next, assuming only the existence of robust delay fault tests for a very small set of paths, we show how the circuit speed can be selected such that 100% robust delay fault coverage is achieved.

Three relevant encoding problems are input, output and state encoding.Several algorithms have been proposed for their solutions that decompose the problem into symbolic minimization (yielding a set of constraints) and constraint satisfaction.At least two exact formulations of the input encoding constraint satisfaction problem exist.However, a more important use of encoding is in state assignment of finite state machines where both input and output encoding constraints must be satisfied to obtain the most effective implementations.We develop a framework for the simultaneous satisfaction of input and output encoding constraints.We describe an algorithm, polynomial in the number of symbols to be encoded, to check for the existence of a solution for a set of input and output constraints.We provide an efficient atgorithm that determines the minimum number of encoding bits required to satisfy all the given constraints.We demonstrate how heuristic algorithms can be developed within the framework.Firtatly, we discuss the use of this framework in solving a variety of encoding problems with different cost functions.Some preliminary results on medium sized machines are given for both exact and heuristic algorithms.

The authors introduce an efficient method for generating the functional forms of path analysis problems. They demonstrate that the resulting function is linear in the size of the circuit. The functions are then tested for satisfiability either using a Boolean network satisfiability algorithm suggested by T. Larrabee (1989) or through the construction of BDDs. The effectiveness of the proposed approach is shown for timing analysis and robust path delay-fault test generation. This method also holds promise for both static and dynamic hazard analysis, and for test generation using all other delay-fault models, tau -irredundant fault models, and stuck-open fault models.>

The question of whether single stuck-at-fault redundancies are necessary to increase performance or whether they are only an unnecessary by-product of performance optimization is addressed. A constructive resolution of this question is given in the form of an algorithm that takes as input a combinational circuit and returns an irredundant circuit that is as fast. The utility of this algorithm is demonstrated on a well-known circuit, the carry-skip adder, and a novel irredundant design of that adder is presented. As the algorithm may either increase or decrease circuit area, the authors leave unresolved the question as to whether every circuit has an irredundant circuit that is at least as fast and is of equal or lesser area.>

Logic optimization procedures principally attempt to optimize three criteria: performance, area and testability. The relationship between area optimization and testability has recently been explored. As to the relationship between performance and testability, experience has shown that performance optimizations can, and do in practice, introduce single stuck-at-fault redundancies into designs. Are these redundancies necessary to increase performance or are they only an unnecessary byproduct of performance optimization? In this paper we give a constructive resolution of this question in the form of an algorithm that takes as input a combinational circuit and returns an irredundant circuit that is as fast. We demonstrate the utility of this algorithm on a well known circuit, the carry-skip adder, and present a novel irredundant design of that adder. As our algorithm may either increase or decrease circuit area, we leave unresolved the question as to whether every circuit has an irredundant circuit that is at least as fast and is of equal or lesser area.

Since redundancy is undesirable in high performance circuits, the authors explore timing optimization procedures to determine whether performance optimization may be achieved without introducing redundancy. They demonstrate the conditions under which timing optimization may introduce single stuck-fault redundancies into a given irredundant circuit and illustrate the difficulties in removing or preventing these redundancies. The authors then resolve the question of whether a testability criterion exists that may be retained or easily maintained as invariant during timing resynthesis.>

Simplification of a multi-level network is used to perform form transformations on parts of the network to obtain an alternate structure that is optimal with respect to area. A technique for obtaining such an optimal structure involves the use of two-level logic minimization on the components of the multi-level logic network. At each component, the structure of the network is captured by intermediate and fan-out don't care sets, which are utilized in the two-level minimization. However, the generation of all the don't cares yield very large sets for most networks and consequently the complete minimization of the components of the circuits require a very large amount of computer time. In this paper we describe algorithms to reduce the size of the don't care sets, so that only the portions that will be useful in minimization at each component of the circuit are retained. We develop both an exact filter and a heuristic filter that prove to be very effective for a large set of benchmark examples. Results show that our technique achieves the same quality as that obtained by doing complete minimizations at each component of the circuits but in much shorter time. This new approach to simplification of multi-level networks has been incorporated into the MIS (version 2.1) logic synthesis system.

An automatic tool that heuristically determines a good partitioning of a single large programmable logic array (PLA) into a PLA with a smaller number of encoded outputs (and usually fewer product terms), followed by a set of decoders to regenerate the original outputs, has been developed. Initial results using logic descriptions of processor chips and a benchmark set of industrial PLAs show area savings of up to 35% and delay reductions of up to 45%. The approach can be considered an alternative to Boolean decomposition and factoring in multilevel logic synthesis.>