JPH01209574A - Layout improving system - Google Patents

Abstract

PURPOSE:To reduce a calculation value by selecting parts which have no connecting relation with each other when parts groups which are exchanged at one time are selected. CONSTITUTION:A exchange candidate production circuit 15 selects the parts groups which are not connected to each other via a wiring net as the parts which are exchanged at one time. An evaluation function calculating circuit 17 calculates the evaluation values of the parts independently of each other and for each new locating place when a relocating method is evaluated and adds these calculated evaluation values together to obtain the total evaluation value. Thus it is possible to calculate the change of the evaluation value at the time of movement of each parts and independently of the moving ways of other parts. In such a way, the calculation value can be reduced.

Description

DETAILED DESCRIPTION OF THE INVENTION (Industrial Application Field) The present invention relates to a design support device, and in particular to a placement improvement method for determining the placement of ICs and transistors inside a printed board or LSI on which an electric circuit is mounted. Regarding.

(Prior Art) - Conventionally, as a method for improving a given arrangement, there is, for example, a bare exchange method. In this method, from among all parts,
This process is repeated by taking two random parts, considering their replacement, and accepting the replacement if the evaluation value based on the virtual wiring length (for example, Manhattan length) improves, and not replacing it if it does not improve. .

This method only replaces two parts at a time, so
Even though the arrangement at a certain point in time is not the optimal arrangement, it is easy to fall into a locally optimal solution, where a better arrangement cannot be found no matter which two parts are replaced.

In order to avoid falling into this local optimum solution, consider replacing four parts at the same time, for example, and replace method 4! The method used was to evaluate all 24 options and select the best replacement method. Since the replacement of four parts includes the replacement of two parts, a better solution can always be expected than the pair replacement method.

(Problem to be Solved by the Invention) Although it is possible to obtain a better solution using such a method, falling into a locally optimal solution is inevitable, and in order to further prevent falling into a locally optimal solution, An effective method is to consider replacing more parts at the same time, evaluate all of the replacement methods, and select the best replacement method.

However, if you increase the number of parts to be replaced at the same time, the amount of calculation required for the evaluation will be n! , and it is practically difficult to increase the number n of parts to be replaced at the same time.

(Means for Solving the Problems) Means provided by the present invention to solve the above-mentioned problems are as follows:
By replacing multiple parts at the same time, evaluating all replacement methods, and using the total virtual wiring length for all wiring to evaluate the placement, it is possible to evaluate the placement status of multiple parts that have already been placed. A placement improvement method that sequentially improves and better arranges a group of parts that are interconnected by a wiring net within a predetermined area, and selects a group of parts that are not connected to each other by a wiring net as parts to be replaced at the same time. and means for calculating the evaluation value for each new placement location of each part independently and adding them together to obtain the overall evaluation value when evaluating the replacement method. do.

(Effect) When selecting a group of parts to be replaced at the same time, if you select parts that have a connection relationship with each other, the change in evaluation value when one part is moved to another location will be due to the connection relationship with that part. It depends on where you place the parts.

Therefore, when considering the replacement of n parts, how to replace them is n! For each street, an evaluation value must be calculated after replacing the parts.

However, by choosing parts that are not connected to each other,
Changes in evaluation values when each part is moved can be calculated independently of how other parts are moved.

Therefore, when considering the replacement of n parts, it is only necessary to calculate the evaluation value of each of the n parts when placed in n places, so the calculation of the evaluation value of each part is n2
It only takes a few times.

After calculating the evaluation values of individual parts, when adding them together, 01 calculations must be performed, but since this is simply an addition of n evaluation values, 01 evaluation values must be calculated one by one. Compared to conventional methods, the overall amount of calculation can be significantly reduced.

(Example) Next, embodiments of the present invention will be described using the drawings.

FIG. 1 is a block diagram showing the configuration of a placement improvement device that is an embodiment of the present invention.

The embodiment shown in FIG. 1 includes a host processor 11, a connection list memory 12, a placement state memory 13, a termination condition determination circuit 14, an exchange candidate creation circuit 15, an evaluation function table creation circuit 16, and an evaluation function table creation circuit 16. It is composed of a function calculation circuit 17, an evaluation result comparison circuit 18, and a placement state update circuit 19.

In this example, a method is used in which a group of components, each connected to other components by several wires, is already placed, and the placement is improved by repeatedly replacing four components at the same time. Let's talk about.

FIG. 2 shows an example of a state in which a group of components, each connected to other components by several wires, have already been arranged. Second
In the figure, rectangles are parts, and line segments are virtual wiring that connects the parts.

In this way, the arrangement of parts already arranged in a certain state is improved, and the virtual wiring length as shown in FIG. 3 is used to evaluate the arrangement. In FIG. 3, the wire 33 connecting the component 31 and the component 32 has a length equivalent to four components, so the virtual wire length is four.

An outline of the process is shown in FIG. First, select four parts that are not connected to each other. Next, we evaluate all of their replacements. As a result, if a better arrangement than the original arrangement is found, it is replaced with that arrangement. The arrangement is improved by repeating this series of processes.

FIG. 1 shows an apparatus that performs such processing.

In FIG. 1, a host processor 11 has a function of loading a problem to be improved in placement and saving the processing results.The host processor 11 stores the initial placement state in the placement state memory 13 and the component connection information. After loading the connection list memory 12 and setting the termination condition for the process in the termination condition determination circuit 14, the termination condition determination circuit 14 is activated. Further, when a signal indicating that the processing has been completed is received from the termination condition determination circuit 14, the processing result is read from the arrangement state memory 13.

The connection list memory 12 is loaded from the host,
This is a memory that holds component connection information.

The arrangement state memory 13 is a memory that holds the latest arrangement state of components.

The termination condition determination circuit 14 generates exchange candidates after receiving a synchronization signal sent from the placement state update circuit 19 every time one processing is completed until the termination condition set by the host processor is satisfied. A start signal is sent to the circuit 15.

For example, the termination conditions are (1) until the number of exchange attempts reaches 10,000, (2) until the number of successful exchanges reaches 10,000,
The following conditions can be considered.

Furthermore, when the termination condition is satisfied, a signal is sent to the host processor to inform the host processor of the termination.

Each time the replacement candidate creation circuit 15 receives a start signal from the end condition determination circuit 14, it selects four parts that are not connected to each other while referring to the connection list memory, and creates an evaluation function table using the part numbers. to circuit 16.

The following method can be considered as a method for selecting four components that are not connected to each other in the replacement candidate creation circuit 15.

The exchange candidate creation circuit 15 has a table as shown in FIG. 5 inside. In the table, the left column shows each part, and the right column is for checking whether the part can be selected.

First, if no parts are selected, write 0 in all check boxes. Next, select one of the parts for which O is written in the check column, and write 1 in the check column corresponding to the selected component and the components connected to that component.

Then, select one component for which O is written in the tick column, and continue this process until the required number of components are selected.

The evaluation function table creation circuit 16 has an evaluation function table therein,
After receiving the part numbers of the four replacement candidates from the replacement candidate creation circuit 15, it evaluates the evaluation function when each part is placed at each location while referring to the connection list memory 12 and placement state memory 13. Record in function table. As the evaluation function, when a certain part is placed at a certain location, the sum of the virtual wiring lengths of all the wiring connected to that part is used.

Suppose now that the evaluation function table creation circuit 16 is instructed by the replacement candidate creation circuit 15 to replace four parts A, B, C, and D as shown in FIG.

a each of the places where they are currently located.

Let them be b, c, and d.

At this time, the four selected components A, B, C, and D are not connected to each other by wiring.

Therefore, when part A is placed at locations a, b, c, and d,
The virtual wiring length of the wiring connected to component A is component B,
It can be determined regardless of the arrangement of C and D. As a result, an evaluation function table as shown in FIG. 7 can be created.

In FIG. 6, parts A, B, and C are shown in each blank.

Write the total virtual wiring length of all wiring connected to each component when D is placed at locations a, b, c, and d, respectively.

When the evaluation function table creation circuit 16 completes the evaluation function table, it sends the evaluation function table to the evaluation function calculation circuit 17.

When the evaluation function calculation circuit 17 receives the evaluation values sent from the evaluation function table creation circuit 16, it calculates A and B.

The evaluation values for each of 24 ways of replacing the four parts C and D are determined. In Figure 8, A.

It shows all the ways to buy four parts B, C, and D by placing them in four places a, b, c, and d. In FIG. 8, each row represents one way of replacement, and represents where four parts A, B, C, and D should be placed. 24
To obtain the evaluation value of a given value, select one by one from each row and column of the evaluation function table shown in Figure 7, changing the selection method in order, and add them together.For example, the selection method shown in Figure 9 is used to find the evaluation value when A is placed, B is placed on d, C is placed on a, and D is placed on C.

After the evaluation function calculation circuit 17 finishes calculating the evaluation value, the evaluation function calculation circuit 17 calculates 2
The four evaluation results are sent to the evaluation result comparison circuit 18.

The evaluation result comparison circuit 18 compares the 24 evaluation results sent from the evaluation function calculation circuit 17, determines which replacement method is the best, and sends the result to the placement state update circuit 1.
Send to 9.

The placement state update circuit 19 updates the placement state memory 13 based on the results sent from the evaluation result comparison circuit 18 and the four part numbers sent from the replacement candidate creation circuit 15, if the evaluation value can be improved. The arrangement is updated, and a synchronization signal is sent to the end state determination circuit 14 to notify that one process has been completed, together with information as to whether the arrangement has been updated.

(Effects of the Invention) As described above, the present invention has the advantage that when selecting a group of parts to be replaced at the same time, by selecting parts that are not connected to each other, changes in evaluation values when moving each part are The calculation can be performed independently of how the parts move, which has the effect of greatly reducing the amount of calculation.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is a diagram showing an example of a problem to which the embodiment of FIG. Fig. 1 is a flowchart showing the processing procedure of the embodiment, Fig. 5 is an explanatory diagram of a method of selecting parts that are not connected to each other, Fig. 6 is a diagram showing an example of replacement candidates, and Fig. 7r! lJ is an explanatory diagram of an evaluation function table for recording the evaluation value of each part when each part is placed in each place, and Figure 8 is an explanatory diagram of the evaluation function table for recording the evaluation value of each part when it is placed in each place.
FIG. 9, an explanatory diagram showing a street, is a diagram showing an example of a replacement method. DESCRIPTION OF SYMBOLS 11... Host processor, 12... Connection list-memory, 13... Arrangement state memory, 14... Termination condition determination circuit, 15... Exchange candidate creation circuit, 16...
・Evaluation function table creation circuit, 17...Evaluation function calculation circuit,
18...Evaluation result comparison circuit, 19...Arrangement state update circuit, 31-32...Components, 33...Virtual wiring.

Claims (1)

[Claims] By replacing multiple parts at the same time, evaluating all replacement methods, and using the total virtual wiring length for all wiring to evaluate placement, multiple parts that have already been placed can be replaced. In the placement improvement method, which sequentially improves the arrangement of parts and better arranges a group of parts that are interconnected by wiring nets within a predetermined area, the parts that are replaced at the same time are not connected to each other by wiring nets. When evaluating the means for selecting a group of parts and the replacement method, by independently calculating and adding up the evaluation value for each new location of each part,
A wiring improvement method characterized by comprising: means for obtaining an overall evaluation value.