JPH067387B2 - Automatic layout method - Google Patents

Description

Description: FIELD OF THE INVENTION The present invention relates to an automatic layout system for electronic circuits,
In particular, it relates to an automatic layout method for a large-scale circuit described hierarchically.

[Background of the Invention]

In a conventional digital electronic circuit automatic layout system or the like, arranged objects whose shapes are determined in advance are arranged so that the wiring distance between them is short, and automatic wiring is performed between them. When there are many placements,
With a very large number of possible alternatives for their placement, it is difficult to get a good plan even with a computer.

Regarding this type of conventional technology, for example, JIRI SOUKU
P, “Circuit Layout", Proceedings of the IE ³ , Vol.69,
NO.10, October 1981. and so on.

[Object of the Invention]

It is an object of the present invention to provide an automatic layout method which realizes one method for solving a layout problem in which there are large-scale and complicated constraints among layout objects.

[Outline of Invention]

In the layout method of the present invention, a layout pattern having a variable structure in which the arrangement and wiring conditions of objects are stored is prepared in advance, and the circuit to be laid out is embedded in this pattern to have a hierarchical structure. Create a layout plan for circuits, etc.

Since it uses a pattern, compared to other cases,
It is possible to prevent the generation and evaluation of alternatives that are unacceptable as a layout plan, and to efficiently create a circuit layout having large-scale and complicated conditions.

Example of Invention

An embodiment of the present invention will be described below with reference to FIG.

FIG. 1 is a conceptual drawing of a layout target. Reference numeral 100 represents an arrangement target (block) whose name is do and whose predicted area value is 750. In this block do, three sub-blocks do1 (110) and do2 are included.
(120) and do3 (130) exist. There is a connection between sub-blocks, there is a 5 unit connection between do1 and do2 (132), and a 3 unit connection between do2 and do3.

Each of the blocks do1 (140) and the like has a hierarchical structure and has, for example, an expected area of 450, and the blocks do11 (1)
42) and the like, and there is a connection between blocks.

Block do11 (150) has an expected area of 150,
It is composed of blocks do111, do112, and do113.

The block do111 (160) is composed of blocks b15 (162) and b16 (164) as elements, and the block b15 (170) is a basic circuit having a definite size of 4 × 6 as shown. In this embodiment, the first
A method of laying out the hierarchically described circuit shown in the figure will be described. In order to simplify the explanation, in this embodiment, only the arrangement function is taken up and the wiring function is omitted.

FIG. 2 (a) is a diagram showing a hardware environment when implementing the present invention. The input of the connection data is performed by the keyboard 12, the light pen 13, the tablet 14, or the like. The knowledge base, database, etc. are realized by the memory device 16, the magnetic disk file 15, and the like. The layout result and the intermediate result are realized by the display 17, the drawing machine 18, the printer 19 and the like which are output devices.

FIG. 2 (b) is a software functional configuration diagram of the present invention. The computer system 200 includes a hierarchical data file 210 and a hierarchical layout program 2 shown in FIG.
20, the pattern library 230, and the output data file of the layout result are connected.

FIG. 3 is a flowchart showing the flow of layout processing.

First, the layout target block name (usually do in FIG.
And the layout target shape of the target block in the absolute coordinate system (30
0).

Next, the area expected value of the block, the sub-block name, and other information are checked (304).

Next, the initial layout of the block is stored (30
2) The initial plan for selecting a good layout plan in the subsequent processing.

Next, select one pattern library (30
6).

Next, one subblock allocation method is assumed for the selected pattern, and the estimated shape of the block in this case is calculated (308).

Next, assume the rotation angle of the selected pattern (310).

Next, the estimated shape of the block after pattern rotation in the absolute coordinate system is calculated (312).

Next, a trial chain error is made until the estimated shape of the block matches the target shape, and the result is stored (314).

Next, as shown in 316, the entire sub-blocks of the block are laid out (this part is performed recursively. In other words, the layout is performed by repeatedly using the processing functions of the entire FIG. 3).

Next, the shape of this block is calculated from the layout result shape of each sub-block (318).

Next, as shown at 320, the target shape of this block is compared with the actual shape described above, and the layout of this block is erroneously created by trial chain until the actual shape satisfies the target shape.

The program list (I) describes the system of FIG. 1 and has the contents of FIG. 2 210. In this embodiment, the prolog language, which is a well-known artificial intelligence language, is used for explanation.

In 400, the block do is sub-blocks do1 and do.
2, do3, which indicates that the expected area value of do is 750.

In 410, do1 is sub-blocks do11, do12,
It is composed of do13 and shows that the predicted area value is 450.

420 and 430 are similar data for do11 and do111.

440 is the data of the lowest block b15, which indicates that the area is 24 and the actual shape is 4 × 6.

Similarly, reference numerals 450 and 460 indicate the shapes of b16 and b17.

The program list (2) is connection data between blocks of the circuit shown in FIG. 500 is blocks do21 and do2
It shows that there are 3 connections between 3 and 510
Indicates that there are three connections between do22 and do23.

The program list (3) is the hierarchical layout program of FIG. 220. Reference numeral 600 denotes the head of the program called layout (the symbol: -the left side is called the head, and the right side is called the main body). The name of this program is layout, the first variable BLOCK is the layout target block, the second variable FLOO is the name of the pattern when laying out the block specified by BLOCK, and the third variable ROTATION is the layout angle of the pattern. , The fourth variable [GX, GY] is the layout shape target value of the block to be laid out, and the fifth variable [RX, R]
Y] represents the actual shape.

Reference numeral 610 corresponds to FIG.
Initially memorize a bad layout plan in which the gap between the layout shape and the target is extremely large.

620 corresponds to FIG. 3 304, and the variable BLOC from FIG. 4 is used.
Extract the sub-block of the block designated by K and the expected area value. Reference numeral 630 corresponds to 306 to 320 in FIG. 3, and layout is performed using a pattern.
Real shape [RX, R that satisfies the target shape [GX, GY]
Y] is created.

640 outputs and displays the obtained layout (see FIG. 24).
0)).

Reference numeral 650 shows a specific example of FIG. 300, and instructs to lay out the block do under the target shape [25, 30].

306 to 320 in FIG. 3 are processes for assigning circuits to library patterns. Before explaining this, the layout pattern will be described with reference to FIG.

Reference numeral 700 is a layout pattern of a block having no sub-block, as in b15 of step 440 of the program list (1), which is a rectangular shape of horizontal X and vertical Y. Here, X and Y are unknowns.

Reference numeral 710 is a pattern for laying out a block composed of three sub-blocks, B1, B2 and B3 are variables for storing the names of the blocks allocated to each part,
X11 to Y31 are variables representing the shape.

720 is a pattern for laying out a block having two sub blocks, and 730 is a pattern different from 710 for laying out a block having three sub blocks.

In the layout, an appropriate one is selected from these patterns and the circuit to be laid out is embedded in this pattern. For example, in the pattern 710, the shape variable X1 is used.
For Y1, Y11, etc., a target value is set in consideration of the expected area value of each sub-block, etc., and each sub-block is laid out based on this target value (recursive processing).

FIG. 5 shows the rotation angle of the pattern with respect to the absolute space. 800 is the layout of the pattern of FIG. 710 at an angle of 0, and 850 is the layout at an angle of 90 °. The angle itself is also subject to layout planning.

The program lists (4) to (7) are examples of the contents of FIG. 230 and create layouts for the patterns of 700 to 730 of FIG.

Step 900 of the program list (4) is the head of the program, pattern name floor0, variable BLOCK indicating the layout target block, variable R indicating the pattern rotation angle.
OTATION, sub-block is empty ([]), target shape [GX, GY] in the absolute coordinate system, same layout real shape [RX, RY], pattern real shape [RX1
1, RY11] and so on.

At 910, the rotation angle is first obtained, and at 920, the pattern actual shapes RX11, RY11 are corrected according to the rotation angle to obtain the layout actual shapes RX, RY in the absolute coordinate system.

At 930, the target shapes GX and GY and the actual shapes RX and RY are compared with each other, and the difference between them is put into SHAPEGAPVALUE.

At 940, the gap SGV between the target shape and the actual shape of the layout plan created and stored in the past is checked for the block.

In 950, it is compared with the plan currently being created, and if it is improved, the past memory is erased (960) and the trial result of this time is newly stored.

At 980, the target shapes GX and GY are compared with the actual shapes RX and RY to determine whether the result is good or not.

The processing of 910 to 980 corresponds to the portions of 306 to 320 in FIG. 3, but this pattern is the third because the structure is simple.
Since some of the processes in the figure are unnecessary, some may not exist in the program list (4).

The program list (5) corresponds to the pattern of FIG.

1000 is the head of the program, and the program is selected in FIG. 306 in FIG. 3 by matching with 630 of the program list (3).

1010 and 1020 correspond to FIG.

1030 asks if the target shape variables are all positive.

1040 is the calculation of the approximate value of the total wiring length between blocks associated with the sub-block allocation to the pattern in 1010, 1050 is the assumption of the rotation angle corresponding to 310 in FIG. 3, and 1052 is 312 in FIG.
It corresponds to 1054, 1056 and 314.

Reference numerals 1058 to 1062 denote layout processing of sub-blocks B1, B2, B3, and recursive processing corresponding to FIG.
Calling out the program in program list (4).

1064 corresponds to 318 in FIG.

The program list (6) corresponds to the pattern shown in FIG. 720, and 1100 to 1166 are similar to the description contents of the list (5), so the description thereof will be omitted.

The program list (7) corresponds to FIG. 4 730, and 1200 to 1266 are also similar to FIG.

The program list (8) is the substance of the functions used in the programs up to the program list (7), 1300 can be 0 ° and 90 ° as rotation angles, and 1310 is
Description of the law that the vector (X, Y) is changed by the rotation angle, 1320 is the maximum value calculation, 1330 is the calculation of the gap value between the target shape and the actual shape, and 1340 is the determination of the closeness between the target shape and the actual shape. , 1350, 1360 is a list of the number of wires between blocks (2)
Read out from the data of 1370, 1380 is the storage and deletion of the layout result, 1390 is the value of MAX used in 1340 is 500
Is shown.

When the circuit of FIG. 1 is expressed as program lists (1) and (2) and the program of list (3) is executed by giving 650 instructions, patterns of lists (4) to (8) The library is repeatedly used, and as a result, it is shown in FIG.
Within 0, the layout plan can be obtained.

FIG. 6 illustrates the layout plan obtained. The whole corresponds to do, and do1 is 1500 part, do2
Is arranged in 1510 parts, do12 is arranged in 1520, b1 is arranged in 1530 and the like.

Note that 1540 indicates that there are two wirings between b41 and b42.

Although one embodiment of the case where the arithmetic processing is performed by a large-scale computer or the like has been described above, modifications such as the case where the processing of the present invention is divided into blocks and each of which is performed by a plurality of microprocessors or a case where a dedicated computer is used are possible.

〔The invention's effect〕

As described above, according to the present invention, it is possible to efficiently solve a layout problem in which a large number of arrangement objects have complicated constraints.

[Brief description of drawings]

FIG. 1 is a conceptual diagram for explaining a hierarchical structure of an electronic circuit as an object of the present invention, FIG. 2 (a) is a block diagram showing a hardware environment of an embodiment of the present invention, and FIG. 2 (b). Is a software functional configuration diagram of the present invention system, FIG. 3 is a process flow diagram of the present invention system, FIGS. 4 and 5 are conceptual diagrams of layout patterns in the present invention, and FIG. 6 is a layout obtained by the present invention. It is explanatory drawing of a result.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Noboru Horie 111 No. Nishiyokote-cho, Takasaki City, Gunma Prefecture Takasaki Plant, Hitachi, Ltd. (56) References JP 55-87457 (JP, A) Kenji Kani "Printed Circuit Board CAD and its Examples" (Published February 27, 1981) Applied Technology Publishing P.A. 84 ~ 89

Claims (1)

[Claims] 1. A computer having an input device and a storage device, wherein data indicating a target shape of a block to be laid out in an electronic circuit is input from the input device, and a layout pattern of a block composed of a layout pattern group and a wiring pattern group is generated. Storing a plurality of them in the storage device, selecting the layout pattern, assigning the target shape to the selected layout pattern, and repeating the assignment of the layout pattern until the actual shape of the block satisfies the target shape. Automatic layout method characterized by.