Multi-dimensional physical arrangement techniques using bin-packing with per-branch combination tries

• US 9,183,342 B2
• Filed: 06/10/2014
• Issued: 11/10/2015
• Est. Priority Date: 12/06/2013
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: GlobalFoundries, Inc.
• Inventors: Moffitt, Michael David
• Primary Examiner(s): Chiang, Jack
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US14/300,688
• Publication Number:
  US 20150161317A1
• Time in Patent Office: 518 Days
• Field of Search: 716/122
• US Class Current: 1/1
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A recursive solution to a bin-packing algorithm provides efficient placement of objects in a physical layout. The algorithm determines requirement vectors for the objects that specify requirement for placement of the object in multiple dimensions, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the objects to physical partitions or “bins” by recursively exploring partial solutions that place the objects in the partitions by extending the partial solutions via recursion until the objects are placed. The bin-packing algorithm tests requirements vectors for remaining unassigned ones of the objects for both assignment and non-assignment to a current partition in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of objects.

Claims

1. A computer-performed method of placing objects in partitions of a physical layout, the method comprising:

within a computer system, first determining requirements vectors corresponding to the objects, wherein the requirements vectors contain values specifying requirements of the object in multiple dimensions;

assigning the objects to the partitions of the physical layout within a model of the physical layout using a bin-packing algorithm executed by the computer system that recursively explores partial solutions for assigning the objects to individual ones of the partitions in order to satisfy the requirements vectors for the objects, wherein the bin-packing algorithm extends the partial solutions via the recursion until the requirements in the requirements vectors are met by assignment of the corresponding object to partitions having sufficient resources in the multiple dimensions to meet the values specified in the requirements vectors, wherein the bin-packing algorithm tests requirements vectors of remaining unassigned ones of objects for both assignment and non-assignment to a current individual partition in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirements vectors for the objects; and

placing the objects within the physical layout according to the complete solution determined by the assigning.

2. The method of claim 1, wherein the bin-packing algorithm terminates the recursion of partial solutions that do not become the complete solution upon detecting that a partial solution being explored is covered by a dominant solution previously explored.

3. The method of claim 2, wherein the detecting is performed by second determining that a requirements vector for an excluded object can be satisfied by the current individual partition without excluding another object assigned to the current individual partition in the current partial solution.

4. The method of claim 1, wherein the bin-packing algorithm comprises:

for the current partial solution, second determining if any objects remain to be assigned to the partitions;

responsive to having determined that objects remain to be assigned to the partitions, selecting an unassigned object;

with the selected object assigned to the partition corresponding to the current partial solution, first recursively applying the assigning of the objects to assign the remaining objects other than the selected object;

third determining if the recursively applying generated a complete solution assigning the remaining objects;

responsive to having determined that the recursively applying did not generate a complete solution, fourth determining if the current partition has an included object; and

responsive to having determined that the current group has an included object, with the selected object excluded from the current partition, second recursively applying the assigning of the objects to assign the remaining objects other than the selected object.

5. The method of claim 4, further comprising:

prior to the second determining if any objects remain to be assigned to the partitions, fifth determining if any object placed in the current partition has a requirements vector that cannot be satisfied by the current partition or if any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions; and

responsive to having determined that the requirements vector cannot be satisfied by the current partition or if any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions, not performing the selecting, the first recursively applying and the second recursively applying.

6. The method of claim 1, wherein the partitions are physical layout resources of an electronic device, and wherein the objects are interconnecting conductors of the electronic device, and wherein the placing comprises fabricating the electronic device according to the complete solution.

7. The method of claim 1, wherein the partitions are physical storage locations, and wherein the objects are objects to be stored, and wherein the placing comprises placing the objects within the physical storage locations.