Chip layout method based on minimum total wire length

This application claims priority to Chinese Patent Application No. 202110644276.3 with a filing date of Jun. 9, 2021. The content of the aforementioned application, including any intervening amendments thereto, is incorporated herein by reference.

The present disclosure relates to the technical field of chip layout, and in particular, to a chip layout method based on a minimum total wire length.

In very large-scale integration (VLSI) chip design, the minimum total wire length of the chip concerns how a variable-sized rectangular chip is determined by n rectangular circuit modules with given widths and heights, such that all rectangular circuit modules can be legitimately placed and the total length of wires between the circuit modules in the rectangular chip is minimum. The legitimacy means that all placed rectangular circuit modules fall within the boundary of the rectangular chip, with edges parallel to the edges of the rectangular chip and without the mutual overlap. The total wire length refers to a total length of wires through which the rectangular circuit modules are connected from pins thereon.

The minimization of the total wire length on the chip is crucial for the VLSI chip design. The VLSI chip design involves the placement of a set of rectangular modules on the rectangular chip and wire connection of these modules. In this case, the goals to be considered are minimization for the area of the rectangular chip and minimization for the total length of the wires. As is known to all, the performance of the chip is the first and foremost goal to be considered and optimized during the VLSI chip design, and the lengths of interconnecting wires are main factors to determine the power dissipation, delay, reliability and other performance of the chip. On the other hand, materials for producing the chip are very expensive, so the minimization of the total wire length can be helpful to save the metal wires and reduce the manufacturing cost; and particularly in large-scale production, improving the utilization rates of chip materials can bring the remarkable economic benefits.

However, most existing algorithms applied to the VLSI chip design attach importance to optimization of a total area of the chip, while ignoring the interconnecting wires between the rectangular circuit modules, such that the power dissipation and delay of the chip cannot be reduced. Concerning minimization of the wire length on the VLSI chip, existing methods are to simply connect the rectangular circuit modules through their respective centers, and thus the results are too simple to be representative and address the practical problems well.

In view of the minimization of the total wire length on the chip, the present disclosure provides a chip arrangement method based on a minimum wire length. The method can achieve the utmost performance of the integration chip and the reasonable chip layout by minimizing the total wire length of the chip during the VLSI chip design; and furthermore, the present disclosure can save materials for producing the rectangular chip at maximum, improve the utilization rates of the materials, and bring remarkable economic benefits to enterprises in large-scale production. The present disclosure is superior to the existing methods, with improved solutions for most typical cases.

In view of the defects in the background art, an objective of the present disclosure is to provide a chip arrangement method based on a minimum total wire length. The method can achieve the utmost performance of the integration chip and the reasonable chip layout by minimizing the total wire length of the chip during the VLSI chip design; and furthermore, the present disclosure can save materials for producing the rectangular chip at maximum, improve the utilization rates of the materials, and bring remarkable economic benefits in large-scale production.

In order to achieve the above objective, the present disclosure adopts the following technical solutions:

A chip layout method based on a minimum total wire length includes the following steps:

step A: initializing a total wire length of a chip to a maximum preset wire length, and initializing a number of iterations;

step B: randomly generating a sequence pair, the sequence pair being used to represent a positional relationship between rectangular circuit modules, inputting the sequence pair to a model, and solving to obtain a minimum total wire length and a corresponding present sequence pair at a present number of iterations;

step C: changing a field operator of the present sequence pair to obtain a new sequence pair, inputting the new sequence pair to the original model, and solving to obtain a new sequence pair and a total wire length corresponding to the new sequence pair;

step D: determining whether the total wire length corresponding to the new sequence pair is less than the total wire length corresponding to the present sequence pair, and if no, deleting the new sequence pair, retaining the present sequence pair, and repeating step C; and if yes, deleting the present sequence pair, retaining the new sequence pair and labeling the new sequence pair as the present sequence pair; and

step E: determining whether a number of iterations changed by the field operator is reached, and if yes, outputting the total wire length corresponding to the present sequence pair and a coordinate position of each of the rectangular circuit modules, the total wire length being a minimum total wire length; and if no, repeating step C.

Preferably, step B may further include: determining pin coordinate information of the rectangular circuit modules based on the rectangular circuit modules, and gathering the pin coordinate information of the rectangular modules to generate pin network sets;

randomly generating a sequence pair, and representing the positional relationship between the rectangular circuit modules with the sequence pair; and

inputting the sequence pair, the rectangular circuit modules, the pin coordinate information and the pin network sets to the original model and solving to obtain a present sequence pair corresponding to a minimum total wire length at a present number of iterations.

Preferably, the sequence pair may be used to represent the positional relationship between the rectangular circuit modules, specifically including:

the positional relationship between the rectangular circuit modules may be represented based on positive and negative subsequence pairs;

if a present rectangular circuit module has a sequence position in front of another rectangular circuit module in the positive and negative subsequence pairs, the present rectangular circuit module may be actually located on a left side of the another rectangular circuit module;

if the present rectangular circuit module has a sequence position in back of the another rectangular circuit module in the positive and negative subsequence pairs, the present rectangular circuit module may be actually located on a right side of the another rectangular circuit module;

if the present rectangular circuit module has a sequence position in front of the another rectangular circuit module in the positive subsequence pair, and has a sequence position in back of the another rectangular circuit module in the negative subsequence pair, the present rectangular circuit module may be actually located above the another rectangular circuit module; and

if the present rectangular circuit module has a sequence position in back of the another rectangular circuit module in the positive subsequence pair, and has a sequence position in front of the another rectangular circuit module in the negative subsequence pair, the present rectangular circuit module may be actually located below the another rectangular circuit module.

Preferably, step B may further include:

step B1: randomly generating a sequence pair, inputting the sequence pair, the rectangular circuit modules, the pin coordinate information and the pin network sets to the model, and solving to obtain a new sequence pair and a total wide length corresponding to the new sequence pair;

step B2: determining whether the total wide length corresponding to the new sequence pair is less than a total wire length corresponding to an original sequence pair, and if yes, retaining the total wide length corresponding to the new sequence pair, replacing the original sequence pair with the new sequence pair, and jumping to step B3; and if no, repeating step B1; and

step B3: determining whether a number of iterations is reached, and if yes, outputting the sequence pair and the total wire length corresponding to the new sequence pair in step B2; and if no, repeating step B1.

Preferably, the original model may include:

min Σ N∈ w(N)·(x N + −x N − +y N + −y N − );

∀N∈ , p∈N, i(p)≠∅;

x i(p) −x N − ≥−x(p);

y i(p) −y N − ≥−y(p);

x N + −x i(p) ≥x(p);

y N + −y i(p) ≥y(p);

∀N∈ , p∈N, i(p)≠∅;

t 0 −x N − ≥−x(p);

t 0 −y N − ≥−y(p);

x N + −t 0 ≥x(p);

y N + −t 0 ≥y(p);

∀r i ∈R, r i ≠r j ;

t 0 −x i ≥w i −W, t 0 −y i ≥h i −H;

y i −y j ≥h j +k ij −y i ≥h i +k ij ; and

x i −x j ≥w j +d ij , x j −x i ≥w i +d ij ,

where:

N represents a pin network;

w(N) represents a weight of the pin network;

represents pin network sets;

x N + , x N − , y N + , y N − represents four decision variables, the four decision variables being formed into a minimum-cycle long-axis parallel rectangle of each network N [x N + −x N − ]×[y N + −y N − ];

p represents a pin;

x i(p) , y i(p) represents a transverse coordinate and a longitudinal coordinate of a rectangular circuit module r i where the pin p is located;

x (p) , y (p) represents offsets of the pin p relative to the coordinates of the located rectangular circuit module;

t 0 represents a constant;

r i represents the rectangular circuit module;

R represents a set of all rectangular circuit modules;

x i , y i represents the transverse coordinate and the longitudinal coordinate of the rectangular circuit module r i ;

x j , y j represents a transverse coordinate and a longitudinal coordinate of a rectangular circuit module r j ;

k ij represents a wiring distance between the rectangular circuit modules r i , r j in a vertical direction;

d ij represents a wiring distance between the rectangular circuit modules r i , r j in a horizontal direction;

W represents a width of a region where all rectangular circuit modules are placed, and H represents a height of the region where all rectangular circuit modules are placed;

w i and h i represent a height and a width of the rectangular circuit module r i ; and

w j and h j represent a height and a width of the rectangular circuit module r j .

Preferably, the chip layout method may include: converting the original model into a dual model to obtain a new sequence pair and a total wire length corresponding to the new sequence pair, where

the dual model may include:

maxΣb ij f ij ,

where:

b ij represents a right-hand side of a constraint of the original model;

f ij represents a dual variable corresponding to a constraint v j −v i ≥b ij of the original model;

f jk represents a dual variable corresponding to a constraint v k −v j ≥b jk of the original model; and

v j , v i , v k represents types of variables in the original model, the types of the variables in the original model including:

x N + , y N + , x N − , y N − , x i , y i , x i(p) , y i(p) , where x(N) − , y(N) − represents x N − , y N − in the original model, and x(N) + , y(N) + represents x N + , y N + in the original model.

The present disclosure achieves the following technical effects over the prior art:

The present disclosure implements the chip layout by minimizing the total length of interconnecting wires, and achieves the better performance of the chip. With the minimum total wire length, the method further achieves a better chip layout (the rectangular circuit modules on the chip are arranged compactly as much as possible to reduce the total area of the chip to some extent). Compared with existing methods, the present disclosure is implemented more simply and easily; and by converting the problem model into the dual model, the method is equivalent to a maximum-cost flow problem, such that the problem is solved within polynomial time to improve the efficiency.

FIG. 1 illustrates a flow chart of a chip layout method based on a minimum total wire length according to an embodiment of the present disclosure; and

FIG. 2 illustrates a positional relationship between rectangular circuit modules a and b in a sequence pair according to an embodiment of the present disclosure.

The technical solutions of the present disclosure will be described in more detail below with reference to the accompanying drawings and specific implementations.

Most existing technologies applied to the VLSI chip design attach importance to optimization of a total area of the chip, while ignoring the interconnecting wires between the rectangular circuit modules, such that the power dissipation and delay of the chip cannot be reduced. Concerning minimization of the wire length on the VLSI chip, existing methods are to simply connect the rectangular circuit modules through their respective centers, and the obtained results are too simple to be representative and address the practical problems well. In view of the above problems, the present disclosure provides a chip layout method based on a minimum total wire length. The method is implemented by initializing a total wire length to a very large number, controlling a number of iterations, continuously and randomly generating a sequence pair to represent a positional relationship between rectangular circuit modules, inputting the sequence pair to a model, and solving to obtain a sequence pair having a minimum wire length at a present number of iterations; changing a field operator of the sequence pair to obtain a new sequence pair, inputting the new sequence pair to the model, retaining, if an obtained total wire length is less than the original total wire length, the new sequence pair obtained by changing the field operator, or otherwise, abandoning the new sequence pair; repeating the above operation till a number of iterations changed by the field operator is reached; and outputting a minimum total wire length, and a coordinate of each of the rectangular circuit modules to obtain the chip layout based on the minimum total wire length.

As shown in FIG. 1 , L represents a present total wire length, L′ represents a total wire length which is sought first, Γ represents a present randomly generated sequence pair, and Γ′ represents a sought sequence pair. Specifically, the chip layout method includes the following steps:

Step A: Initialize a total wire length of a chip to a maximum preset wire length, and initialize a number of iterations.

Step B: Randomly generate a sequence pair, the sequence pair being used to represent a positional relationship between rectangular circuit modules, input the sequence pair to a model, and solve to obtain a present sequence pair corresponding to a minimum total wire length at a present number of iterations.

Preferably, the step includes: Determine pin coordinate information of the rectangular circuit modules based on the rectangular circuit modules, and gather the pin coordinate information of the rectangular modules to generate pin network sets.

Randomly generate a sequence pair, and represent the positional relationship between the rectangular circuit modules with the sequence pair.

Input the sequence pair, the rectangular circuit modules, the pin coordinate information and the pin network sets to the original model and solve to obtain a present sequence pair corresponding to a minimum total wire length at a present number of iterations.

Preferably, the sequence pair is used to represent the positional relationship between the rectangular circuit modules, specifically including:

The positional relationship between the rectangular circuit modules is represented based on positive and negative subsequence pairs.

If a present rectangular circuit module has a sequence position in front of another rectangular circuit module in the positive and negative subsequence pairs, the present rectangular circuit module is actually located on a left side of the another rectangular circuit module.

If the present rectangular circuit module has a sequence position in back of the another rectangular circuit module in the positive and negative subsequence pairs, the present rectangular circuit module is actually located on a right side of the another rectangular circuit module.

If the present rectangular circuit module has a sequence position in front of the another rectangular circuit module in the positive subsequence pair, and has a sequence position in back of the another rectangular circuit module in the negative subsequence pair, the present rectangular circuit module is actually located above the another rectangular circuit module.

If the present rectangular circuit module has a sequence position in back of the another rectangular circuit module in the positive subsequence pair, and has a sequence position in front of the another rectangular circuit module in the negative subsequence pair, the present rectangular circuit module is actually located below the another rectangular circuit module.

As shown in FIG. 2 , the present disclosure takes rectangular circuit modules a and b as an example to describe the comparison between two modules. Given two modules a and b, a is located on the left side of b if a is in front of b in the positive and negative sequences; a is located on the right side of b if a is in back of b in the positive and negative sequences; a is located above b if a is in front of b in the positive sequence but in back of b in the negative sequence; and a is located below b if a is in back of b in the positive sequence but in front of b in the negative sequence. With the sequence pair (Γ + , Γ − )=(124,214) for example, 1 is in front of 4 in the positive and negative sequences, indicating that 1 is located on the left side of 4; 1 is in front of 2 in the positive sequence but in back of 2 in the negative sequence, indicating that 1 is located above 2; and 2 is in front of 4 in the positive and negative sequences, indicating that 2 is located on the left side of 4. The above are the positional relationship between the three modules represented by the sequence pair (Γ + , Γ − )=(124,214).

Preferably, Step B further includes:

Step B1: Randomly generate a sequence pair, input the sequence pair, the rectangular circuit modules, the pin coordinate information and the pin network sets to the model, and solve to obtain a new sequence pair and a total wide length corresponding to the new sequence pair.

Step B2: Determine whether the total wide length corresponding to the new sequence pair is less than a total wire length corresponding to an original sequence pair, and if yes, retain the total wide length corresponding to the new sequence pair, replace the original sequence pair with the new sequence pair, and jump to Step B3; and if no, repeat Step B1.

Step B3: Determine whether a number of iterations is reached, and if yes, output the sequence pair and the total wire length corresponding to the new sequence pair in Step B2; and if no, repeat Step B1.

Step C: Change a field operator of the present sequence pair to obtain a new sequence pair, input the new sequence pair to the original model, and solve to obtain a total wire length corresponding to the new sequence pair.

Step D: Determine whether the total wire length corresponding to the new sequence pair is less than the total wire length corresponding to the present sequence pair, and if no, delete the new sequence pair, retain the present sequence pair, and repeat Step C; and if yes, delete the present sequence pair, retain the new sequence pair and label the new sequence pair as the present sequence pair.

Step E: Determine whether a number of iterations changed by the field operator is reached, and if yes, output the total wire length corresponding to the present sequence pair and a coordinate position of each of the rectangular circuit modules, the total wire length being a minimum total wire length; and if no, repeat Step C.

Preferably, the original model includes:

min Σ N∈ w(N)·(x N + −x N − +y N + −y N − );

∀N∈ , p∈N, i(p)≠∅;

x i(p) −x N − ≥−x(p);

y i(p) −y N − ≥−y(p);

x N + −x i(p) ≥x(p);

y N + −y i(p) ≥y(p);

∀N∈ , p∈N, i(p)≠∅;

t 0 −x N − ≥−x(p);

t 0 −y N − ≥−y(p);

x N + −t 0 ≥x(p);

y N + −t 0 ≥y(p);

∀r i ∈R, r i ≠r j ;

t 0 −x i ≥w i −W, t 0 −y i ≥h i −H;

y i −y j ≥h j +k ij −y i ≥h i +k ij ; and

x i −x j ≥w j +d ij , x j −x i ≥w i +d ij ,

where:

N represents a pin network;

w(N) represents a weight of the pin network;

represents pin network sets;

x N + , x N − , y N + , y N − represents four decision variables, the four decision variables being formed into a minimum-cycle long-axis parallel rectangle of each network N [x N + −x N − ]×[y N + −y N − ];

p represents a pin;

x i(o) , y i(p) represents a transverse coordinate and a longitudinal coordinate of a rectangular circuit module r i where the pin p is located;

x (p) , y (p) represents offsets of the pin p relative to the coordinates of the located rectangular circuit module;

t 0 represents a constant;

r i represents the rectangular circuit module;

R represents a set of all rectangular circuit modules;

x i , y i represents the transverse coordinate and the longitudinal coordinate of a rectangular circuit module r i ;

x j , y i represents a transverse coordinate and a longitudinal coordinate of the rectangular circuit module r j ;

k ij represents a wiring distance between the rectangular circuit modules r i , r j in a vertical direction;

d ij represents a wiring distance between the rectangular circuit modules r i , r j in a horizontal direction;

W represents a width of a region where all rectangular circuit modules are placed, and H represents a height of the region where all rectangular circuit modules are placed;

w i and h i represent a height and a width of the rectangular circuit module r i ; and

w j and h j represent a height and a width of the rectangular circuit module r j .

Preferably, the chip layout method includes: Convert the original model into a dual model to obtain a new sequence pair and a total wire length corresponding to the new sequence pair, where

the dual model includes:

maxΣb ij f ij ;

where:

b ij represents a right-hand side of a constraint of the original model;

f ij represents a dual variable corresponding to a constraint v j −v i ≥b ij of the original model;

f jk represents a dual variable corresponding to a constraint v k −v j ≥b jk of the original model;

v j , v i , v k represents types of variables in the original model, the types of the variables in the original model including:

x N + , x N − , y N + , y N − , x i , y i , x i(p) , y i(p) , where x(N) − , y(N) − represents x N − , y N − in the original model, and x(N) + , y(N) + represents x N + , y N + in the original model.

The technical principles of the present disclosure are described above with reference to the specific embodiments. These descriptions are merely intended to explain the principles of the present disclosure, and may not be construed as limiting the protection scope of the present disclosure in any way. Therefore, those skilled in the art may derive other specific implementations of the present disclosure without creative effort, but these implementations should fall within the protection scope of the present disclosure.