Patent ID: 6499133
Filing Date: 2002-12-24
Classification: G06F

Abstract:
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 (2pâˆ’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.