DOMAIN-AGNOSTIC RESOURCE ALLOCATION FRAMEWORK
First Claim
1. A method for allocating a set of items to a set of bins, comprising:
- receiving a specification, the specification describing, in declarative fashion, various characteristics of a particular allocation problem; and
using the specification, together with a domain-agnostic resource allocation framework, to 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,the resource allocation framework being implemented by computing functionality.
2 Assignments
0 Petitions
Accused Products
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.
39 Citations
20 Claims
-
1. A method for allocating a set of items to a set of bins, comprising:
-
receiving a specification, the specification describing, in declarative fashion, various characteristics of a particular allocation problem; and using the specification, together with a domain-agnostic resource allocation framework, to 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, the resource allocation framework being implemented by computing functionality. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A problem-solving framework for solving a constraint problem, comprising:
-
plural processing elements, each processing element configured to repetitively; generate input data associated with the constraint problem; and attempt to compute a solution to the constraint problem, based on the input data. - View Dependent Claims (17)
-
-
18. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing a resource allocation framework when executed by one or more processing devices, the computer readable instructions comprising:
-
a first logic component configured to provide an ordering of items; a second logic component configured to select a next bin bincurrent in an ordering of bins; a third logic component configured to select a next item ballcurrent from the ordering of items; a fourth logic component configured to call a utilization module for a current allocation of items to bins (alloccurrent), together with bincurrent and ballcurrent; a fifth logic component configured to 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; a sixth logic component configured to 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 a seventh logic component configured to determine whether utilcurrent satisfies specified constraints, and, if so, to persist a result of the sixth logic component, and, if not, to void a result of the sixth logic component, operations performed by the first through seventh logic components being repeated for different respective items and bins until a solution is found, corresponding to a final assignment of items to bins. - View Dependent Claims (19, 20)
-
Specification