A Statistical Physical Placement Theory for LSI Circuits and a Technique for Estimating Wiring Accommodation

Mean Wire Length and Wire Length Distribution

Fig.1 Mean Wire Length and Wire Length Distribution

Gate array schematic

Fig.1 Gate array schematic

Gate array channel model

Fig.2 Gate array channel model

Logic circuit wiring model (LSI model)

Fig.3 Logic circuit wiring model (LSI model)

Comparison of theoretical and measured wire length distributions

Fig.4 Comparison of theoretical and measured wire length distributions

Relation of temperature and mean wire length (high temperature)

Fig.5 Relation of temperature and mean wire length (high temperature)

Relation of temperature and mean wire length (low temperature)

Fig.6 Relation of temperature and mean wire length (low temperature)

Formula for statistically optimal placement

Fig.7 Formula for statistically optimal placement

Proper placement and estimation of wiring accommodation for effective use of the limited space on an LSI chip are very important to the manufacture of the chips used in supercomputers and other such machines. The work reported here concerns the layout design of an LSI chip that is fabricated as a gate array (Fig. 1). If the area devoted to wiring is large, the chip area is large; if the area devoted to wiring is small, then layout design is difficult and there is no room for required wiring. To solve that problem, we formulated a world’s-first statistical physical theory for LSI chips, developed a method for estimating LSI wiring length based on that theory, and showed the validity and practicality of that method.

A gate array LSI and a cell placement LSI that have the same functions are modeled as a v1 by v2 cell array (Fig. 2), we represent it as a v by v square lattice graph (v=v1=v2, where v>=1)) for simplicity in theoretical description. All that is required is the correspondence between the nodes in the graph, the cells (logic circuits, etc.), and information on the wiring between cells, so the layout is represented as a undirected graph.

The models can be divided into three types: (1) those represented by a connected graph with only one edge between nodes (Fig. 3), (2) MCP models, which allow parallel edges , and (3) models in which all edges are distinguished. In this paper, we explain a theory only for case (1). The number of nodes in the graph that represents the logic circuits to be implemented is basically the same as the size of the array (v × v = v2 = V). That is, the theory is constructed with the assumption that all of the cells are used. The gaps between theory and actual practice such as wiring NET problems and cell use rate are filled by appropriate techniques.

The placement problem for when this kind of modeling is used is the problem of assigning graph nodes to lattice points on the substrate. Evaluation of that placement is based on the total wiring length, which is measured as the sum of the Manhattan distances of all the edges between the nodes. The shorter that total distance, the higher the evaluation of the placement. The problem of obtaining the placement that minimizes the value of the overall placement evaluation function is referred to as an ‘NP complete’ or ‘NP hard’ problem. Algorithms for solving such problems for functions that have many terms are not currently available.

While that makes it difficult to overcome the problem of placement itself, the problem of estimating capacity for accommodating wiring does not require that we obtain a single optimum placement; it is just a matter of finding a method for appropriate estimation. The need for this estimate is at the stage of LSI substrate design, before details of the logic circuits have been decided. Also, considering that the logic circuits number in the several hundred and that many processes proceed in parallel, this matter must be settled. After analyzing these problems and circumstances, we reached the conclusion that a practical solution requires the establishment of an essential placement theory and a method of description with a small number of parameters is indispensable.

An approach that is useful for such difficult problems is statistical physical methodology. We used that approach to construct a clear placement theory, develop a wiring length prediction method based on that theory, and verified the validity of the theory and the practicality of the prediction method.

In this theory, the edges (wires) of a connected graph that represents a circuit are modeled as statistical physics ‘particles’, the length of the wire when the edge is placed on substrate is modeled as ‘particle energy’ and the irregularity of the placement (complexity) is modeled as ‘temperature’. This leads to the applicable statistics being “Fermi-Dirac statistics” for the LSI model (connected graph with at most one edge), “Bose-Einstein statistics” for the MCP model (connected graph with parallel edges permitted), and “Boltzmann statistics” for the approximate distribution theory.

However, the constant for the Boltzmann coefficients is 1. In approximation theory, the mean wire length, R, and the wire length distribution are determined solely by the temperature, T, as defined in Eq. 1 (last in the group of figures and tables). We can see that a temperature of absolute zero corresponds to placement in which the lengths of all wires are 1. Figure 4 compares the approximation theory distribution and the distribution of measured wire lengths in an actual LSI. The approximate distribution well expresses the actual distribution.

However, when the relation between the temperature and the mean wiring length is plotted in a graph as in Fig. 5 and Fig. 6, we can see that the handling of the placement problem of the actual LSI corresponds to an extremely low temperature. That means the problem must be dealt with by means of Fermi-Dirac statistics or Bose-Einstein statistics. In that case, the placement with the shortest mean wire length is believed to correspond to the limiting case for the temperature, etc. We introduce a relation for which the shape of the distribution conforms to Fermi-Dirac statistics in that case and submit it as a statistical placement optimization formula (Fig. 7).

For most estimates of wiring accommodation capacity, estimation of wire length is fundamental, but this statistical placement optimization formula can be used to obtain the average wire length of the optimum placement in a statistical sense. This method is applied to and solving the problems of wiring accommodation that arise in the design, development and fabrication of the LSI substrates and MCP that are used in actual supercomputers.

Thus, in this document we solved the difficult technical problem of estimating the wiring accommodation capacity of an LSI by taking a new statistical physical approach to placement theory. We also established a practical estimation method on top of that theory. Furthermore, this is expected to extend beyond LSI layout problems and contribute to the development of a broad range of fields relevant to combination problems. The author of this paper, Norio Harada (at Takushoku University), was awarded the IEICE Best Paper Award in 1985 and again in 1988.



Publications

[1] Norio HARADA、LSI Interconnection Length Prediction Method
Using a Statistical Mechanical Placements
Theory、1984、NEC Research & Development,No.72,pp56-63

Related Researches

Category

Information Processing
(Others(Information Processing))

Events in World

1985
World science exposition opened in Tsukuba City.
1985
Nippon Telegraph and Telephone Public Corporation was privatized and NTT was inaugurated.
Page Top