Method and computer program for incremental placement and routing with nested shells

A method of placing and routing an integrated circuit design includes generating an initial placement and routing for at least a portion of an integrated circuit design. The initial placement and routing of the integrated circuit design is analyzed to find a critical location and is partitioned into a series of nested shells. Each shell surrounds the critical location and each preceding shell. An ordering of the shells and at least one of a timing constraint and an area constraint are selected for each shell. Each shell is placed and routed in the order selected according to the timing constraint and area constraint.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention is directed to the design and manufacture of integrated circuits. More specifically, but without limitation thereto, the present invention is directed to methods of placement and routing for an integrated circuit design.

2. Description of Related Art

An important phase in the design of an integrated circuit is to verify that each logic path in the integrated circuit design meets all timing constraints required to meet performance specifications. The verification of the timing for each logic path in an integrated circuit design is typically called timing closure. For example, if the propagation delay is too long in a path that propagates a clock signal to a flip-flop, the flip-flop may not be set to the correct value when the clock signal arrives, resulting in a timing violation. Also, signal routing congestion may occur in locations where there are more signals to route than there is available routing area on the chip. The locations in the integrated circuit design where timing violations or congested routing areas occur are referred to herein as critical areas.

Timing closure is a resource-intensive task in which all timing violations and congested signal routes in the placement and routing must be resolved before an integrated circuit design may be taped out, that is, generated in mask form for depositing and etching layers of various materials on a silicon substrate. Place and route tools typically resolve timing and signal congestion problems in critical areas by moving the problems outside of the critical areas into the surrounding logic.

SUMMARY OF THE INVENTION

A method of placing and routing an integrated circuit design includes steps of (a) generating an initial placement and routing for at least a portion of an integrated circuit design; (b) analyzing the initial placement and routing of the integrated circuit design to find a critical location; (c) partitioning the initial placement and routing of the integrated circuit design into a series of nested shells wherein each shell surrounds the critical location and each preceding shell; (d) selecting an ordering of the shells; (e) selecting at least one of a timing constraint and an area constraint for each shell; and (f) placing and routing each shell in the order selected in step (d) according to the at least one timing constraint and area constraint selected in step (e).

In another embodiment, a computer program product includes:a medium for embodying a computer program for input to a computer; anda computer program embodied in the medium for causing the computer to perform steps of:(a) generating an initial placement and routing for at least a portion of an integrated circuit design;(b) analyzing the initial placement and routing of the integrated circuit design to find a critical location;(c) partitioning the initial placement and routing of the integrated circuit design into a series of nested shells wherein each shell surrounds the critical location and each preceding shell;(d) selecting an ordering of the shells;(e) selecting at least one of a timing constraint and an area constraint for each shell; and(f) placing and routing each shell in the order selected in step (d) according to the at least one timing constraint and area constraint selected in step (e).

DESCRIPTION OF THE ILLUSTRATED EMBODIMENTS

The following description is not to be taken in a limiting sense, rather for the purpose of describing by specific examples the general principles that are incorporated into the illustrated embodiments. For example, certain actions or steps may be described or depicted in a specific order to be performed. However, practitioners of the art will understand that the specific order is only given by way of example and that the specific order does not exclude performing the described steps in another order to achieve substantially the same result. Also, the terms and expressions used in the description have the ordinary meanings accorded to such terms and expressions in the corresponding respective areas of inquiry and study except where other meanings have been specifically set forth herein.

FIG. 1illustrates a typical placement and routing diagram100for an integrated circuit design of the prior art. Shown inFIG. 1are flip-flops102,104,106,108, and110, logic clouds112,114,116, and118, interconnects120, and a fan-in cone122.

InFIG. 1, the flip-flops102,104,106,108, and110are placed around the logic clouds112,114,116, and118and are connected to one another by routing the interconnects120between them. Each of the logic clouds112,114,116, and118represent a series of logic elements such as inverters, NAND gates, multiplexers, and so on that are connected together to perform a logical function on one or more input signals. The fan-in cone122results when a number of interconnects120merge at a common point. In the example ofFIG. 1, the common point of the fan-in cone122is the input of the flip-flop110.

The placement and routing for the integrated circuit design is generally analyzed to find critical areas, that is, the locations of timing violations and congested signal routes. For example, the interconnect120between the flip-flop104and the logic cloud114may have a length that results in a timing violation at the flip-flop110. Also, the fan-in cone122may have more interconnects120than there is available routing area around the flip-flop110, resulting in congested signal routes. To achieve timing closure, a typical placement and routing method moves the flip-flop104closer to the logic cloud114to correct the timing violation and moves the flip-flop108and the logic cloud118away from the fan-in cone122to increase the signal routing area as shown inFIG. 2.

InFIG. 2, the interconnect120between the flip-flop104and the logic cloud114has been shortened to avoid the timing violation, and the logic cloud118has been moved away from the flip-flop110to avoid the congested signal routing area. However, shortening the interconnect120between the flip-flop104and the logic cloud114also lengthens the interconnect120between the logic cloud112and the flip-flop104. Also, moving the logic cloud118away from the flip-flop110reduces the available routing area in the surrounding logic. A disadvantage of resolving timing and signal. congestion problems in critical areas by moving the problems from the critical areas into the surrounding logic is that new timing violations and congested signal routing areas may be created in the surrounding logic that may be more difficult to correct than before. In some cases, it may not be possible to correct the new problems without redesigning the entire integrated circuit chip. Accordingly, it is desirable to correct timing violations and congested signal routing areas in a way that does not propagate the problems in the critical areas into the surrounding logic.

In one embodiment, a method of placing and routing an integrated circuit design includes steps of (a) receiving a netlist for an integrated circuit design; (b) generating an initial placement and routing of the integrated circuit design from the netlist; (c) analyzing the initial placement and routing of the integrated circuit design to find a critical location; (d) partitioning the initial placement and routing into a series of nested shells wherein each shell surrounds the critical location and each preceding shell; (e) selecting an ordering of the shells; (f) selecting at least one of a timing constraint and an area constraint for each shell; and (g) placing and routing each shell in the order selected in step (e) according to the at least one timing constraint and area constraint selected in step (f).

InFIG. 3, the initial placement and routing ofFIG. 1is partitioned into the nested shells304and306. The first shell304surrounds the critical area302, which includes the fan-in cone122. The second shell306surrounds the preceding shell304and includes a portion of the logic elements in the integrated circuit design that lie outside the preceding shell304. In this example, the portion of the logic elements in the integrated circuit design that lie outside the preceding shell304includes the flip-flops102,104,106, and108and the logic clouds112and116. Only two nested shells are used in the example ofFIG. 3; however, any number of shells may be nested in the same manner to practice various embodiments within the scope of the appended claims.

FIG. 4illustrates the nested shells ofFIG. 3after placing and routing each shell in an order from outermost to innermost. Shown inFIG. 4are flip-flops102,104,106,108, and110, logic clouds112,114,116, and118, interconnects120, a fan-in cone122, a critical area302, and nested shells404and406.

InFIG. 4, the logic elements inside the outermost shell406are placed and routed using the initial placement and routing coordinates ofFIG. 1as a starting point. Alternatively, a new placement and routing may be performed for the logic elements inside the outer shell406without using the initial placement and routing coordinates ofFIG. 1. The placement and routing of the logic elements in the shell406may be performed in the same manner as for the entire integrated circuit design, except that the placement and routing of the logic elements in the shell406is an incremental, or partial, placement and routing of only the portion of the integrated circuit design that is included within the shell406. In other words, the placement and routing is performed for only the logic elements that lie inside the shell406and outside the preceding shell404. Accordingly, the area of the shell406is optimized for the portion of the logic elements in the integrated circuit design that lie inside the shell406and outside the shell404.

As a result of the optimization realized by the incremental placement and routing of the shell406, the area of the shell406is reduced compared to that of the shell306inFIG.3, and the area of the innermost shell404is increased compared to that of the shell304.

After placing and routing the outermost shell406, the next outermost shell is placed and routed in the same manner. In this example, the next outermost shell is the innermost shell404surrounding the critical area302. The additional area provided by performing the placement and routing of the outermost shell406before the placement and routing of the innermost shell404resolves the problems created by the initial placement and routing ofFIG. 1without propagating the problems to the surrounding logic.

FIG. 5illustrates a diagram500of how boundaries of nested shells may be defined for an incremental placement and routing of the initial placement and routing ofFIG. 1. Shown inFIG. 5are nested shells502,504, and506, a critical area508, a critical location510, logic levels512, and flip-flop levels514.

InFIG. 5, the critical location510is, for example, the location of the flip-flop at which the worst timing violation occurs or the center of the most congested routing area in the initial placement and routing of an integrated circuit design. The critical area508includes the critical location510and extends from the critical location by a distance determined, for example, by a user selected distance. Alternatively, the critical area508may be determined by a distance along each path from the critical location510that includes a selected number n of logic levels512, that is, all logic elements are counted toward the selected number n including inverters, NAND gates, and flip-flops. In another embodiment, the critical area508may be determined by a distance along each path from the critical location510that includes a selected number n of flip-flop levels regardless of the number of intervening logic elements, that is, only flip-flops are counted toward the selected number n.

The area of the innermost shell502may be identical to the critical area508, or the innermost shell502may be larger or smaller than the critical area508, depending on the integrated circuit design. Each of the subsequent shells504and506may have a boundary that is relatively distant from the preceding shell boundary by the same distance, number of logic levels, or number of flip-flop levels as the boundary of the innermost shell502is from the critical location510.

The nested shells502,504, and506are depicted as circles inFIG. 5to illustrate the concept that each shell surrounds a preceding shell. In general, each of the nested shells502,504, and506is representative of a subset of the placement and routing diagram and is not necessarily circular in shape.

Alternatively, other criteria may be used to determine the boundaries of the outer shells504and506according to well-known techniques to practice various embodiments within the scope of the appended claims.

FIG. 6illustrates a flow chart600of a method of incremental placement and routing of an integrated circuit design using the nested shells ofFIG. 5.

Step602is the entry point of the flow chart600.

In step604, an initial placement and routing is generated for an integrated circuit design, for example, from a netlist according to well-known techniques.

In step606, the initial placement and routing of the integrated circuit design is analyzed according to well-known techniques to find a critical location, for example, the worst timing violation. Timing reports generated by typical timing closure software include a start point and an end point of each timing violation. The end point is usually a receiving flip-flop. The location of the receiving flip-flop reporting the worst timing violation, that is, the highest value of negative slack, would be a critical location in this example. Alternatively, the critical location may be the center of the area having the greatest number of congested signal routes.

In step608, the initial placement and routing of the integrated circuit design is partitioned into a series of nested shells wherein each shell surrounds the critical location and each preceding shell. The boundary of the innermost shell may be determined, for example, by a user selected distance from the critical location, by a distance along each path from the critical location that includes a selected number of logic levels or by a distance along each path from the critical location that includes a selected number of flip-flop levels. Accordingly, a shell may include partial nets if a selected number of logic levels is used to establish the shell boundary, or a shell may include only entire nets if a selected number of flip-flops is used to establish the shell boundary.

Each of the outer shells may have a boundary determined by the same user selected distance from the boundary of the preceding shell, or by the same number of logic levels, or by the same number of flip-flops from the boundary of the preceding shell. The boundary of a shell may also terminate at an input or output of the integrated circuit design before reaching the selected number of logic levels or flip-flops. Alternatively, each shell may have a boundary that is determined by any selected distance, number of logic levels, or number of flip-flops from the boundary of the preceding shell to practice various embodiments within the scope of the appended claims.

The entire integrated circuit design may be partitioned into shells as described above, or only a portion of the integrated circuit design may be partitioned into shells if desired to practice various embodiments within the scope of the appended claims. For example, a user may select only the first 100 flip-flop levels of the integrated circuit design for partitioning into a series of10nested shells surrounding a critical location to resolve timing violations and/or congested signal routes.

In step610, an ordering of the shells is selected. For example, the ordering may be from outermost to innermost so that the outermost shell is placed and routed first, and the innermost shell is placed and routed last. As explained above, this ordering passes the area and timing savings inward to the critical location where they are most needed. Alternatively, any other ordering may be selected to practice various embodiments within the scope of the appended claims. For example, a shell that includes the fewest timing violations and/or congested signal routes may be placed and routed first, and so on, until the shell having the most timing violations and/or congested signal routes is placed and routed last. Also, some shells may be omitted from the ordering. For example, a user may omit shells from the ordering that are reserved for logic that has not yet been placed.

In step612, one or more timing constraints and/or area constraints are selected for each shell. For example, a timing constraint may be a minimum slack margin, and an area constraint may be a maximum signal routing density.

In step614, a shell is selected in the order selected in step610and placed and routed according to the timing and/or area constraints selected in step612.

In step616, the selected shell is analyzed to detect timing violations and congested signal routes.

In step618, if no timing violations or congested signal routes are found, then the selected shell is error-free, and the method continues from step624. If a number of timing violations or congested signal routes is found that does not exceed a selected error threshold T, for example 10, then the method continues from step620. If a number of timing violations or congested signal routes exceeds the selected error threshold, then the method continues from step622.

Alternatively, the selected error threshold may be expressed as a percentage of a clock cycle. For example, a timing violation that is less than 10 percent of a clock cycle may probably be corrected by adjusting the timing and/or area constraints of the shell, while a timing violation that exceeds 10 percent of a clock cycle may require changing the definition of the shell boundary.

In step620, the timing and/or area constraints for the shell are changed, and the method continues from step614. For example, the area of the selected shell may be decreased, or the timing slack margin may be increased to ensure that timing closure may be achieved in succeeding shells.

In step622, the boundaries of the shells are changed, that is, a new partition of nested shells is defined. For example, a new partition of nested shells may be defined by decreasing the number of logic levels or flip-flop levels in each shell. The method then continues from step610.

In step624, if any shells remain to be placed and routed, the method continues from step614. Otherwise, the method continues from step626.

Step626is the exit point of the flow chart600.

The number of shells and the area of each shell may be adjusted to the complexity of the integrated circuit design so that the number of logic elements and interconnects for each shell may be readily accommodated by the placement and routing software. The area of each shell may be subsequently increased or decreased by the placement and routing software as needed to expedite the resolution of timing violations and congested signal routes.In another embodiment, a computer program product includes:a medium for embodying a computer program for input to a computer; anda computer program embodied in the medium for causing the computer to perform steps of:(a) generating an initial placement and routing for an integrated circuit design;(b) analyzing the initial placement and routing of the integrated circuit design to find a critical location;(c) partitioning the initial placement and routing of the integrated circuit design into a series of nested shells wherein each shell surrounds the critical location and each preceding shell;(d) selecting an ordering of the shells;(e) selecting at least one of a timing constraint and an area constraint for each shell; and(f) placing and routing each shell in the order selected in step (d) according to the at least one timing constraint and area constraint selected in step (e).

FIG. 7illustrates a flow chart700of a computer program product summarizing the method ofFIG. 6.

Step702is the entry point of the flow chart700.

In step704, an initial placement and routing is generated for at least a portion of an integrated circuit design. For example, if a netlist is available for only some part of an integrated circuit design, then the initial placement and routing may be generated for the partial integrated design.

In step706, the initial placement and routing of the integrated circuit design is analyzed to find a critical location.

In step708, the initial placement and routing of the integrated circuit design is partitioned into a series of nested shells wherein each shell surrounds the critical location and each preceding shell.

In step710, an ordering of the shells is selected.

In step712, a timing constraint and/or an area constraint is selected for each shell.

In step714, each shell is placed and routed in the order selected in step710according to timing constraint and/or area constraint selected in step712.

Step716is the exit point of the flow chart700.

Although the flowchart description above is described and shown with reference to specific steps performed in a specific order, these steps may be combined, sub-divided, or reordered without departing from the scope of the claims. Unless specifically indicated, the order and grouping of steps is not a limitation of other embodiments that may lie within the scope of the claims.

The specific embodiments and applications thereof described above are for illustrative purposes only and do not preclude modifications and variations that may be made within the scope of the following claims.