JPH03211859A - Device for deciding layout position - Google Patents

Abstract

PURPOSE:To obtain a layout position deciding device which can make excellent aggregation and division by optimizing a flow on a network which represents the logic connecting information between arranged elements. CONSTITUTION:When a logic connecting network storing section 1 stores a logic connecting network which represents logic connecting information, a minimum cost flow calculating section 2 sets the capacity of a virtual arc to be connected to a source on the logic connecting network to '1' and calculates the minimum cost flow on the network. An aggregating and dividing section 3 discriminates whether or not an element aggregate can be divided into two parts by an arc aggregate, the flow quantity of which is not zero, and terminates the calculation when the element aggregate can be divided into two parts. When the aggregate cannot be divided, the section 3 adds '1' to the capacity of the virtual arc. Therefore, the element aggregate can be divided into tow parts on the basis of the (optimum) minimum cost flow and the quality of the solution can be improved.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a placement position determining device, and particularly to a placement position determining device for an LSI.

[Conventional technology]

Conventionally, the mini-cut method, which is one of the impact methods for determining the placement of LSI, deals with the process of dividing the entire element set into two sets under the following conditions.

■The difference in the number of elements in each set shall be less than or equal to the preliminarily specified tolerance value.

■Minimize the number of wires spanning the set.

In the conventional method, the initial solution is first roughly divided into two sets, and then the initial solution is improved by local transformation.

Such conventional methods are described in detail in the proceedings of ``Edahiro, Yoshimura: Routing Algorithm for Standard Cells Using Hierarchical Clustering J'' 19B9 IEICE Autumn National Conference, A-94.

[Problem to be solved by the invention]

As described above, in the method of improving the initial solution, the quality of the solution largely depends on the quality of the initial division, and there are cases where a good solution cannot be obtained.

An object of the present invention is to provide a placement position determination device that performs good set division by optimizing flows on a network expressing logical connection information between placed elements.

[Means to solve the problem]

The placement position determination device of the present invention includes: a logical connection network storage unit that stores a logical connection network representing logical connection information between placement elements given as input; and a minimum cost flow calculation unit that calculates a minimum cost flow on the network. and a set dividing unit that divides the element set into two sets based on the state of the flow on the network.

[Operation] Element set division according to the present invention will be explained based on FIGS. 3 to 5. In addition, FIG. 3 is an explanatory diagram of logical connection and element set division, and FIG. 4 is an explanatory diagram of logical connection network and work.
FIG. 5 is an explanatory diagram showing the relationship between the flow amount and cost of each arc in the logical connection network.

When the storage unit is given logical connection information between arranged elements as shown in FIG. 3(a), that is, logical connection information of all element sets, it stores a logical connection network representing the logical connection information. In FIG. 3(a), the opening represents logical connection information of the external input/output terminal 21, O represents the logical connection information of the arranged element 22, and - represents the logical connection information of the wiring 23 between the elements. Figure 4 shows the stored logical connection network, where ■ indicates the source 31 of the flow, and ■ indicates the sink 3 of the flow.
2, mouth is virtual node 34, - is virtual arc 33.3
5a, 35b.

35c, 36a, 36b, and 36c, ◯ indicates a node 37 corresponding to an element to be placed or an external input/output terminal, and ◯ indicates an arc 38 corresponding to a wiring.

The minimum cost flow calculation unit calculates virtual arcs 35a, 35b, 35c, 36a, 3 in the logical connection network.
The minimum cost flow from the source 31 to the sink 32 is set as
Calculated based on the relationship between arc flow amount and cost shown in the figure.

The element set is determined by using the set of arcs for which the flow amount determined by the minimum cost flow calculation unit is non-zero, as shown in Fig. 3 (
Divide the element set into two as shown in b). Figure 3 (
In b), the element set 24 divided by the cut line 25
a, 24b are shown.

[Example] Next, the present invention will be explained in detail. FIG. 1 is a block diagram showing an embodiment of the placement position determination device of the present invention.

The logical connection network storage unit 1 stores logical connection networks representing logical connection information.

The minimum cost flow calculation unit 2 calculates the minimum cost flow on the logical connection network.

The set dividing unit 3 divides the element set into two based on the minimum cost flow on the logical connection network.

Next, the operation of this embodiment will be explained with reference to the flowchart of FIG.

When the logical connection network storage unit 1 stores a logical connection network representing logical connection information (step S1),
The minimum cost flow calculation unit 2 sets the capacity of the virtual arc connected to the source on the logical connection network to 1 (step S2), and calculates the minimum cost flow on the logical connection network (step S3).

The set dividing unit 3 judges whether the element set can be divided into two by a set of arcs with non-zero flow amount (step S4), and if the division is possible, the process ends; if the division is not possible, the virtual set in step S2 is used. Add 1 to the arc capacity and return to step S3 (step S5).

〔Effect of the invention〕

As described above, according to the present invention, the element set is divided based on the (optimal) minimum cost flow, so that the quality of the solution can be improved compared to the conventional method.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing an embodiment of the arrangement position calculation device of the present invention, Fig. 2 is a flowchart for explaining the operation of the embodiment of Fig. 1, and Fig. 3 is a diagram showing logical connections and element set division. FIG. 4 is an explanatory diagram of the logical connection network, and FIG. 5 is an explanatory diagram showing the relationship between the flow amount and cost of each arc of the logical connection network. 1...Logical connection network storage unit 2...
Minimum cost flow calculation unit 3...set division unit 21...external input/output terminal 22...placed elements 23...wiring 24a, 24b...divided element set 25...
・Cut line 31... Source 32... Sink 33, 35.36... ・Virtual arc 37...
Node 38・・・・・・Arc

Claims (1)

[Claims] (1) a logical connection network storage unit that stores a logical connection network representing logical connection information between arranged elements given as input; a minimum cost flow calculation unit that calculates a minimum cost flow on the network; 1. A placement position determination device comprising: a set dividing section that divides an element set into two sets based on a flow state.