Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2001-06-13
2004-12-28
Phan, Thai (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S013000, C716S030000, C716S030000
Reexamination Certificate
active
06836753
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to the computation of time budgets. The present invention is more specifically related to the field of Computer-Aided Design (CAD) tools for automating the design and verification of electronic systems and circuits, and particularly the computation of time budgets.
2. Discussion of Background
Transistor placement (cells) and wire routing (nets) of a circuit design on a substrate has become an important area for computer-aided design (CAD). Advances in circuit integration have made it possible for circuit designers to incorporate designs having more than a million transistors on a single chip. Even using advanced CAD based approaches to place and route (P&R), circuit designs are complicated and both time and computationally intensive. Faster clock cycles and critical path constraints make the traditional process even more complicated.
A typical design process includes having a user design a logic circuit, and then direct a computer to program a logic device or to design a set of masks to implement the desired logic design. Timing of signals passed between parts of the logic device depends in part upon placement of the user's circuit elements into transistor groups in the physical structure and the resultant arrangement of the metal wires. In general, longer wires mean longer delays, but the actual timing is also heavily dependent upon capacitances, resistances, which vary based on placement and proximity to other wires and circuit elements, and the number of logic elements a signal must traverse. In addition, as transistors have become faster, a larger percentage of the delay in passing a signal through the device is contributed by the wiring. Therefore it has become a worthwhile effort to select wiring segments carefully to minimize the delay caused by these wiring segments.
One problem is computing the net delay upper bounds. This problem consists of transforming design-level timing constraints (such as clock period) into local net delay constraints. These local net delay constraints are then used by the placer to do a timing driven placement, so they play a very important role in the final layout and performance. This problem has been already explored in the past, and there are some existing algorithms: Zero Slack Algorithm (ZSA), “Generation of Performance Constraints for Layout” Nair and co IEEE CAD 1989, MIMP, “Bounds on Net Delays for VLSI Circuits” Habib Youssef and co IEEE Transactions on Circuits and Systems November 1992, and LBA, “Iterative and Adaptative Slack Allocation for Performance-Driven Layout and FPGA Routing” Jon Frankle DAC92.
Another previous system is described in “A Delay Budgeting Algorithm Ensuring Maximum Flexibility in Placement,” M. Sarrafzadeh, D. A. Knol, G. E. Tellez, IEEE transactions on CAD of Integrated Circuits and Systems November 1997. The method described here uses a Linear Programming formulation. However none of the above systems provide an optimal solution.
SUMMARY OF THE INVENTION
The present inventors have realized that existing solutions for determination of net delay constraints and budgets are inadequate. This invention presents a new approach to the problem of computing the net delay upper bounds.
The present invention is embodied as a method of computing a time budget for each edge in a Domain Restricted Timing Cone (DRTC) of a graph, comprising the steps of, determining timing constraints including a required output time (R) for an endpoint of the DRTC and an arrival time (Ai) for each input (i) of the DRTC, decorating each vertex in the graph with a time to endpoint (tte) value and a weight to endpoint (wte) value, tte representing a longest time to reach the endpoint and wte representing a largest sum of weight to reach the endpoint, computing a smallest slack to weight on each edge of the graph within the DRTC using the tte and wte pair for each edge.
The present invention also includes a method for performing analysis on a set of domain- restricted timing cones, comprising the steps of, selecting a domain restricted timing cone, determining a slack to weight ratio for each edge in the domain restricted timing cone, for each edge, if the determined slack to weight ratio for an edge is less than a current slack to weight ration for that edge, then, replacing the current slack to weight ratio with the current slack to weight ratio, and selecting a next domain restricted timing cone and repeating said steps of determining and replacing until each timing cone has been analyzed.
The present invention also includes A method of slack allocation within a timing graph, comprising the steps of, setting an initial edge time for each edge in the timing graph, and iteratively performing the following steps, computing an amount of the available slack to be budgeted to each edge of the graph, for each edge having a weight greater than zero, if the computed slack is greater than a predetermined epsilon, then restore the edge time to that in an immediately preceding iteration, and if the computed slack is less than or equal to the predetermined epsilon, then saving a current edge time and setting a weight of the edge to zero, stopping the iterative steps if an amount of slack to allocate is less than the predetermined epsilon, determining a new budget for each edge, and incrementing the edge time for each edge by the corresponding new budget, until the iterative steps are stopped or a maximum number of iterations is performed.
The invention may be embodied in a device and both the device and/or method may be conveniently implemented in programming on a general purpose computer, or networked computers, and the results are intended to be input to other devices or processes, such as timing driven placement, optimization, and so on, with the very end goal being to produce a chip. However, the results may also be displayed on an output device connected to any of the general purpose, networked computers, or transmitted to a remote device for output or display. In addition, any components of the present invention represented in a computer program, data sequences, and/or control signals may be embodied as an electronic signal broadcast (or transmitted) at any frequency in any medium including, but not limited to, wireless broadcasts, and transmissions over copper wire(s), fiber optic cable(s), co-ax cable(s), and opto-electric devices, etc.
REFERENCES:
patent: 3617714 (1971-11-01), Kernighan et al.
patent: 4593363 (1986-06-01), Burstein et al.
patent: 4612618 (1986-09-01), Pryor et al.
patent: 4630219 (1986-12-01), DiGiacomo et al.
patent: 4924430 (1990-05-01), Zasio et al.
patent: 5053980 (1991-10-01), Kanazawa
patent: 5095454 (1992-03-01), Huang
patent: 5111413 (1992-05-01), Lazansky et al.
patent: 5144563 (1992-09-01), Date et al.
patent: 5187784 (1993-02-01), Rowson
patent: 5197015 (1993-03-01), Hartoog et al.
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5224056 (1993-06-01), Chene et al.
patent: 5237514 (1993-08-01), Curtin
patent: 5239493 (1993-08-01), Sherman
patent: 5251197 (1993-10-01), Leube et al.
patent: 5426591 (1995-06-01), Ginetti et al.
patent: 5461576 (1995-10-01), Tsay et al.
patent: 5475607 (1995-12-01), Apte et al.
patent: 5483461 (1996-01-01), Lee et al.
patent: 5521837 (1996-05-01), Frankle et al.
patent: 5778216 (1998-07-01), Venkatesh
patent: 6378116 (2002-04-01), Ginetti
patent: 6480991 (2002-11-01), Cho et al.
patent: 6622291 (2003-09-01), Ginetti
Venkatesh, S.V. (1995) “Hierarchical Timing-driven Floorplanning and Place and Route Using a Timing Budgeter,”IEEE 1995 Custom Integrated Circuits Conferencepp. 469-472.
Frankle, Jon (1992) “Iterative and Ada
Cadence Design Systems Inc.
Carpenter John W.
Phan Thai
Reed Smith LLP
LandOfFree
Cone slack allocator for computing time budgets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cone slack allocator for computing time budgets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cone slack allocator for computing time budgets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287725