Method of optimizing placement of elements

• US 6,499,133 B1
• Filed: 03/17/2000
• Issued: 12/24/2002
• Est. Priority Date: 03/18/1999
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Kurokawa, Keiichi, Toyonaga, Masahiko
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): ROSSOSHEK, YELENA
• Application Number:
  US09/527,474
• Time in Patent Office: 1,012 Days
• Field of Search: 716/1-21, 326/38, 326/39, 327/99
• US Class Current: 716/119
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An initial arrangement is effected based on a net list and a cell library. Combination functions are extracted from a cost function. An optimum estimated temperature is calculated based on the difference between values of the cost function before and after two adjacent elements that have been selected randomly from elements to be arranged are interchanged in position, while near-optimum estimated temperatures are calculated based on the differences between respective values of the combination functions before and after the positional interchange. Of the near-optimum estimated temperatures, those lower than the optimum estimated temperature are recorded in a temperature schedule list together with the optimum estimated temperature. Thereafter, the Monte-Carlo method based on a random positional interchange between the elements to be arranged using the cost function is executed in order of the decreasing temperatures recorded in the temperature schedule list, whereby the initial arrangement is improved.

Claims

1. A method of optimizing placement of elements in designing a semiconductor device by using a cost function for evaluating the placement of elements, the cost function being expressed as a sum of p (p is an integer not less than 2) partial functions and varying with an estimated temperature as a parameter, the method comprising:

a first step of inputting a net list and a cell library and effecting an initial arrangement of elements to be arranged;

a second step of extracting functions each expressed with either one of the p partial functions of the cost function or, when p is an integer not less than 3, expressed as a sum of a combination of not less than 2 and not more than (p−

1) partial functions of the p partial functions of the cost function as q (q is an integer not less than 1 and not more than (2^p−

2)) combination functions;

a third step of randomly selecting two elements adjacent to each other from the elements to be arranged, calculating one optimum estimated temperature based on a difference between values of the cost function before and after the two elements are interchanged in position, and calculating q optimum estimated temperatures based on differences between respective values of the q combination functions before and after the interchange;

a fourth step of recording, in a temperature schedule list, the temperatures of the q optimum estimated temperatures derived from the q combination functions which are lower than the optimum estimated temperature derived from the cost function together with the optimum estimated temperature derived from the cost function; and

a fifth step of executing a Monte-Carlo method based on a random positional interchange between the elements to be arranged using the cost function in order of the decreasing temperatures recorded in the schedule list and thereby improving the initial arrangement.

2. The method of claim 1, wherein the second step includes a step of, extracting all or part of the p functions expressed with the respective p partial functions of the cost function as all or part of the q combination functions.

3. The method of claim 1, wherein the second step includes a step of extracting, when p is an integer not less than 3, all or part of (2^p−

p−

2) functions each expressed as a sum of a combination of not less than 2 and not more than (p−

1) partial functions of the p partial functions of the cost function as all or part of the q combination functions.

4. The method of claim 1, wherein the fourth step includes a step of updating the temperature schedule such that a plurality of temperatures having a difference not exceeding a given threshold value therebetween are represented by one of the temperatures.