Multi-dimensional computing and communication resource allocation using bin-packing with per-branch combination tries

• US 9,400,697 B2
• Filed: 06/09/2014
• Issued: 07/26/2016
• Est. Priority Date: 12/06/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Moffitt, Michael David
• Primary Examiner(s): Rashid, Wissam
• Application Number:
  US14/299,569
• Publication Number:
  US 20150160979A1
• Time in Patent Office: 778 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A recursive solution to a bin-packing algorithm provides efficient allocation of computing or communications resources to resource consumers in a computer or network system. The algorithm determines resource requirement vectors for the consumers that specify amounts of multiple resource types required for each consumer, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the resource consumers to corresponding groups of computing or communication resources by recursively exploring partial solutions that assign the consumers to the groups by extending the partial solutions via recursion until the requirements in the resource requirement vectors are met. The bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers.

Claims

1. A method of assigning a plurality of resource consumers to groups of computing or communications resources, the method comprising:

first determining resource requirement vectors corresponding to the plurality of resource consumers, wherein the resource vectors contain values specifying resource amounts for multiple types of required resources for the corresponding resource consumer; and

assigning the resource consumers to corresponding ones of the groups of computing or communication resources using a bin-packing algorithm that recursively explores partial solutions for assigning the resource consumers to individual ones of the groups of computing or communication resources in order to satisfy the resource requirement vectors for the plurality of resource consumers, wherein the bin-packing algorithm extends the partial solutions via nested recursion that descends via repetitive invocations of the bin-packing algorithm from within the bin-packing algorithm, wherein the nested recursion descends until the requirements in the resource requirement vectors are met by assignment of individual groups of the resources that are sufficient to satisfy the resource amounts for the multiple types specified in a corresponding resource requirement vector, wherein the bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers.

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

detecting that the current partial solution is covered by a dominant solution previously explored; and

in response to detecting that current partial solution is covered by a dominant solution previously explored, terminating the recursion of the current partial solution.

3. The method of claim 2, wherein the detecting is performed by second determining that a resource requirement vector for an excluded resource consumer can be satisfied by assignment to the current individual group without excluding another resource consumer assigned to 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 resource consumers remain to be assigned to the groups;

responsive to having determined that resource consumers remain to be assigned to the groups, selecting an unassigned resource consumer;

with the selected resource consumer assigned to the group corresponding to the current partial solution, first recursively applying the assigning of the resources to assign the remaining resource consumers other than the selected resource consumer;

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

responsive to having determined that the recursively applying did not generate a complete solution, fourth determining if the current group has an assigned resource consumer; and

responsive to having determined that the current group has an assigned resource consumer, with the selected resource consumer excluded from the group corresponding to the current partial solution, second recursively applying the assigning of the resources to assign the remaining resource consumers other than the selected resource consumer.

5. The method of claim 4, further comprising:

prior to the second determining if any resource consumers remain to be assigned to the groups, fifth determining if any resource consumer assigned to the current group has a resource requirement vector that cannot be satisfied by the current group or if any item excluded from assignment to the current group has a resource requirement vector that cannot be satisfied by a remaining one of the groups of computing or communication resources; and

responsive to having determined that the resource requirement vector cannot be satisfied by the current group or if any item excluded from assignment to the current group has a resource requirement vector that cannot be satisfied by a remaining one of the groups of computing or communication resources, not performing the selecting, the first recursively applying and the second recursively applying.

6. The method of claim 1, wherein the computing or communication resources are real or virtual hardware processing, communications or storage resources of a computer system, and wherein the resource consumers are software applications requiring the real or virtual hardware processing, communications or storage resources for execution.

7. The method of claim 1, wherein the computing or communication resources are communication resources within a computer network, and wherein the resource consumers are processing nodes requiring communications with other processing nodes.