Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-02-28
2002-09-10
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06449759
ABSTRACT:
TECHNICAL FIELD
The present invention relates to integrated circuit chip design. More particularly the present invention relates to integrated circuit chip design systems and methods for placement of repeaters on the floor plan of an integrated circuit chip. Even more particularly, the present invention relates to integrated circuit chip design systems and automated methods for placement of repeater buffers on the floor plan of an integrated circuit chip design.
BACKGROUND OF THE INVENTION
It is known that propagation delays are not desirable in the design of next generation microprocessors and must be factored in the chip design to minimize the interconnect delay. See generally U.S. Pat. No. 5,910,747 to Matta et al., assigned to the assignee of the present invention. The propagation delays are physical phenomenon associated with interconnect resistivity of the metals comprising the interconnects, capacitive coupling associated with proximity of the interconnects to other interconnects, and the non-linear effects associated with the geometry of the chip. Since a chip design comprises millions of interconnects, the propagation delay problem becomes a significant obstacle to next-generation microprocessor design. Thus, although the technology is resulting in smaller and smaller geometries, the propagation delays are increasing due to the large magnitude of the interconnects (nets). It is known in the art, as U.S. Pat. No. 5,910,747 describes, that propagation delays are due to the need for an input signal driver to charge a resistive-capacitive (RC) circuit formed by the complex interconnect network distributed throughout the chip. The multitude of RC circuits are thus charged by drivers, and by additional drivers, which effectively speed up the charging time for the RC circuits. The use of a repeater buffer driver depends on whether the charging time for the RC circuit formed by the interconnect, or by the receiving load, exceeds a threshold value critical to the chip design. The buffer drivers are cascaded inverting or non-inverting amplifiers. It is also known, as U.S. Pat. No. 5,910,747 describes, that to further speed up the charging of the RC circuits formed by the interconnect, single stage inverting amplifiers, known as repeaters, are utilized. Repeaters serve to provide additional drive current for long interconnect segments. U.S. Pat. No. 5,910,747 teaches a recursive computer aided design (CAD) program for placing drivers in a net in a recursive fashion to isolate a branch interconnect from a parent interconnect, and thus reduce the overall charging time. U.S. Pat. No. 5,910,747 further teaches that by evenly placing repeaters in forkless branches, i.e. an interconnect terminating at a receiver, or load, the charging times are further decreased. U.S. Pat. No. 5,910,747 teaches a formula, k, for an interconnect segment in an unforking branch, to determine the number of repeaters. The formula k is related to the resistance and capacitance in an equivalent circuit of an unforking interconnect branch.
Other prior art methods include manually placing repeater buffers on a chip floor plan, whereby an engineer utilizes a CAD layout of the design to select where to place the repeaters. While, effective to reduce the propagation delays, the manual method does not optimally place the repeaters at near optimal distance from one another. Also, the manual method is not the most efficient in designing a new product.
Thus, refinement in the art of repeater placement tools is seen to exist to give a near optimal placement of repeaters on the floor plan of a chip to decrease the propagation delays, and to continue providing efficient new product designs.
BRIEF SUMMARY OF THE INVENTION
Accordingly, the present invention provides a computer aided automated system in the form of a repeater placement tool for placing repeater buffers on a floor plan of an integrated circuit chip. More particularly, the repeater placement tool, of the present invention, provides a near optimal placement of repeaters on the floor plan of a chip. The tool utilizes an algorithm which uses a combination of approximate geometric placement with iterative heuristic improvements on the basic geometric layout. A rule-driven repeater-type update system is used to ensure that the strength, load, and other characteristics of the repeater buffer are correct, given the repeater location and the topology and loads of the nets. The method comprises the tool loading the locations of drivers and receivers, and grouping the drivers that are close together, as well as the receivers that are close together. A “center of gravity (CG)” is then computed for each group of nets in a bus that are located close to one another. This CG is the receiver, or driver, that is closest to the center of the distribution of elements in the group. The tool allows for the specification of a maximum spread distance so if the drivers, or receivers, of a particular bus are distributed over too large an area, two or more [center of gravities] CGs will be found and repeated separately. The tool places repeaters to boost the signal on nets from the driver groups to the receiver groups. This placement is done to a first approximation using a geometric grouping algorithm. One driver CG is addressed at a time and the receiver CG(s) are grouped with respect to their angular proximity in relation to the driver CG. Repeaters are then placed to service each of these angle groups. This repeater placement is done by placing the repeater along the angle central to the subtending solid angle that defines the grouping. The distance at which it is placed is as far from the driver as possible (a parameter which is a function of the user defined maximum distance serviceable for the different types of repeater buffer). The algorithm is recursive so it then performs the same operation on each of the newly placed repeaters. The algorithm is run on each of the angle groupings with the repeater for a particular group being treated as a driver and the CG(s) in the angle grouping all being all the receivers to be driven.
To achieve a better configuration, a number of heuristic improvements are then applied to the results of the geometric grouping algorithm. These heuristic improvements involve removing repeaters that are too close to receiver CG(s) and moving the previous repeater in the net in order to fill the longer distance from the removed repeater. The tool also attempts to reconnect a receiver CG to a repeater farther back in the repeater chain servicing it so as to reduce the delay introduced by making a net go through too many repeater buffers.
The final stage of the algorithm is a rule based update mechanism that assigns a type to each repeater. The assignment is based on various requirements like the length of wire the repeater must drive, the maximum allowable propagation delay, and input load. The user can define all these parameters and specify the type which should be assigned to each repeater in the layout based on the configuration of all the drivers/receivers/repeaters and requirements on the individual nets.
Other features of the present invention are disclosed or are apparent in the section entitled: “DETAILED DESCRIPTION OF THE INVENTION.”
REFERENCES:
patent: 5838580 (1998-11-01), Srivatsa
patent: 5910747 (1999-06-01), Matta et al.
patent: 5926397 (1999-07-01), Yamanouchi
patent: 6145116 (2000-11-01), Tawada
Culetu et al., “A Practical Repeater Insertion Method in High Speed VLSI Circuits,” 1998 ACM/DAC, pp. 392-395.*
van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” 1990 IEEE, pp. 865-868.
Subramanian Sridhar
Whitney Mark G.
Garbowski Leigh Marie
LaRiviere Grubman & Payne, LLP
Smith Matthew
LandOfFree
System and method for automatic insertion and placement of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for automatic insertion and placement of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for automatic insertion and placement of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885666