Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-04-22
2001-06-05
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06243850
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an allocation apparatus and method for determining cell allocation in the automatic layout, etc. of semiconductor circuits.
2. Description of the Related Art
As the technology for semiconductor integrated circuits has recently improved, the improvement in integration of very large-scale integration (VLSI) chips and the increase in the scale of circuits has become remarkable. Since both the improvement in integration and the increase in circuit scale are accompanied by an increase in the number of cells included in VLSI chips, it is getting harder and harder to get an optimum solution to a cell allocation issue.
In the layout design of LSIs, the process of partitioning an allocation area on a chip is repeated utilizing a computer system, and thereby the default allocation of each cell is determined. The allocated cells correspond to module components, etc., the shapes of the cells are usually rectangular, and the cells have a certain area. As one conventional partitioning method there is a method of using a resistive network model based on the analogy of electric circuits (R-S. Tsay, E. Kuh, and C-P. Hsu, “A Sea-of-Gates Placement Algorithm”, IEEE Design & Test of Computers, December 1988, pp.44-56).
FIG. 1A
is a flowchart showing a block Gauss-Seidel method being one partitioning method using the resistive network model. When the process is started, first the system constructs a resistive network based on a net list for indicating the wiring of a given circuit (step S
1
).
Here, a resistive network means a graph in which cells are represented by nodes and a plurality of cells belonging to the same net are connected by means of edges. In this case, for the model indicating the connection of cells, a complete connection model as shown in
FIG. 1B
is used. In the complete connection model each node on one net is connected with all other nodes of the net.
Then, the simultaneous linear equations of the constructed resistive network are created, and are solved using a successive over-relaxation (SOR) method (step S
2
). The SOR method corresponds to a generalized Gauss-Seidel method, which is an iterative method for solving simultaneous linear equations.
It is generally known that the solution of the simultaneous linear equations of a resistive network gives the cell positions where the following objective function of a cell allocation issue becomes a minimum.
L
(
x
,
y
)
=
1
/
2
∑
i
,
j
=
1
n
c
ij
[
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2
]
=
x
t
Bx
+
y
t
By
(
1
)
where n, (x
i
, y
i
), and x and y represents the total number of cells, the coordinates of the i-th cell (i=1, 2, 3, . . . , n), and the n-dimensional vector with the x-coordinate and y-coordinate of n cells as the elements, respectively.
c
ij
is a connection coefficient between the i-th cell and j-th cell, where c
ii
=0 and c
ij
=c
ji
. The matrix B of n×n is expressed using a symmetrical matrix C with a c
ij
as the element as follows:
B=D−C (2)
Provided that a matrix D is a diagonal matrix with the following diagonal element.
d
ii
=
∑
j
=
1
n
c
ii
(
3
)
Therefore, the objective function L (x, y) of the equation (1) corresponds to the sum of squares of the wire lengths between the cells, and it is considered that the cell position (x, y) where the value of L (x, y) becomes a minimum, gives the optimum cell allocation. The solution of the simultaneous linear equations of a resistive network corresponds to a cell position such as this.
Then, the obtained cell position (x
i
, y
i
) is sorted according to the respective values of the x-coordinate and y-coordinate (step S
3
). Then, cells are put in one partitioned block of the allocated area in ascending order of the respective coordinate values, and when the cell areas are balanced, the remaining cells are put in the other partitioned block (step S
4
).
The point where the cell areas are balanced means, for example, the point where the total sum of cell areas contained in a block becomes about half of the sum of all cell areas. In this way, n cells are so divided into two blocks that both areas are balanced, and then the process is terminated. By repeating the division of both the x-direction and y-direction in this way, the size of the blocks is gradually reduced, and finally each block can be made to contain only one cell.
However, the above-mentioned conventional partitioning method has the following problems.
Since a complete connection model as shown in
FIG. 1B
is used when converting a net list to a resistive network, the value of the objective function does not become small unless all distances between the cells connected to a certain net are about the same. Accordingly, as a result, cells are uniformly distributed in two-dimensions, and the result does not necessarily match with an actual wiring pattern.
In this partitioning method, although the solution is sorted according to the value of a cell position coordinate when applying a block Gauss-Seidel method, the number of cuts on the boundary of blocks is not taken into consideration. The number of cuts means the number of wires transversing a cut line (border line), and in the layout design of semiconductor integrated circuits, it is desirable to minimize this number.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an allocation apparatus and method for optimizing the cell allocation in the layout design of semiconductor integrated circuits using a circuit model closer to actual wiring.
The allocation apparatus of the present invention comprises a creation unit, a storage unit, a calculation unit and an output unit, and determines the cell allocation of a given circuit.
The creation unit creates both cell nodes corresponding to a plurality of cells and a net node corresponding to a net between cells from a net list of the circuit. The storage unit stores the parameters for simultaneous equations on the positions of both the cell nodes and the net node. The calculation unit solves the simultaneous equations using the stored parameters. The output unit outputs the solution.
By adopting an allocation apparatus such as this, since a net node is inserted among cell nodes, there is no need to directly connect the cell nodes. Accordingly, the connection relationship among cell nodes becomes weaker than with a conventional node model, and the flexibility of cell allocation is improved compared with the conventional model.
For the simultaneous equations for determining cell allocation, for example, the above-mentioned simultaneous linear equations of a resistive network are used, and by solving the equations using the SOR method, the positions of both the cell nodes and net node are optimized. The partitioning of cells, grouping of flip-flops, partitioning of cells in consideration of an existing wiring pattern, determination of external terminal positions in a floor plan, etc., can also be implemented by using this result.
REFERENCES:
patent: 4908772 (1990-03-01), Chi
patent: 6035111 (2000-03-01), Suzuki et al.
patent: 6038382 (2000-03-01), Kanazawa
patent: 7-321208 (1995-12-01), None
R. Tsay, et al., “Proud: A Sea-of-Gates Placement Algorithm”,IEEE Design&Test of Computers, pp. 44-56, (1988).
Fujitsu Limited
Phan Trong
LandOfFree
Allocation apparatus and method for determining cell... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Allocation apparatus and method for determining cell..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Allocation apparatus and method for determining cell... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464300