Progressive insertion placement of elements on an integrated circuit
First Claim
1. A method of determining the placement of a plurality of interrelated elements to be placed in fixed physical location and thereafter interconnected to form a functional integrated system, said method comprising the steps of:
- a. randomly determining for each of a plurality of elements a respective different one of plural physical locations to establish a preliminarily determined location for each element, said randomly determining being an intermediate placement determining;
b. recording said randomly determined locations;
c. scoring a placement interconnection score for all of the elements according to said randomly determined locations, said score being a first score;
d. establishing a predetermined order of placement for each element;
sequentially placing, according to said predetermined order, an element in all available locations, scoring said placement with respect to all other elements based on the last recorded locations of said all other elements, and recording the placement of said placed element in the location obtaining the best score;
f. repeating step "e" for all said elements;
g. if the final score of steps "e" and "f" is better than said first score, in an intermediate placement determining, determining the placement of all said circuit elements according to the last occurring recorded placement of steps "e" and "f" and setting said first score to said final score, otherwise maintaining the current intermediate determined placement; and
h. repeating steps "e", "f" and "h" until the final score in step "g" is no better than said first score for a predetermined number of sequential repetitions, the intermediate determined placements at the end of this step being the finally determined placements.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of placing circuit elements in an integrated circuit. The chip area is divided into a grid. In an initial pass, the elements are randomly placed in the grid locations, and these placements are recorded. Thereafter, the elements are sequentially replaced in each of the grid locations, and a score is calculated for the wiring interconnections to the remaining elements as they were last recorded. The placement yielding the best score is recorded for that element. This placement is repeated for each of the elements. Once all the elements have been replaced, a final score is compared with the last best score. If the recent final score is better, the placements associated with that score are saved as the best placements. Then the process of replacement is repeated until a given number of iterations fails to yield a better score.
-
Citations
7 Claims
-
1. A method of determining the placement of a plurality of interrelated elements to be placed in fixed physical location and thereafter interconnected to form a functional integrated system, said method comprising the steps of:
-
a. randomly determining for each of a plurality of elements a respective different one of plural physical locations to establish a preliminarily determined location for each element, said randomly determining being an intermediate placement determining; b. recording said randomly determined locations; c. scoring a placement interconnection score for all of the elements according to said randomly determined locations, said score being a first score; d. establishing a predetermined order of placement for each element; sequentially placing, according to said predetermined order, an element in all available locations, scoring said placement with respect to all other elements based on the last recorded locations of said all other elements, and recording the placement of said placed element in the location obtaining the best score; f. repeating step "e" for all said elements; g. if the final score of steps "e" and "f" is better than said first score, in an intermediate placement determining, determining the placement of all said circuit elements according to the last occurring recorded placement of steps "e" and "f" and setting said first score to said final score, otherwise maintaining the current intermediate determined placement; and h. repeating steps "e", "f" and "h" until the final score in step "g" is no better than said first score for a predetermined number of sequential repetitions, the intermediate determined placements at the end of this step being the finally determined placements. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
Specification
-
- Resources
-
Current AssigneeInternational Business Machines Corporation
-
Original AssigneeInternational Business Machines Corporation
-
InventorsCarpenter, Kurt D., Jackson, Roger K., Lallier, Keith W.
-
Primary Examiner(s)Lall, Parshotam S.
-
Assistant Examiner(s)NOT, DEFINED
-
Application NumberUS06/800,569Time in Patent Office950 DaysField of Search364/491, 364/300, 364/489, 364/520, 364/488, 364/492US Class Current716/123CPC Class CodesG06F 30/392 Floor-planning or layout, e...
