System and method for input data load adaptive parallel processing

• US 10,310,901 B2
• Filed: 09/28/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/145,632
• Publication Number:
  US 20190026153A1
• Time in Patent Office: 249 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 at least one of hardware logic and software logic executing on a plurality of processors, for computing resource management, the system comprising:

a first subsystem configured to allocate an array of units of computing capacity among instances of a set of programs, each program of the set of programs comprising a respective plurality of instances, wherein

the allocating is based at least in part on respective volumes of processing data for each program of the set of programs, and

the allocating results in a unique subset of the array of units of computing capacity allocated to each program of the set of programs;

a second subsystem configured to, for each program of the set of programs, assess a relative readiness for execution among the plurality of instances of the respective program, wherein

the relative readiness is assessed based at least in part on respective volumes of processing data available to each instance of the plurality of instances; and

a third subsystem configured to select, for each program of the set of programs, a highest priority subset of instances of the plurality of instances of the respective program for execution on the array of units of computing capacity according to a number of units of the unique subset of the array of units allocated to the respective program, wherein

the highest priority subset of instances is selected based at least in part on the relative readiness for execution, and

selecting results in a plurality of selected instances;

wherein

the plurality of selected instances includes

one or more assigned instances currently executing on a given unit of the array of units of computing capacity, and

one or more unassigned instances currently unassigned to any unit of the array of units of computing capacity, wherein

selecting the highest priority subset of instances comprises, for at least one program of the set of programs, prioritizing an unassigned instance of the at least one program over an assigned instance of a given program of the set of programs currently executing on a given unit of the array of units of processing capacity, resulting in preemption of the assigned instance, wherein the prioritizing is based at least in part on newly available data to the at least one program.

2. The system of claim 1, wherein the assessing comprises ranking the plurality of instances of the respective program into an execution priority order.

3. The system of claim 1, wherein, for a portion of the set of programs, the array of units is allocated by the first subsystem based further in part on an entitlement for one or more units of computing capacity held by the respective program.

4. The system of claim 3, wherein allocating the array of units based in part on the entitlement comprises ensuring the entitlement for each of the portion of the set of programs is met prior to meeting additional demand by the set of programs, wherein the additional demand is based at least in part based on the respective volume of processing data of each respective program of the set of programs.

5. The system of claim 1, wherein the allocating comprises:

quantifying the respective volume of processing data queued to each program of one or more programs of the set of programs as a count of processing data units; and

allocating one or more units of the array of units of computing capacity to each program of the one or more programs based at least in part on the count of processing data units.

6. The system of claim 1, wherein the volumes of processing data are available at a plurality of input data buffers, each input data buffer queuing data for a respective program of the set of programs.

7. The system of claim 1, wherein allocating comprises allocating the array of units of computing capacity based at least in part on a respective processing quota of each application program of at least a portion of the plurality of application programs.

8. The system of claim 1, further comprising a fourth subsystem configured to assign, for each program of the plurality of programs, each unit of the array of units of computing capacity allocated to the respective program to a different instance of the respective program, wherein

the assigning results in assignment of the plurality of selected instances of the respective program to the unique subset of the array of units allocated to the respective program.

9. The system of claim 1, wherein the allocating, the selecting and the assessing are performed periodically according to a core allocation period.

10. The system of claim 9, wherein periodically allocating comprises periodically adjusting allocations based at least in part on changes in respective volumes of data associated with each program of the set of programs.

11. The system of claim 1, wherein the array of units of computing capacity comprise an array of virtual cores.

12. The system of claim 1 wherein the array of units of computing capacity comprises one of a) at least two types of units and b) units of a reconfigurable type.

13. A method for computing resource management, implemented by a controller comprising software logic executing on processors and/or hardware logic, the method comprising:

allocating, by the controller, an array of units of computing capacity among instances of a set of programs, each program of the set of programs comprising a respective plurality of instances, wherein

the allocating is based at least in part on respective volumes of processing data for each program of the set of programs, and

the allocating results in a unique subset of the array of units of computing capacity allocated to each program of the set of programs;

assessing, by the controller, a relative readiness for execution among the plurality of instances of the respective program, wherein

the relative readiness is assessed based at least in part on respective volumes of processing data available to each instance of the plurality of instances; and

selecting, by the controller for each program of the set of programs, a highest priority subset of instances of the plurality of instances of the respective program for execution on the array of units of computing capacity according to a number of units of the unique subset of the array of units allocated to the respective program, wherein

the highest priority subset of instances is selected based at least in part on the relative readiness for execution, and

selecting results in a plurality of selected instances;

wherein

the plurality of selected instances includes

one or more assigned instances currently executing on a given unit of the array of units of computing capacity, and

one or more unassigned instances currently unassigned to any unit of the array of units of computing capacity, wherein

selecting the highest priority subset of instances comprises, for at least one program of the set of programs, prioritizing an unassigned instance of the at least one program over an assigned instance of a given program of the set of programs currently executing on a given unit of the array of units of processing capacity, resulting in preemption of the assigned instance, wherein the prioritizing is based at least in part on newly available data to the at least one program.

14. The method of claim 13, wherein, for a portion of the set of programs, the array of units is allocated based further in part on an entitlement for one or more units of computing capacity held by the respective program.

15. The method of claim 14, wherein allocating the array of units based in part on the entitlement comprises ensuring the entitlement for each of the portion of the set of programs is met prior to meeting additional demand by the set of programs, wherein

the additional demand is based at least in part on the respective volume of processing data of each respective program of the set of programs.

16. The method of claim 13, wherein the volumes of processing data are available at a plurality of input data buffers, each input data buffer queuing data for a respective program of the set of programs.

17. The method of claim 13, wherein allocating comprises allocating the array of units of computing capacity based at least in part on a respective processing quota of each application program of at least a portion of the plurality of application programs.

18. The method of claim 13, further comprising assigning, by the controller, for each program of the plurality of programs, each unit of the array of units of computing capacity allocated to the respective program to a different instance of the respective program, wherein

the assigning results in assignment of the plurality of selected instances of the respective program to the unique subset of the array of units allocated to the respective program.

19. The method of claim 13, wherein the allocating, the selecting and the assessing are performed periodically according to a core allocation period.

20. The method of claim 13, wherein the assessing comprises ranking the plurality of instances of the respective program into an execution priority order.

21. The method of claim 13, wherein the allocating comprises:

quantifying the respective volume of processing data queued to each program of one or more programs of the set of programs as a count of processing data units; and

allocating one or more units of the array of units of computing capacity to each program of the one or more programs based at least in part on the count of processing data units.