Timing-driven global placement based on geometry-aware...

Details Timing-driven global placement based on geometry-aware... Timing-driven global placement based on geometry-aware...

2001-04-11

2002-11-12

Wong, Don (Department: 2821)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06480991

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to a system and method for designing and placing circuitry on semiconductor chips, and more particularly, to a system and method for incorporating a timing-closed placement solution into a physical design process of integrated circuitry.
2. Description of the Related Art
The development of electronic manufacturing technology has created the ability to build thousands of circuits on a single chip. To take advantage of this technology, thousands of circuits must by physically placed and connected on the chip. This can be a very time-consuming process, especially when the actual process of designing, placing and connecting the circuits on the chip can affect the performance and timing requirements of the chip. Therefore, it has become necessary to automate the design process by using a computer to quickly place and wire predesigned circuits into a functional chip.
The basic problem with this automation technique is that it sacrifices the performance of the resulting circuit for the ability to get a connected circuit in a reasonable amount of computing time. When the functional chip being designed is a central processing unit of a computer or other chip in which performance is critical and design complexity high, the performance sacrificed is not acceptable and the automation technique is not useful. This performance sacrifice usually manifests itself in the inability to obtain timing closure in complicated logic. Timing closure is the difference between the time allowed for processing information on the chip as logically designed, and the time required for processing information on the chip as physically designed.
Timing closure is not met when the chip as physically wired and placed is not as fast as required by the logical design.
With advances in VLSI technology, the size of modules in integrated circuits is becoming smaller and the density of modules on a chip is increasing. Consequently, intramodule delays are becoming smaller, and the total delay in the circuit is being dominated by delays in the interconnections between the modules. The communication-bounded nature of total circuit delay, along with more stringent timing requirements due to more aggressive design style, have made timing driven layout an important area of study. To meet the needs of a fast-expanding electronics industry, high performance chips must be designed in a short period. Accordingly, a design flow which incorporates timing analysis and verification into the physical design is desirable. This motivates the development of layout tools which optimize layout area and timing simultaneously.
The problem of timing-driven placement has been studied extensively over recent years. Existing timing-driven approaches can be broadly classified into net-based methods and path-based methods. In a net-based algorithm, timing constraints are first translated into physical constraints, such as upper and lower bounds on the lengths of nets. More specifically, net-based algorithms try to satisfy timing constraints by (1) assigning higher weights to nets which are part of critical paths, or (2) by transforming timing requirements into a set of upper bounds on the net delays. In scenario (1), minimizing the delay in a critical net may increase the delay in other nets. This may result in additional critical paths and the delays of the nets in these paths also then have to be minimized. This again may result in an excessive delay in the previous critical net. It is desirable to prevent this oscillating effect. In scenario (2) above, delay constraints on the paths are translated into either length or timing lower and upper bounds (slacks) for each net. The bounds are then used to guide the placement and routing. Timing driven placement optimization will not shorten nets that are below the threshold, but nets near or above the threshold are very strongly weighted for improvement. A major problem of these approaches is the selection of the weights or bounds. Also, the use of individual net bounds may overconstrain the problem.
Path-based methods consider timing requirements explicitly, and try to satisfy timing requirements and physical requirements simultaneously during the placement phase. A major difficulty encountered in path-based methods is the enormous complexity of computation. Path-based approaches overcome these difficulties via an optimization process which models the problem using paths instead of individual nets. The problem may be modeled as a linear programming or transforming the quadratic programming problem into a Lagrangian problem to reduce the number of constraints. However, this optimization process becomes very complex and time consuming in deep sub-micron designs.
A legal (or feasible) solution to the timing-driven placement problem should satisfy the following placement constraints: (1) Macros should be placed at legitimate locations without overlapping, (2) there should be sufficient space to implement interconnections, (3) timing constraints should be satisfied for all logically possible paths in the circuit, (4) region constraints should be satisfied, i.e., some modules may be placed only in an certain regions, for example, (a) for movable I/O pins (input/output terminals): some I/O pins' positions may be fixed, others may be assigned to any of the available I/O pads, (b) locations of some modules may already be fixed.
An input to a timing-driven placement problem is a set of modules and a net list, where each module has a fixed shape and fixed terminal locations. The goal is to find the best position for each module on the chip according to appropriate cost functions. Timing driven placement incorporates timing objective functions into the placement problem. Nets that must satisfy timing requirements are called critical nets. In timing-driven placement, it is desirable to make critical nets timing-efficient and other nets length- and area-efficient.
In a net-based timing-driven layout, timing requirements are usually first translated into physical requirements. Delay slacks correspond to budget wiring delays. Slack is the difference between the designed (logical) delay and the actual delay (after added wiring delay) from the wiring program. A positive slack implies that the current cycle-time is fulfilled by the physical layout (i.e., the net meets the design criteria), while a negative value indicates that the layout violates the timing conditions. In addition, a large positive value indicates that the cycle-time can be further improved. Hence, the goal in timing-driven layout is to maximize the min-slack.
The delay budgeting problem seeks to allocate delay slacks before the placement and routing steps. Thus, as a result of delay budgeting, the performance-driven placement and routing steps are given net delay bounds. Since the delay slacks equate with wiring delay, it is natural to expect all nets to have positive slacks. Furthermore, the distribution of these slacks determines the difficulty of finding a feasible placement (and/or routing) solution.
Excessive local congestion gives rise to future routing difficulty and also increases potential crosstalk noise in high-speed signal lines. Furthermore, it increases power dissipation due to coupling capacitance. In a timing analysis of a prerouting design, the routing of a net is usually assumed to be a minimal rectilinear Steiner tree. Due to the congestion, the capacitance (i.e., wirelength) of this routing tree is larger than the one with a minimal Steiner tree. Thus, we need to avoid the timing-critical nets from the congested areas.
Existing timing-driven flows lead to unpredictable and suspicious timing results. Their main flaw is a lack of timing coverage which requires designers to spend days or even weeks iterating between synthesis and layout to achieve timing closure. Extremely complex deep submicron designs requires a new placement algorithm being completed with faster clocks.
There have been many works in timing-driven placement in recent years.

Affiliated with

Also associated with

Rating

Timing-driven global placement based on geometry-aware... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Timing-driven global placement based on geometry-aware..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Timing-driven global placement based on geometry-aware... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2951186