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

• US 5,144,563 A
• Filed: 03/13/1990
• Issued: 09/01/1992
• Est. Priority Date: 03/16/1989
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Date, Hiroshi, Hayashi, Terumine
• Primary Examiner(s): Lall, Parshotham S.
• Assistant Examiner(s): Trans, V. N.
• Application Number:
  US07/492,906
• Time in Patent Office: 903 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/131, 364/148, 395/800
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Element placement optimizing method and apparatus for determining an optimum placement of constituent elements for an LSI or the like. A parallel processing type computer system including a plurality of CPUs is used. An initial element placement is established and a number of paired element candidates for position exchange are selected from the initial placement, the number being equal to that of CPUS. A cost improvement value resulting from the exchange is determined for each of the paired candidates by the associated CPU. The exchange of the elements is performed for the paired element candidates for which the cost improvement value is maximum of those determined by the CPUs. By repeating the exchange, an optimum element placement is determined.

Claims

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 with the aid of a parallel computer system including a plurality of central processing units (CPUs), the method comprising the steps of:

establishing the initial placement for a number of elements;

selecting a number of pairs of elements at random, said number being a number of said CPUs which are employed;

determining a value of cost improvement expected to be brought about by exchange of the paired elements for each of said pairs by said number of CPUs;

exchanging positions of the paired elements only for a pair in which the cost improvement value determined at said determining step is a maximum or exceeds a given threshold value;

executing repeatedly said selecting to said exchanging steps for a predetermined number of times; and

outputting information indicating an optimal element placement of said elements by executing repeatedly said exchanging step while increasing the number of CPUs until a predetermined number of CPUs are employed.

2. An element placement optimizing method according to claim 1, wherein at said establishing step, the initial element placement is determined through a heuristic procedure or by using pseudo-random numbers.

3. A method of optimizing an element placement including a number of elements which correlate to one another by exchanging appropriately positions of said elements with the aid of a parallel computer system including a plurality of central processing units (CPUs), the method comprising the steps of:

establishing an initial placement for a number of elements;

establishing an upper limit of CPUs which can be employed;

selecting a number of pairs of elements at random, said number being a number of CPUs which are employed;

determining a value of cost improvement expected to be brought about by exchange of the paired elements for each of said pairs by said number of CPUs;

exchanging the positions of the paired elements only for a pair for which the cost improvement value determined at said determining step is a maximum or exceeds a given threshold value;

executing repeatedly said selecting to exchanging steps until the element pairs for which the cost improvement value can be obtained at said selecting step are no longer present; and

outputting information indicating an optimal element placement of said elements obtained by executing repeatedly said executing step while increasing the number of CPUs until a number of an upper limit of CPUs are employed.

4. An element placement optimizing method according to claim 3, wherein at said establishing step, the initial element placement is determined through a heuristic procedure or by using pseudo-random numbers.

5. An element placement optimizing apparatus for determining optimum positions of elements, wherein a number of the elements correlate with one another, by exchanging appropriately the positions of the elements with the aid of a parallel processing computer system including a plurality of central processing units (CPUs), comprising:

initial placement setting means for establishing an initial element placement of a plurality of elements;

CPU upper limit number means for setting an upper limit number of CPUs which can be employed;

paired candidate selecting means for selecting at random a number of paired element candidates, said number of paired element candidates corresponding to the number of said CPUs which are employed for operation;

operation means for determining cost improvement values expected to be brought about by exchanging positions of the paired element candidates assigned to said CPUs, respectively;

element position exchanging means for exchanging the positions of the paired element candidates for which a cost improvement value determined by said operation means is a maximum or exceeds a given threshold value; and

output means for outputting information indicating an optimum element placement of said elements, by executing repeatingly the operations of said paired candidate selecting means, said operation means and said element position exchanging means until it is determined that no more paired element candidates exist in which a cost thereof 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.

6. An element placement optimizing apparatus which comprises a parallel processing computer including a plurality of central processing units (CPUs) for determining an optimal element placement by appropriately exchanging positions of elements in an placement including a number of the elements, said apparatus comprising:

initial position setting means for setting initial positions of said elements;

first memory means for storing a connection table concerning said initial positions and inter-element interconnection relations in an placement after having been changed and an placement position table concerning placed positions of the individual elements;

second memory means for storing the results of operation;

third memory means for storing conditions for executing said operation and/or a threshold value;

paired candidate selection/determination means for allowing each of two or more CPUs to select a random the paried element candidates and determine arithmetically a cost improvement value obtained by exchanging the element positions for the selected paired candidates, the result of said arithmetic opertion being stored in said second memory means;

element position exchanging means for updating said connection table and said placed position table 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;

execution repeating/outputting means for repeating executions by said paired candidate selection/determination 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;

wherein the number of times said execution is repeated in case there exist no paired candidates for which the cost improvement value resulting from the operation of said paired candidates selection/determination means is positive or exceeds said threshold value is placed in said third memory means,

said execution repeating/outputting means outputting the placement resulting from said repetition of excecution for said predetermined number of times as the optimum element placement

initial placement setting means for establishing an initial element placement;

wherein said third memory means is further provided with an upper limit number of the CPUs employed for execution by said paired candidate selection/determination means, and a starting number of the CPUs employed at the time of starting the execution, wherein the number of the CPUs is increased in the course of the execution,

wherein said execution is started with said starting number of the CPUs, the execution of said paired candidate selection/determination means is repeated for a predetermined number of times, being followed again by repetition of the execution of said paired candidate selection/determination means for said predetermined number of times with the number of CPUs increased in the course of the execution, and

wherein said execution repeating/outputting means outputs as the optimal element placement the placement obtained when said upper limit number of the CPUs has been attained as the result of repeatedly increasing of the number of the CPUs.

7. An apparatus for optimizing an optimal element placement of a plurality of elements by exchanging appropriately positions of the elements, wherein the elements correlate to one another, said apparatus comprising:

initial placement setting means for establishing an initial placement of the elements;

paired candidates selecting means for selecting at random plural pairs of element candidates for exchange of positions;

operation means for determining a value of cost improvement expected to be brought about by exchange of positions for each of the paired element candidates by a number of CPUs;

element position exchanging means for exchanging element positions of the paired element candidates only for a pair which a cost improvement value determined by said operation means is a maximum or exceeds a given threshold value;

means for executging repeatedly a predetermined number of times operations of said paired candidate selecting means said operation means and said element position exchanging means; and

outputting means for outputting information indicating an optimal element placement of said elements by executing repeatedly said element position exchanging means while increasing the number of CPUs until a predetermined number of CPUs are employed.

8. An apparatus for optimizing an optimal element placement of a plurality of elements by exchanging appropriately positions of the elements, wherein the elements correlate to one another, said apparatus comprising:

means for establishing an initial placement for a number of elements;

means for establishing an upper limit of CPUs which can be employed;

means for selecting a number of pairs of elements at random, said number being a number of CPUs which are employed;

means for determining a value of cost improvement expected to be brought about by exchange of paired elements for each of said pairs by said number of CPUs;

means for exchanging positions of paired elements only for a pair of which a cost improvement value determined by said means for determining is a maximum or exceeds a given threshold value;

means for executing repeatedly a predetermined number of times said means for selecting, said means for determining and said means for exchanging until element pairs for which a cost improvement value determined by said means for determining are no longer present; and

means for outputting information indicating an optimal element placement of said elements obtained by executing repeatedly a predetermined number of times said means for exchanging while increasing the number of CPUs until a number of an upper limit of CPUs are employed.