US 9,753,778 B2Granted

Domain-agnostic resource allocation framework

AssigneeMicrosoft Technology Licensing, LLC

InventorsSaikat Guha, Ranjita Bhagwan, Anshul Rai

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

6 more elements

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 bincurrent in an ordering of bins;
(c) select a next item ballcurrent from the ordering of items;
(d) select a utilization module for a current allocation of items to bins (alloccurrent), together with bincurrent and ballcurrent;
(e) receive a consumption vector consumebin/ball from the utilization module that describes a consumption of resources associated with a proposed assignment of ballcurrent to bincurrent;
(f) add resources associated with consumebin/ball to a current utilization vector utilcurrent, Utilcurrent describing a current utilization of resources for a current partial assignment of items to bins;
and
(g) determine whether utilcurrent 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.

6 more elements

Dependencies are inferred from the claim text.