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

• US 8,918,750 B1
• Filed: 12/06/2013
• Issued: 12/23/2014
• Est. Priority Date: 12/06/2013
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Moffitt, Michael David
• Primary Examiner(s): Chiang, Jack
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US14/099,021
• Time in Patent Office: 382 Days
• Field of Search: 716/122
• US Class Current: 716/122
• 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 system comprising a processor for executing program instructions coupled to a memory for storing the program instructions, wherein the program instructions are program instructions for placing objects in partitions of a physical layout, and wherein the program instructions comprise:

program instructions for first determining requirements vectors corresponding to the objects, wherein the requirements vectors contain values specifying requirements of the object in multiple dimensions; and

program instructions for assigning the objects to the partitions of the physical layout by implementing a bin-packing algorithm 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.

2. The computer system of claim 1, wherein the program instructions for the bin-packing algorithm terminate 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 computer system of claim 2, wherein the program instructions for detecting include program instructions for second determining that a requirements vector for an excluded object can be satisfied by the current individual without excluding another object assigned to the current individual partition in the current partial solution.

4. The computer system of claim 1, wherein the program instructions implementing the bin-packing algorithm comprise:

program instructions that, for the current partial solution, second determine if any objects remain to be assigned to the partitions;

program instructions for selecting an unassigned object in response to the program instructions that second determine having determined that objects remain to be assigned to the partitions;

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

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

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

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

5. The computer system of claim 4, wherein the program instructions further comprise program instructions for 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 prior to the second determining if any objects remain to be assigned to the partitions, and wherein the program instructions for selecting, first recursively applying and second recursively applying are not executed if the program instructions for fifth determining determine that the requirements vector cannot be satisfied by the current partition or that any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions.

6. The computer system 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.

7. The computer system of claim 1, wherein the partitions are physical storage locations, and wherein the objects are objects to be stored.

8. A computer program product comprising a computer-readable storage device storing program instructions for placing objects in partitions of a physical layout, wherein the program instructions comprise program instructions for:

first determining requirements vectors corresponding to the objects, wherein the requirements vectors contain values specifying requirements of the object in multiple dimensions; and

assigning the objects to the partitions of the physical layout by implementing a bin-packing algorithm 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.

9. The computer program product of claim 8, wherein the program instructions that implement the bin-packing algorithm terminate 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.

10. The computer program product of claim 9, wherein the program instructions for detecting comprise program instructions for 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.

11. The computer program product of claim 8, wherein the program instructions for implementing the bin-packing algorithm comprise program instructions for:

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

selecting an unassigned object in response to having determined that objects remain to be assigned to the partitions;

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

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

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

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

12. The computer program product of claim 11, wherein the program instructions further comprise program instructions for 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 prior to the second determining if any objects remain to be assigned to the partitions, and wherein the program instructions for selecting, first recursively applying and the second recursively applying are not executed if the program instructions for fifth determining determine that the requirements vector cannot be satisfied by the current partition or that any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions.

13. The computer program product of claim 8, wherein the partitions are physical layout resources of an electronic device, and wherein the objects are interconnecting conductors of the electronic device.