Netlist resynthesis program based on physical delay calculation

Details Netlist resynthesis program based on physical delay calculation Netlist resynthesis program based on physical delay calculation

2000-12-14

2003-04-29

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

06557144

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the design of integrated circuits (ICs) using computer-aided design and computer-aided engineering programs (CAD/CAE). In particular, the present invention relates to CAD/CAE programs that optimize the design of an IC.
BACKGROUND OF THE INVENTION.
The design process for an integrated circuit (IC) is a process of transforming a specification for desired logic or analog functions to a physical or geometric arrangement for an IC die that can -perform the desired functions. Modern integrated circuits, particularly VLSI circuits, are very complex and various stages in the design process are automated using CAD/CAE software tools.
Typically, a technology mapping program will be used to convert a specification into an arrangement of library elements, such as gates, and interconnections. The output of the technology mapping process is a trial netlist which lists the library elements used and their interconnections, also called nodes. The technology mapping process is iterative and several trial netlists may be tried before an accepted netlist is found that has acceptable delays for each node based on a simplified delay calculation performed as part of the technology mapping. This simplified delay calculation, however, does not take into account the physical placement of the elements or interconnections.
Next, a physical placement program is used to specify geometric locations for each library element and also a geometric path for each interconnect. After a trial physical placement is made, a more complex delay calculation is made that takes into account the physical placement of the library elements and the interconnections. As the more complex delay calculation identifies critical nodes with excessive delays, the physical placement is iteratively repeated to reduce the delay to an acceptable amount. In some cases, the delay does not converge to an acceptable delay, and development activity returns to the technology mapping program to generate another accepted netlist to be tried by the physical placement program.
At the end of the process, an accepted netlist and global placement are created that may satisfy the delay requirements, however, because of the limitations of the simple delay calculations made in the technology mapping program, the netlist and global placement may not be optimized well for implementation as an IC.
A program is needed that will optimize the netlist and the global placement without, the limitations imposed by the simple delay calculations in the technology mapping used to generate the netlist.
SUMMARY OF THE INVENTION
Disclosed is a computer program that improves a netlist of logic nodes and physical placement for an IC. The program (a) identifies critical nodes based on delay information calculated from the physical placement. Then the program (b) selects a set of critical nodes and optimally collapses their critical fan-ins and part of the non-critical fan-ins based on their Boolean relationship, which includes at least one critical node. After that, the program (c) remaps the collapsed sub-netlist by covering its subject graph with an optimal pattern graph, and by dynamically estimating and updating the fanout loads. The program returns to step (b) if the remapped sub-netlist is unacceptable, and returns to step (a) after updating the delay information and coordinates of newly mapped gates if the remapped sub-netlist is acceptable. The program exits at step (a) when no more critical nodes are identified at step (a)


REFERENCES:
patent: 5526514 (1996-06-01), Pradhan et al.
patent: 5875117 (1999-02-01), Jones et al.
patent: 5917728 (1999-06-01), Ueda
patent: 5999715 (1999-12-01), Sato
patent: 6009248 (1999-12-01), Sato et al.
patent: 6030110 (2000-02-01), Scepanovic et al.
patent: 6038385 (2000-03-01), Scepanovic et al.
patent: 6068662 (2000-05-01), Scepanovic et al.
patent: 6075933 (2000-06-01), Pavisic et al.
patent: 6085032 (2000-07-01), Scepanovic et al.
patent: 6405345 (2002-06-01), Ginetti
M. Pedram et al. Layout Driven Technology Mapping, 28thACM/IEE Design Automation Conference, pp. 99-105, Jun. 1991.*
A. Lu et al., Technology Mapping for Simultaneous Gate and Interconnect Optimisation, IEEE Proceedings of Computers and Digital Techniques, pp. 21-31, Jan. 1999.*
E. Sentovich et al., Sequential Circuit Design Using Synthesis and Optimization, VLSI Design: VLSI in Computers and Processors, pp. 328-333, Oct. 1992.*
“Combining Technology Mapping with Post-Placement Resynthesis for Performance Optimization” by A. Lu et al.,IEEE, pp. 616-621, (1998).
“Computing the Area Versus Delay Trade-Off Curves in Technology Mapping” by K. Chaudhary et al.,IEEE,pp. 1480-1489, (1995).
“Delay Estimation and Optimization of Logic Circuits: A Survey” by M. Fujita et al.,IEEEpp. 25-30, (1997).
“Multi-Level Logic Optimization by Implication Analysis” by W. Kunz et al.,ACM,pp. 6-13, (1994).
“Post-Layout Logic Restructuring for Performance Optimization” by Y. Jiang et al.,ACM,pp. 662-665, (1997).
“Post-Layout Optimization for Deep Submicro Design” by K. Sato et al.,ACM,pp. 740-745, (1996).
“Technology Mapping of LUT based FPGAs for Delay Optimisation” by X. Lin et al,FPL,pp. 245-254 (1997).
“Timing Driven Placement in Interaction with Netlist Transformations” by G. Stenz et al.,ISPD,pp. 36-41, (Apr. 1997).

Affiliated with

Also associated with

Rating

Netlist resynthesis program based on physical delay calculation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Netlist resynthesis program based on physical delay calculation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Netlist resynthesis program based on physical delay calculation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3007158