JPH0642254B2 - Equal size block layout method - Google Patents

Description

The present invention relates to an improved system for arranging electronic components in an LSI design printed circuit board design.

(Prior Art) Conventionally, the pair conversion method has been often used to improve the layout of ICs and logic gates. In this method, two parts are randomly picked out from n × n two-dimensionally arranged parts, and by exchanging them, it is determined whether the total wiring length is reduced or not by calculating the total Manhattan distance. It was improving while evaluating. This method is one of the so-called hill climbing methods. If the total wiring length is made to correspond to the height of a mountain and all the parts are arranged, the two optional parts can be replaced. It was a method of judging whether or not the height of the mountain would be lowered, and proceeding with the processing while selecting the exchange pair so as to move toward the lower side.

(Problems to be Solved by the Invention) According to the conventional pair exchange method, only two pairs are considered to be exchanged at the same time. Even if the value of the evaluation function may approach the optimum value when three or more parts are replaced at the same time, only two parts are replaced at the same time. However, there is a drawback that the evaluation function stops at a relatively bad place, and further processing is aborted.

(Means for Solving the Problem) The method of the present invention relaxes the constraint in the pair exchange method that only two parts are exchanged at the same time, so that m (m ≧ m)
3) The value of the evaluation function can be
This is achieved by bringing the value closer to the optimum value and simultaneously executing the calculation of the evaluation function for the combination of m factorials when m parts are simultaneously replaced in parallel and performing the processing at high speed.

(Example) Next, the Example of this invention is described with reference to drawings.

FIG. 1 is an explanatory diagram showing the principle of the present invention.

In FIG. 1, numerals 1 to 64 indicate small areas divided into 8 × 8 grids, and one component is arranged in each small area. In the initial placement, for example, a method called the center of gravity method is used to place each component in accordance with the placement determined using the wiring connection information between each component given in advance. In this embodiment, as an example, the case where 64 rectangular parts are placed at 64 positions is considered, but the same method can be applied even if the number of parts is increased.

In the method of the present invention, as the first step, m parts are randomly selected from 64 initially arranged parts. In Fig. 2, small areas 19,30,50,5 with diagonal lines
The case where 6 is selected (when m = 4) is shown.

Next, as a second step, an evaluation function is obtained for each of the four factorial = 24 types of arrangements, which are all ways of arbitrary arrangement exchange of these four parts. 4 as an evaluation function
The sum of the number of connecting lines having a value called the Manhattan distance between the individual parts and the connected parts is used. The Manhattan distance is the length of a line segment that connects the start point and the end point to be connected at the shortest distance using only the line segments parallel to the X and Y directions. As the third step, if there is a value whose value is smaller than that before performing the exchange out of the obtained 24 evaluation functions, only one of them is selected and the exchange is executed. If none of them have become smaller, the process ends. When the exchange is performed, the above-mentioned placement exchange processing is further repeated based on the state of the placement.

In the above example, the method of obtaining four components at the same time and obtaining the evaluation function for the 24 ways of arrangement has been described. However, by further increasing the number of the components to be extracted at the same time, the evaluation function can be made closer to the optimum value. It is possible. In the case of mass-produced products, it is advantageous to approach the optimum value as much as possible to improve the yield. For example, it is possible to take out 5 parts at the same time and process them in parallel in 120 ways of arrangement, but Since the increase and the degree of improvement are saturated, practically about four parts can obtain good results in terms of cost performance.

Although only the pair exchange method is described in the present embodiment, there is a simulated annealing method as an extension of the pair exchange method, and in this case, even if the evaluation function becomes a little worse, the pair is exchanged within a certain range. . The present invention can be similarly applied to this method.

FIG. 2 is a block diagram showing an example of an apparatus for implementing the equal size block layout method of the present invention. First
The equal size block layout system shown in the figure comprises a host personal computer 101, an interface circuit 102, data driven pipeline processors 103-110, and an image memory 111.

The position information of the parts to be processed and the connection information between the parts are transferred from the personal computer 101 to the interface circuit 102.
And is stored in the image memory 111 via. The eight pipeline processors 103-110 are programmable,
The control code is initialized from the personal computer in advance according to the contents of the process, and the interface circuit 10
2 performs address generation of the image memory 111, read / write control, and data transfer with the processor groups 103 to 110 in a time division manner.

The placement information of the initial placement is six processor groups 104 to 109.
And used in the calculation of the evaluation function. 2 in total
Since there are four ways of arrangement, four ways are evenly assigned to six processors and processed in parallel. The processors 103 and 110 are used for pre-processing and post-processing, respectively, and the processor 103 divides into 24 ways of arrangement, and the address values of the image memory 111 necessary for the six processor groups 104 to 110. And the X and Y coordinate values of the small area that is the target of the layout exchange are transferred.

The processor 111 selects one of the 24 evaluation functions, which has become smaller than the evaluation value before the layout exchange, exchanges the component position, and stores it in the image memory 111. Update the component placement information. It is determined whether or not the evaluation function value is further improved, and if it is not improved, the processing is ended and a processing end interrupt signal is sent to the personal computer 101.

(Effect of the invention) As described above, according to the present invention, the sum of Manhattan distances can be used as the evaluation function based on the connection information and the initial arrangement information of electronic components, and it is possible to obtain a value closer to the optimum value Moreover, there is an effect that processing can be performed at high speed by a system having a parallel processor configuration.

[Brief description of drawings]

FIG. 1 is an explanatory view of the principle of the present invention, and FIG. 2 is a block diagram showing an example of an apparatus for carrying out the present invention. 101 …… Personal computer, 102 …… Interface circuit, 103-110 …… Data-driven pipeline processor, 111 …… Image memory.

Claims (1)

[Claims] 1. An n × n array arranged in a two-dimensional equidistant grid pattern.
Of the same size parts, at least m (m ≧ 3)
Then, for all the combinations of the placement exchanges according to the factorial of m, the evaluation function value is obtained by using the sum of the shortest wiring lengths between the components as an evaluation function, and compared with the evaluation function value before the placement exchange. Only when the evaluation function value after the arrangement exchange becomes small, the operation for performing the arrangement exchange is repeated to bring the evaluation function close to the minimum, and the calculation processing of the evaluation function according to the factorial of m is executed in parallel. A block layout method of equal size, characterized in that the layout of electronic components is improved.