Minimizing the interconnection cost of electronically linked objects

• US 5,251,147 A
• Filed: 06/20/1989
• Issued: 10/05/1993
• Est. Priority Date: 06/20/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Finnerty, James L.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/369,655
• Time in Patent Office: 1,568 Days
• Field of Search: 364/488, 364/4889, 364/490, 364/491
• US Class Current: 716/101
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The interconnection costs of electronically linked objects is minimized by the successive partitioning of the initial logic design. The partitioning is based upon the electrical properties of the drivers and loads of the linked objects forming the design. Further, time critical connections are weighted so as to further minimize interconnection cost. A further method refines the result of the successive partitioning by calculating each linked object'"'"'s contribution to the overall delay of the design. Both the design of device function and timing and the physical realization of the electronically linked objects are solved jointly to make use of the information available from the logical and physical designs.

Claims

1. A method for operating a programmable computing apparatus to minimize the interconnection cost between ports of a plurality of models forming a logic design to be placed on a supporting structure having a plurality of placement slots;

the method comprising the steps of;

a. bisecting an initial assignment of models to the plurality of placements slots on the supporting structure, to obtain a first and a second partition;

b. computing a partial gain for each of said models based upon the electrical properties of said models and the critical and noncritical delays associated with interconnections;

c. ordering said partial gains for the models in the first partition in a first data structure and the models in the second partition in a second data structure;

d. swapping a pair of said placement slots, one from each of the first and second data structures, to obtain a total maximum gain;

e. storing the swapped pair and a cumulative gain for the logic design in a third data structure and removing the swapped pair from their respective first and second data structures;

f. repeating steps (b)-(e) for a predetermined number of the placement slots; and

g. replaying the swaps stored in the third data structure to restore the logic design solution to its point of maximum cumulative gain.

2. A method according to claim 1 further comprising the steps of:

h. randomizing the initial assignment of models to placement slots; and

i. repeating steps (a)-(h) a set number of times to determine a new logic design solution with each pass through the steps.

3. A method according to claim 2 further comprising the steps of:

j. storing each of said logic design solutions; and

k. implementing the predefined selection criteria of said stored logic design solutions.

4. A method according to claim 2 further comprising the steps of:

j. repeating steps (a)-(i) separately for each of the partitions to further bisect the first and second partitions.

5. A method according to claim 4 further comprising the step of:

k. repeating steps (a)-(j) in a breadth-first manner until each partition includes less than a predefined number of placement slots.

6. A method according to claim 5 wherein for each resulting partition having less than a predefined number of placement slots, the method further comprises the steps of:

l. locating a single port in a signal in said partition;

m. determining the two nearest ports in said signal and calculating a signal delay for each connection between said single port and said two nearest ports;

n. calculating the single port'"'"'s delay contribution as the sum of the two lesser signal delays minus the greater signal delay obtained from step (m);

o. repeating steps (m) and (n) for a randomly different initial location of said single port; and

p. placing said single port in the placement slot wherein said single port'"'"'s contribution to delay is a minimum.

7. A method according to claim 6 wherein steps (m)-(o) are repeated for all of said ports on the model and said model is placed in the placement slot wherein the model'"'"'s contribution to delay is minimized.

8. A method according to claim 2 wherein the step of replaying the swaps stored in the third data structure is performed in a reverse order.

9. A method according to claim 1 wherein the apparatus'"'"' operating time is a linear function with respect to the number of ports on said models.

10. A method according to claim 1 wherein said step of swapping further comprises the steps of:

a. choosing the pair of placement slots, one from each of said first and second data structures, that have the highest partial gain in their respective data structures to determine if they produce the total maximum gain;

b. calculating a swapped gain by determining the interconnection cost change that would occur by swapping said pair of placement slots;

c. setting said swapped gain as a bounding limit for choosing the pair of placement slots to achieve the total maximum gain.

d. repeating steps (a) and (b) for another pair of placement slots having the same or the next highest partial gains;

e. resetting the bounding limit if said new swapped gain is greater than the old bounding limit; and

f. repeating steps (a)-(e) until the sum of the partial gains of the pair of placement slots is less than or equal to said bounding limit and then choosing said pair which produced the current bounding limit to have the total maximum gain.

11. A method according to claim 1 wherein an empty placement slot has a partial gain equaling a predetermined number.

12. A method according to claim 1 further comprising:

h. providing a plurality of signal counters; and

i. tracking the swaps performed by steps (a)-(g) with said plurality of signal counters.

13. A method according to claim 1 wherein the interconnection of the critical delays is given a greater weight than a non-critical delay.

14. A method for operating a programmable computing apparatus to minimize interconnection cost among models in a partition, the method comprising the steps of:

a. locating a single port in a signal in said partition;

b. determining the two nearest ports in said signal and calculating a signal delay for each connection between said single port and said two nearest ports;

c. calculating the single port'"'"'s delay contribution as the sum of the two lesser signal delays minus the greater signal delay obtained from step (b);

d. repeating steps (b) and (c) for a randomly different initial location of said single port; and

e. placing said single port in the placement slot wherein said single port'"'"'s contribution to delay is a minimum.

15. A method according to claim 14 wherein steps (b)-(d) are repeated for all of said ports on the model and said model is placed in the placement slot wherein the model'"'"'s contribution to delay is minimized.

16. A method according to claim 15 wherein said apparatus'"'"' operating time is linear in the number of ports in the signal.