Automatic placement method for arranging logic cells

• US 5,140,402 A
• Filed: 01/22/1991
• Issued: 08/18/1992
• Est. Priority Date: 01/22/1990
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Murakata, Masami
• Primary Examiner(s): Mintel, William
• Assistant Examiner(s): POTTER, ROY KARL
• Application Number:
  US07/643,984
• Time in Patent Office: 574 Days
• Field of Search: 364/491, 357/45, 357/40
• US Class Current: 257/499
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: Y10S 257/923 with means to optimize electrical conductor current carrying capacity, e.g. particular conductor aspect ratio

Abstract

An automatic placement method for arranging logic cells on a chip, having a setting step for setting an evaluation function, target values thereof, placement improvement methods, and a range of a satisfaction level of each evaluation function, a calculating step for calculating a difference between a value of each evaluation function and, its target value, an improving step for selecting one of the placement improvement methods to optimize the evaluation function having the largest difference and then executing the placement improvement method; wherein the above processing is repeatedly executed over a required number of times, the range of each evaluation function is set by using probabilistic fluctuation each processing, and the range of each evaluation function is further narrowed with every processing.

Claims

1. An automatic placement method for arranging logic cells on a semiconductor substrate such as a chip, comprising:

a setting step for setting at least one evaluation function, a target value for each evaluation function, placement improvement methods for optimizing each evaluation function, and a range of a satisfaction level of each evaluation function;

a calculating step for calculating a difference between a value of each evaluation function by which a current placement state of the logic cells is evaluated and a target value of each evaluation function;

an improving step for selecting one of the placement improvement methods in order to optimize the evaluation function having the largest difference and then executing the placement improvement method as a current improvement method in order to re-arrange the current placement state of the logic cells into a new placement state;

a deciding step for deciding whether the value of the evaluation function having the largest difference according to the current placement improvement method is close to the target value of the evaluation function, and if a value of each evaluation function other than the evaluation function having the largest difference is being kept in the range of the satisfaction level thereof, respectively;

a re-setting step for storing the current placement state of the logic cells into a predetermined store means, further limiting the range of the satisfaction level according to each evaluation function into a smaller range, and calculating a difference between the value of each evaluation function by which the current placement state of the logic cells has been evaluated and the target value of each evaluation function when one of two conditions comprising a first condition that the value of the evaluation function having the largest difference is decreased and the values of the evaluation functions other than the evaluation function having the largest difference are kept in the ranges of the satisfaction levels thereof, and a second condition that the result obtained by the deciding step being satisfied, is met; and

an excluding step for changing the current placement state of the logic cells to the preceding placement state, and excluding the current placement improvement method in the next operation when one of two conditions comprising a first condition that the value of the evaluation function having the largest difference is not decreased and the values of at least an evaluation function other than the evaluation function having the largest difference is not kept in the range of the satisfaction level thereof, and a second condition that the result obtained by the deciding step being not satisfied is met,

wherein processing comprising the improving step, the deciding step, the re-setting step, and the excluding step is repeatedly executed a required number of times, the range of each evaluation function being set by using probabilistic fluctuation at each processing, and the range of each evaluation function further reduced by every processing.

2. An automatic placement method according to claim 1, wherein at each processing a weight for each evaluation function is set in the calculating step and the re-setting step, and the difference between the value of each evaluation function and the target value thereof is then calculated by using the weight.

3. An automatic placement method according to claim 1, wherein the range of the satisfaction level for each evaluation function is obtained by the probabilistic fluctuation equations:

space="preserve" listing-type="equation">fsf(i)=fsi+fsa(i)+fsp(i)

space="preserve" listing-type="equation">fsa(i)=(fsi*p)/(q+1)

space="preserve" listing-type="equation">fsp(i)=fsa(i)/k*(a,b)

where, fsf(i) is a value of a satisfaction level according to i-th evaluation function at 1-th placement improvement process, fsp(i) is a range of a satisfaction level at i-th placement improvement process, fsi is an intended satisfaction level for each evaluation function, fsa(i) is the value introduced to determine the probabilistic perturbation value, p, g, and k are constants, i is the number of process iterations, and (a,b) is a random number between a and b.

4. An automatic placement device for automatically arranging logic cells on a semiconductor substrate such as a chip, comprising:

a setting means for setting at least one evaluation function, a target value of each evaluation function, placement improvement methods for optimizing each evaluation function, and a range of a satisfaction level of each evaluation function;

a calculating means for calculating a difference between a value of each evaluation function by which a current placement state of the logic cells is evaluated and a target value of each evaluation function;

an improving means for selecting one of the placement improvement methods in order to optimize the evaluation function having the largest difference and then executing the placement improvement method as a current improvement method in order to re-arrange the current placement state of the logic cells to a new placement state;

a deciding means for deciding whether the value of the evaluation function having the largest difference according to the current placement improvement method is close to the target value of the evaluation function, and a value of each evaluation function other than the evaluation function having the largest difference being kept in the range of the satisfaction level thereof, respectively;

a re-setting means for storing the current placement state of the logic cells into a predetermined store means, further limiting the range of the satisfaction level according to each evaluation function in a smaller range, and calculating a difference between the value of each evaluation function by which the current placement state of the logic cells has been evaluated and the target value of each evaluation function when one of two conditions comprising a first condition that the value of the evaluation function having the largest difference is decreased and the values of the evaluation functions other than the evaluation function having the largest difference are kept in the ranges of the satisfaction levels thereof, and a second condition that the result obtained by the deciding step being satisfied, is met; and

an excluding means for changing the current placement state of the logic cells to the preceding placement state, and excluding the current placement improvement method in the next operation when one of two conditions comprising a first condition that the value of the evaluation function having the largest difference is not decreased and the values of at least an evaluation function other than the evaluation function having the largest difference is not kept in the range of the satisfaction level thereof, and a second condition that the result obtained by the deciding step being not satisfied is met,

wherein a processing carried out by the improving means, the deciding means, the re-setting means, and the excluding means is repeatedly executed a required number of times, the range of each evaluation function being set by using probabilistic fluctuation at each processing, and the range of each evaluation function further limited by every processing.