Automatic parts placement system, method, and medium

Details Automatic parts placement system, method, and medium Automatic parts placement system, method, and medium

2000-03-10

2003-05-06

Picard, Leo (Department: 2125)

Data processing: generic control systems or specific application

Specific application, apparatus or process

Product assembly or manufacturing

C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06560505

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to an automatic placement system and method for parts and, in particular, to an automatic parts placement system and method each of which is suitable to be used in, for example, a CAD (computer aided design) system automatically placing parts, figures, or the like on a plane.
2. Description of the Related Art
Some of parts placement methods applied to a previous printed wiring board or a previous semiconductor integrated circuit are disclosed in documents. For example, a parts placement optimizing method is disclosed in Japanese Laid Open Publication No. H06-332983 (namely, 332983/1994, U.S. Pat. No. 5,600,555). With this method, it is possible to determine, in a short time, parts placement which provides a comparatively low valuation standard, such as a total wiring length. Hereinafter, the document will be referred to as “document 1”. Specifically, the parts placement optimizing method virtually converts parts into uniform size of blocks or a set of blocks (initial placement), and replaces blocks in the blocks or in the set of blocks. As a result, the method improves the parts placement so that the valuation reference such as a total wiring length may become small as possible, and finally returns the virtually converted blocks to real parts.
The method may be implemented through a program in a computer system which includes an input device, such as a keyboard, a display device such as a CRT display, and a data processing device having a CPU, a memory, and a hard disk.
Further, disclosure is made in Japanese Laid Open Publication No. H03-108739 (namely, 108739/1991, U.S. Pat. No. 5,309,371) about an integrated circuit blocks placement method of placing variant size of blocks and determining a wiring between the blocks. The document will be, hereinafter, referred to as “document 2”.
The method initially places the blocks using a mass system spring model in which each of circuit blocks is assumed to be connected to the other circuit blocks by a spring with the block size neglected. It may be said that energy of the dynamic model corresponds to sums of squares of net lengths. Under the above-assumption, the initial placement is made such that the energy may become minimum by using a method of placing the parts in a gravity point (barycenter).
Then, the parts or circuit blocks are approximated by circles which have block sizes to calculate placement of each circle. Thereafter, the circles are transformed to the real configurations of the blocks to replace the blocks so that there are no overlaps among the blocks. In other words, the method compacts the blocks along with a frame of a circuit board and modifies the shape of each block from the circular figure to the actual shape.
Finally, the method assigns a zone for wiring by swelling the blocks and adjusts an aspect ratio of each block in a tolerance level.
Similarly, a method disclosed in Japanese Laid Open Publication No. H03-124046 (namely, 124046/1991, U.S. Pat. No. 5,309,371) utilizes the mass system spring model and performs the similar initial placement as described above. Herein, the document is referred to as “document 3”.
Furthermore, disclosure is made in Japanese Laid Open Publication No. H06-332984 (namely, 332984/1994) about an element placement method which is capable of determining an optimum solution in a short time without exchanging two elements. The document is, hereinafter, referred to as “document 4”.
The method comprises the steps of (1) determining a gravity point of each net, (2-1) determining an average vector by determining vectors from each terminal position and by averaging the vectors, (2-2) determining a position to which the element is moved based on the average vector, (3) determining a permutation of the elements according to coordinate values of the position, and (4) determining a matrix structured placement of the elements so that there are no overlaps between elements in consideration of the shapes of the elements and a matrix structured initial placement placing the elements according to the determined permutation.
As described above, the method of the document 1 determines an optimum parts placement so that the total wiring length becomes minimum. The total wiring length is defined as a sum of Manhattan distances between parts elements connected by the net.
On the other hand, the method of the document 2 and the method of the document 4 use the sums of squares of distances between the parts elements connected through the net to determine an optimum parts placement.
However, there is no analytical solution against a problem of finding the above optimum parts placement. Therefore, to find an optimum solution, a method has been adopted which selects a combination which has a minimum value among total wiring lengths obtained by calculating all combinations of possible parts placements.
But, the number of combinations becomes equal to N! (N is the number of the parts). In consequence, an amount of computations required to find the optimum solution increases explosively as the number N increases.
Therefore, parts placement algorithm of finding a solution close to an optimum solution in a short time has been developed.
As described above, the prior method of repeatedly selecting parts placement by exchanging parts so as to shorten its own total wiring length causes critical placements to occur such that no reduction is possible. There are often a plurality of critical parts placements. Once a solution is found which corresponds to such a critical parts placement, any other optimum solutions can not be found, although there is another optimum solution which leads to less total wiring length. This problem is known as local stabilization.
Here, to avoid the local stabilization and to determine an optimum solution, a simulated annealing method may be simultaneously used. The method applies a principle of leaving from a state of local stabilization using state transition of disturbance in heating a molecule, to search of parts placement. That is, some solutions are generated by random modification, and then, the most improved solution (for example, a solution which leads to less total wiring length) is selected among these solutions.
Also, a method has been known which improves a solution by repeating steps of generating “descendant” solutions resulting from random disturbance of a part of initially obtained solutions based on genetic algorithm, and selecting the most improved solution among the “descendant” solutions.
However, the parts placement system using the simulated annealing method or the genetic algorithm still has a problem that an operation time is incomparably larger than a time needed for determining a solution by the pair exchange method.
This is because the system using the simulated annealing method or the genetic algorithm has many and complex procedures. Specifically, the system generates a large number of solutions which are slightly different from each other using the random disturbance, determines improved solutions using the pair exchange method based on each of the generated solutions, generates a large number of solutions again by disturbing the improved solutions, and estimates the finally generated solutions.
There are two substantial points in the system. A first point is that the disturbance process should be performed appropriately and in a fully broad range not to miss a path to an optimum solution. A second point is that convergence process should be completely performed so as to converge the randomly disturbed solutions.
Consequently, to obtain a solution closer to an optimum solution, it is required to perform as much fully disturbance process as possible and perform complete convergence process to convergence the disturbance. Thus, if one would obtain more proper solution, a longer operation time is required.
On the other hand, in the methods disclosed in the document 2 through the document 4, since each of the methods uses the mass system spring model, a shorter operation time is realiz

Affiliated with

Also associated with

Rating

Automatic parts placement system, method, and medium does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Automatic parts placement system, method, and medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic parts placement system, method, and medium will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3024366