MACHINE PROCESS FOR POSITIONING INTERCONNECTED COMPONENTS TO MINIMIZE INTERCONNECTING LINE LENGTH

• US 3,681,782 A
• Filed: 12/02/1970
• Issued: 08/01/1972
• Est. Priority Date: 12/02/1970
• Status: Expired due to Term

• Current Assignee: Scanlon F. Taylor
• Original Assignee: Scanlon F. Taylor
• Inventors: Scanlon, F. Taylor
• Primary Examiner(s): Ruggiero, Joseph F.
• Application Number:
  US05/094,464
• Time in Patent Office: 608 Days
• Field of Search: 235/150,150.1,151,151.1 444/1
• US Class Current: 700/56
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A machine process is disclosed in which components of an interconnected network are simultaneously repositioned and their interconnections simultaneously reordered to minimize interconnecting line length. The repositioning and reordering process is performed first on nets having two components, then on nets having three components, etc., until all nets have been processed. The components are repositioned in accordance with a formula which allows large movement of interconnected components towards each other but prevents overshoot of such components. In this way, the components can be rapidly rearranged to achieve an efficient interconnecting pattern.

Claims

1. A machine process for positioning interconnected modules on a planar field defined by a Cartesian coordinate system having X and Y axes by use of a programmed digital computer having stored in its internal memory a program enabling the computer to perform the following steps:

a. randomly assigning modules to locations on the field, b. calculating an attraction vector for each module of every pair of interconnected modules, said vector being directed from the module in question toward the module to which it is connected and having a magnitude proportional to (i) the distance separating the two modules, and (ii) the number of lines connecting the two modules, c. calculating the X- and Y-components of each attraction vector, d. deleting from each module, pairs of oppositely directed vector components, beginning with the pair having the greatest magnitude in their respective directions and continuing with the pair having the next greatest magnitude, etc. until all such pairs have been deleted, e. calculating a repulsion vector for each module of every pair of unconnected modules, said repulsion vector being directed from the module in question in a direction opposite that in which the other module of the pair lies and having a magnitude inversely proportional to the distance separating the two modules, f. calculating for each module a resultant vector from the module'"'"''"'"'s attraction vectors and repuslion vectors, and g. simultaneously repositioning said modules by moving each in the direction of its resultant vector by an amount proportional to the magnitude of its resultant vector.

2. A process as in claim 1 wherein the magnitude of said attraction vector equals with negative values being set equal to zero.

3. A process as in claim 2 wherein each of said modules is moved by an amount equal to

4. A process as in claim 3 wherein the sequence of steps in said process are iterated not more than a predetermined number of times m.

5. A process as in claim 4 wherein the steps of said process are performed first on nets having two pins, then on nets having three pins, etc., until all nets have been processed.

6. A process as in claim 5 further comprising the steps of h. calculating the total line length of the interconnection of the modules, i. terminating the process if the average total line length for the past z iterations is within e percentage of the total line length obtained for the most recent iteration, where z and e are predetermined values, j. generating an error indication if the average total line length for the past z iterations is not within e percentage of the total line length obtained for the most recent iteration and either (1) the average total line length for the past z iterations is less than the total line length obtained for the most recent iteration, or (2) the number of iterations completed equals m, and k. repeating steps (b) through (j) if the average total line length for the past z iterations is not within e percentage of and is not less than the total line length obtained for the most recent iteration and if the number of iterations completed is less than m.

7. A process as in claim 6 further including the steps of l. calculating an attraction vector in accordance with step (b) for each module of every pair of modules whose centers are separated by a distance of more than one-half the sum of the widths of the pair, m. calculating an overlap vector for each module of every pair of modules whose centers are separated by a distance of less than one-half the sum of the widths of the pair, said overlap vector being directed from the module in question in a direction opposite that in which the other module of the pair lies and having a magnitude inversely proportional to the distance separating the pair, n. calculating for each module a resultant vector from the module'"'"''"'"'s attraction vectors and overlap vectors, o. performing step (g).

8. A process as in claim 7 wherein the magnitude of said overlap vector equals

9. A process as in claim 8 further comprising the steps of p. calculating a field boundary vector for each module whose center point is within a distance equal to one-half the width of the module from the edge of the field or whose center point is not on the field, said field boundary vectors being directed from the module in question away from the field edge and perpendicular thereto and having a magnitude of if the center point of the module is still on the board, and said field boundary vectors being directed from the module in question toward the field edge and perpendicular thereto and having a magnitude of if the center of the module is not on the field, q. performing steps (l) and (m), r. calculating for each module a resultant vector from the module'"'"''"'"'s field boundary vectors, attraction vectors, and overlap vectors, and s. performing step (o).

10. A process as in claim 1 further comprising the step of reordering the connections of said modules in accordance with predetermined connection rules if the total line length is reduced by such reordering.

11. A machine process for positioning interconnected modules on a planar field defined by a Cartesian coordinate system having X and Y axes by use of a programmed digital computer having stored in its internal memory a program enabling the computer to perform the following steps:

a. designating as a fixed module each module whose center point is to have predetermined X and Y coordinates on the field, b. designating as a fixed X module each module whose center point is to have a predetermined X coordinate on the field, c. designating as a fixed Y module each module whose center point is to have a predetermined Y coordinate on the field, d. designating as a free module each module which may be assigned any position on the field, e. designating each module having a nonlimited length in one dimension as a free bar module if the module may be assigned any position on the field, as a fixed X bar module if the center line along the nonlimited length of the module has a predetermined X coordinate on the field, and as A fixed Y bar module if the center line along the nonlimited length of the module has a predetermined Y-coordinate on the field, f. representing each void on said planar field as a module whose dimensions correspond to the dimensions of the void, g. randomly assigning field coordinates to each free module, randomly assigning a Y field coordinate to each fixed X module, randomly assigning an X field coordinate to each fixed Y module, randomly assigning an X field coordinate to each free bar module extending in the Y direction, and randomly assigning a Y field coordinate to each free bar module extending in the X direction, Y h. calculating an attraction vector for each module of every pair of interconnected modules, said vector being directed from the module in question toward the module to which it is connected, said vector having a magnitude q proportional to (1) the distance separating the two modules and (2) the number of lines connecting the two modules if said pair of modules are free modules and having X and Y components of magnitude x1 and y1 respectively, said vector'"'"''"'"'s X component having a magnitude of zero if said module in question is a fixed module, a fixed X module, or a fixed X bar module and having a magnitude of 2x1 if said module in question is a fixed module, a fixed Y module, or a free bar module and said other module is a fixed module, a fixed X module or a fixed X bar module, and said vector'"'"''"'"'s Y component having a magnitude of zero if said module in question is a fixed module, a fixed Y module, or a fixed Y bar module and having a magnitude of 2y1 if said module in question is a free module, a fixed X module, or a free bar module and said other module is a fixed module, a fixed Y module, or a fixed Y bar module, i. deleting from each module pairs of oppositely directed vector components, beginning with the pair having the greatest magnitude in their respective directions and continuing with the pair having the next greatest magnitude, etc. until all such pairs have been deleted, j. calculating a repulsion vector for each module of every pair of unconnected modules, said repulsion vector being directed from the module in question away from the other module of the pair, said vector having a magnitude r inversely proportional to the distance separating the two modules if said pair of modules are free modules and having X and Y components of magnitude x2 and y2 respectively, said repulsion vector'"'"''"'"'s X component having a magnitude of zero if said module in question is a fixed module, a fixed X module, or a fixed X bar module and having a magnitude of 2x2 if said module in question is a free module, a fixed Y module, or a free bar module and said other module is a fixed module, a fixed X module, or a fixed X bar module, and said repulsion vector'"'"''"'"'s Y component having a magnitude of zero if said module in question is a fixed module, a fixed Y module, or a fixed Y bar module and having a magnitude of 2y2 if said module in question is a free module, a fixed X module, or a free bar module and said other module is a fixed module, a fixed Y module, or a fixed Y bar module, k. calculating for each module a resultant vector from the module'"'"''"'"'s attraction vectors and repulsion vectors, and

12. A process as in claim 11 wherein the magnitude q of said attraction vector equals with negative values being set equal to zero.

13. A process as in claim 12 wherein each of said modules is moved by an amount equal to

14. A process as in claim 13 wherein the sequence of steps in said proceSs are iterated not more than a predetermined number of times m.

15. A process as in claim 14 wherein the steps of said process are performed on nets having n pins, where n is initially set equal to two and then successively incremented by one after each iteration of the process until all nets have been processed.

16. A process as in claim 15 further comprising the steps of m. calculating the total line length of the interconnections of the modules, n. terminating the process if the average total line length for the past z iterations is within e percentage of the total line length obtained for the most recent iteration, where z and e are predetermined values, o. generating an error indication if the average total line length for the past z iterations is not within e percentage of the total line length obtained for the most recent iteration and either (1) the average total line length for the past z iterations is less than the total line length obtained for the most recent iteration, or (2) the number of iterations completed equals m, and p. repeating steps (h) through (o) if the average total line length for the past z iterations is not within e percentage of and is not less than the total line length obtained for the most recent iteration and if the number of iterations completed is less than m.

17. A process as in claim 16 further including the steps of q. calculating an attraction vector in accordance with step (h) for each module of every pair of modules which are separated by a distance of more than one-half the sum of the widths of the pair, r. calculating an overlap vector for each module of every pair of modules whose centers are separated by a distance of less than one-half the sum of the widths of the pair, said overlap vector being directed from the module in question away from the other module of the pair, said overlap vector having a magnitude s inversely proportional to the distance separating the pair if said pair of modules are free modules and having X and Y components of magnitude x3 and y3 respectively, said overlap vectors'"'"''"'"'s X component having a magnitude of zero if said module in question is a fixed module, a fixed X module, or a fixed X bar module and having a magnitude of 2x3 if said module in question is a free module, a fixed Y module, or a free bar module and said other module is a fixed module, a fixed X module, or a fixed X bar module, and said overlap vector'"'"''"'"'s Y components having a magnitude of zero if said module in question is a fixed module, fixed Y module, or a fixed Y bar module and having a magnitude 2y1 if said module in question is a free module, a fixed X module, or a free bar module and said other module is a fixed module, a fixed Y module or a fixed Y bar module, s. calculating for each module a resultant vector from the modules attraction vectors and overlap vectors, t. performing step (1).

18. A process as in claim 17 wherein the magnitude s of said overlap vector equals

19. A process as in claim 18 further comprising the steps of u. calculating a field boundary vector for each module whose center point is within a distance equal to one-half of the width of the module of the edge of the field or whose center point is not on the field, said field boundary vector being directed from the module in question away from the field edge and perpendicular thereto if the center point of the module is on the field and toward the field edge and perpendicular thereto if the center point of the module is not on the field, said field boundary vector having a magnitude t proportional to the distance from the center point of the module to the field edge if the center point is not on the field and if the module is a free module, and having a magnitude u inversely proportioNal to the distance from the center point of the module to the field edge if the center point is still on the field and if the module is a free module, said field boundary vector having X and Y components of magnitude x4 and y4 respectively, said field boundary vector'"'"''"'"'s X component having a magnitude of zero if the module in question is a fixed module, a fixed X module, or a fixed X bar module and having a magnitude of 2x4 if said module in question is a free module, a fixed Y module, or a free bar module, and said field boundary vector'"'"''"'"'s Y component having a magnitude of zero if said module in question is a fixed module, a fixed Y module, or a fixed Y bar module and having a magnitude of 2y4 if said module in question is a free module, a fixed X module, or a free bar module, v. performing steps (q) and (r), w. calculating for each module a resultant vector from the module'"'"''"'"'s field boundary vector, attraction vectors, and overlap vectors, and x. performing step (t).

20. A process as in claim 19 wherein the magnitude t equals