Method and apparatus for optimizing element placement and deciding the optimal element placement

Claim 1

A method of optimizing an element placement including a number of elements which correlate to one another by exchanging appropriately positions of said elements, comprising: a first step for establishing an initial placement for a number of elements; a second step for selecting plural pairs of elements at random; a third step for determining a value of cost improvement expected to be brought about by exchange of the paired elements for each of said pairs; a fourth step for exchanging the positions of the paired elements only for the pair for which the cost improvement value determined at said third step is maximum or exceeds a given threshold value; and a fifth step for outputting the result of the optimal element placement obtained by executing repeatedly said second to fourth steps for a predetermined number of times.

Claim 2

A method of optimizing an element placement including a number of elements which correlate to one another by exchanging appropriately positions of said elements, comprising: a first step for establishing an initial placement for a number of elements; a second step for selecting plural pairs of elements at random; a third step for determining a value of cost improvement expected to be brought about by exchange of the paired elements for each of said pairs; a fourth step for exchanging the positions of the paired elements only for the pair for which the cost improvement value determined at said third step is maximum or exceeds a given threshold value; and a fifth step for outputting the result of the optimal element placement obtained by executing repeatedly said second to fourth steps for a predetermined number of times.

Claim 11

The apparatus according to one of the claims 5 to 8, further comprising CPU upper limit number setting means (15) for setting an upper limit number of CPUs which can be employed, wherein said paired candidate selecting means (12, 13, 14) select a number of paired element candidates, said number corresponding to that of said CPUs which are employed for operation, said operation means (14) are determining cost improvement values expected to be brought about by exchanging positions of the paired element candidates assigned to said CPUs, respectively, and said execution of the operations of said paired candidate selecting means, said operation means and said element position exchanging means is repeated until it is decided that there exist no more the paired element candidates for which the cost can be improved by exchanging the element positions when said upper limit number of the CPUs set at said CPU upper limit number setting means are used.

Claim 12

The apparatus according to one of the claims 5 to 9, further comprising first memory means for storing a connection table (12) concerning said initial positions and interelement interconnection relations in a placement after having been changed and a placement position table (13) concerning placed positions of the individual elements; second memory means (1, .... N) for storing the results of operation; third memory means for storing conditions for executing said operation and/or a threshold value; said paired candidate selecting and said operation means (15) are respectively allowing each of two or more CPUs to select at random the paired element candidates and are determining arithmetically the cost improvement value, the result of said arithmetic operation being stored in said second memory means, said element position exchanging means (15) are updating said connection table (12) and said arranged position table (13) stored in said first memory means to the element positions for the paired candidates for which the cost improvement value is greatest among those stored in said second memory means or exceeds the threshold value stored in said third memory means, and said output means (16) are repeating executions by said paired candidate selection/operation means and said element position exchanging means in accordance with the conditions stored in said third memory means and outputting the resulting placement as the optimum placement.