Method for improving the assignment of circuit locations during fabrication

[0002] 1. Field of the Invention

[0003] The present invention relates to circuit fabrication. More particularly, it relates to a method for improving the location assignment of circuits during fabrication.

[0004] 2. Prior Art

[0005] The process of assigning circuits to locations in, e.g., a chip, frequently includes a stage where all the circuits have been assigned locations, but the assignments are not optimal from either a wiring or timing perspective. For example, certain nets may be on the critical path, and as a result may have delays that are too large. A determination may then be made as to what sets of motions (i.e., assigning a subset of gates to different locations) decrease the sum of the capacitances of the nets on the critical path, with or without weights for the different nets.

[0006] Circuit synthesis has traditionally operated on optimized netlists. These optimizations have included both boolean and electrical optimizations. Placement algorithms, on the other hand, have focused primarily on the spatial domain, such as minimizing the total net length or a weighted average of net lengths. With the emergence of sub-micron technologies, there is a need for synthesis and placement algorithms to work seamlessly across all three domains, i.e., boolean, electrical and spatial.

[0007] Generally, physical designs have focused on spatial optimizations where the locations of netlist objects are selected with the goal of optimizing a given parameter, e.g., timing, wireability, etc. Recently, synthesis-like electrical optimizations have been implemented into placement subsystems. These electrical optimizations typically operate on the netlist and primarily use the spatial domain only to estimate wire capacitance/RC using a wire length estimator such as a Steiner estimator. Unfortunately, these optimizations do not make significant changes in the locations of the objects.

[0008] In view of the foregoing, there is also a need for placement synthesis algorithms to understand the location domain primarily from two main perspectives: 1) correct modeling of the spatial domain; and 2)optimization along the spatial domain. With respect to the correct modeling of the spatial domain, even if one were to focus on only the electrical and boolean domains, in order for the synthesis optimizations to be useful, they would have to model the interconnection correctly. This modeling requires the spatial information. Current techniques in synthesis for modeling interconnection which, for example, estimate wire capacitances as a function of fanouts, are inaccurate.

[0009] Examples of optimization along the spatial domain would be moving and rearranging the placement of circuits so as to improve the quality of the circuit for aspects such as timing and wireability. Synthesis has typically dealt with the two dimensions of boolean and electrical optimizations. Various combinations of algorithms are applied, each optimization creating possibilities for further boolean or electrical optimizations or a combination of both. Examples of boolean optimizations are factoring, redundancy removal, etc., while fanout correction/buffer insertion and sizing are examples of electrical optimizations. In later stages of synthesis (known as timing correction), mostly electrical optimization with some boolean optimizations are applied. With the increase in the capacitance/RC of interconnects with sub-micron technologies, synthesis must now consider the spatial domain, and therefore, optimizations now have to operate in all three domains.

[0010] As shown in FIG. 1, the synthesis and physical design are separate aspects of the fabrication. Thus, there is a need for an overall strategy of integrating the physical design and synthesis by creating a common framework in which electrical, boolean and location (spatial) optimizations can be performed simultaneously.

[0011] In one embodiment of the present invention, the placement of the individual cells of a circuit are manipulated to improve the overall timing of the circuit. The changes in such locations can be done in concert with resizing, buffer insertion, re-mapping and other such standard synthesis electrical and boolean transformations.

[0012] We consider the physical image in terms of an array of bins, each of which can hold a collection of gates. We assume that each gate has a known area and that for each bin, we know the available area. It is possible to have more sophisticated measures, such as wiring tracks available, so as to measure the wiring requirements. We consider Bin Circuit Count as the equivalent area required by the circuits and Bin Capacity as the equivalent area available for circuits.

[0013] The two criteria of interest in the present invention are wireability and timing. For coarse placement, wireability can either be directly estimated or one can use simpler measurements such as Bin Circuit Count vs. Bin Capacities, and Total Wire Length.

[0014] According to an embodiment of the invention, the method for improving circuit location assignment comprises the steps of determining the critical path of assigned circuit locations; generating a list of nets on the critical path; generating a list of motions for each net on the critical path; generating a set of motions for a complete path; testing each move to determining and improvement in slack for all gates participating in the move, and executing the move that provides the greatest improvement.

[0015] The selection of nets to be worked upon may use a different process than the one described here. In addition, the path that is given by the above process may be selected differently. This invention embodies all possible approaches, and is primarily concerned with the selection of motions after a net or a set of nets has been selected, and this is one example of a process by which the nets and path can be selected.

[0016] The applications envisioned for the present invention are improving a critical path, improving a critical section of the circuit (i.e., a DAG), improving wireability, resolving a bin overflow situation after moving circuits for timing, and resolvig.

[0017] During fabrication, the less often a complete timing analysis must be performed the better. The basic strategy is that when one works on improving wireability, they allows only nets with relatively large slack to increase in wire length and no critical or near-critical net is allowed to increase in wire length. When working on timing improvements, one may want to make sure that a significant improvement has been obtained. After this, the total picture may change so much that a complete timing analysis may need to be performed for further improvement.

[0018] Thus far, timing and timing improvements have been discussed. However, the present invention is applicable whenever there is a need for shortening selected nets. This can include, for example, placement for wireability, noise, or power.

[0019] A more complete appreciation of this invention, and many of the attendant advantages thereof, will be readily apparent as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings, in which like reference symbols indicate the same or similar components, wherein:

[0020] FIG. 1 is a graphical representation of optimization along various domains;

[0021] FIG. 2 is a graphical representation of the changes in locations for critical paths;

[0022] FIG. 3 is a graphical representation of the motion of individual circuits.

[0023] FIG. 4 is a flow diagram of the method for improving the overall assignment of circuit locations for any parameter according to an embodiment of the present invention;

[0024] FIG. 5 is a flow diagram of the method for improving the timing in the assignment of circuit locations according to an embodiment of the invention;

[0025] FIG. 6 is a flow diagram for creating strong motions according to an embodiment of the invention;

[0026] FIG. 7 is a flow diagram for generating strong motions for sets of nets according to an embodiment of the present invention; and

[0027] FIG. 8 is a flow diagram for improving the critical path according to an embodiment of the present invention.

[0028] The question as to which movements would have the most beneficial effects on the timing behavior of the whole circuit relates specifically to the behavior of the critical path.

[0029] FIG. 2 shows an exemplary critical path 10 which will be used for purposes of describing the present invention. The questions presented for determining the most beneficial effects are: 1) What cells need to be moved to affect the capacitance of a net?; and 2) what cells need to be moved to affect the total capacitance of a set of nets? Consider the possibility of a meander in a critical path 10. Moving any individual circuit C, D or E would have no effect on the capacitance of the critical path, while the movement of a subsequence C, D and E of the driving cells in a critical path would achieve the desired result. A more complex problem arises when we consider that the circuits C, D or E have fanouts in a net.

[0030] Similarly, FIG. 3 shows a single net 20, and with four nodes H1, H2, H3, and H4 connected to it. If any individual node is moved in the horizontal direction, there is no benefit (assuming orthogonal routing), however, if two adjacent nodes are moved together, the total net length can be decreased. The examples provided in FIGS. 2 and 3 illustrate the need for a formal definition of the valid motions of a node or a set of nodes that improve either the capacitance of a given net or the overall timing of the design.

[0031] FIG. 4 is a flow diagram 40 of the method for improving the overall assignment of circuit locations for any parameter according to an embodiment of the present invention. Initially, the locations of circuits is assigned 42 (i.e., placement). Once assigned, a determination is made as to what subset of nets or paths needs to be improved (step 44). The motions that improve the given circuit parameter are then identified (step 46). Each move is then tested to determine the extent of improvement for the given parameter (step 48). After testing, the move that provides the greatest improvement is executed (step 50). The entire process returns to step 44 to further improve the circuit placement.

[0032] FIG. 5 is a flow diagram of the method for improving the timing in the assignment of circuit locations according to an embodiment of the invention. As shown, the locations of the circuits (i.e., placement) is initially performed (step 54). Once assigned, a determination as to the subset of nets from the critical path too improve is made (step 56). The set of motions on the nets that improve the slack are identified (step 58), and each identified motion is tested for the improvement in slack (step 60). The move that provides the greatest improvement in slack is then executed (step 62).

[0033] Stability of Motions

[0034] In order to handle the aforementioned problems, the notion of stable motions has been developed. The following are definitions to aide in defining the present invention.

[0035] A net n consists of points p₁, p₂, . . . p_k, where each point P_iis at a location x_i, y_i. The configuration of a net can be given as a vector of size 2k as C_n. More specifically, C_ncan be written as x₁, y₁, x₂, y₂, . . . x_k, y_k. The length L(n) of wire required to interconnect the configuration C_ncan be estimated or computed in several different ways. For purposes of this disclosure, Manhattan lengths will be used and other metrics ignored.

[0036] 1. Often, for the sake of simplifying the computation, the length of wire is estimated to be that of the sum of the horizontal and vertical extent of the set of points. It is trivial to find cases for nets with 4 or more points where that length is inaccurate.

[0037] 2. The minimal spanning tree length can be used (although it is a pessimistic measure in many cases)

[0038] 3. The Steiner tree length is a commonly used measure. In this measure, one can generate intersection points where three or four wires connect, so that it gives the shortest length of wire required for interconnecting the set of points in a rectilinear system.

[0039] A fundamental theorem for constructing minimal length Steiner trees is:

[0040] Theorem 1 (Hanan): Consider the set of points that are needed to complete any rectangle formed by any pair of points p_iand p_jof the rectangle. For a Steiner tree to have minimal length, the intersection of points can be a subset of the original points of the net plus the rectangle-completing set of points.

[0041] Consider the direction vector of any point p_ias m_i. The direction is represented as a binary vector of size 4, which indicates the motions in +x, −x, +y, −y, respectively. For example, the direction vector of node p_i, in direction +x is given by the direction vector <1000>. An example of p_ican be any point A-E in FIG. 2 (i.e., p_irefers to any circuit in the design).

[0042] Definition 1: The motion M in a graph is defined as a set S of T, where T is a tuple of the form (p_i, m_i), where p_iis the node and m_iis its direction vector.

[0043] Definition 2: A primitive motion is one where just one node moves 1 step.

[0044] Definition 3: The derivative of L(n) is given as $\begin{array}{cc}\frac{dL\left(n\right)}{dM}=\underset{u\to 0}{\overset{u>0}{\lim }}\frac{L\left(C+\mathrm{Mu}\right)-L\left(C\right)}{u}& \left(1\right)\end{array}$

[0045] The notion of composition of two vectors M₁and M₂.

[0046] Definition 4: Two motions M₁and M₂are composable if for any vector element either M₁or M₂has a value of 0. This means that no point p moves simultaneously in both sets.

[0047] Definition 5: A motion M_cis a component of M if any vector element in M_chas the same value as the corresponding vector element in M or is 0.

[0048] Definition 6: A motion M_cis a proper component of M if it is a component of M and is not identical to M and has a non-zero vector element.

[0049] Definition 7: Two primitive motions M₁and M₂, that start at the same x coordinate and go in the same +y direction (or −y direction) are called parallel motions; similarly, if they should start at the same y coordinate and both go in +x direction (or both in the −x direction) are also called parallel. A motion M is called parallel if all pairs of components are parallel. Finally, the concept of stability is defined:

[0050] Definition 8: A motion M is not stable if there exists a decomposition into two non-zero motions M₁and M₂such that

[0051] M=M_i+M₂

[0052] Corollary 1: If a motion is stable then for any decomposition such that $\frac{dL\left(n\right)}{M}\ge \frac{dL\left(n\right)}{M_1}+\frac{dL\left(n\right)}{M_2}$ $M=M_1+M_2$

[0053] we find that $\frac{dL\left(n\right)}{M}<\frac{dL\left(n\right)}{M_1}+\frac{dL\left(n\right)}{M_2}$

[0054] The following is assumed to be true (it is readily proven for spanning rectangles—for Steiner trees and minimal spanning trees they are conjectures at this stage).

[0055] Conjecture 2: For the spanning rectangle, the minimal spanning tree, and Steiner tree, in the Manhattan metric, a motion M can be stable only if it is also a parallel motion.

[0056] Stability of Nets

[0057] The weighted sum of lengths of nets is now considered.

[0058] Definition 9: Consider a set S of nets n₁, n₂, . . . , n_m. Assume there exists a weight vector corresponding to the net weight w₁, w₂, . . . , w_m, where each w_iis greater than 0.

[0059] Let $\begin{array}{cc}L\left(S\right)=\sum _{i=1}^m{w}_{i}L\left(n_i\right)& \left(2\right)\end{array}$

[0060] be the length of the set S.

[0061] We can find all nodes p₁, p₂, . . . , p_kwhich belong to at least one net in S, the configuration C(S)=x₁, y₁, x₂, y₂, . . . , x_k, y_kand motions just as for the case of a single net.

[0062] Lemma 1: For any motion M $\frac{dL\left(S\right)}{dM}=\sum _{i=1}^m{w}_i\frac{dL\left(n_i\right)}{dM}$

[0063] For the case of the weighted sum length of nets, we can also define stable sets of motions exactly as in definition 8. The properties embodied in corollary 1 hold for the function L(S). The conjecture 2 also extends to motions with sets of nets and the length L(S).

[0064] Conjecture 3: A motion M cannot be a stable motion for L(S) if it is not a parallel motion.

[0065] Another consideration for correctness is:

[0066] Theorem 4: A motion on a subset p=(P₁p₂. . . p_h) of the nodes of S cannot be a stable set for the weighted set of nets S, if there exists a partition of P into two sets P₁and P₂such that no net in S contains at least one node from P₁and one node from P₂.

[0067] The proof of the theorem is straight forward: any motion in P₁affects a different set of nets as compared to a motion in P₂: therefore, the derivatives for the two sets of motion must be additive.

[0068] Theorem 5: A motion M cannot be a stable motion for L(S) if every non-primitive component of M is not a stable motion for some net in S.

[0069] Strong Motions

[0070] The basic interest of algorithms in this field is to find moves which have large negative derivatives. As such, a stronger criterion than that for stability of motions is introduced.

[0071] Definition 10: A strong motion M is a stable motion which has the property that for all proper components M_cof M $\begin{array}{cc}\frac{dL\left(S\right)}{dM}<\frac{dL\left(S\right)}{d{M}_c}& \left(3\right)\end{array}$

[0072] Should motion M be primitive, it can be considered a strong motion.

[0073] In order to determine whether a motion M is strong, in the worst case one would test against all possible sub-components whether definition 10 holds. However, should a proper component M_cof M be strong, then one need not test against any sub-component of M_c.

[0074] Conjecture 6: For a motion M to be strong, all primitive components of M must be parallel with each other.

[0075] Theorem 7: For a motion to be strong, P(M) cannot be divided into two subsets P₁and P₂such that no net has members in both P₁and P₂.

[0076] According to theorem 4, the motion M cannot be stable. However, stability is a requirement for a strong motion.

[0077] We believe that the conjecture 4 extends also to strong motions.

[0078] Conjecture 7: A motion M cannot be a strong motion for L (S) if any pair of primitive motions composing M are not parallel.

[0079] Theorem 9: A motion M cannot be a strong motion for L(s) if every component of M is not a strong motion for some net in S.

[0080] Creating Strong Motions for a Single Net Referring to FIG. 6, there are several sets of motions which constitute the complete set of strong motions for a single net:

[0081] 1. The primitive motions of the individual nodes (see definition 2) are found for individual nodes (step 66).

[0082] 2. Should more than 1 node be at the same coordinate, one would also test the joint movement of all the nodes at that coordinate (step 68).

[0083] 3. The combined motions from 1 or more sets of positions that are strong are found (step 70), where the positions have either the same value of x or y and the motion is perpendicular to the alignment of the positions. Here, note that the only time such a motion can be strong is when a contiguous subset (or the complete set) of the positions along the alignment moves in lockstep.

[0084] Except for the first item (i.e., the primitive motions of the individual nodes) all other motions need testing whether their first derivative is less than any of its component motions.

[0085] Procedure for Creating Complex Moves for a Net

[0086] Complex Moves are those that involve the motion of more than one node. These include the moving of all nodes at the same location, that are called primitive. The main procedure is as follows:

[0087] 1. The basic data structure is a list of nodes together with their location.

[0088] 2. Sort the nodes horizontally, and then vertically.

[0089] 3. If a sequence of nodes has the same x,y location, generate a joint move for these: use a procedure called GenerateBinMove.

[0090] 4. Use a procedure called GenerateComplexMoves to generate the moves in the horizontal direction.

[0091] 5. Sort the nodes vertically, and then horizontally.

[0092] 6. Use a procedure called GenerateComplexMoves to generate the moves in the vertical direction.

[0093] The procedure GenerateComplexexMoves works on subsets of nodes that have the same x(or y) coordinate. These are further divided into bins at identical x,y coordinates. For each of the subsets at identical x(or y) coordinates, it finds the number of bins. A complex move consists of moving contents of two or more adjacent bins in the x (or y) direction. The number of such combinations, when m is the number of bins that can be simultaneously moved, is given as m(m−1)/2. Each such move can be indexed by its position pos(pos starts at 0) in the list of adjacent bins at the same x(or y) coordinate and the number l of bins simultaneously moved (where l is at least 2). The formula for such an index is given by

[0094] index=pos+(l−2)m−(l−2)(l−2)/2

[0095] The nodes are, as stated previously, sequentially ordered, and can be addressed by the sequence number in that order. For each node we generate two pairs of indices: one pair states which nodes are the first and last node to have the same x(or y) coordinate, and which nodes are the first and last node to share the same bin. The procedure GenerateComplexMoves then works as follows:

[0096] 1. Compute the four index structures—call the samebinfirst, samebinlast and alignedfirst, alignedlast—which are indexed with the nodes position in the sorted list and where ‘samebinfirst’ holds for any node the position of the first node in the same bin, ‘samebinlast’ holds for any node the position of the last node in the same bine, and similarly for ‘alignedfirst’ and ‘alignedlast’, except now it refers to the alignment of the nodes.

[0097] 2. Set i to be the sequence number of the first book in the list—in C and C++, usually 0.

[0098] 3. While i less than the number of books,

[0099] If samebinlist(i)<alignedlast(i) then do:

[0100] compute m=number of bins and create a table structure to hold entries for the m(m −1)/2 possible moves

[0101] for j=0 to j=m−2, and dir=positive, negative, do:

[0102] for l=2 to m−j−2, do:

[0103] Compute the change in capacitance for moving the bins indexed by samebinfirst (i+j) to samebinlast (i+j+l1) and decide whether that move satisfied either the criterion for a stable or strong move: if so, label it as usable and insert it into the move list for this net—otherwise unusable. The function doing this checking is called TestSplit

[0104] *endfor

[0105] endfor

[0106] Endif

[0107] 4. Set i to 1+alignedlast(i).

[0108] Creating Motions for a Set of Nets

[0109] The primary interest is finding motions that have a negative derivative for L(S). Thus, we are interested in finding the motions having a negative derivative for some L(n), where n is some net. For this algorithm, we use two results—Conjecture 8 and theorem 7. Referring to FIG. 7,

[0110] 1. Compile a set or list of strong motions for all nets in a selected subset S (step 74).

[0111] 2. Initialize a list of motions with negative derivatives in L(S) (e.g., L_neg) (step 76).

[0112] 3. For all net-wise strong motions M, which also have negative derivatives in L(n) (step 8), do

[0113] (a) Test if M has a negative derivative in L(S): if so, add it to L_neg.

[0114] (b) Otherwise, open a list of candidate motions C(M), that initially holds only M

[0115] (c) While C(M) is not empty, do

[0116] i. Take a motion M_cfrom C(M)

[0117] ii. If (dL(S)/dM_c) is negative enter it in L_neg.

[0118] iii. Otherwise, consider E(M_c), the set of nets that are connected to nodes in P(M_c), the set of nodes that have motion in M_c.

[0119] iv. For all n ε E(M_c) where (dL(n)/dM_c)is positive, do

[0120] If there is a strong motion Mⁿin n such that both M²∩ and M_cand Mⁿ−M_care not empty, then enter Mⁿ∩ M_cas a candidate in C(M).

[0121] The list L_negis the end-product of this algorithm (step 80).

[0122] Improving a Critical Path

[0123] This algorithm is called with a threshold for the improvement required. It works as follows (using intermediate variables ImprovedPath and Improvement; ‘Improvement’ keeps track of the amount by which the path has been improved, while ‘ImprovedPath’ allows one to terminate the process should no improvement be possible):

[0124] Set ImprovedPath 1 (step 84)

[0125] While ImprovedPath>0 (step 86)

[0126] Set ImprovedPath=0

[0127] Find critical Path

[0128] Set Improvement=0

[0129] Find strong moves and any logical transformations that may improve the path (step 90)

[0130] while Improvement<threshold (at step 92)

[0131] find most significant motion that does not interfere with any other critical path (step 94)

[0132] if none is found, exit

[0133] apply motion and update Improvement

[0134] Update list of motions

[0135] Set ImprovedPath=1 (step 84)

[0136] Report new value for slack

[0137] If the ImprovedPath is not greater than 0 (step 86) the slack is updated (step 88).

[0138] Path Selection for Pressure Points

[0139] The problem is that of improving not just the critical path, but reducing the number of nets that are in the critical region. Thus, the concept of a critical pressure path is developed. That is, a path that, should it be improved, would improve many other paths. A path is selected by first defining a critical region: this includes all timing points whose slack are below some predetermined threshold. It also includes all timing segments that connect timing points of the critical region and whose delay alone would be sufficient to keep the source and the sink of the timing segment in the critical region. The number of distinct paths that emanate from it in the critical region and the number of distinct paths that enter it can be computed by recursive methods for each timing point. The number of paths that go through each timing point is the product of the number of paths entering and the number of paths emanating from it.

[0140] The starting point for selecting a critical pressure path is to start with a node with the largest value of the number of paths. One continues this path by going forward through the segments of the critical region and selecting recursively among the successors the one with the largest number of paths, and also going backward through segments again selecting recursively among the predecessors the one with the largest number of paths.

[0141] It should be understood that the present invention is not limited to the particular embodiment disclosed herein as the best mode contemplated for carrying out the present invention, but rather that the present invention is not limited to the specific embodiments described in this specification except as defined in the appended claims.