Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-02-22
2001-12-25
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06334205
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and a device for optimal technology mapping in logic circuit designs; in particular, a method and device for optimally mapping circuit delay and other cost functions on directed acyclic graphs.
2. Discussion of Related Art
In high-performance logic circuit designs, meeting delay targets in the control logic imposes a major challenge. Control logic usually undergoes changes till very late in the design cycle. Control logic is quite often not regular enough to lead to an intuitive data-flow type implementation. Logic synthesis is therefore necessary to meet the project schedules for these high-performance designs, and ensure a correct implementation of the irregular subcircuits. Logic synthesis is the process of automatically generating optimized logic-level representation from a high-level description. With the rapid advances in integrated circuit technology and the resultant growth in design complexity, designers increasingly rely on logic synthesis to shorten the design time while achieving performance objectives.
Known logic synthesis systems typically employ a three-phase methodology. The phases are usually: (1) technology independent optimization; (2) technology mapping; and (3) timing corrections. See, L. Stok et al. Booledozer logic synthesis for asics.
IBM Journal of Research and Development
, Vol. 40(4): 407-430, July 1996. Varying the three phases impact greatly the structure and cost functions of technology mapped logic. Cost functions affect the area of the cells, delay through the cells or other measures of merit. See “Technology mapping in MIS”, E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, November 1987. Minimizing delay in the technology mapping phase had been an important goal in the aforementioned designs.
Traditional technology mapping can be described as a 3-step procedure. First, the technology-independent circuit is decomposed in terms of some primitives to have some well-defined logic structure to aid the technology mapping process. This phase is typically referred to as the circuit decomposition phase. Second, a pattern matcher performs analysis on the circuit and the library, either structurally or functionally, and determines a set of matches for all nodes in the circuit. The third and final step identifies the best set of matches (based on some cost functions) for the circuit such that every node in the circuit is covered exactly once. The final set of matches that cover all the nodes in the circuit are used to describe the circuit in terms of the target technology library cells.
Another target of optimization in circuit synthesis is the reduction of the area of the cells. In K. Keutzer. Dagon: “Technology binding and local optimization by dag matching”, In
Proc of the
24
th Design Automation Conference
, June 1987, a technology independent net list description of a combinational circuit is partitioned into a forest of trees, then using a tree pattern matching automation, individual trees are matched to create a technology bound circuit. The least cost in size or area is obtained. Drawback of this technique is that it is only optimal for trees. Most circuits consist of directed acyclic graphs (DAGs) and require a non-trivial decomposition of the DAGs into trees.
Technology mapping works mostly on a fixed subject graph. Therefore, the result is highly dependent on the preceding decomposition of the network. In E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, “Logic decomposition during technology mapping”,
IEEE Trans on CAD
, 16(8):813-834, August, 1997, logic decomposition is combined with the mapping phase itself to avoid problems of optimizations in disconnected phases. The proposed algorithm runs on tree leaf DAGs. However, exhaustive embedding of decompositions leads to a large increase in the subject graph, which renders the algorithm impractical for larger sizes of circuits.
A need therefore exists for a simple and practical device and method for logic circuit design that is delay optimized for DAGs.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, a method for optimizing a cost function in logic synthesis for directed acyclic graphs is provided, comprising the steps of: partitioning a circuit into a plurality of slices, each slice representing a subcircuit, each subcircuit having a netlist, a head boundary closer to primary outputs, and a tail boundary closer to primary inputs of the circuit; matching each net in each subcircuit by advancing from the head boundary of the first subcircuit through each partitioned subcircuit in the direction of primary outputs while generating and implementing cell matches; covering each net in each subcircuit by advancing from the tail boundary of the first subcircuit through each partitioned subcircuit in the direction of primary outputs while performing timing analysis and selecting matches having optimal times; and discarding portions of subcircuits not selected.
According to another aspect of the present invention, a stored program device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing a cost function in logic synthesis is provided, the method steps comprising: partitioning a circuit into a plurality of slices, each slice representing a subcircuit, each subcircuit having a netlist, a head boundary closer to primary outputs, and a tail boundary closer to primary inputs of the circuit; matching each net in each subcircuit by advancing from the head boundary of the first subcircuit through each partitioned subcircuit in the direction of primary outputs while generating and implementing cell matches; covering each net in each subcircuit by advancing from the tail boundary of the first subcircuit through each partitioned subcircuit in the direction of primary outputs while performing timing analysis and selecting matches having optimal times; and discarding portions of subcircuits not selected.
Preferably, the method for optimizing a cost function in logic synthesis includes use of fall and rise time delay models in performing timing analysis for each net in each subcircuit. The step of selecting matches preferably includes selection from a load-independent delay library.
Further, the step of generating and implementing cell matches may include one of or a combination of a structural matcher, a boolean matcher and a PLA matcher.
REFERENCES:
patent: 4703435 (1987-10-01), Darringer et al.
patent: 4816999 (1989-03-01), Berman et al.
patent: 4916627 (1990-04-01), Hathaway
patent: 5029102 (1991-07-01), Drumm et al.
patent: 5282147 (1994-01-01), Goetz et al.
patent: 5519627 (1996-05-01), Mahmood et al.
patent: 5784557 (1998-07-01), Oprescu
patent: 5787010 (1998-07-01), Schaefer et al.
patent: 5790416 (1998-08-01), Norton et al.
patent: 5854926 (1998-12-01), Kingsley et al.
Stok et al., “BooleDozer: Logic Synthesis for ASICs,” IBM Journal of Research and Development, vol. 40, No. 4, pp. 407-430, Jul. 1996.
Shepard et al., “Design Methodology for the s/390 Parallel Enterprise Server G4 Microprocessors, ” IBM Journal of Research and Development, vol. 41, No. 4/5, pp. 515-547, Jul./Sep. 1997.
Detjen et al., “Technoloby Mapping in MIS,” IEEE, pp. 116-119, 1987.
Kurt Keutzer, “DAGON: Technology Binding and Local Optimization, ” 24thACM/IEEE Design Automation Conference, Paper 21.1, pp. 341-347, 1987.
Lehman et al., “Logic Decomposition During Technology Mapping” .
Grodstein et al., “a Delay Model for Logic Synthesis of Continuously-Sized Networks” .
Iyer Mahesh A.
Stok Leon
Sullivan Andrew J.
F. Chau & Associates LLP
International Business Machines - Corporation
Smith Matthew
Speight Jibreel
LandOfFree
Wavefront technology mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wavefront technology mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wavefront technology mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2564141