Automated positioning of relative instances along a given dimension

• US 6,363,518 B1
• Filed: 08/06/1996
• Issued: 03/26/2002
• Est. Priority Date: 11/04/1993
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Lee, Tsu-Chang
• Primary Examiner(s): STAMBER, ERIC W
• Application Number:
  US08/692,612
• Time in Patent Office: 2,058 Days
• Field of Search: 364/578, 364/488, 364/489, 364/490, 364/491, 364/468.05, 364/468.06, 395/207, 395/208, 395/209, 703/1, 716/2, 716/8, 716/10
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A computer-automated tool re-positions an instance relative to another instance along a given dimension. First, positions of both instances along the given dimension are determined. Then, a modified position is determined for one instance according to a convex function, which defines a global minimum solution between the initial instance positions.

Claims

1. In a computer based system comprising a storage device coupled to a processor, the method for modifying a distance between a plurality of objects, each of the objects representing one of blocks, components, and circuit cells in a physical circuit design, the method comprising the steps of:

(a) determining a position of a first object and a second object of said plurality of objects in a physical circuit design;

(b) selecting an axis in said physical circuit design;

(c) determining a first limitation and a second limitation between said first object and said second object, said first limitation representing an absolute minimum separation between said first object and said second object along said selected axis, said second limitation representing a desired minimum separation between said first object and said second object along said selected axis;

(d) determining if said plurality of objects form an over-constrained system, said over-constrained system occurring if said positions of said plurality of objects cause a violation of one of said first limitation and said second limitation;

(e) automatically determining a first value representing a degree of said violation for each of said violations determined in step (d), including the steps of;

(1) obtaining a function from one of a user and the storage device, said function defining a convex function representing a potential energy of a hypothetical elastic device coupled between said first object and said second object along said selected axis; and

(2) determining, in the processor, said first value as a global minimum solution for said function;

(f) determining a second value representing a combination of all of said first values determined in step (e);

(g) repeating steps (b)-(f) for a plurality of axes; and

(h) determining a third value representing a combination of each of said second values associated with each of said selected axes as determined in step (f), said third value representing a distance between each of the plurality of objects;

(i) modifying the distance between said first object and said second object.

2. The method of claim 1, further comprising the steps of:

(j) repeating steps (a)-(i); and

(k) modifying the distance between said first object and said second object if said third value associated with said modified first objects is more optimal than said third value associated with said unmodified objects.

3. The method of claim 1, after step (b), further comprising the steps of:

determining a third limitation and a fourth limitation between said first object and a third of said plurality of objects, said third limitation representing an absolute minimum separation between said first object and said third object along said selected axis, said fourth limitation representing a desired minimum separation between said first object and said third object along said selected axis; and

determining a fifth limitation and a sixth limitation between said second object and said third object, said fifth limitation representing an absolute minimum separation between said second object and said third object along said selected axis, said sixth limitation representing a desired minimum separation between said second object and said third object along said selected axis.

4. A computer readable memory capable of directing a computer to operate in accordance with the method of claim 1.

5. A computer program embodied in a tangible medium and capable of being read by a computer, for performing the method of claim 1.

6. In a computer based system comprising a storage device coupled to a processor, the method for modifying a distance between a plurality of objects, each of the objects representing one of blocks, components, and circuit cells in a physical circuit design, the method comprising the steps of:

(a) determining a position of a first object and a second object of said objects in a physical circuit design;

(b) selecting an axis in said physical circuit design;

(c) determining a first limitation and a second limitation between said first object and said second object, said first limitation representing an absolute minimum separation between said first object and said second object along said selected axis, said second limitation representing a desired minimum separation between said first object and said second object along said selected axis;

(d) determining if said plurality of objects form an over-constrained system, said over-constrained system occurring if said positions of said plurality of objects cause a violation of one of said first limitation and said second limitation;

(e) automatically determining a first value representing a degree of said violation for each of said violations determined in step (d), including the steps of;

(1) obtaining a function from one of a user and the storage device, said function defining a concave function representing a potential energy of a hypothetical elastic device coupled between said first object and said second object along said selected axis;

(2) determining, in the processor, said first value as a global maximum solution for said function. (f) determining a second value representing a combination of all of said first values determined in step (e);

(g) repeating steps (b)-(f) for a plurality of axes; and

(h) determining a third value representing a combination of each of said second values associated with each of said selected axes as determined in step (f), said third value representing a distance between each of the plurality of objects;

(i) modifying the distance between said first object and said second object.

7. The method of claim 6, further comprising the steps of:

(j) repeating steps (a)-(i); and

(k) modifying the distance between said first object and said second object if said third value associated with said modified first objects is more optimal than said third value associated with said unmodified objects.

8. The method of claim 6, after step (b), further comprising the steps of:

determining a third limitation and a fourth limitation between said first object and a third of said plurality of objects, said third limitation representing an absolute minimum separation between said first object and said third object along said selected axis, said fourth limitation representing a desired minimum separation between said first object and said third object along said selected axis; and

determining a fifth limitation and a sixth limitation between said second object and said third object, said fifth limitation representing an absolute minimum separation between said second object and said third object along said selected axis, said sixth limitation representing a desired minimum separation between said second object and said third object along said selected axis.

9. A computer readable memory capable of directing a computer to operate in accordance with the method of claim 6.