Task switching and inter-task communications for coordination of applications executing on a multi-user parallel processing architecture

• US 10,430,242 B2
• Filed: 04/30/2019
• Issued: 10/01/2019
• 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/399,567
• Publication Number:
  US 20190258518A1
• Time in Patent Office: 154 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 for managing execution of a plurality of software applications on an array of processing units, the system comprising:

a core fabric comprising

the array of processing units, and

a plurality of input data buffers, each input data buffer being provided for buffering input data directed to a respective software application of the plurality of software applications and being dedicated to the respective software application, wherein

each buffer of the plurality of input data buffers is deployed in the core fabric apart from the array of processing units, and

each software application of the plurality of software applications is provided one or more input data buffers of the plurality of input data buffers; and

a controller comprising hardware logic and/or software logic for performing operations for repeatedly reconfiguring task assignment to the array of processing units, the operations comprising, for each iteration of a plurality of iterations,

identifying, for each software application of at least a portion of the plurality of software applications, an amount of input data at one or more input data buffers of the plurality of input data buffers buffering data for the respective software application,

allocating, to each software application of the portion of the plurality of software applications, a number of processing units of the array of processing units based at least in part on the amount of input data buffered for the respective software application, and

for each software application of the portion,

i) assigning one or more task instances of the respective software application for concurrent processing of the amount of input data to the number of processing units allocated to the respective software application by the allocating as one or more assigned instances, and

ii) adjusting, based at least in part on a change in a count of units between the number of processing units allocated to the respective software application and a number of previously allocated processing units allocated to the respective software application during a previous iteration of the plurality of iterations, a relative portion of the amount of input data to be processed by at least one assigned instance of the one or more assigned instances;

wherein, for one or more iterations of the plurality of iterations where a current number of the one or more processing units allocated to any given software application of the portion of the plurality of software applications is increased by the allocating, adjusting comprises relatively decreasing the portion of the amount of input data to be processed by at least one instance of the one or more assigned instances of the respective software application; and

wherein for one or more other iterations of the plurality of iterations where a present number of the one or more processing units allocated to any given software application of the portion of the plurality of software applications is decreased by the allocating, adjusting comprises relatively increasing the portion of the amount of input data to be processed by at least one instance of the one or more assigned instances of the respective software application.

2. The system of claim 1, wherein identifying the amount of input data comprises identifying a number of buffered data units at the one or more input buffers of the plurality of input buffers buffering input data for the respective software application.

3. The system of claim 1, wherein:

assigning results in a plurality of newly assigned processing units of the array of processing units for one or more applications of the portion of the plurality of software applications, wherein

each newly assigned processing unit was assigned to a different task of a respective one of the plurality of applications during a previous iteration of the plurality of iterations; and

the operations further comprise causing connection, in accordance with the assigning, of the input data from each buffer of at least a portion of the plurality of input data buffers to a different unit of the plurality of newly assigned processing units assigned to a respective application of the portion of the plurality of software applications to connect respective input data to the respective software application that the respective input data is directed to.

4. The system of claim 3, wherein:

the assigning comprises storing mapping information identifying each mapping between a respective assigned instance of the one or more assigned instances of a given software application of the portion of the plurality of software applications and a respective processing unit of the plurality of allocated processing units to which the respective assigned instance is placed; and

causing connection comprises automatically connecting using hardware logic of the system based on the mapping information.

5. The system of claim 1, wherein the controller is operable to perform the operations by hardware logic operating without software involvement for at least a portion of the plurality of iterations.

6. The system of claim 1, wherein the input data comprises at least one of a plurality of data records for processing, a plurality of instructions for processing, an identification of data records for processing, and an identification of instructions.

7. A system for managing execution of a plurality of software applications on an array of processing cores, the system comprising:

the array of processing cores; and

a controller comprising hardware logic and/or software logic for performing operations for repeatedly reconfiguring task assignment to the array of processing cores, the operations comprising, for each iteration of a plurality of iterations,

identifying, for each software application of at least a portion of the plurality of software applications, a processing load input at one or more input buffers provided for buffering information for the respective software application,

allocating, to each software application of the portion of the plurality of software applications, one or more processing cores of the array of processing cores based at least in part on the processing load input for the respective software application, and

for each software application of the portion,

i) identifying one or more previously assigned task instances of the respective software application for processing of the processing load input of the respective software application, wherein the one or more previously assigned task instances were each assigned to a respective processing core of the array of processing cores during a previous iteration of the plurality of iterations,

ii) assigning one or more task instances of the respective software application for processing of the processing load input to the one or more processing units allocated to the respective software application by the allocating as one or more assigned instances, wherein the one or more previously assigned task instances are prioritized in placing to the array of processing cores ahead of any other assigned instances of the respective software application; and

iii) providing a portion of the processing load input to each task instance of the one or more assigned instances for concurrent processing of the processing load input;

wherein, for one or more iterations of the plurality of iterations where a current number of the one or more processing cores allocated to any given software application of the portion of the plurality of software applications is increased by the allocating, providing the portion of the processing load input comprises relatively decreasing the portion of the processing load input to be processed by at least one of the assigned instances placed to at least one core of the one or more of processing cores allocated to the respective software application; and

wherein, for one or more other iterations of the plurality of iterations where a present number of the one or more processing cores allocated to any given software application of the portion of the plurality of software applications is decreased by the allocating, providing the portion of the processing load input comprises relatively increasing the portion of the processing load input to be processed by at least one of the assigned instances placed to at least one core of the one or more of processing cores allocated to the respective software application.

8. The system of claim 7, further comprising:

a plurality of input data buffers, each input data buffer being provided for buffering the information directed to a respective software application of the plurality of software applications and being dedicated to the respective software application, wherein

each software application of the plurality of software applications is provided one or more input data buffers of the plurality of input data buffers;

wherein identifying the processing load input comprises identifying an amount of input data at the one or more input data buffers provided to the respective software application.

9. The system of claim 8, wherein identifying the amount of input data comprises identifying a number of buffered data units.

10. The system of claim 8, wherein:

assigning results in a plurality of newly assigned processing cores of the array of processing cores for one or more applications of the portion of the plurality of software applications, wherein

each newly assigned processing core was assigned to a different task of a respective one of the plurality of applications during a previous iteration of the plurality of iterations; and

the operations further comprise causing connection, in accordance with the assigning, of the input data from each buffer of at least a portion of the plurality of input data buffers to a different core of the plurality of newly assigned processing cores assigned to a respective application of the portion of the plurality of software applications to connect respective input data to the respective software application that the respective input data is directed to.

11. The system of claim 10, wherein:

the assigning comprises storing mapping information identifying each mapping between a respective assigned instance of the one or more assigned instances of a given software application of the portion of the plurality of software applications and a respective processing core of the array of processing cores to which the respective assigned instance is placed; and

causing connection comprises automatically connecting the input data using hardware logic of the system based on the mapping information.

12. The system of claim 7, wherein assigning the one or more task instances comprises maintaining prior assignment of each instance of at least one of the one or more previously assigned task instances to a respective processing core of the array of processing cores assigned to the respective instance during the previous iteration.

13. The system of claim 7, wherein the controller is operable to perform the operations by hardware logic operating without software involvement for at least a portion of the plurality of iterations.

14. The system of claim 7, wherein the processing load input comprises at least one of input data for processing, a plurality of instructions for processing, an identification of input data, and an identification of instructions.

15. A system for managing execution of a plurality of software programs on a plurality of processing units on behalf of a plurality of users, the system comprising:

the plurality of processing units; and

a plurality of subsystems comprising hardware logic and/or software logic for performing operations for repeatedly reconfiguring task distribution on the array of processing units, the plurality of subsystems comprising

a first subsystem comprising hardware logic and/or software logic for identifying, for each software program of at least a portion of the plurality of software programs, a processing load input at one or more input buffers provided for buffering information for the respective software program,

a second subsystem comprising hardware logic and/or software logic for allocating, to each software program of the portion of the plurality of software programs, a number of processing units of the plurality of processing units based at least in part on the processing load input for the respective software program identified by the first subsystem,

a third subsystem comprising hardware logic and/or software logic for assigning, for each software program of the portion of the plurality of software programs, one or more active task instances of the respective software program to one or more processing units of the plurality of processing units, wherein

a count of the one or more active task instances equals the number of processing units allocated to the respective software program by the second subsystem, and

the one or more active task instances are assigned for processing of the processing load input, and

a fourth subsystem comprising hardware logic and/or software logic for providing, for each software program of the portion of the plurality of software programs, a portion of the processing load input of the respective software program to each task instance of the one or more active task instances of the respective software program for concurrent processing of the processing load input;

wherein the identifying, the allocating, the assigning, and the providing are repeated for a plurality of iterations, wherein, for a given iteration of the plurality of iterations and a given program of the plurality of software programs,

when the number of units allocated to the respective program is increased from a previous number of units allocated to the respective allocation during a previous iteration of the plurality of iterations, providing the portion of the processing load input comprises relatively decreasing a previously provided portion of the processing load input to at least one task instance of the one or more active task instances of the respective software program, and

when the number of units allocated to the respective program is decreased from the previous number of units allocated to the respective allocation during the previous iteration of the plurality of iterations, providing the portion of the processing load input comprises relatively increasing a previously provided portion of the processing load input to at least one task instance of the one or more active task instances of the respective software program.

16. The system of claim 15, wherein:

the third subsystem further comprises hardware logic and/or software logic for identifying, for each software program of the portion of the plurality of software programs, one or more previously assigned task instances for processing of the processing load input of the respective software program, wherein the one or more previously assigned task instances were each assigned to a respective processing unit of the array of processing units during a previous iteration of the plurality of iterations; and

the assigning comprises prioritizing placement of the one or more previously assigned task instances ahead of any unassigned one or more instances of the respective software program to the array of processing units.

17. The system of claim 16, wherein assigning the one or more task instances comprises maintaining prior assignment of each instance of at least one of the one or more previously assigned task instances to a respective processing unit of the plurality of processing unit assigned to the respective instance during the previous iteration.

18. The system of claim 15, further comprising:

a plurality of input data buffers, each input data buffer being provided for buffering the information directed to a respective software program of the plurality of software programs and being dedicated to the respective software program, wherein

each software program of the plurality of software programs is provided one or more input data buffers of the plurality of input data buffers;

wherein identifying the processing load input comprises identifying an amount of input data at the one or more input data buffers provided to the respective software program.

19. The system of claim 18, wherein identifying the amount of input data comprises identifying a number of buffered data units.

20. The system of claim 18, wherein:

assigning results in a plurality of newly assigned processing units of the plurality of processing units for one or more programs of the plurality of software programs, wherein

each newly assigned processing unit was assigned to a different task of a respective one of the plurality of software programs during a previous iteration of the plurality of iterations; and

the plurality of subsystems further comprises

a fifth subsystem comprising hardware logic and/or software logic for causing connection, in accordance with the assigning, of the input data from each buffer of at least a portion of the plurality of input data buffers to a different unit of the plurality of processing units assigned to a respective program of the portion of the plurality of software programs to connect respective input data to the respective program that the respective input data is directed to.

21. The system of claim 20, wherein:

the assigning comprises storing mapping information identifying each mapping between a respective assigned instance of the one or more assigned instances of a given software program of the portion of the plurality of software programs and a respective processing unit of the plurality of allocated processing units; and

causing connection comprises automatically connecting using hardware logic of the system based on the mapping information.

22. The system of claim 15, wherein the controller is operable to perform the operations by hardware logic operating without software involvement for at least a portion of the plurality of iterations.

23. The system of claim 15, wherein the processing load input comprises at least one of input data for processing, a plurality of instructions for processing, an identification of input data, and an identification of instructions.