System for optimizing a physical organization of elements of an integrated circuit chip through the convergence of a redundancy function

• US 5,159,682 A
• Filed: 10/26/1989
• Issued: 10/27/1992
• Est. Priority Date: 10/28/1988
• 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: Okude, Hiroaki, Akino, Toshiro, Toyonaga, Masahiko
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harrity, Paul
• Application Number:
  US07/426,957
• Time in Patent Office: 1,097 Days
• Field of Search: 364/200, 364/900, 364/491, 364/148, 364/488, 364/489, 364/490, 395/500
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

During an optimization of an organization of mutually-related elements, an element organization is gradually changed toward an objective specification by local changes of the element organization. A value of an objective function depends on a degree of a nearness of the element organization to the objective specification. A redundancy function of a number of elements in an improvement group is determined in consideration of a fluctuation in the value of the objective function, so that suitable changes of the improvement group are performed by use of the definite redundancy. An intermediate element organization is rejected and accepted in accordance with the redundancy function value, so that a final element organization can be obtained in consideration of a global aspect of the element organization.

Claims

1. A computer implemented method of optimizing a physical organization of a plurality of mutually-related elements of an integrated circuit chip to establish a resulting chip size and performance, wherein the element organization is gradually changed toward an objective specification of circuit functionality with minimum production cost by local changes of the element organization, the method comprising the steps of:

a firts step including sub steps of;

defining an objective function whose value depends on a degree of a nearness of a particular element organization of a plurality of possible element organization of a plurality of possible element organizations to an objective specification of circuit functionality with minimum production cost.

defining an iteration number of improvement for each improvement group of elements in each of which several types of element organization could be generated, an iteration number of improvement for all elements of any improvement group, an initial number of elements in each improvement group, a smallest number of elements which can be improved in each improvement group, a total number of elements equal to said plurality of elements, and a concentration parameter that controls a group redundancy and a number of elements in each successive improvement group, and

generating an initial element organization;

a second step including sub steps of;

performing at least one of random exchange and movement of elements in the initial element organization,

calculating a fluctuation in a value of the objective function which responds to said random exchange and movement,

calculating a value of said fluctuation which results from an execution of one time of said random exchange and movement,

calculating a product of said fluctuation value and the number of elements in an improvement group and

using said product of the fluctuation value and the number of elements in an improvement group as a redundancy function;

a third step including sub steps of selecting one of the elements at random and setting an improvement group of elements whose origin agrees with the selected element, wherein the number of elements in the improvement group is less than the total number of elements;

a fourth step including sub steps of;

calculating a value of the objective function of a current element organization,

changing the current element organization to a new element organization by performing at least one of exchange and movement of elements in the improvement group,

calculating a value of the objective function of the new element organization,

calculating a difference between the values of the objective functions of the current element organization and the new element organization,

calculating a degree of redundancy on the basis of a product of the concentration parameter and a value of the redundancy function which corresponds to the organization of the improvement group,

judging whether or not the objective function value difference is greater than the degree of redundancy,

rejecting the new element organization and maintaining the current element organization when the objective function value difference is greater than the degree of redundancy,

accepting the new element organization when the objective function value difference is not greater than the degree of redundancy, and

reiterating said sub steps of the fourth step a number of times which agrees with the iteration number of improvement for each improvement group,

wherein said third step and said fourth step correspond to a whole element organization improving process;

a fifth step including sub steps of;

reiterating the whole element organization improving process a number of times which agrees with the iteration number of improvement for all elements,

calculating a value of the objective function which occurs after said reiterating of the whole element organization improving process,

judging whether or not the objective function value which occurs after said reiterating of the whole element organization improving process is smaller than the objective function value which occurs before said reiterating of the whole element organization improving process,

further repeating the whole element organization improving process a number of times which agrees with the iteration number of improvement for all elements when the objective function value which occurs after said reiterating of the whole element organization improving process is smaller than the objective function value which occurs before said reiterating of the whole element organization improving process, and

performing a sixth step when the objective function value which occurs after said reiterating of the whole element organization improving process is not smaller than the objective function value which occurs before said reiterating of the whole element organization improving process;

said sixth step of multiplying a current number of elements in an improvement group by the concentration parameter to change the current number of elements in the improvement group into a new number of elements in the improvement group;

a seventh step including sub steps of;

judging whether or not the new number of elements is greater than the smallest number of elements in an improvement group,

calculating a value of the redundancy function related to the new number of elements and then preforming said third step when the new number of elements is greater than the smallest number of elements in an improvement group,

judging whether or not the value of the redundancy function is equal to 0 when the new number of elements is not greater than the smallest number of elements in an improvement group,

setting the value of the redundancy function to 0 and then performing the third step when the value of the redundancy function is not equal to 0, and

performing an eighth step when the value of the redundancy function is equal to 0;

said eighth step of outputting a finally-obtained element organization which corresponds to an optimal element organization satisfying the circuit functionality and producing a smaller chip size; and

a ninth step of organizing the elements of the integrated circuit chip in accordance with the finally-obtained element organization thus reducing the production cost of the integrated circuit chip.

2. The method of claim 1 wherein said third step comprises:

exchanging an element with the selected element at the origin of the improvement group to change the element organization;

calculating a value of the objective function of the element organization which occurs before said exchanging related to the origin element;

calculating a value of the objective function of the element organization which occurs after said exchanging related to the origin element;

calculating a difference between the objective function values which occur before and after the exchanging related to the origin element;

comparing a predetermined reference value and said difference between the objective function values which occur before and after the exchanging related to the origin element; and

forming the improvement group of elements from a group of elements in which said difference between the objective function values which occur before and after the exchanging related to the origin element is equal to or less than the predetermined reference value.

3. A computer implemented method of optimizing a placement of a plurality of inter-related elements of an integrated circuit chip wherein degrees of the inter-relationship between the elements are represented by distances between the elements, and the element placement is gradually changed toward an objective specification of circuit functionality with minimum production cost by local changes of the element placement, the method comprising the steps of:

a first step including sub steps of;

defining an objective function whose value depends on distances between the elements and on a degree of nearness of a particular element placement to an objective specification of circuit functionality with minimum production cost,

defining an iteration number of improvement for each improvement group of elements in each of which several types of element placement could be generated, an iteration number of improvement for all elements of any improvement group, an initial number of elements in each improvement group, a smallest number of elements which can be improved in each improvement group, a total number of elements equal to said plurality of elements, and a concentration parameter that controls a group redundancy and a number of elements in each successive improvement group, and

generating an initial element placement;

a second step including sub steps of

moving and exchanging elements having average relations therebetween so that the elements are changed from conditions where the elements are distant from each other by a maximal distance of an improvement group into conditions where the elements are distant from each other by a minimal distance of an improvement group,

calculating a difference between values of the objective function which occur before and after said average element moving and exchanging,

using said difference between values of the objective function which occur before and after said average element moving and exchanging as a value of fluctuation per element,

calculating a product of said fluctuation value and the area of an improvement group, and

using said product of the fluctuation value and the area of an improvement group as a redundancy function;

a third step including sub steps of selecting one of the elements at random and setting an improvement group of elements whose origin agrees with the selected element, wherein the number of elements in the improvement group is less than the total number of elements;

a fourth step including sub steps of;

calculating a value of the objective function of a current element placement,

changing the current element placement to a new element placement by performing at least one of exchange and movement of elements in the improvement group,

calculating a value of the objective function of the new element placement,

calculating a difference between the values of the objective functions of the current element placement and the new element placement,

calculating a degree of redundancy on the basis of a product of the concentration parameter and a value of the redundancy function which corresponds to the placement of the improvement group,

judging whether or not the objective function value difference is greater than the degree of redundancy,

rejecting the new element placement and maintaining the current element placement when the objective function value difference is greater than the degree of redundancy,

accepting the new element placement when the objective function value difference is not greater than the degree of redundancy, and

reiterating said sub steps of the fourth step a number of times which agrees with the iteration number of improvement for each improvement group,

wherein said third step and said fourth step correspond to a whole element placement improving process;

a fifth step including sub steps of;

reiterating the whole element placement improving process a number of times which agrees with the iteration number of improvement for all elements,

calculating an average of values of the objective function which occur before said reiterating of the whole element placement improving process and calculating an average of the values of the objective function which occur after said reiterating of the whole element placement improving process,

judging whether or not the objective function value average which occurs after said reiterating of the whole element placement improving process is smaller than an average of the objective function values which occur before said reiterating of the whole element placement improving process,

further repeating the whole element placement improving process a number of times which agrees with the iteration number of improvement for all elements when the objective function value average which occurs after said reiterating of the whole element placement improving process is smaller than the objective function value average which occurs before said reiterating of the whole element placement improving process, and

performing a sixth step when the objective function value average which occurs after said reiterating of the whole element placement improving process is not smaller than the objective function value average which occurs before said reiterating of the whole element placement improving process;

said sixth step of multiplying a current number of elements in an improvement group by the concentration parameter to change the current number of elements in the improvement group into a new number of elements in the improvement group;

a seventh step including sub steps of;

judging whether or not the new number of elements is greater than the smallest number of elements in an improvement group,

calculating a value of the redundancy function related to the new number of elements and then preforming said third step when the new number of elements is greater than the smallest number of elements in an improvement group,

judging whether or not the value of the redundancy function is equal to 0 when the new number of elements is not greater than the smallest number of elements in an improvement group,

setting the value of the redundancy function to 0 and then performing the third step when the value of the redundancy function is not equal to 0, and

performing an eighth step when the value of the redundancy function is equal to 0;

said eighth step of outputting a finally-obtained element placement which corresponds to an optimal element placement satisfying the circuit functionality and producing a smaller chip size; and

a ninth step of organizing the elements of the integrated circuit chip in accordance with the finally-obtained element placement thus reducing the production cost of the integrated circuit chip.

4. The method of claim 3 wherein said third step comprises:

exchanging an element with the selected element at the origin of the improvement group to change the element placement;

calculating a value of the objective function of the element placement which occurs before said exchanging related to the origin element;

calculating a value of the objective function of the element placement which occurs after said exchanging related to the origin element;

calculating a difference between the objective function values which occur before and after the exchanging related to the origin element;

comparing a predetermined reference value and said difference between the objective function values which occur before and after the exchanging related to the origin element; and

forming the improvement group of elements from a group of elements in which said difference between the objective function values which occur before and after the exchanging related to the origin element is equal to or less than the predetermined reference value.

5. An apparatus for optimizing a physical organization of a plurality of mutually-related elements of an integrated circuit chip to establish a resulting chip size and performance, wherein the element organization is gradually changed toward an objective specification of circuit functionality with minimum production cost by local changes of the element organization, the apparatus including a programmed computer comprising:

first program means for defining an objective function whose value depends on a degree of a nearness of a particular element organization of a plurality of possible element organizations to an objective specification of circuit functionality with minimum production cost,

said first program means further defining an iteration number of improvement for each improvement group of elements in each of which several types of element organization could be generated, an iteration number of improvement for all elements of any improvement group, an initial number of elements in each improvement group, a smallest number of elements which can be improved in each improvement group, a total number of elements equal to said plurality of elements, and a concentration parameter that controls a group redundancy and a number of elements in each successive improvement group, and

said first program means generating an initial element organization;

second program means for performing at least one of random exchange and movement of elements in the initial element organization, calculating a fluctuation in a value of the objective function which responds to said random exchange and movement, calculating a value of said fluctuation which results from an execution of one time of said random exchange and movement, calculating a product of said fluctuation value and the number of elements in an improvement group, and using said product of the fluctuation value and the number of elements in an improvement group as a redundancy function;

third program means for selecting one of the elements at random and setting an improvement group of elements whose origin agrees with the selected element, wherein the number of elements in the improvement group is less than the total number of elements;

fourth program means for calculating a value of the objective function of a current element organization, changing the current element organization to a new element organization by performing at least one of exchange and movement of elements in the improvement group, calculating a value of the objective function of the new element organization, calculating a difference between the values of the objective functions of the current element organization and the new element organization, calculating a degree of redundancy on the basis of a product of the concentration parameter and a value of the redundancy function which corresponds to the organization of the improvement group, judging whether or not the objective function value difference is greater than the degree of redundancy, rejecting the new element organization and maintaining the current element organization when the objective function value difference is greater than the degree of redundancy, accepting the new element organization when the objective function value difference is not greater than the degree of redundancy, and reiterating said functions of the fourth program means a number of times which agrees with the iteration number of improvement for each improvement group, wherein said third program means and said fourth program means perform a whole element organization improving process;

fifth program means for reiterating the whole element organization improving process a number of times which agresss with te iteration number of improvement for all elements, calculating a value of the objective function which occurs after said reiterating of the whole element organization improving process, judging whether or not the objective function value which occurs after said reiterating of the whole element organization improving process is smaller than the objective function value which occurs before said reiterating of the whole element organization improving process, further repeating the whole element organization improving process a number of times which agress with the iteration number of improvement for all elements when the objective function value which occurs after said reiterating of the whole element organization improving process is smaller than the objective function value which occurs before said reiterating of the whole element organization improving process, and causing operation of a sixth program means when the objective function value which occurs after said reiterating of the whole element organization improving process is not smaller than the objective function value which occurs before said reiterating of the whole element organization improving process;

said sixth program means for multiplying a current number of elements in an improvement group by the concentration parameter to chnage the current number of elements in the improvement group into a new number of elements in the improvement group;

seventh program means for judging whether or not the new number of elements is greater than the smallest number of elements in an improvement group, calculating a value of the redundancy function related to the new number of elements and then causing operation of said third program means when the new number of elements is greater than the smallest number of elements in an improvement group, judging whether or not the value of the redundancy function is equal to 0 when the new number of elements is not greater than the smallest number of elements in an improvement group, setting the value of the redundancy function to 0 and then causing operation of said third program means when the value of the redundancy function is not equal to 0, and causing operation of an eight program means when the value of the redundancy function is equal to 0; and

said eighth program means for outputting a finally-obtained element organization which corresponds to an optimal element organization satisfying the circuit functionality and producing a smaller chip size, thereby organizing the elements of the integrated circuit chip in accordance with the finally-obtained element organization thus reducing the production cost of the integrated circuit chip.

6. An apparatus for optimizing a placement of a plurality of inter-related elements of an integrated circuit chip wherein degrees of the inter-relationship between the elements are represented by distances between the elements, and the element placement is gradually changed toward an objective specification of circuit functionality with minimum production cost by local changes of the element placement, the apparatus including a programmed computer comprising:

first program means for defining an objective function whose value depends on the distances between the elements and on a degree of a nearness of a particular element placement to an objective specification of circuit functionality with minimum production cost,

said first program means further defining an iteration number of improvement for each improvement group of elements in each of which several types of element placement could be generated, an iteration number of improvement for all elements of any improvement group, an initial number of elements in each improvement group, a smallest number of elements which can be improved in each improvement group, a total number of elements equal to said plurality of elements, and a concentration parameter that controls a group redundancy and a number of elements in each successive improvement group, and

said first program means generating an initial element placement;

second program means for moving and exchanging elements having average relations therebetween so that the elements are changed from conditions where the elements are distant from each other by a maximal distance of an improvement group into conditions where the elements are distant from each other by a minimal distance of an improvement group, calculating a difference between values of the objective function which occur before and after said average element moving and exchanging, using said difference between values of the objective function which occur before and after said average element moving and exchanging as a value of fluctuation per element, calculating a product of said fluctuation value and the area of an improvement group, and using said product of the fluctuation value and the area of an improvement group as a redundancy function;

third program means for selecting one of the elements at random and setting an improvement group of elements whose origin agrees with the selected element, wherein the number of elements in the improvement group is less than the total number of elements;

fourth program means for calculating a value of the objective function of a current element placement, changing the current element placement to a new element placement by performing at least one of exchange and movement of elements in the improvements group, calculating a value of the objective function of the new element placement, calculating a difference between the values of the objective functions of the current element placement and the new element placement, calculating a degree of redundancy on the basis of a product of the concentration parameter and a value of the redundancy function which corresponds to the placement of the improvement group, judging whether or not the objective function value difference is greater than the degree of redundancy, rejecting the new element placement and maintaining the current element placement when the objective function value difference is greater than the degree of redundancy, accepting the new element placement when the objective function value difference is not greater than the degree of redundancy, and reiterating said functions of the fourth program means a number of times which agrees with the iteration number of improvement for each improvement group, wherein said third program means and said fourth program means perform a whole element placement improving process;

fifth program means for reiterating the whole element placement improving process a number of times which agrees with the iteration number of improvement for all elements, calculating an average of values of the objective function which occurs before said reiterating of the whole element placement improving process and calculating an average of the values of the objective function which occur after said reiterating of the whole element placement improving process, judging whether or not the objective function value average which occurs after said reiterating of the whole element placement improving process is smaller than an average of the objective function values which occur before said reiterating of the whole element placement improving process, further repeating the whole element placement improving process a number of times which agrees with the iteration number of improvement for all elements when the objective function value average which occurs after said reiterating of the whole element placement improving process is smaller than the objective function value average which occurs before said reiterating of the whole element placement improving process, and causing operation of a sixth program means when the objective function value average which occurs after said reiterating of the whole element placement improving process is not smaller than the objective function value average which occurs before said reiterating of the whole element placement improving process;

said sixth means for multiplying a current number of elements in an improvement group by the concentration parameter to change the current number of elements in the improvement group into a new number of elements in the improvement group;

seventh program means for judging whether or not the new number of elements is greater than the smallest number of elements in an improvement group, calculating a value of the redundancy function related to the new number of elements and then causing operation of said third means when the new number of elements is greater than the smallest number of elements in an improvement group, judging whether or not the value of the redundancy function is equal to 0 when the new number of elements is not greater than the smallest number of elements in an improvement group, setting the value of the redundancy function to 0 and then causing operation of said third program means when the value of the redundancy function is not equal to 0, and causing operation of an eighth program means when the value of the redundancy function is equal to 0; and

said eighth program means for outputting a finally-obtained element placement which corresponds to an optimal element placement satisfying the circuit functionality and producing a smaller chip size, thereby organizing the elements of the integrated circuit chip in accordance with the finally-obtained element placement thus reducing the production cost of the integrated circuit chip.