System and method for input data load adaptive parallel processing

• US 10,310,902 B2
• Filed: 12/19/2018
• Issued: 06/04/2019
• Est. Priority Date: 11/04/2011
• Status: Active Grant

• Current Assignee: Mark Henrik Sandstrom
• Original Assignee: Mark Henrik Sandstrom
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US16/226,502
• Publication Number:
  US 20190114209A1
• Time in Patent Office: 167 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, executing on at least one of hardware logic and software logic executing on a plurality of processors, for hosting a plurality of application programs, the system comprising:

a plurality of processing data input buffers, each input buffer of the plurality of processing data input buffers queuing data for a corresponding instance of one program of the plurality of application programs, wherein each program of the plurality of programs comprises a plurality of instances;

an array of cores of computing capacity;

a first subsystem configured to allocate the array of cores of computing capacity among the plurality of application programs, wherein

allocating comprises allocating the array of cores of computing capacity based at least in part on

a respective volume of processing data at each buffer of the plurality of processing data input buffers, and

a respective processing quota of each application program of at least a portion of the plurality of application programs,

and

allocating comprises allocating more than one core of the array of cores of computing capacity to at least one of the plurality of application programs;

a second subsystem configured to

assign, for each program of the plurality of application programs, each core allocated to the respective program to a different instance of the plurality of instances of the respective program, wherein

the assigning results in assignment of a plurality of selected instances of the plurality of instances of the plurality of application programs, the plurality of instances comprising one or more executable instances of each program of the plurality of application programs, wherein

a number of the plurality of selected instances is fewer than a maximum number of the plurality of instances, and

the plurality of selected instances is selected based at least in part on respective volumes of processing data available for each instance of the plurality of instances of the respective program at the portion of the plurality of data input buffers queuing data for the respective program, and

according to the assigning, control connectivity between the plurality of processing data input buffers and the array of cores; and

a third subsystem configured, according to the controlling, to establish direct data access from each input buffer of at least a subset of the plurality of processing data input buffers to the respective core of the array of cores that is assigned to a given corresponding instance of the program for which the respective input buffer is queuing data;

wherein the array of cores is periodically allocated by the first subsystem and assigned by the second subsystem based at least in part on changes in respective volumes of processing data associated with each program of the plurality of application programs.

2. The system of claim 1, wherein controlling connectivity comprises providing, for each core of the array of cores of computing capacity, an identification of an instance of a program of the plurality of application programs assigned for execution on the respective core.

3. The system of claim 2, wherein:

controlling connectivity comprises providing an input buffer selection configuration for at least one multiplexer of a plurality of core-specific multiplexers for causing connection of input data from a particular input buffer of the plurality of processing data input buffers to a particular core of the array of cores of computing capacity, wherein

the at least one multiplexer is specific to the particular core.

4. The system of claim 1, wherein allocating comprises, for at least one program of the plurality of application programs:

quantifying the respective volume of processing data queued for the respective program in one or more input buffers corresponding to the respective program as a count of processing data units; and

allocating one or more cores to the respective program based at least in part on the count of processing data units.

5. The system of claim 1, wherein the respective processing quota comprises an entitlement held by each program of the portion of the plurality of application programs.

6. The system of claim 5, wherein a first plurality of cores of the array of cores of computing capacity is allocated so that an expression of demand for the array of cores of computing capacity by each of the portion of the plurality of application programs is assured to be met at least up to the entitlement of the respective program.

7. The system of claim 6, wherein, for each program of the plurality of application programs, the respective expression of demand by the respective program is based at least in part on a volume of processing data at the portion of the plurality of processing data input buffers queuing data for the respective program.

8. The system of claim 1, wherein, for at least one program of the plurality of application programs, a maximum number of the one or more executable instances of the respective program includes an upper limit of a number of concurrently executable instances of the at least one program.

13. The system of claim 1, further comprising a fourth subsystem configured to, prior to assigning the plurality of selected instances,

for each program of the plurality of application programs, selecting at least one instance, wherein

selecting is based at least in part on relative readiness for execution among the plurality of instances of the respective program, and

a different instance of the respective program is selected for each core allocated to the respective program.

9. A method, implemented on hardware logic and/or on software logic executing on processors, for executing a plurality of application programs, the method comprising:

on each of a plurality of data input buffers, queuing respective data for a corresponding program of the plurality of application programs;

periodically allocating an array of units of computing capacity among the plurality of application programs, wherein allocating comprises, for each period of a plurality of allocation periods,

identifying expressions of demand for the array of units of computing capacity by each program of the plurality of application programs, wherein

the respective expression of demand for a given program of the plurality of application programs is based at least in part on quantifying the respective data queued for the given program in one or more input buffers of the plurality of data input buffers corresponding to the given program as a count of processing data units, and

allocating the array of units of computing capacity based at least in part on the expressions of demand of the plurality of application programs; and

for each period of a plurality of allocation periods, responsive to the allocating,

assigning, for each program of the plurality of application programs, one or more instances of the respective program for execution on a respective one or more units of the array of units of computing capacity, wherein

the one or more instances are assigned according to i) a respective number of the units of the array of units of computing capacity allocated to the respective program, and ii) execution priorities among instances of the respective program, and

according to the assigning, establishing direct data access from each buffer of at least a subset of the plurality of data input buffers to the cores respective unit of the array of units of computing capacity that is assigned a given corresponding instance of the respective program for which the respective data buffer is queuing input data, wherein

establishing direct data access comprises enabling the given corresponding instance to access and process the respective input data at the respective data buffer.

10. The method of claim 9, wherein, for at least one program of the plurality of application programs:

queuing the respective data comprises queuing respective amounts of data for individual instances of the respective program; and

assigning comprises determining the execution priorities based at least in part on the respective amounts of data queued to the individual instances of the respective program.

11. The method of claim 9, wherein, for each period of the plurality of allocation periods and for each program of at least a portion of the plurality of application programs, the array of units of computing capacity is allocated based further in part on a respective entitlement to the array of units of computing capacity held by the respective program, wherein

periodically allocating comprises ensuring the respective expressions of demand for the units of computing capacity at least up to the entitlement are met for each program of the portion of the plurality of application programs.

12. The method of claim 11, wherein, for each period of at least a portion of the plurality of allocation periods, after ensuring that the respective expressions of demand for the units of computing capacity at least up to entitlements are met for each of the portion of the plurality of application programs, remaining units of the array of units of computing capacity are allocated based further in part on remaining unmet demand for the remaining units by one or more programs of the plurality of application programs until i) the demand by each of the one or more programs is met, or ii) all units of computing capacity are allocated.

14. A system, executing on at least one of hardware logic and software logic executing on a plurality of processors, for hosting a plurality of application programs, the system comprising:

a plurality of data buffers, each buffer of the plurality of data buffers queuing input data for a respective program of the plurality of application programs, wherein

the respective program is configured to access and process the input data during execution of the respective program;

a plurality of processing units;

a first subsystem configured to allocate the plurality of processing units among the plurality of application programs, wherein allocating comprises

allocating the plurality of processing units based at least in part on a respective volume of input data at each buffer of the plurality of data buffers,

and

allocating, for at least some time periods, more than one processing unit of the plurality of processing units to at least one of the plurality of application programs;

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

selecting is based at least in part on respective volumes of input data available for each instance of the plurality of instances of the respective program, and

a different instance of the respective program is selected for each processing unit allocated to the respective program;

a third subsystem configured to assign, for each program of the plurality of application programs, each processing unit allocated to the respective program to a different instance of the one or more instances of the respective program in accordance with the selecting; and

a fourth subsystem configured, according to the assigning, to establish direct data access from each buffer of at least a subset of the plurality of data buffers to the respective processing unit of the plurality of processing units that is assigned a given corresponding instance of the respective program for which the respective data buffer is queuing input data, wherein

establishing direct data access comprises enabling the given corresponding instance to access and process the respective input data at the respective data buffer;

wherein the plurality of processing units is periodically allocated by the first subsystem, selected by the second subsystem, and assigned by the third subsystem based at least in part on changes in respective volumes of input data associated with each program of the plurality of application programs.

15. The system of claim 14, wherein allocating comprises allocating the plurality of processing units based further in part on a respective entitlement of each program of at least a portion of the plurality of application programs to processing resources of the plurality of processing units.

16. The system of claim 14, wherein selecting based at least in part on respective volumes of input data comprises selecting based at least in part on quantifying a number of queued items of the respective data queued for the respective program in one or more buffers of the plurality of data buffers corresponding to the respective program.

17. The system of claim 14, further comprising:

a plurality of program instance specific multiplexers, each program instance specific multiplexer being specific to one instance of one of the plurality of application programs;

wherein establishing direct data access comprises, for each processing unit of at least a portion of the plurality of processing units, controlling, using the program instance specific multiplexer of the instance assigned to the respective processing unit, connectivity between the respective processing unit and the program specific data buffer of a program of the plurality of application programs corresponding to the instance assigned to the respective processing unit.