Application load adaptive multi-stage parallel data processing architecture

• US 10,133,600 B2
• 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,674
• Publication Number:
  US 20180300178A1
• Time in Patent Office: 152 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 hardware logic and/or software logic executing on processors, for load-adaptive resource management of a pool of processing resources on behalf of a plurality of software programs, the plurality of subsystems comprising:

a first subsystem configured to periodically, for successive allocation periods,

allocate a plurality of cores of the pool of processing resources to the plurality of software programs based at least in part on i) a processing demand of each software program of the plurality of software programs, and ii) a processing resource quota of each program of one or more software programs of the plurality of software programs to computing capacity of the pool of processing resources, wherein

periodically allocating causes allocations of the plurality of cores to adjust over time based at least in part on changes in readiness to execute among one or more instances of a set of instances of each of the plurality of software programs;

a second subsystem configured to, for each of the plurality of software programs, select a set of highest priority instances of one or more instances of the set of instances, corresponding to a number of cores allocated to the respective program by the first subsystem during a current allocation period of the successive allocation periods, wherein

the set of highest priority instances are selected based at least in part on a relative readiness for processing among the set of instances of the respective program; and

a third subsystem configured to assign the set of highest priority instances of each of the plurality of software programs selected by the second subsystem to the plurality of cores for execution during an upcoming allocation period based at least in part on the allocations of the cores among the plurality of software programs by the first subsystem, wherein,

for at least one of the plurality of software programs,

the set of highest priority instances comprises at least one assigned instance currently assigned to a given core of the plurality of cores, and

assigning the at least one assigned instance comprises preserving a core assignment of the at least one assigned instance from a current allocation period;

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

2. The system of claim 1, wherein the processing demand of each program of the plurality of software programs is based in part on volumes of data associated with the set of instances of the respective program.

3. The system of claim 2, wherein the volumes of data of the set of instances of the plurality of software programs include volumes of queued data available to each of the plurality of software programs for processing.

4. The system of claim 1, wherein selecting the set of highest priority instances of each of the plurality of software programs by the second subsystem comprises ranking the instances of each of the plurality of software programs in an execution priority order.

5. The system of claim 4, wherein the instances of each of the plurality of software programs are ranked based at least in part on respective volumes of data associated with each of the instances.

6. The system of claim 1, wherein allocating comprises:

allocating a first number of the plurality of cores to the one or more software programs based, for each of the one or more software programs, at least in part on the processing demand of the respective software program up to the respective processing resource quota; and

allocating 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 software programs based in part on remaining processing demand of each of the plurality of software programs.

7. The system of claim 6, wherein allocating the first number of the plurality of cores comprises ensuring that each respective processing resource quota for each of the one or more software programs is met.

8. The system of claim 6, wherein the processing resource quota comprises an entitlement held by the respective software program.

9. The system of claim 1, wherein at least a subset of the plurality of cores are central processing units (CPUs).

10. 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.

11. A system including processors and implemented on hardware logic and/or software logic executing on the processors, the system comprising a plurality of subsystems for load-adaptive resource management of a pool of processing resources on behalf of a plurality of applications, the plurality of subsystems comprising:

a first subsystem configured to allocate a plurality of processing units of the pool of processing resources to the plurality of applications based at least in part on i) respective expressions of demand for the pool of processing resources by the plurality of applications, and ii) respective entitlements of one or more applications of the plurality of applications to computing capacity of the pool of processing resources;

a second subsystem configured to, for each application of the plurality of applications, select a set of highest priority instances of one or more instances of the respective application corresponding to processing units allocated by the first subsystem for an upcoming allocation period, wherein the set of highest priority instances are selected based at least in part on a relative readiness for processing among the one or more instances of the respective application; and

a third subsystem configured to assign the set of the highest priority instances of each of the plurality of applications for execution during the upcoming allocation period on a respective one or more processing units of the plurality of processing units based at least in part on the allocation of the plurality of processing units among the plurality of applications by the first subsystem;

wherein the allocating is repeated periodically such that allocations of the plurality of processing units vary over time based at least in part on changes in expressions of demand for the pool of processing resources associated with each of the plurality of applications, wherein

assigning the set of highest priority instances of each of the plurality of applications comprises preserving core assignments to instances selected for execution on consecutive core allocation periods;

the system being further configured to periodically adjust allocations of the plurality of processing units of the pool of processing resources over time, wherein such adjusting is followed by accordingly carrying out the selecting and the assigning.

12. The system of claim 11, wherein:

the relative expressions of demand are based at least in part on volumes of data associated with each of the plurality of applications; and

periodically adjusting allocations comprises periodically adjusting based at least in part on changes in respective volumes of data associated with each of the plurality of applications.

13. The system of claim 11, wherein:

periodically adjusting allocations comprises scheduling 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 once for each predetermined period of time.

14. The system of claim 11, wherein the second subsystem selects each of the set of highest priority instances based at least in part on a relative readiness for execution among the one or more instances of the respective application.

15. The system of claim 14, wherein the relative readiness for execution of at least a given one of instances of the respective application is based at least in part on availability of input data for the given instance.

16. The system of claim 11, wherein one or more of the plurality of processing units are virtual processing cores.

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

18. A method for load-adaptive resource management of a parallel processing system on behalf of application programs, the method comprising:

a) identifying, by a control system, a respective expression of demand for the computing capacity of the parallel processing system associated with each program of a plurality of application programs;

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

c) 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 allocating is based at least in part on i) the expressions of 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;

d) 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 set of highest priority instances of the one or more instances of the respective program for execution on the parallel processing system according to i) a number of units of the plurality of units of computing capacity allocated to the respective application program, and ii) the relative readiness for execution among the one or more instances of the respective program;

e) assigning 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 based at least in part on the allocations of the units of computing capacity among the plurality of application programs; and

f) periodically repeating steps a) through e) to modify allocations over time based at least in part on changes in the respective expressions of demand for each of the plurality of application programs;

wherein assigning the set of highest priority instances of each of the subset of the plurality of application programs comprises preserving core assignments to instances selected for execution on consecutive repetitions of steps a) through e).

19. The method of claim 18, 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

for at least one program of the plurality of application programs, and for at least some periods of a series of periods for which said allocating is performed, allocating comprises allocating at least one unit of computing capacity exceeding the entitlement of the respective program.

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