Domain-agnostic resource allocation framework

Patent metadata

Field	Value
Publication number	US-9753778-B2
Application number	US-201213553847-A
Country	US
Kind code	B2
Filing date	Jul 20, 2012
Priority date	Jul 20, 2012
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

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.

First claim

What is claimed is:

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 (

Assignees

• Guha Saikat
• Bhagwan Ranjita
• Rai Anshul
• Microsoft Technology Licensing Llc

Inventors

• Guha Saikat
• Bhagwan Ranjita
• Rai Anshul

Classifications

• G06F9/5038 Primary

  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) · CPC title