1. Field of the Invention
The present invention generally relates to the design of semiconductor chips and integrated circuits, and more particularly to the use of buffer insertion to manage timing and electrical requirements in an integrated circuit design.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cell types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process for very large scale integrated (VLSI) devices, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer-aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance. Several different programming languages have been created for electronic design automation (EDA), including Verilog, VHDL and TDML. A typical EDA system receives one or more high level behavioral descriptions of an IC device, and translates this high level design language description into netlists of various levels of abstraction.
Faster performance and predictability of responses are elements of interest in circuit designs. As process technology scales to the submicron regime, interconnect delays increasingly dominate gate delays. Consequently, physical design optimization tools such as floorplanning, placement, and routing are becoming more “timing-driven” than the previous generation of tools. Owing to the tremendous drop in VLSI feature size, a huge number of buffers (i.e., amplifiers or inverters) are needed for achieving timing objectives and fixing electrical violations for interconnects. Higher relative interconnect resistance forces buffers to be placed closer together to achieve optimal performance. It is estimated that the number of buffers will rise dramatically, reaching about 15% of the total cell count for intrablock communications for 65 nanometer technology, and close to 800,000 buffers required for 50 nanometer technologies. Therefore, both the complexity and importance of buffer insertion is increasing in an even faster pace.
Physical synthesis is prominent in the automated design of integrated circuits such as high performance processors and application specific integrated circuits (ASICs). Physical synthesis is the process of concurrently optimizing placement, timing, power consumption, crosstalk effects and the like in an integrated circuit design. This comprehensive approach helps to eliminate iterations between circuit analysis and place-and-route. Physical synthesis has the ability to repower gates, insert buffers, clone gates, etc., so the area of logic in the design remains fluid. However, physical synthesis can take days to complete.
During physical synthesis, buffer insertion is called for to either optimize nets for delay or to fix nets due to electrical violations. One mechanism for performing buffer insertion on a fixed Steiner integrated circuit topology is known as the van Ginneken algorithm, described in the article “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” L. van Ginneken, IEEE Proceedings (ISCAS) pp. 865-868 (1990). Given a fixed Steiner tree topology, the van Ginneken algorithm finds the optimal buffer placement on the topology under an Elmore delay model for a single buffer type and simple gate delay model. The primary idea of van Ginneken is to choose a set of buffer candidate locations that lie on the Steiner topology at some uniformly fixed distance apart. Buffer insertion then proceeds for that particular set of candidates from sink to source. When a candidate location falls within a region that is blocked because it is too densely populated with logic, that location is skipped and a buffer is inserted into the next candidate insertion location that is not blocked while maintaining the uniform spacing.
As seen in FIG. 1, a Steiner tree representation of a net 1 places candidate buffer insertion points 2 at regular intervals along the paths from source 3 to sinks 4 and 5. A buffer blockage 6 such as a memory array or IP core is present in the path of the net. The portion of the net block by logic cell 6 is skipped when determining candidate buffer insertion points 2. The spacing between candidate insertion points may be increased or decreased by the designer to achieve a particular timing requirement. Increasing the frequency of buffer insertion locations can improve timing of the net, but at an increased buffer cost, i.e., an increased size or area of the silicon chip used for the buffers.
A variation of the van Ginneken approach can be used to minimize a cost function subject to given timing constraints, as explained in the article “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model,” J. Lillis et al., IEEE Journal of Solid State Circuits, vol. 31, no. 3, pp. 437-447 (1996). According to that methodology, different possible solutions are examined at each potential buffer node, progressing in a bottom-up direction from a sink to a source (postorder traversal). FIG. 1 illustrates two possible solutions for the buffer location next to sink 5, a first solution with no buffer and a second solution with a buffer at that location. The next iteration of the analysis has four possible solutions that build on the first set of solutions: one solution with no buffer at either of the two locations; two solutions with only one buffer location at either of the two locations; and one solution with buffers at each of the two locations. At any point in the analysis “suboptimal” solutions may be eliminated. Each solution is associated with a three-tuple comprised of capacitance/cost/slack (C, W, Q), and a solution is deemed suboptimal if each of these three components is worse than the corresponding components of any other solution. In this example, the fourth solution with buffers at both of the first two buffer locations is suboptimal and removed from further consideration.
Two possible solutions are similarly built for the branch starting with sink 4. There are accordingly six possible solutions presented to the next buffer location upstream from logic cell 6. The process of propagating different solutions continues for all wire branches and all buffer locations until the source (driver) is reached, with suboptimal solutions continuously pruned. Solutions which violate the delay constraint at the driver are also pruned. The set of solutions which survive thus excel in at least one aspect of downstream capacitance, buffer cost or slack (required arrival time, or RAT). The buffer assignments selected as the final solution correspond to the solution with the smallest overall cost.
While this approach provides a valuable tool for delay optimization, it does not address other important electrical characteristics such as slew. Slew (or slew rate) refers to the rise time or fall time of a switching digital signal. Different definitions can be used to quantify slew, the most common being the 10/90 slew which is the time it takes for a waveform to cross from the 10% signal level to the 90% signal level. Other definitions such as 20/80 slew or 30/70 slew are often used when the waveform has a slowly rising or falling tail. Since higher interconnect resistivity also causes signal integrity to degrade more quickly with each advancing technology, buffers need to be inserted on long interconnects to meet slew constraints. The number of buffers on a typical chip is rising dramatically due to this increasing interconnect resistance. For example, an application-specific integrated circuit (ASIC) designed for use in a computer server might have between 2 and 3 million gates. Electrical correction for such a circuit might take as long as 46 hours, with the insertion of as many as 500,000 buffers. This large number of buffers can degrade overall design performance by forcing the rest of the logic to be spread further apart to accommodate the buffers. The buffers themselves are a drain on power and can cause other gates to be sized to higher power levels since they are further apart on the chip.
Prior art buffer insertion tools fail to adequately deal with slew constraints as they pertain to the increased costs from buffering. An extension of the Lillis algorithm accommodates a generalized decay model which takes into account the effect of signal slew of buffer delay which can contribute to overall delay. However, that approach merely integrates slew constraints while still optimizing for delay, and buffering of non-critical nets may result in unnecessary runtime and resource overhead. Other approaches have different limitations. Length-based buffering, as described in the article “A Practical Methodology for Early Buffer and Wire Resource Allocation,” C. Alpert et al., ACM/IEEE Proceedings (DAC) pp. 189-194 (2001), tries to reduce buffer and wire congestion but it can be area inefficient especially in the presence of blockages and its handling of multi-fanout nets. Another method described in the article “Minimum-Buffered Routing of Non-Critical Nets for Slew Rate and Reliability Control,” C. Alpert et al., IEEE/CAN Proceedings (ICCAD) pp. 408-415 (2001), addresses slew constraints without regard to delay; however that technique does not model slew, it just simplifies the slew constraint to be equivalent to a capacitance constraint, so interconnected resistivity is not actually modeled. While appropriate for vary large fanout nets (e.g., over 1000 sinks), it essentially becomes equivalent to length-based buffering. It would, therefore, be desirable to devise an improved method of buffer insertion which could control slew violations while reducing or minimizing buffer cost. It would be further advantageous if the method could be carried out independently of the timing analysis.