Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-03-24
2001-06-26
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06253356
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to logic circuits and, more particularly, to a method and apparatus for improving logic synthesis by fanout optimization.
2. Description of the Related Art
Logic circuits designs attempt to reduce a number of timing and capacitance violations. Fanout optimization is one method of achieving this reduction. Fanout optimization is the construction of a buffer tree to drive large capacitive loads so that timing and capacitance violations are reduced as much as possible. Fanout optimization is important in improving the performance of a logic circuit during logic synthesis but is one of the most time consuming synthesis transforms.
A proposed method of addressing the fanout problem is addressed in an article by K. J. Singh et al., “A Heuristic Algorithm for the Fanout Problem”, pp. 357-360, Proc. of the 27th Design Automation Conference, 1990. The method described in this article relies on heuristics which assume some template topology for the buffer tree and then use some intelligent combinational search to select a buffer size for each tree node and a sink arrangement. These types of methods are polynomial in the number of sinks, the number of stages in the buffer tree and the number of buffers available in the library. As a result the runtime can be prohibitive when the number of sinks and the number of available buffers are large. The conventional approach typically builds a fanout tree based on the sizes and loads of buffers.
Therefore, a need exists for a fanout optimization method and apparatus for increasing the speed of logic synthesis. A further need exists for obtaining buffer sizes and a topology of a buffer tree while avoiding a combinational search by using an underlying delay model of the buffers. Yet another need exists for a method of reasoning with gain to build a fanout tree.
SUMMARY OF THE INVENTION
A method of fanout optimization includes the steps of inputting a net list including fanout regions, each fanout region having sources, each source being coupled to at least one sink, determining a gain for inverters to be placed in a buffer tree, wherein the gain has a same value for all inverters to be placed within the tree, computing a number of inverters used to couple the source to each sink and introducing inverters into the buffer tree to couple the source to each sink.
In alternate methods, the step of selecting inverters for the buffer tree from a library may also be included. A cost function may be used to select the gain based on layout area. The gain may be selected by the step of varying a value of the gain within a gain window until layout area is at a lowest value. The step of apportioning a delay on a path between inverters by assigning a level value for each path for representing the number of the inverters between each sink and the source of each path may be included. The step of apportioning the delay may further include assigning the level by taking a ratio between a delay on the path between a source and a sink a delay of an inverter, and truncating a result by removing a fractional portion. The step of modifying the level for each path based on a polarity of the sink may also be included. The step of constructing the buffer tree by sizing the inverters based on a load calculated between the source and the sink for each path and dividing by the gain may be included. The step of combining inverters on a path by introducing a larger inverter to replace multiple smaller inverters on the path may also be included.
A method for reducing timing and capacitance violations in logic circuits includes the steps of identifying problematic fanout regions of a circuit, the fanout regions having a source coupled by a path to at least one sink, determining a gain based on a cost function for inverters to be introduced into the circuits between on each path, constructing a buffer tree for each fanout region by calculating a number of inverters on the path between the source and each sink in accordance with load and timing constraints and placing the inverters in the buffer tree starting from each sink and moving toward the source.
In alternate methods, the step of selecting inverters for the buffer tree from a library may be included. The cost function may select the gain based on layout area. The gain may be selected by the step of varying a value of the gain within a gain window until layout area is at a lowest value. The step of apportioning a delay on a path between inverters by assigning a level value for each path for representing the number of the inverters between each sink and the source of each path may be included. The step of apportioning the delay may further include assigning the level by taking a ratio between a delay on the path between a source and a sink a delay of an inverter, and truncating a result by removing a fractional portion. The step of modifying the level for each path based on a polarity of the sink may be included. The step of constructing the buffer tree may include the step of sizing the inverters based on a load calculated between the source and the sink for each path and dividing by the gain. The step of combining inverters on a path by introducing a larger inverter to replace multiple smaller inverters on the path may also be included.
A system for reducing load and timing violations in logic circuits includes means for inputting a net list including fanout regions, each fanout region having sources, each source being coupled to at least one sink, means for determining a gain for inverters to be placed in a buffer tree, wherein the gain has a same value for all inverters to be placed within the tree and is determined based on a cost function, means for computing a number of inverters used to couple the source to each sink and means for introducing inverters into the buffer tree to couple the source to each sink.
In alternate embodiments, the system may include inverters for the buffer tree selected from a library. The inverters may be single stage inverters.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.
REFERENCES:
patent: 5396435 (1995-03-01), Ginetti
patent: 5402356 (1995-03-01), Schaefer et al.
patent: 5648911 (1997-07-01), Grodstein et al.
patent: 5654898 (1997-08-01), Roetcisoender et al.
patent: 5799170 (1998-08-01), Drumm et al.
patent: 6006023 (1999-12-01), Higashida
Kung et al “A Fast Fanout Optimization Algorithm for Near-Continuous Buffer Libraries,” IEEE, pp. 352-355, Jun. 1998.*
Navarro et al “CMOS Tapered Buffer Design for Small Width Clock/Data Signal Propagation,” IEEE, pp. 89-94, Feb. 1998.*
Carragher et al “Simple Tree-Construction Heuristics for the Fanout Problem,” IEEE, pp. 671-679, 1995.*
Kanwar Jit Singh et al., “A Heuristic Algorithm for the Fanout Problem”, 27th ACM/IEEE Design Automation Conference, University of California, Berkeley, Paper 21.5, pp. 357-360, Jun. 1990.
Kang, M., Dai, W.W.,-M., Dillinger, T., and LaPotin, D., “Delay Bounded Buffered Tree Construction for Timing Driven Floorplanning”, IEEE/ACM International Conference on Computer-Aided Design, Nov. 13, 1997, pp. 707-712.*
Alpert, C., and Devgan, A., “Wire Segmenting for Improved Buffer Insertion”, Proceedings of the 34th Design Automation Conference, Jun. 13, 1997, pp. 588-593.*
Brand, D., Damiano, R.F., van Ginneken, L.P.P.P., and Drumm, A.D., “In the Driver's Seat of BooleDozer”, Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, Oct. 12, 1994, pp. 518-521.*
Kodandapani, K., Grodstein, J., Domic, A., and Touati, H., “A Simple Algorithm for Fanout Optimization Using High-Performance Buffer Libraries”, IEEE/ACM International Conference on Computer-Aided Design, Nov. 11, 1993, pp. 466-471.*
Ginetti, A., and Brasen, D., “Modifying the Netlist after Placement for Performance Improvement”, Proceedings of the IEEE
F. Chau & Associates LLP
International Business Machines - Corporation
Siek Vuthe
Smith Matthew
LandOfFree
System and method for improving logic synthesis in logic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for improving logic synthesis in logic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for improving logic synthesis in logic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499033