Computational resource allocation

Patent metadata

Field	Value
Publication number	US-10445137-B2
Application number	US-201715833213-A
Country	US
Kind code	B2
Filing date	Dec 6, 2017
Priority date	Dec 8, 2016
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Requesting computational resources for executing a program including a number of program portions includes computing sets of requests. Each set, except an initial set, is processed by a computational resource manager only if the previously submitted sets were granted. One or more additional sets are formed for processing by the manager after the initial set. A request of the additional sets includes a partial request for a program portion that is in a least-fulfilled set of program portions. Each program portion is associated with a respective fulfillment ratio of its quantity of previously requested resources divided by an associated target quantity. The partial request requests a quantity of resources that is small enough so that, after the partial request is granted, each program portion in the least-fulfilled set will have a fulfillment ratio that is greater than its fulfillment ratio had been, and is still smaller than one.

First claim

What is claimed is:

1. A method for requesting, from a computational resource manager, computational resources for executing a program in a computing system, the method including:
storing information specifying target quantities of computational resources associated with respective ones of a plurality of program portions of the program, where each program portion uses computational resources granted by the computational resource manager enabling that program portion to be executed in the computing system; and
computing requests for submission to the computational resource manager as a plurality of sets of requests, where each set of requests, except for an initial set of requests, is processed by the computational resource manager only if the previously submitted one or more sets of the plurality of sets of requests were granted by the computational resource manager, the computing including:
forming the initial set of requests, and
forming one or more additional sets of requests for processing by the computational resource manager after the initial set of requests,
wherein at least one set of requests of the additional sets of requests includes a partial request for at least one program portion that is in a least-fulfilled set of one or more program portions,
wherein each program portion is associated with a respective fulfillment ratio of its quantity of previously requested computational resources divided by its associated target quantity of computational resources,
wherein a program portion is a member of the least-fulfilled set if its associated fulfillment ratio, over all of the plurality of program portions, is the minimum of the associated fulfillment ratios, and
wherein the partial request requests a quantity of computational resources that is small enough so that, after the partial request is granted, each program portion in the least-fulfilled set will have a fulfillment ratio that is greater than its fulfillment ratio had been before the partial request had been granted, and is still smaller than one.

2. The method of claim 1 , wherein the partial request requests a quantity of computational resources that is small enough so that, after the partial request is granted, each program portion in the least-fulfilled set will have a fulfillment ratio that is still smaller than a fulfillment ratio of at least one program portion outside of the least-fulfilled set.

3. The method of claim 2 , wherein the partial request requests a quantity of computational resources that is large enough so that, after the partial request is granted, each program portion in the least-fulfilled set will have a fulfillment ratio that is at least as large as a fulfillment ratio of at least one program portion outside the least-fulfilled set.

4. The method of claim 1 , wherein the partial request requests a quantity of computational resources that is large enough so that, after the partial request is granted, each program portion in the least-fulfilled set will have a fulfillment ratio that is at least as large as a fulfillment ratio of at least one program portion outside the least-fulfilled set.

5. The method of claim 1 , wherein the initial set of requests includes a minimum request for each program portion, where each minimum request requests a minimum quantity of computational resources needed to execute the corresponding portion of the program.

6. The method of claim 5 , wherein at least one of the program portions is associated with a fixed target quantity of computational resources and at least one of the program portions is associated with a variable target quantity of computational resources, and the minimum request for each program portion associated with a fixed target quantity of computational resources is a full request corresponding to the complete target quantity of computational resources, and the minimum request for each program portion associated with a variable target quantity of computational resources is a partial request corresponding to less than the complete target quantity of computational resources.

7. The method of claim 6 , wherein the minimum request for each program portion associated with a variable target quantity of computational resources is a partial request corresponding to a single unit of computational resources, where each variable target quantity of computational resources is defined in terms of a granularity of computational resources that divides the complete target quantity of computational resources into a plurality of units of equal size.

8. The method of claim 1 , wherein at least some requests in at least one set of requests correspond to quantities of computational resources of different sizes from each other.

9. The method of claim 1 , wherein storing the information specifying target quantities of computational resources associated with respective ones of the plurality of program portions includes, for at least one program portion, determining its associated target quantity of computational resources based at least in part on user input.

10. The method of claim 1 , wherein the computational resources are distributed over a plurality of computing nodes.

11. The method of claim 10 , wherein at least some of the program portions require that their granted computational resources are obtained from a specific one or more computing nodes of the plurality of computing nodes.

12. The method of claim 10 , wherein computational resources associated with each request of each set of requests of the plurality of sets of requests must be obtained from a single computing node of the plurality of computing nodes.

13. The method of claim 1 , wherein at least some of the program portions are configured to process data items from one or more data sources and the method further includes determining the target quantities of computational resources for each of the program portions based at least in part on the data items from the one or more data sources.

14. The method of claim 13 , wherein determining the target quantities of computational resources for each of the program portions based at least in part on the data items from the one or more data sources includes, for each program portion, adding computational resources associated with a single instance of the program portion to the target quantity of computational resources associated with the program portion for each data item to be processed by the program portion.

15. The method of claim 1 , wherein each request, of each set of requests of the plurality of sets of requests, requests computational resources required by a single instance of a particular program portion of the plurality of program portions.

16. The method of claim 1 , wherein a first program portion of the plurality of program portions is associated with a plurality of requests from the plurality of sets of requests.

17. The method of claim 1 , further including receiving, in response to the initial set of requests, an indication that one or more requests of the initial set of requests was not fulfilled and aborting execution of the program based on the response.

18. Software stored in a non-transitory form on a computer-readable medium, for requesting, from a computational resource manager, computational resources for executing a program in a computing system, the software including instructions for causing a computing system to:
store information specifying target quantities of computational resources associated with respective ones of a plurality of program portions of the program, where each program portion uses computational resourc

Assignees

• Ab Initio Technology Llc

Inventors

• Chu Jacky Cheuk Kei
• Schmidt Stephen J
• Wang Bo

Classifications

• G06F9/5061 Primary

  Partitioning or combining of resources · CPC title

• G06F2209/5013

  Request control · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/485

  Task life-cycle, e.g. stopping, restarting, resuming execution (G06F9/4881 takes precedence) · CPC title

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