Application load adaptive multi-stage parallel data processing architecture

• US 10,133,599 B1
• Filed: 06/21/2018
• Issued: 11/20/2018
• Est. Priority Date: 11/04/2011
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US16/014,658
• Publication Number:
  US 20180336068A1
• Time in Patent Office: 152 Days
• Field of Search: None
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 30/04 Billing or invoicing

Abstract

Systems and methods provide an extensible, multi-stage, realtime application program processing load adaptive, manycore data processing architecture shared dynamically among instances of parallelized and pipelined application software programs, according to processing load variations of said programs and their tasks and instances, as well as contractual policies. The invented techniques provide, at the same time, both application software development productivity, through presenting for software a simple, virtual static view of the actually dynamically allocated and assigned processing hardware resources, together with high program runtime performance, through scalable pipelined and parallelized program execution with minimized overhead, as well as high resource efficiency, through adaptively optimized processing resource allocation.

Claims

1. A system including processors and comprising a plurality of subsystems, implemented on hardware logic and/or software logic executing on the processors, for dynamic resource management of a pool of processing resources on behalf of application programs, the system comprising:

a first subsystem configured to periodically allocate a plurality of processing units of the pool of processing resources among a plurality of application programs over time, wherein

the plurality of processing units comprises units of at least two types of processing units and/or units of a reconfigurable type, and

allocating the plurality of processing units among the plurality of application programs is based at least in part on i) a respective processing demand of each of the plurality of application programs, and ii) a respective processing resource quota of each program of a subset of the plurality of application programs;

a second subsystem configured to, for each program of the plurality of application programs, select a set of highest priority instances of one or more instances of a respective program, wherein

a number of instances in the set of instances corresponds to a number of processing units allocated to the respective application program by the first subsystem during a current allocation period, and

each instance of the set of highest priority instances is selected based at least in part on a) the number of processing units allocated to the respective program and b) a relative readiness for execution among the one or more instances of the respective application program; and

a third subsystem configured to assign, for each of the plurality of application programs, the respective set of highest priority instances to a subset of the processing units allocated by the first subsystem for the respective application program for execution during an upcoming allocation period, wherein, for at least a portion of instances of at least a portion of the plurality of application programs,

a respective instance of the respective set of highest priority instances is associated with a processing unit type or configuration, wherein

assigning comprises

placing the respective instance to a respective processing unit of the plurality of processing units based at least in part on the processing unit type or configuration associated with the respective instance, and

prioritizing placement of the respective instance to the particular type or configuration processing unit demanded;

wherein the system is further configured to periodically adjust allocations of the plurality of processing units of the pool of processing resources over time, wherein, for each periodic adjustment,

the adjusting is followed by the selecting and the assigning.

2. The system of claim 1, wherein the processing demand of each of the application programs is based at least in part on one or more ready-to-execute instances of the one or more instances of the respective application program, wherein

the one or more ready-to-execute instances includes at least one of

one or more assigned instances currently assigned to a given processing unit of the plurality of processing units, and

one or more unassigned instances currently unassigned to any processing unit of the plurality of processing units.

3. The system of claim 1, wherein the units of the reconfigurable type are configurable in at least two different ways, to respectively provide at least two different forms of application specific processing units.

4. The system of claim 3, wherein assigning comprises, for at least one given instance of the set of highest priority instances of at least one program of the plurality of application programs, reconfiguring the respective processing unit to the processing unit configuration associated with the at least one given instance.

5. The system of claim 1, wherein assigning the set of instances comprises maintaining any assigned instances on the respective given processing unit.

6. The system of claim 1, wherein allocating the plurality of processing units of the pool of processing resources among the plurality of application programs by the first subsystem comprises allocating a first number of the plurality of processing units to one or more of the plurality of application programs based, for each of the plurality of application programs, on a processing demand of the respective application program up to the processing resource quota of the respective application program.

7. The system of claim 6, wherein allocating the plurality of processing units of the pool of processing resources among the plurality of application programs by the first subsystem comprises, after allocating the first number of processing units, allocating remaining processing units of the plurality of processing units to one or more additional programs of the plurality of application programs based in part on remaining processing demand of each of the plurality of application programs.

8. The system of claim 1, wherein at least a subset of the plurality of processing units are CPUs.

9. The system of claim 1, wherein at least one of the first subsystem, the second subsystem, and the third subsystem is software-implemented.

10. A system including processors and implemented on hardware logic and/or software logic executing on the processors, comprising a plurality of subsystems for managing access to a pool of processing resources by application programs, the system comprising:

a first subsystem configured to allocate a plurality of processing cores of the pool of processing resources to a plurality of application programs based at least in part on

respective expressions of demand for processing resources of the plurality of processing cores by the plurality of application programs and respective entitlements for the processing resources by a subset of the plurality of application programs, wherein

the respective expressions of demand relate in part to readiness to execute of one or more instances of a respective application program, and

the plurality of processing cores comprises at least two types of processing cores and/or cores of a reconfigurable type;

a second subsystem configured to, for each program of the plurality of application programs, select a set of highest priority instances of one or more instances of the respective application program, wherein each of the set of instances is selected based at least in part on a) the number of cores allocated to the respective program and b) a relative readiness for execution among the one or more instances of the respective application program; and

a third subsystem configured to assign the respective set of highest priority instances of each of the plurality of application programs for execution on a respective one or more processing cores of the plurality of processing cores, wherein assigning is based at least in part upon a type or configuration of processing core demanded by the respective application program instance;

wherein allocating the plurality of processing cores by the first subsystem comprises adjusting allocations of the plurality of processing cores over time based at least in part on changes in the respective expressions of demand for the processing resources of the plurality of processing cores,

wherein assigning further comprises prioritizing placement of the set of highest priority instances to the particular processing core type or configuration demanded, and

wherein the system periodically repeats the selecting and the assigning at least in response to the adjusting allocations.

11. The system of claim 10, wherein adjusting allocations comprises:

allocating a first number of the plurality of processing cores to instances of the plurality of application programs based, for each of the subset of the plurality of application programs, on respective expression of demand up to the respective entitlement, and

after allocating the first number, allocating remaining processing cores of the plurality of processing cores to one or more of the plurality of application programs based at least in part on an unmet portion of the expression of demand of the respective application program after allocating the first number.

12. The system of claim 11, wherein allocating remaining processing cores comprises:

allocating a second number of processing cores of the plurality of processing cores according to the unmet portions of the expressions of demand of the plurality of application programs; and

after allocating the second number of processing cores, allocating all remaining processing cores among the plurality of application programs.

13. The system of claim 10, wherein:

the cores of the reconfigurable type are configurable in at least two different ways, to respectively provide at least two different forms of application specific processing cores; and

assigning comprises, for at least one given instance of one program of the plurality of application programs, reconfiguring the respective processing core to the processing core configuration associated with the given instance.

14. The system of claim 10, wherein:

the system schedules the allocating periodically, once per allocation period, wherein the allocation period is a predetermined period of time; and

the allocating, the selecting, and the assigning are performed within each predetermined allocation period.

15. The system of claim 14, wherein assigning the number of instances of each of the plurality of application programs to the plurality of processing cores by the third subsystem comprises preserving processing core assignments for instances selected for execution on consecutive allocation periods.

16. The system of claim 10, wherein at least one of the first subsystem, the second subsystem, and the third subsystem comprises dedicated hardware for performing a subset of the operations of the respective subsystem.

17. The system of claim 10, wherein assigning the plurality of processing cores comprises prioritizing matching the type or configuration of processing core demanded by the respective program instance of the set of highest priority instances of each of the plurality of application programs.

18. A method for managing resource access on a parallel processing system on behalf of application programs, the method comprising:

identifying, by a control system comprising at least one of hardware logic and software logic, a respective expression of demand for computing capacity of the parallel processing system associated with each of one or more programs of a plurality of application programs;

identifying, by the control system, a respective entitlement for computing capacity associated with each of one or more programs of the plurality of application programs;

allocating, by the control system, a plurality of units of the computing capacity of the parallel processing system to at least a subset of the plurality of application programs, wherein

the plurality of units comprises units of at least two different types and/or units of a reconfigurable type, and

the allocating is based at least in part on i) the expressions for demand of each of the subset of the plurality of application programs, and ii) the entitlements of the one or more programs of the subset of application programs;

for each program of the subset of application programs,

assessing, by the control system, a relative readiness for execution among one or more instances of the respective application program, and

selecting, by the control system, a set of highest priority instances of the one or more instances of the respective application program for execution on the parallel processing system according to a) a number of units of the plurality of units of computing capacity allocated to the respective application program, and b) the relative readiness for execution among the one or more instances of the respective application program;

assigning, by the control system, the set of the highest priority instances of each of the at least the subset of the plurality of application programs for execution on a respective one or more units of the plurality of units of computing capacity, wherein

assigning comprises, for each instance of the set of highest priority instances expressing a demand for a particular type or configuration of unit, prioritizing placement of the respective instance to the particular type or configuration of unit demanded; and

adjusting, by the control system, allocations of the plurality of units of computing capacity over time based at least in part on changes in the expressions of demand or the entitlements of the plurality of application programs, wherein adjusting comprises periodically repeating the identifying of the respective expression of demand, the identifying the respective entitlement, the allocating, the assessing, the selecting, and the assigning.

19. The method of claim 18, wherein:

the units of the reconfigurable type are configurable in at least two different ways, to respectively provide at least two different forms of application specific units; and

assigning comprises, for at least one given instance of one program of the plurality of application programs, reconfiguring the respective unit for the respective given instance to the particular type of unit associated with the given instance.

20. The method of claim 18, wherein allocating the plurality of units of the computing capacity comprises allocating a first number of the plurality of units of computing capacity to one or more of the at least the subset of the plurality of application programs based, for each of the at least the subset of the plurality of application programs, on a processing demand of the respective application program up to the entitlement of the respective application program.