Domain-agnostic resource allocation framework

• US 9,753,778 B2
• Filed: 07/20/2012
• Issued: 09/05/2017
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Guha, Saikat, Bhagwan, Ranjita, Rai, Anshul
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): NAJEE-ULLAH, TARIQ S
• Application Number:
  US13/553,847
• Publication Number:
  US 20140025822A1
• Time in Patent Office: 1,873 Days
• Field of Search: 709226
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A resource allocation framework is described herein which allocates items (conceptualized as balls) to item-receiving slots (conceptualized as bins) in a domain-agnostic manner. A user instantiates the resource allocation framework to a particular allocation problem by generating a specification that describes the allocation problem in a declarative fashion. Among other features, the specification maps real-world entities to the balls and bins, and describes the constraints associated with the allocation problem. The specification also provides a utilization function that computes the consumption of resources for a proposed assignment of a particular ball to a particular bin. According to another aspect, the resource allocation framework uses many processing elements (e.g., GPU threads, CPU threads, etc.), operating in parallel, to attempt to find a solution to the allocation problem. In this search for a solution, the resource allocation framework operates in any combination of an explore mode and an exploit mode.

Claims

1. A computer-implemented method for allocating a set of items to a set of bins, comprising:

using a computing device for;

at a resource allocation framework that can be applied to different types of allocation problems, the resource allocation framework comprising one or more processing elements, receiving a specification that describes characteristics of a particular allocation problem, the specification comprising a mapping of real-world entities associated with the allocation problem to the set of items, a mapping of real-world entities associated with the allocation problem to the set of bins, and a resource vector which identifies resources associated with the allocation problem, together with capacities of the respective resources; and

using the specification, together with the one or more processing elements of the resource allocation framework, to iteratively determine a solution which allocates the set of items to the set of bins, the specification being associated with at least a utilization function which describes, for a proposed assignment of a particular item to a particular bin, a consumption of resources associated with that proposed assignment, wherein the resource allocation framework operates using any combination of an explore mode and an exploit mode;

in the explore mode, the input data associated with a particular iteration of a particular processing element is not dependent on an evaluation of results provided in a prior iteration; and

in the exploit mode, the input data associated with a particular iteration of a particular processing element, other than a first iteration, is dependent on an evaluation of results provided in a prior iteration; and

using the determined solution to allocate the real-world entities related to the set of items to the real-world entities associated with the set of bins.

2. The method of claim 1, wherein the resource vector includes one or more dimensions associated with non-shared resources.

3. The method of claim 1, wherein the resource vector includes one or more dimensions associated with shared resources.

4. The method of claim 3, wherein one shared resource is a communication link which couples two communicating entities together.

5. The method of claim 1, wherein the resource vector includes at least one conflict dimension having a conflict-checking capacity value assigned thereto.

6. The method of claim 1, wherein the specification additionally sets forth a friend relationship between at least a first item and a second item, the friend relationship prompting the resource allocation framework to attempt to assign the first item and the second item to a same bin.

7. The method of claim 1, wherein the specification additionally sets forth a foe relationship between at least a first item and a second item, the foe relationship prompting the resource allocation framework to attempt to assign the first item and the second items to different respective bins.

8. The method of claim 1, wherein the specification additionally sets forth a pinning constraint that defines a circumstance in which at least one item is pinned to at least one bin at a start of a solving operation performed by the resource allocation framework.

9. The method of claim 1, wherein the specification additionally sets forth at least one soft constraint, said at least one soft constraint describing a condition in which at least one other constraint is permitted to be violated.

10. The method of claim 1, wherein the computing functionality is implemented by a plurality of processing elements which operate in parallel to find the solution.

11. The method of claim 10, wherein each processing element operates in an independent manner from other processing elements to find a solution.

12. The method of claim 10, wherein the plurality of processing elements include respective groups of processing elements, and wherein the processing elements in each group work in cooperative fashion to find a single solution.

13. The method of claim 10, wherein the allocation problem comprises assigning virtual machines (VMs) to servers without consideration of bandwidth requirements.

14. The method of claim 10, wherein the allocation problem comprises assigning virtual machines (VMs) to servers connected by a plurality of paths.

15. The computer-implemented method of claim 1 wherein the real-world entities associated with the items are virtual machines and wherein the real-world entities associated with the bins are servers.

16. A computer-implemented domain-agnostic problem-solving system for solving a constraint problem that allocates a set of items to a set of bins, comprising:

one or more computing devices with plural processing elements comprising logic components, wherein each processing element iteratively;

generates input data associated with the constraint problem that allocates the set of items to the set of bins; and

attempts to compute a solution to the constraint problem using the domain-agnostic problem solving system and a specification tailored to the constraint problem, the specification being associated with at least a utilization function that describes, for a proposed assignment of a particular item to a particular bin, a consumption of resources associated with that proposed assignment, and the specification comprising a mapping of real-world entities associated with the constraint problem to the set of items, a mapping of real-world entities associated with the constraint problem to the set of bins, and a resource vector which identifies resources associated with the constraint problem, together with capacities of the respective resources, based on the input data

wherein the problem-solving system operates using any combination of an explore mode and an exploit mode;

in the explore mode, the input data associated with a particular iteration of a particular processing element is not dependent on an evaluation of results provided in a prior iteration; and

in the exploit mode, the input data associated with a particular iteration of a particular processing element, other than a first iteration, is dependent on an evaluation of results provided in a prior iteration.

17. The problem-solving system of claim 16, wherein the constraint problem comprises assigning virtual machines (VMs) to servers with consideration of time-varying resource allocation.

18. A computer readable storage device for storing computer readable instructions, the computer readable instructions providing a resource allocation framework that when executed by one or more processing devices cause the one or more processing devices to:

(a) provide an ordering of items;

(b) select a next bin bin_current in an ordering of bins;

(c) select a next item ball_current from the ordering of items;

(d) select a utilization module for a current allocation of items to bins (alloc_current), together with bin_current and ball_current;

(e) receive a consumption vector consume_bin/ball from the utilization module that describes a consumption of resources associated with a proposed assignment of ball_current to bin_current;

(f) add resources associated with consume_bin/ball to a current utilization vector util_current, Util_current describing a current utilization of resources for a current partial assignment of items to bins; and

(g) determine whether util_current satisfies specified constraints, and, if so, to persist a result of the adding of the resources, and, if not, to void the result of the adding of the resources,

repeating (a) through (g) for different respective items and bins until a solution is found, corresponding to a final assignment of items to bins.

19. The computer readable storage device of claim 18, wherein the resource allocation framework includes a plurality of processing elements, each processing element implementing (a) through (g), wherein each processing element attempts to find a solution independent of other processing elements.

20. The computer readable storage device of claim 18, wherein the resource allocation framework includes a plurality of groups of processing elements, wherein processing elements in a group implement at least (d) through (g) for different respective items in the ordering of items,

further comprising (h) determining whether current utilization vectors Util_current computed by separate processing elements in a group jointly satisfy the specified constraints.