JP2553709B2 - How to group cells - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a polycell type semiconductor integrated circuit,
The present invention relates to a method of dividing cells constituting a circuit into a plurality of groups.

2. Description of the Related Art In a polycell type semiconductor integrated circuit, generally rectangular cells having a logical function and having a uniform height are arranged to form a cell row, and a plurality of cell rows are arranged and wiring is provided between the rows. It is composed of

In the cell layout, placing cells having a high degree of coupling close to each other often leads to the minimization of the wiring length between the cells and the minimization of the layout area. Therefore, grouping according to the degree of cell coupling is an important technique in the cell placement problem. Conventionally, there is a cluster growth method as a method of grouping cells. FIG. 3 shows an algorithm diagram of cell grouping by the cluster growth method. 71 is a group number determination step, 72 is a seed selection step, and 73 is a cell addition (addition) step. A method of grouping cells will be described with reference to FIG. First, in order to determine the number of groups to be divided, a group number determining step 71 manually specifies the number of groups. Here, each divided group is referred to as a cluster (hereinafter referred to as a cluster). Next, for each cluster, the seed selection step 72 selects the center of the cluster, called the seed. Then, in the cell adding step 73, cells each having a high degree of coupling with the cells already included in the cluster and not yet included in the cluster are sequentially selected for each cluster, and the cells are added to each cluster. .

Further, there is a cell placement method using a minimum cut as one of the methods for performing cell placement. FIG. 4 is a layout diagram of a polycell type semiconductor integrated circuit for showing a method of calculating the number of cuts. 81 is a cell row, 82 is a first cell, and 83 is a second cell connected to the first cell. Cell, 84 indicates the cut line.

The number of cuts is evaluated by the total number of wirings that cross the cut line 84 set in the cell row 81. For example, in FIG. 4, the number of wires that the first cell 82 crosses the cut line 84, that is, the number of cuts, is two due to the positional relationship of the second cell 83 connected to the first cell 82. The larger the number of cuts, the larger the number of wirings that cross the cell row, and the longer the wiring length. Therefore, one of the evaluations for reducing the layout area is to reduce the number of cuts.

FIG. 5 shows an algorithm diagram of the cell arrangement method by the minimum cut, 91 is an initial arrangement step, 92 is a cell selection step, 93 is a cut number evaluation step, 94 is a cut number determination step, and 95 is a cell movement step. , 96 are movement determination steps.

The conventional cell placement method configured as described above will be described based on the algorithm of FIG. In the initial placement step 91, in order to reduce the influence of the processing order on the placement state of cells, all cells are initially assigned to each cell row so that the specified number of cell rows is obtained by using a random number.

In the cell selection step 92, the cell to be moved is selected from the cells allocated to each cell row in order to improve the layout. In the cut number evaluation step 93, the number of cuts before moving the cell and the number of cuts after moving the cell are obtained. Next, in the cut number determination step 94, if the cut number is reduced by moving the cell by comparing the cut numbers obtained in the cut number evaluation step 93, the cell moving step 95
To move the cell. By repeatedly applying the above processing, the number of cuts is minimized and the optimum arrangement position is obtained.

However, in the grouping of cells by the conventional cluster growth method, the grouping depends on the order of cells entering the cluster. Further, in the cell placement method using the minimum cut, when the whole circuit is composed of the regular repeating structure of the partial circuits, the random number is initially placed, so that the circuit structure is hard to be saved, and There is a problem that the result is different each time the processing is performed.

In view of the above point, the present invention has an object to provide a cell grouping method for realizing grouping that does not depend on the order of cells that enter each cluster.

Means for Solving the Problems The present invention provides (1) two cells included in a semiconductor integrated circuit.
Number determining step for determining the number of cells to be included in one set A and B, and an external terminal for connecting the semiconductor integrated circuit to an external circuit with a seed required for determining the cells to be included in the set A and the set B. And the set A and the set B
A seed selection step from among cells not included in the set A, a cell separation step of determining the cells to be included in the set A and the set B according to the degree of connection with the seed, and the set A and the set B. And a cut number minimizing step for minimizing the number of cuts of the wirings crossing the cut line set between the set A and the set B by exchanging cells between the set A and the set B.

Action According to the present invention, the cell is divided into two sets and the number of cuts between the sets is minimized by the configuration (1) described above. It is used repeatedly to realize division of two or more sets. From the above, the coupling degree of the cells in the set is strong.
Further, after cells have once entered the set, cells are exchanged between the sets by minimizing the number of cuts between the sets, so that grouping is performed without depending on the order of the cells entering the set.

Embodiment (Embodiment 1) FIG. 1 shows an algorithm diagram of a cell grouping method in a first embodiment of the present invention. In FIG. 1, 11 is a cluster (set) division determination step, 12 is a number determination step, 13 is a seed selection step, 14 is a cell separation step, and 15 is a cut number minimization step. FIG. 2 shows a conceptual diagram of the grouping method of the same embodiment. In FIG. 2, 41 is an I / O pad, 42 is an external terminal of the left cluster, 43 is an external terminal of the right cluster, 44 is a cut line, 45 is a target cluster, 46 is a left cluster, and 47 is a right cluster. A cluster, 48 is a cell on the left side of the cluster, 49 is an external terminal on the left side of the cluster, 410 is a cell on the right side of the cluster, 411 is an external terminal on the right side of the cluster, and 412 is a group of external terminals.

The procedure of the cell grouping method configured as described above will be described below.

In the number determination step 12, the number of cells to be included in each of the clusters 46 and 47 formed when the cluster is divided into two is determined according to the number of external terminals included in the target cluster (target cluster 45). The group 412 of external terminals included in the target cluster 45 is divided into two parts according to the positional relationship of the groups 412. At this time, the external terminal 42 on the left side
Is n1, the number of external terminals 43 on the right side is n2, and the number of cells included in the target cluster 45 is n, the number of cells included in the left cluster 46 is n · n1 / (n1 + n2), and the right cluster is The number of cells included in 47 is n · n2 / (n1 + n2). Next, in the seed selection step 13, in order to divide the target cluster 45 into two, a seed to be used as a reference for calculating the degree of coupling for selecting cells included in the clusters 46 and 47 is determined. As an example, the external terminal 42 on the left side is the seed of the cluster 46 on the left side, and the external terminal 43 on the right side is the seed of the cluster 47 on the right side. Further, in order to reduce the total wiring length in consideration of the influence of coupling with cells existing in other than the target cluster 45 (cell 48 on the left side of the cluster, cell 410 on the right side of the cluster), the left side of the target cluster 45 The cell 48 and the external terminal 49 on the left side are the seeds of the cluster 46 on the left side, and the cell 49 and the external terminal 410 on the right side are the seeds of cluster 47 on the right side. Next, in the cell separation step 14, the two clusters 46 and 47 are alternately selected one by one and the cell having the highest coupling degree, and the cells are added to the cluster. Finally, in the cut number minimizing step 15, cells are exchanged between the clusters 46 and 47 so that the degree of coupling between the two clusters 46 and 47 is minimized.

As described above, according to the present embodiment, by performing the clustering considering the degree of coupling in each cluster and then minimizing the coupling between the clusters, the grouping independent of the order of the cells entering each cluster is realized. In addition, it is possible to group cells having the characteristics that the degree of coupling between cells between clusters is small and the degree of coupling between cells within a cluster is large.

EFFECTS OF THE INVENTION As described above, according to the present invention, grouping that does not depend on the order of cells that enter each set is realized, and the degree of coupling between cells between each set is small. It is possible to group cells with a characteristic that the degree of coupling is large.

[Brief description of drawings]

FIG. 1 is an algorithm diagram of a cell grouping method in Embodiment 1 of the present invention, FIG. 2 is a conceptual diagram of the grouping method of the embodiment, FIG. 3 is an algorithm diagram of a conventional grouping method, and FIG. FIG. 5 is a conceptual diagram showing the calculation of the number of cuts in the conventional cell placement method, and FIG. 5 is an algorithm diagram of the conventional cell placement method. 11 ... Cluster division determination step, 12 ... Number determination step, 13 ... Seed selection step, 14 ... Cell separation step, 15 ... Cut number minimization step, 41 ... I / O pad, 42 ... Left side External terminal of cluster, 43 ... right external terminal of cluster, 44 ... cut line, 45 ... target cluster, 46 ... left cluster, 47 ... right cluster,
48 ... cells on the left side of the cluster, 49 ... external terminals on the left side of the cluster, 410 ... cells on the right side of the cluster, 411 ... external terminals on the right side of the cluster, 412 ... groups of external terminals.

Claims (1)

(57) [Claims] 1. A semiconductor integrated circuit of a polycell system, which is configured by arranging a plurality of polycells having a logical function to form a cell row, arranging a plurality of cell rows and providing wiring between the rows, the semiconductor integrated circuit comprising: And a number determining step of determining the number of the cells that divide the cells included in each of the two sets A and B into each of the two sets A and B, and a reference for calculating a coupling degree for determining the cells that enter the set A and the set B. A seed selection step of selecting a seed from an external terminal to which the semiconductor integrated circuit is connected to an external circuit and cells not included in the set A and the set B, and the set A and the set depending on the degree of coupling with the seed. A cell separation step of determining the cells that enter the set B, the set A and the set B
And a cut number minimizing step of minimizing the number of cuts of wirings crossing the cut line set between the set A and the set B by exchanging cells between the set A and the set B.