Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-06-08
2002-06-25
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06412101
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the design of electrical connections, or interconnects, situated within integrated circuits, and more particularly, to a simultaneous path optimization (SPO) system and method for automatically and efficiently determining where to insert repeaters (buffers or drivers) within interconnects of an integrated circuit during the design of the interconnects in order to ultimately reduce signal propagation delays in the interconnects.
BACKGROUND OF THE INVENTION
As operating frequencies increase to hundreds of megahertz (MHz) for multimedia processors and application specific integrated circuits (ASICs) and increase to around a gigahertz (GHz) for the next generation of central processing units (CPUs), the global electrical signals, for example, reset, stall, clock, and control, have less time to traverse an integrated circuit (IC) on a microchip (chip) due to reduced cycle time. The problem is compounded even further as IC chips get larger and larger. Therefore, global signals often exhibit larger than desirable propagation delays, and the circuits need to be optimized so that signals meet timing specifications.
Generally, the propagation delay associated with a signal, or the time necessary for the signal to propagate from one point to another on a chip, is caused by resistances and/or capacitances imposed upon the signal path, and is sometimes referred to as “RC delay.” These resistances and capacitances also degrade the signal (decrease its rising/falling slope) as the signal propagates along a connection, which is another undesirable deleterious effect.
Many diverse approaches to this problem have been developed by researchers and published in the past few years. Consider the following, as examples: (1) N. Menezes, R. Baldick, and L. T. Pileggi, “A Sequential Quadratic Programming Approach to Concurrent Gate,” Department of Electrical and Computer engineering, University of Texas at Austin,
ICCAD
, November 1995; (2) J. Lillis, C. K. Cheng, and T. T. Lin, “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model,” University of California, San Diego, Calif.,
ICCAD
, November 1996; (3) J. Cong, and C. K. Koh, “Simultaneous Driver and Wire Sizing for Performance and Power Optimization,” University of California, Los Angeles, Calif.,
IEEE, Transactions on Very Large Scale Integration Systems
, Vol. 2, No. 4, December 1994; and (4) L. P. Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” IBM, NY,
IEEE International Symposium on Circuits and Systems,
1990.
One effective technique in reducing the delay of a signal involves inserting a “repeater” (also referred to in the art as a “driver” or “buffer”) along the signal path. A repeater is generally a circuit, for example, an inverter or set of cascaded inverters, that reduces the RC delay and slope degradation of the propagated signal. Historically, determining where to insert repeaters has been accomplished by creating and analyzing models of IC circuits. A mathematical algorithm known as “Elmore” has been used in the past to compute RC delays before and after introduction of repeaters in a circuit. The Elmore algorithm is described in detail in L. P. Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” IBM, NY,
IEEE International Symposium on Circuits and Systems,
1990. However, this process is time consuming and has traditionally been performed by having an engineer or designer review circuit models and determine where to insert repeaters.
Software tools for modeling and simulating circuits are well known in the art. Well known delays simulators (or calculators) include, for example, SPICE, and OPTspice (available from Hewlett-Packard Company, U.S.A.). Although the foregoing software programs can be used for modeling and simulations, they do not automatically determine where and to what extent repeaters should be placed within a circuit.
Thus, a heretofore unaddressed need exists in the industry for a way to automatically and efficiently determine where to insert repeaters when designing an IC in order to reduce signal propagation delays in the IC.
SUMMARY OF THE INVENTION
A simultaneous path optimization (SPO) system (and associated method) automatically and efficiently determines where to insert repeaters (or buffers or drivers) within interconnects of an integrated circuit (IC) during the design of the interconnects in order to ultimately reduce signal propagation delays in the interconnects. The SPO system is implemented in software, hardware, or a combination thereof, but is preferably implemented as a software tool executed by a computer system that is used in connection with one or more conventional delay simulators (e.g., the SPICE program), also in the form of software that is executed by a computer system.
In architecture, the SPO system is designed as follows. The SPO system is designed to receive or obtain a description, or netlist, of an electrical network. The netlist indicates a source node, a plurality of sink nodes, a plurality of electrical branches connecting the source node with each the sink node, a plurality of resistances associated respectively with the branches, a plurality of capacitances associated respectively with the branches, and a plurality of timing constraints associated respectively with the branches. Each the timing constraint represents a maximum propagation time delay between the source and a respective one of the sinks.
The SPO system causes the netlist to be simulated using a delay simulator. Although not required to practice the present invention, the SPO system defines and utilizes a slack parameter. The SPO system determines a slack parameter for each branch of the network. The slack parameter is computed for each branch by mathematically combining (e.g., subtracting) a signal propagation delay associated the each branch and a timing constraint associated with each branch. The SPO system determines a main branch in the network as one of the branches that exhibits the largest one of the slack parameters. The SPO system produces a total slack parameter by mathematically combining (e.g., adding) the slack parameters. The SPO system determines how many of the repeaters, if any, should be inserted in at least one side branch extending from the main branch by simulating at least one repeater in at least one side branch and determining whether the total slack parameter decreases by insertion of the at least one repeater. The SPO system determines how many of the other repeaters, if any, should be inserted along the main branch using a first delay simulator and simulating at least one other repeater. The SPO system determines a position for each of the other repeaters using a second delay simulator and simulating the other repeaters. Finally, the SPO system outputs the repeater locations and connectivity. The connectivity is generally a description as to what circuit elements each repeater is connected at its input and output ports.
Although not limited to this implementation, in the preferred embodiment, the aforementioned first delay simulator uses either a fast balanced segment delay process/system or an exhaustive search process, and the aforementioned second delay simulator uses a slower balanced segment delay process. In a sense, this overall process can be viewed as having a course adjustment part and a fine adjustment part, which achieves speedy and accurate results.
The invention may also be viewed as providing one or more methods for determining where to insert repeaters when designing an integrated circuit in order to reduce signal propagation delays in the integrated circuit. In this regard, one of the methods can be broadly summarized by the following steps: (a) obtaining a description of an electrical network; (b) determining a main branch in said network from said description based upon signal propagation delays associated with respective branches of said network; (c) simulating at least one repeater in at least one
Chang Norman H
Wanek John D
LandOfFree
Simultaneous path optimization (SPO) system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Simultaneous path optimization (SPO) system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simultaneous path optimization (SPO) system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901452