System and chip synthesis must evaluate candidate Register-Transfer (RT) architectures with respect to finished physical designs. Current RT level cost measures, however, are highly simplified and do not reflect the real physical disign. Complete physical design, on the other hand, is quite costly, and infeasible to be iterated many times. In order to establish a more realistic assessment of layout effects, we propose a new layout model which efficiently accounts for the effects of wiring and floorplanning on the area and performance of RT level designs, before the physical design process. Benchmarking has shown that our model is quite accurate.

This paper tends to analyze the trends of the research in logic synthesis. The first part is devoted to an expertise of the efficiency of factorization methods developed during the last decade and to the proposal of dedicated methods for complex logic blocks. The second part shows the importance of Binary Decision Diagrams as representation of Boolean functions. Their use in the technology mapping phase of multiplexor-based FPGAs in an industrial tool is taken as illustration.

We present algorithms for the optimization of sequential synchronous digital circuits using structural model, i.e. interconnections of combinational logic gates and synchronous registers. This approach contrasts traditional methods using state diagrams or transition tables and leveraging state minimization and encoding techniques. In particular, we model circuits by synchronous logic networks, that are weighted multigraphs representing interconnections of gates implementing scalar combinational functions. With this modeling style, area and path delays are explicit and their variation is easy to compute when circuit transformations are applied. Sequential logic optimization may target cycle-time or area minimization, possibly under area or cycle-time constraints. Optimization is performed by a sequence of transformations, directed to the desired goal. This paper describes the fundamental mechansms for transformations applicable to sequential circuits. We review first retiming and peripheral retiming techniques. The former method optimizes the position of the registers, while the latter repositions the registers to enlarge maximally the combinational region where combinational restructuring algorithms can be applied. We consider then synchronous algebraic and Boolean transformations, that blend combinational transformations with local retiming. Both classes of transformations require the representation of circuits by means of logic expressions with labeled variables, the labels representing discrete time-points. Algebraic transformations entail manipulation of time-labeled expressions with algebraic techniques. Boolean transformations exploit the properties of Boolean algebra and benefit from the knowledge of don't care conditions in the search for the best implementation of local functions. Expressing don't care conditions for sequential circuits is harder than for combinational circuits, because of the interaction of variables with different time labels. In addition, the feasibility of replacing a local function with another one may not always be verified by checking for the inclusion of the induced perturbation in local explicit don't care set. Indeed, the behavior of sequential circuits, that can be described appropriately by the relation between input and output traces, may require relational models to express don't care conditions. We describe a general formalism for sequential optimization by Boolean transformations, where the don't care conditions are expressed implicitly by synchronous recurrence equations. We present then an optimization method for this model, that can exploit degrees of freedom in optimization not possible for other methods, and hence providing solutions of possible superior quality. We conclude by summarizing the major features and limitations of optimization methods using structural models.

We introduce automatic procedures for generating and verifying sufficient correctness properties of synchronous processors. The targeted circuits are synchronous array processors designed from localized, highly regular data dependency graphs (DDGs). The specification, in the form of a DDG, is viewed as a maximally parallel circuit. The implementation, on the other hand, is a (partially) serialized circuit. Since these circuits are not equivalent from an automata-theoretic viewpoint, we define the correctness of the implementation against the specification to mean that a certain relation (called the β-relation) holds between the two. We use a compositional approach to decouple the verification of the control circuitry from that of the data path, thereby gaining efficiency. An array processor in isolation may not have a definite flow of control, because control may reside in the data stream. Therefore, for the purpose of verification, we construct an auxiliary machine, which keeps a timing reference and generates control signals abstracted from a typical data stream. Sufficient correctness conditions are expressed as past-tense computation tree logic (CTL) formulae and verified by CTL model-checking procedures. Experimental results of the verification of a matrix multiplication array and a Gaussian elimination array are presented.

The Princeton University Behavioral Synthesis System (PUBSS) performs high-level synthesis on communicating processes. The compiler accepts models written in a subset of VHDL, but performs synthesis using a more specialized model, the behavior FSMs (BFSMs), for synthesis. The simulation semantics of VHDL presents challenges in describing behavior without overly constraining that behavior solely to make the simulation work. This paper describes mismatch between the simulation semantics provided by VHDL and the synthesis semantics required for high-level synthesis and describes how we solved these problems in PUBSS.

This paper describes the hierarchical behavioral description language celled SFL and its processing system. This integrated CAD system called PARTHENON is used for designs of the leading ASICs in the NTT Systems Labs. This paper shows, therefore, the effectiveness of PARTHENON as a practical high-lelel synthesis system through real design experience. SFL was developed to aid in the design of the hardware functions and behaviors of ASICs composed solely of clocksynchronized circuits. The main features of SFL are as follows: (1) It is not mixed with connection description, but employs only behavioral description (like procedual description in program language), and it provides hierarchical expression of behavioral description. (2) It permits the description of parallel processing operations by adopting a new hardware task concept. And, (3) it is linked with the behavioral simulator, logic synthesizer, and other components of the processing system. After describing SFL in some detail, a brief explanation of its synthesizer and other processing components is provided, along with its application results in the real design of some leading ASICs at the NTT Systems Laboratories.

This paper presents a description and an analysis of three standard" hardware description languages (HDLs): Very High Speed Integrated Circuit HDL (VHDL), Verilog-HDL, and Unified Design Language for Integrated Circuits (UDL/I), Kyoto University Education Chip (KUE-Chip) is used as a design benchmark to compare the features and syntax of VHDL, Verilog-HDL, and UDL/I.

A new applicative design language is proposed for developing generators of data-path modules from hardware algorithms. The language includes a set of primitives that represent placement operations, parameterized cells, routing patterns and a set of transformation rules specifying modifications of the module topology without changing its functionality. Using the language, a hardware algorithm designer can easily define both the topological and geometrical specifications of module generation directly at the functional level without engaged in the layout details. A sketch of the language and an example of module design with the language is presented.

Reducing communication complexity is a viable approach to multilevel logic synthesis. A communication complexity based approach was proposed previously. In the previous works, only disjoint input decomposition was considered. However, for certain types of circuits, the circuit size can be reduced by using overlapped decomposition. In this paper, we consider overlapped decompositions. Some design issues for overlapped decompositions such as detecting globals" and deriving subfunctions are addressed. Moreover, the Decomposition Don't Cares (DDC) is considered for improving the decomposed results. By using these techniques together, the area and delay of circuits can be further minimized.

In this paper, a new method of synthesizing multi-level logic circuits directly from binary decision diagrams (BDDs) is proposed. In the simple multiplexer implementation, the depth of the synthesized circuit was always O (n), where n is the number of input variables. The new synthesis method attempts to reduce the depth of circuits. The depth of the synthesized circuits is O (log n log w) where w is the maximum width of given BDDs. The synthesized circuits are 2-rail-input 2-rail-output logic circuits. The circuits have good testability; it is proved that the circuits are robustly path-delay fault testable and also totally self-checking for single stuck-at faults.

This paper shows that coherent optimization strategies for multilevel systhesis should rely on a good link between the factorization, the technology mapping and the netlist optimization. Factorization options are shown to play a key role. The technology mapping should optimize both area and critical path and only netlist structure preserving" optimization techniques (buffer insertion, gate replication) should be applied first to preserve the factorization decision. Only in a last step resynthesis of critical areas based on a local view is applied. The approach has been experimented on a set of large combinational benchmarks.

Logic synthesizers usually have good area minimization capabilities, producing circuits of minimal area. But good delay minimization techniques are still missing in current logic synthesis technology. In [7], the RENO algorithm (which stands for REsynthesis for Network Optimization) was proposed for minimizing the area of multi-level combinational networks, and its effectiveness in designing minimal-area networks has been demonstrated. In this paper, we present improvements and extensions of the RENO algorithm for network delay minimization by using Boolean resynthesis techniques. We will discuss new algorithms for gate resynthesis which have not only reduced the processing time significantly, but also have improved the quality of minimization. Due to the generality of the gate resynthesis algorithms, we can minimize both delay and area of a network concurrently in a unified way, and network delay is reduced significantly with no or very small area penalty. Extensive experimental results and comparison with the speed_up algorithm in SIS-1.0 are presented.

Test pattern generation is getting much harder as the circuit size becomes larger. One problem is that it tends to take much time and another one is that it is difficult to detect redundant faults. Aiming to cope with these problem, an enhanced unique sensitization technique is proposed in this paper. This powerful global implication reduces the number of backtracks with reasonable computational time. And a fast test pattern generator featuring this unique sensitization demonstrates its performance using large benchmark circuits with over ten thousands of gates. It takes only a minute to detect all testable faults and to identify all redundant faults of 20,000 gates circuit on a workstation.

Since the time required for testing logic circuits is proportional to the number of test vectors, the size of test sets as well as test generation time is one of the most important factors to be considered in test generation. The size of test sets becomes an essential issue, especially for scan designed circuits, because of the need to shift a test vector serially into the scan path. In this paper, we propose new methods of generating compact test sets to detect al the irredundant single stuck-at faults in combinational circuits. The proposed algorithms calculate a test function for each fault which corresponds to the set of all test vectors for the fault and generate a compact test set by analyzing the test functions. The analysis is based on finding a test vector which detects the largest number of remaining faults. Since our methods select a test vector among all the test vectors, represented by a test function, for a target fault, smaller test sets can be generated, in general, than that by conventional test set compaction methods. The experimental results show that the size of test sets generated by our method is about one-third as large as that without compaction.