Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-06-12
2001-02-20
Teska, Kevin J. (Department: 2763)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06192508
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to integrated circuit design and layout.
2. State of the Art
Traditional cell-based integrated circuit design follows several steps. The first step is designing the logical gate-level circuit that implements the function to be realized by the circuit (referred to as logic design or logic synthesis, of which logic optimizations are a key part). The next step is placing the gates (or cells) in a physical layout, and the final step is routing the interconnection between the cells. With increasing dominance of interconnection delays and area in circuits implemented in deep submicron technologies, this approach is proving to be no longer viable. The problem is that, during the logic optimization stage, the interconnection is not known yet, and thus the dominant part of the area and the delay cannot be considered.
Attempts to overcome this problem have considered alternating logic synthesis and placement and routing, with “back annotation” of the interconnect information to the subsequent logic synthesis steps. Referring to
FIG. 1
, showing traditional cell-based design flow, a logic design phase is followed by a cell placement phase and then a routing phase. Following the routing phase, interconnection data is back annotated. The logic design, cell placement and routing phases are then repeated. This cycle is continued until, during the routing phase, the design is successfully routed. The problem with this method is that the logic synthesis steps that consider the back annotation information cannot guarantee to fix problems that prevent routing without introducing additional problems due to the modifications made to the circuit gates and topology. There results a large number of iterations between logic synthesis and subsequent place and route, with the possibility of the process never converging.
An alternative approach is to consider placement information during logic optimization. In this methodology, sometimes termed “placement aware synthesis,” placement information is made available in varying degrees during logic optimization, i.e. some placement is done as part of logic synthesis (sometimes referred to in the industry as just synthesis). Logic optimization uses this placement information to estimate the effect of the interconnects on the delay and the area of the circuit. Thus logic optimization attempts to accurately model the interconnect delay and area that might result during a placement step. However, it may result in a placed circuit that cannot be routed using the area resources provided by the placement step. The inability to route the resulting placed circuit results in modifications to the placement, consequently nullifying the interconnection information used during logic optimization.
A circuit that has been placed but cannot be routed subject to the available area constraints is not realizable. Additional routing resources must be created to enable the routing. There results an increase in circuit area and possibly delay, since the wires may now need to go through longer paths.
Placement algorithms are limited in how they can place cells by the timing constraints placed on the design. The timing constraints may result in certain parts of the design being very congested in terms of the wiring (or interconnection) resources needed to connect the cells in those parts of the circuit. It would be possible to relieve the congestion if somehow the cells in the congested area were to be moved apart. However, moving the cells apart may result in an increase in the interconnection delays, which in turn may result in a violation of the timing constraints. Thus a situation results where it is possible to have acceptable timing slacks or acceptable congestion but not both.
The paper by Villarubia and Hojat (ICCD 97) proposes integrated logic optimization and placement. However, the proposed methodology alternates placement and logic optimization and does not consider the impact of the logic optimizations on subsequent placement steps.
SUMMARY OF THE INVENTION
This invention recognizes the ability of logic optimization to help placement relieve congestion. Different types of logic optimizations are used to help placement relieve congestion. In one type of optimization, the speed of parts of the circuit is improved by selecting faster cells. In another type of optimization, the topology of the circuit is changed such that placement can now move cells, which could not have been moved before, to reduce congestion and thus enable routing. A distinguishing feature of this methodology is that it not only uses the placement information for interconnection delay/area estimates during logic optimization, but also uses logic optimization to aid the physical placement steps by providing support to placement so that the congestion of the circuit is improved. The aim is to avoid getting into a situation where the placed circuit cannot be routed.
There are two specific ways in which logic optimization aids placement in relieving congestion. The first method involves determining parts of the circuit which are congested, and then speeding up the logic in these parts. This speedup provides timing slack for a subsequent placement step to move cells while ensuring that this move does not cause the modified interconnections to violate timing constraints. The second method involves modifying the topology of the circuit by adding gates while maintaining the functionality, such that the added gates can then be moved by the placement steps to relieve congestion.
An important aspect of the optimizations, specifically directed towards helping placement relieve congestion, is the ability to undo modifications if placement does not actually use the modifications. The undo capability ensures that no area/power resources are wasted for transformations that are not used as intended.
A critical problem in using logic optimization as part of placement is that logic optimization steps can and do increase the area of circuits. This increase in area can invalidate the results of any placement done thus far, and consequently result in the inability of the combination of these steps to converge. An important part of this invention is to actively bound the area increase of specific parts of the circuit which guarantees that the current placement results are still valid after the logic optimizations, consequently guaranteeing convergence of the integrated logic optimization and placement steps.
REFERENCES:
patent: 4484292 (1984-11-01), Hong et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5561772 (1996-10-01), Dorner et al.
patent: 5572482 (1996-11-01), Hoshizaki et al.
patent: 5847965 (1998-12-01), Cheng
Boyle Douglas B.
Chakraborty Abhijeet
Malik Sharad
Pileggi Lawrence
Yeap Gary K.
Burns Doane Swecker & Mathis L.L.P
Jones Hugh
Monterey Design Systems
Teska Kevin J.
LandOfFree
Method for logic optimization for improving timing and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for logic optimization for improving timing and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for logic optimization for improving timing and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2569755