Application load adaptive multi-stage parallel data processing architecture

• US 10,061,615 B2
• Filed: 03/23/2018
• Issued: 08/28/2018
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US15/933,724
• Publication Number:
  US 20180210757A1
• Time in Patent Office: 158 Days
• Field of Search: None
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• 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/5016 the resource being the memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/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 Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 49/15 Interconnection of switching modules

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 comprising a plurality of subsystems, implemented on processors, for coordinating resource management of a pool of processing resources on behalf of application programs, the system comprising:

a first subsystem configured to, for each period of a plurality of allocation periods,

allocate a first number of a plurality of cores of the pool of processing resources to one or more of the plurality of application programs based, for each of the one or more application programs, on a processing demand of the respective application program up to a respective processing resource quota, wherein

the processing demand is based at least in part on a count of ready-to-execute instances for the respective application program, and

allocate a second number of the plurality of cores after allocating the first number of the plurality of cores to one or more programs of the plurality of application programs based in part on remaining processing demand of each of the plurality of application programs,

such that allocations of the plurality of cores are adjusted over time based at least in part on changes in the processing demands of each of the plurality of application programs;

a second subsystem configured to, for each of the plurality of application programs, select a number of highest priority instances, corresponding to a number of cores allocated to the respective program by the first subsystem, of one or more instances of the respective program for a next allocation period of the plurality of allocation periods, wherein the number of highest priority instances are selected based at least in part on a relative readiness for execution among one or more instances of the respective program, wherein any of the ready-to-execute instances of the respective program has a higher selection priority than any other instances of the respective program; and

a third subsystem configured to assign the number of highest priority instances of each of the plurality of application programs selected by the second subsystem to the cores that are allocated to the corresponding program during the next allocation period of the plurality of allocation periods.

2. The system of claim 1, wherein a length of each allocation period of the plurality of allocation periods is set to a same predetermined interval.

3. The system of claim 1, wherein the pool of processing resources comprises a plurality of central processing units (CPUs).

4. The system of claim 1, wherein at least a subset of the plurality of cores are virtual cores.

5. The system of claim 1, wherein allocating the plurality of cores by the first subsystem comprises allocating the plurality of cores based at least in part on respective volumes of queued data available to each of the plurality of application programs for processing.

6. The system of claim 5, wherein selecting the instances by the second subsystem comprises, for each program of the plurality of application programs, prioritizing the respective one or more instances in an execution priority order based at least in part on a number of items of queued data within an input data buffer associated with each instance.

7. The system of claim 5, wherein the volumes of queued data, for each program of one or more of the plurality of application programs, include messages associated with one or more specific instances of the one or more instances of the respective program.

8. The system of claim 1, wherein the ready-to-execute instances include at least one of a number of assigned instances currently assigned to a given core of the plurality of cores, and a number of unassigned instances currently unassigned to a given core of the plurality of cores.

9. The system of claim 1, wherein the processing resource quota comprises an entitlement held by the respective application program.

10. The system of claim 1, wherein at least one of the first subsystem, the second subsystem, and the third subsystem comprises a plurality of instructions, stored to a non-transitory computer readable medium which, when executed on circuitry, perform a subset of the operations of the respective subsystem.

11. The system of claim 1, 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.

12. A system comprising a plurality of subsystems, implemented on processors, for coordinating 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 cores of the pool of processing resources to a plurality of application programs based at least in part on

i) respective expressions of demand for processing resources of the plurality of processing cores by each of the plurality of application programs, and

ii) respective entitlements to the processing resources of the plurality of processing cores, wherein

a respective entitlement is held by each of one or more programs of the plurality of application programs;

and wherein the respective expression of demand is based at least in part on a count of ready-to-execute instances of each of the plurality of application programs;

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

wherein any of the ready-to-execute instances of the respective program has a higher selection priority than any other instances of the respective program; and

a third subsystem configured to assign the number of the highest priority instances of each of the plurality of application programs for execution on a respective one or more cores of the cores that are allocated to the corresponding program;

wherein allocating the plurality of cores by the first subsystem comprises

allocating a first number of the plurality of cores to the highest priority instances of the one or more programs based, for each of the one or more programs, on respective expression of demand up to the respective entitlement, and

after allocating the first number, allocating a second number of the plurality of cores to a second number of instances of 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.

13. The system of claim 12, wherein:

the system schedules the allocating periodically, once per core allocation period, wherein

the core allocation period is a predetermined period of time; and

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

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

15. The system of claim 13, wherein the respective expressions of demand of each of the plurality of application programs is based at least in part on a volume of data available for processing by the respective application program.

16. The system of claim 15, wherein the respective volume of data available for processing by each application program comprises a number of processing data units queued to at least one buffer associated with the respective application program.

17. The system of claim 12, wherein the selecting by the second subsystem comprises, for each of the plurality of application programs, prioritizing the respective one or more instances based at least in part on a respective volume of data available for processing by each instance of the respective one or more instances.

18. The system of claim 12, wherein selecting the instances of each of the plurality of application programs by the second subsystem comprises ranking the instances of each of the plurality of application programs in an execution priority order.

19. The system of claim 12, wherein one or more of the plurality of cores are virtual processing cores.

20. The system of claim 12, 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.

21. The system of claim 12, wherein at least one of the first subsystem, the second subsystem, and the third subsystem comprises a plurality of instructions, stored to a non-transitory computer readable medium which, when executed on circuitry, perform a subset of the operations of the respective subsystem.

22. A method for managing processing resources of a parallel processing system on behalf of application programs, the method comprising:

identifying, by a control system, a respective expression of demand for computing capacity of the processing resources 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 the computing capacity associated with each of one or more programs of the plurality of application programs;

wherein the respective expression of demand is based at least in part on a count of ready-to-execute instances of each 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 a subset of the plurality of application programs, wherein the allocating is based at least in part on i) the expressions for demand of each of the subset 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 program, and

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

wherein any of the ready-to-execute instances of the respective program has a higher selection priority than any other instances of the respective program; and

assigning the number of the highest priority instances of each of the plurality of application programs for execution on a respective one or more units that are allocated to the corresponding program;

wherein, for each program of the one or more application programs having a respective expression of demand meeting or exceeding a respective entitlement, allocating comprises allocating at least a number of units of computing capacity adequate to meet the entitlement of the respective program;

and wherein, for at least one program of the plurality of application programs, allocating comprises allocating at least one unit of computing capacity exceeding the entitlement of the respective program.

23. The method of claim 22, wherein the control system comprises dedicated hardware logic for performing at least a portion of the operations of the control system.

24. The method of claim 22, wherein assessing the relative readiness for execution comprises ranking the one or more instances of the respective program according to an execution priority order.

25. The method of claim 22, wherein ranking is based at least in part on a respective volume of data available to each instance of the one or more instances for processing.

26. The method of claim 22, wherein the expression of demand is based at least in part on a respective volume of data available to each program of the plurality of application programs for processing.

27. The method of claim 22, wherein assessing relative readiness for execution comprises assessing, for each instance of the one or more instances of the respective program, availability of data to the respective instance for processing.

28. The method of claim 22, further comprising repeating, for each of a plurality of core allocation periods, the identifying the respective expression of demand, the allocating, the assessing, the selecting, and the assigning.

29. The method of claim 28, wherein each of the plurality of core allocation periods is a predetermined period of time.

30. The method of claim 28, wherein the assigning comprises assigning for execution during a next period of the plurality of core allocation periods.