JPH0240774A - Block arrangement processing system - Google Patents

Abstract

PURPOSE:To realize the arrangement of a block for satisfying the request performance for constituting a critical net required for designing an LSI of high speed and high performance, etc. by checking up an allowable interval between specific blocks which are designated in advance in the course of a block arrangement processing. CONSTITUTION:A selecting means 1 selects a nuclear BL from an unarranged block (BL), and arranges it in an arbitrary position on a substrate by an arranging means 2. A selecting means 3 selects the BL whose connecting relation to the already arranged BL is the strongest and whose connecting relation to the unarranged BL is the weakest, as the next arranged BL from in the unarranged BLs. A calculating means 4 derives a position of the center of gravity of the already arranged BL having a connecting relation to its next arranged BL. A moving means 5 sets its position of the center of gravity as an arrangement candidate position of the next arranged BL, a deciding means 6 decides whether the next arranged BL can be arranged in its position or not, and when it is impossible, a new candidate position is derived by a searching means 8 and it is decided. When said arrangement is possible, when an allowable interval of the next arranged BL and other BL is designated by a deciding means 7, a means 9 arranges the BL in the candidate position.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a block placement processing method, and more particularly to a block placement processing method for arranging blocks that are placement units for L31 boards, printed circuit boards, etc.

[Conventional technology]

Conventionally, in this type of block placement processing method, in order to shorten the distance between blocks (block spacing) as much as possible, the next placed block is placed at the center of gravity of the already placed block that has a connection relationship with the already placed block. was (
References [CADJ of Logic Devices, edited by Yuki Ki, Information Processing Society of Japan, published March 20, 1978).

In recent years, high-speed, high-performance SLI, printed circuit boards, etc. have been required, and it has become necessary to limit the line length of critical nets in order to shorten delay time. Therefore, in the block placement process, it has become necessary to reduce the block interval to a certain value or less for blocks on the critical path.

[Problems to be Solved by the Invention] In the conventional block arrangement processing method described above, unplaced blocks are placed at the center of gravity of already placed blocks with connections, so in order to shorten the block intervals on average, it is necessary to (In fact, it is common to use the minimization of the total virtual wire length as the evaluation function for block placement processing.) However, in order to keep the block spacing below a certain value, it is necessary to After completing the placement, check the distance between specific blocks,
The disadvantage is that if the conditions are not met, the placement results must be corrected.

In view of the above-mentioned points, an object of the present invention is to check the allowable spacing between specific blocks specified in advance during the block placement process, thereby providing critical information needed when designing high-speed, high-performance LSLs, printed circuit boards, etc. The object of the present invention is to provide a block placement processing method that can realize the placement of blocks constituting a net in a manner that satisfies required performance.

[Means to solve the problem]

The block placement processing method of the present invention is a block placement processing method that performs placement processing of blocks that are placement units of LSIs, printed circuit boards, etc., and includes a core block selection means for selecting a core block from unplaced blocks, and a core block selection means for selecting a core block from unplaced blocks. The core block placement means places the core block selected by the selection means at an arbitrary position on the board, and the core block that has the strongest connection with the already placed block among the unplaced blocks (and the connection with other unplaced blocks) a next placed block selection means for selecting an unplaced block with the weakest relationship as the next placed block; and a calculation means for determining the center of gravity position of an already placed block that has a connection relationship with the next placed block selected by the next placed block selection means. , a transport means for determining the center of gravity position determined by the calculation means as a candidate position for the next placement block; a placement determination means for checking whether the next placement block can be placed at the placement candidate position on the board; When it is determined by the feasibility determination means that the next placement block can be placed at the placement candidate position, the distance between the placement candidate position of the next placement block and the already placed block is determined for which the allowable spacing between blocks is specified. Specified allowable interval conformance determination means for determining whether or not the interval conforms to the specified allowable interval; and when the specified allowable interval conformity determination means determines that the placement candidate position does not conform to the specified allowable interval; and When the arrangement candidate position is determined to be a position in which the next arrangement block cannot be arranged by the arrangement possibility determining means, the next arrangement candidate for the next arrangement block is searched in a spiral from the center of gravity position determined by the calculation means. It has a search means for finding a position, and a next arrangement block arrangement means for placing the next arrangement block at a possible arrangement candidate position on the substrate.

[Effect]

In the block placement processing method of the present invention, the nuclear pro-7 selection means selects a nuclear block from unplaced blocks, and the nuclear block placement means places the nuclear block selected by the nuclear block selection means at an arbitrary position on the board. The next placed block selection means selects, from among the unplaced blocks, the unplaced block that has the strongest connection relationship with the already placed block and the weakest connection relationship with other unplaced blocks as the next placed block, and performs calculations. The means calculates the center of gravity position of the already placed block that has a connection relationship with the next placed block selected by the next placed block selection means, and the transport means sets the center of gravity position found by the calculation means as the placement candidate position of the next placed block and places it. The possibility determining means checks whether the next placement block can be placed at the placement candidate position on the board, and the specified allowable interval compatibility determining means determines that the next placement block can be placed at the placement candidate position. In the case where the allowable interval between blocks is specified, the interval between the placement candidate position of the next placed bronc and the already placed block is determined, and it is determined whether or not the obtained interval conforms to the specified allowable interval, and the search means When the placement candidate position is determined by the specified allowable interval conformity determination means to not conform to the specified allowable interval, and when the placement possibility determination means determines that the placement candidate position is a position where the next placement block cannot be placed. The next placement candidate position of the next placement block is determined by searching in a spiral pattern from the center of gravity position determined by the calculation means, and the next placement block placement means places the next placement block at a possible placement candidate position on the board. .

〔Example〕

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of a block placement processing method according to an embodiment of the present invention. It is composed of a placement block selection means 3, a calculation means 4, a transfer means 5, a placement possibility judgment means 6, a designated allowable interval compatibility judgment means 7, a search means 8, and a next placement block placement means 9. .

The core block selection means 1 selects a core block (core block) from unplaced blocks.

The nuclear block placement means 2 places the nuclear block selected by the nuclear block selection means 1 at an arbitrary position on the substrate.

The next placed block selection means 3 selects the next unplaced block from among the unplaced blocks that has the strongest connection relationship with the already placed blocks already placed on the board and the weakest connection relationship with other unplaced blocks. Select as placement block. Furthermore, if there is no unplaced block that satisfies the above conditions, the next placed block selection means 3 ends the block placement process.

The calculation means 4 determines the center of gravity of the already placed block that has a connection relationship with the next placed block.

The transport means 5 uses the center of gravity position determined by the calculation means 4 as the placement candidate position of the next placement block.

The placement possibility determining means 6 checks whether the next placement block can be placed at the placement candidate position on the board.

The designated allowable interval conformity determination means 7 calculates the interval between the next placed block and the already placed block when a specific allowable interval between blocks is specified for the next placed block, and places the next placed block at the placement candidate position on the board. Checks whether the specified spacing between blocks is met.

The search means 8 calculates a spiral shape from the center of gravity position determined by the calculation means 4 when it is determined by the placement possibility determination means 6 and the designated allowable interval compatibility determination means 7 that it is impossible to place the next placement block in the placement candidate value Wl. search to find the next placement candidate position of the next placement block.

The next placement block placement means 9 places the next placement block at the placement candidate position on the board.

Referring to FIG. 2, the processing in the block placement processing method of this embodiment includes a core block selection step 11, a core block placement step 12, an unplaced block presence/absence determination step 13, a next placement block selection step 14, Centroid position calculation step 15, barycenter position placement candidate position setting step 16, placement candidate position next placement block placement determination step 17, and allowable interval designation determination step 1
8, a block interval calculation step 19, a specified allowable interval compatibility determination step 20, and a spiral search step 21
and a next placement block placement step 22.

Next, the operation of the block arrangement processing method of this embodiment configured as described above will be explained.

The core block selection means 1 selects a core block (core block) from unplaced blocks (step 11).

Next, the core block placement means 2 selects the core block selection means 1.
The nuclear block selected by is placed at an arbitrary position on the substrate (step 12).

Subsequently, the next placed block selection means 3 selects a block from among the unplaced blocks that has the strongest connection relationship with an already placed block already placed on the board (and has the weakest connection relationship with other unplaced blocks). It is determined whether or not there is a placed block (step 13), and if it is determined that there is a corresponding unplaced block, the corresponding unplaced block is selected as the next placed block (step 14). Furthermore, if there is no unplaced block that satisfies the above conditions, the next placed block selection means 3 ends the pronk placement process.

When the next placed block is selected by the next placed block selection means 3, the calculation means 4 calculates the center of gravity of the already placed block that has a connection relationship with the next placed block selected by the next placed block selection means 3 (step 15).

Once the center of gravity position of the already placed block has been determined by the calculation means 4, the transport means 5 sets the center of gravity position determined by the calculation means 4 as the placement candidate position of the next placed block (step 16).

Once the candidate position for the next placement block has been determined by the transfer means 5, the placement possibility determining means 6 checks whether the next placement block can be placed at the candidate placement position on the board (step 17).

If the placement possibility determining means 6 determines that it is impossible to place the next placement block at the placement candidate position on the board, the search means 8 moves the position on the board that has been set as the placement candidate position by the transfer means 5 in step I6. A new placement candidate position is found by searching in a spiral pattern (step 21), and control is returned to the placement possibility determining means 6.

If the placement possibility determining means 6 determines in step 17 that the next placement block can be placed at the placement candidate position on the board, the specified allowable interval compatibility determining means 7 determines whether the next placement block is compatible with a specific block. It is determined whether an allowable interval is specified between the two (step 18). When a permissible interval between the next placed block and other blocks is specified, the specified permissible interval conformity determining means 7 determines whether the next placed block has a specified permissible interval between it and the already placed block. A distance M (block interval) between the candidate position and the candidate position is determined (step 19), and it is determined whether the determined block interval is within a specified allowable interval (step 20). If it is determined that the interval is not within the allowable interval, the designated allowable interval conformity determining means 7 passes control to the searching means 8.

The searching means 8, which has been given control by the specified allowable interval conformity determining means 7, performs the process of step 21 in the same manner as described above.

If it is determined in step 18 that the allowable interval is not specified for the next placement block, and if it is determined in step 20 that the allowable interval is within the allowable interval, the specified allowable interval conformity determining means 7
transfers control to the next placement block placement means 9.

The next placement block arrangement means 9, which has been given control by the specified allowable interval conformity determination means 7, places the next placement block at the placement candidate position on the board (step 22), and returns control to the next placement block selection means 3.

Next, using FIG. 3, a description will be given of the placement process when block D is selected as the next placement block in the process of step 14.

Here, it is assumed that the next placed block D has a logical connection relationship with the placed block A, the placed block B, and the placed block C, but has no logical connection relationship with the placed block X.

Further, it is assumed that an allowable interval α is specified in advance for the interval between the next placed block D and the already placed block C.

When the next placed block D is selected by the next placed block selection means 3, the calculation means 4 selects the already placed block A,
Center of gravity position G of placed block B and placed block C
is calculated (step 15), and the calculated center of gravity value ffG
is set as the first placement candidate position by the transport means 5 (step 16).

Next, the placement possibility determining means 6 determines the first placement candidate position (
Since it is determined that the next placement block D can be placed at the center of gravity position G) (step 17), the specified allowable interval conformity determining means 7 determines whether or not the next placement block D has an allowable spacing specification (step 17). 18). Since the next placed block D has a specified allowable interval α between it and the already placed block C, the specified allowable interval compatibility determining means 7 determines the distance between the already placed block C and the first placement candidate position (centroid value ? 1fG). The distance on the board is determined (step 19), and it is determined whether the determined distance is within the allowable distance α (step 20)
, Here, if the first placement candidate position (gravity center position G) is separated from the position of the already placed block C by more than the allowable distance α, it is determined that the calculated distance is not within the allowable distance α, and the first placement candidate position ( Since the next placement block D cannot be placed at the center of gravity value fiG), control is passed to the search means 8.

The search means 8 to which the control has been handed searches in a spiral pattern from the center of gravity iG to find the second placement candidate position (here, the position of the already placed block X) (step 21), and determines whether or not the control can be placed. It is passed to the determination means 6.

The placement possibility determining means 6 to which control has been passed determines that placement of the next placement block D is impossible because the second placement candidate position is the position of the already placed block X (step 17).
), the control is again transferred to the search means 8, and the search means 8 performs a spiral search from the center of gravity value 1ifG to the already placed block
Continuing from the position , for example, a position Z on the substrate is determined as the third placement candidate position (step 21).

Next, the placement possibility determination means 6 determines the third placement candidate position I.
Suppose that it is determined that the next placement block D can be placed at z (step 17), the position of the block C for which the allowable interval α is specified between the next placement block D by the specified allowable interval conformance determining means 7 and 3. It is determined whether the interval with the th placement candidate position WZ is within the allowable interval α (steps 18 to 20).

Here, if the arrangement possibility determining means 6 determines that the interval is within the allowable interval α, then the next arrangement block arrangement means 9
Accordingly, the next placement block D is placed at the third placement candidate position WZ (step 22).

Note that various cases can be considered for specifying the above-mentioned allowable range. For example, the interval between blocks must be equal to or greater than α, or equal to or greater than α and equal to or less than β.

It is clear that the block arrangement processing method of this embodiment can be applied to any of these cases.

Further, the block arrangement processing method of the present invention can be realized by creating a program and operating it on a computer, or by implementing it in hardware and operating it.

〔Effect of the invention〕

As explained above, the present invention enables critical nets required when designing high-speed, high-performance ■, SI, printed circuit boards, etc., by checking the allowable interval between specific blocks specified in advance during the block placement process. This has the effect that the arrangement of the constituent blocks can be realized in a manner that satisfies the required performance.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing the configuration of a block arrangement processing method according to an embodiment of the present invention, Fig. 2 is a flowchart showing the processing in the block arrangement processing method of this embodiment, and Fig. 3 is a block arrangement of the next arrangement block. FIG. 3 is a diagram for explaining processing operations. In the figure, 1... Nuclear block selection means, 2... Nuclear block placement means, 3... Next placement block selection means, 4... Calculation means, 5... Transfer means, 6... Placement. Possibility determining means; 7. Specified allowable interval conformity determining means; 8. Searching means; 9. Next arrangement block arranging means.

Claims (1)

[Scope of Claims] A block placement processing method for arranging blocks serving as units of arrangement of LSIs, printed circuit boards, etc., comprising: a core block selection means for selecting a core block from unplaced blocks; and a core block selection means for selecting a core block from unplaced blocks. A nuclear block placement means that places the placed nuclear block at an arbitrary position on the board, and a nuclear block placement means that places the placed nuclear block at an arbitrary position on the board, and a nuclear block placement means that places the placed nuclear block at an arbitrary position on the board, and selects a nuclear block from among the unplaced blocks that has the strongest connection relationship with the already placed block and the weakest connection relationship with other unplaced blocks. a next placement block selection means for selecting a placement block as the next placement block; a calculation means for determining the center of gravity of an already placed block having a connection relationship with the next placement block selected by the next placement block selection means; a transfer means that sets the obtained center of gravity position as a candidate position for the next placement block; a placement determination device that checks whether the next placement block can be placed at the placement candidate position on the board; The allowable spacing between blocks is specified when it is determined that the next placement block can be placed at the candidate position.The spacing determined by calculating the spacing between the placement candidate position of the next placement block and the already placed block is specified. Specified allowable interval conformance determination means for determining whether or not the specified allowable interval conforms to the specified allowable interval, and when it is determined by the designated allowable interval conformance determination means that the placement candidate position does not conform to the specified allowable interval, and the placement propriety determination. When the placement candidate position is determined by the means to be a position where placement of the next placement block is impossible, searching in a spiral pattern from the center of gravity position determined by the calculation means to find the next placement candidate position of the next placement block. and next placement block placement means for placing the next placement block at a placement candidate position on a substrate.