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

• US 10,437,644 B2
• Filed: 04/30/2019
• Issued: 10/08/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,593
• Publication Number:
  US 20190258519A1
• Time in Patent Office: 161 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 buffers, each input buffer being provided for buffering processing load input 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 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 buffers of the plurality of input 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 and communication path connectivity for the array of processing units, the operations comprising, for each iteration of a plurality of iterations,

allocating, to each software application of at least a portion of the plurality of software applications as a plurality of active software applications, a number of units of the array of processing units at least in part in accordance with a plurality of demand expressions, each demand expression of the plurality of demand expressions corresponding to a different software application of the plurality of software applications, wherein

each demand expression of the plurality of demand expressions is based at least in part on a measure of an amount of the processing load input at the one or more input buffers of the respective software application, wherein,

allocating results in, for at least some of the plurality of software applications, a respective one or more allocated processing units of the array of processing units,

obtaining, for each software application of the plurality of active software applications, identification of one or more tasks of the respective software application,

assigning a respective task of the one or more tasks of each application of the plurality of active software applications to at least one respective processing unit of the respective one or more allocated processing units in accordance with the allocating, wherein

for at least a portion of the plurality of active software applications, the number of processing units allocated to the respective software application is less than a number of possible tasks of the respective software application available for assigning, and

assigning comprises,

for each software application of at least a portion of the plurality of active software applications, identifying at least one activating task of the one or more tasks of the respective software application not assigned to the array of processing units for execution for a current iteration of the plurality of iterations, and

for each activating task of each software application of the portion of the plurality of active software applications, identifying at least one available unit of the array of processing units, each available unit corresponding to a respective deactivating task of at least one software application of the plurality of software applications, each deactivating task not assigned to the array of processing units for execution for a next iteration of the plurality of iterations, and

assigning the at least one activating task to the at least one available unit, and

causing connection, in accordance with the assigning, of the processing load input from each buffer of at least a portion of the plurality of input buffers to a different unit of the respective one or more allocated processing units to connect respective processing load input to a task of the one or more tasks of the respective software application that the respective processing load input is directed to;

wherein, for consecutive iterations of the plurality of iterations and for at least one software application of the plurality of active software applications,

a number of the one or more allocated processing units allocated to the respective software application varies with the measure of the processing load input at the one or more input buffers of the respective software application for the respective iteration, and

the assigning comprises assigning a varying number of tasks of concurrent instances of the respective software application corresponding to variations in the number of processing units allocated to the respective software application between the consecutive iterations.

2. The system of claim 1, wherein reconfiguring task allocation comprises, for at least one iteration of the plurality of iterations, reducing a number of the concurrent instances responsive to a reduction in the amount of the processing load input at the one or more input buffers of the respective software application.

3. The system of claim 1, wherein a plurality of executing tasks executing on at least a portion of a plurality of remaining units of the array of processing units exclusive of the at least one available unit continue processing from the current iteration through the next iteration of the plurality of iteration without interruption, wherein,

for each task of the plurality of executing tasks, a current assigned unit of the plurality of processing units for the current iteration is an upcoming assigned unit of the plurality of processing units for the next iteration.

4. The system of claim 3, wherein causing connection from the respective buffer of the one or more input buffers of the at least one software application to each unit of the one or more allocated processing units assigned one of the plurality of tasks of concurrent instances of the respective software application comprises maintaining the connection from the respective buffer to at least one executing task of the plurality of tasks of concurrent instances to continue processing from the current iteration through the next iteration.

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

7. The system of claim 1, wherein, for at least some iterations of the plurality of iterations, one or more of the expressions of demand correspond to a previously inactive application of the plurality of software applications not included in the plurality of active software applications executing on the array of processing units during the current iteration of the plurality of iterations.

8. The system of claim 1, wherein each buffer of the plurality of input buffers is a respective hardware element of a plurality of hardware elements allocated for buffering the processing load input.

9. A method for repeatedly reconfiguring task assignment to an array of processing units and communication path connectivity for the array of processing units, the method comprising:

(a) allocating, by hardware logic and/or software logic to each software application of at least a portion of the plurality of software applications as a plurality of active software applications, a number of units of the array of processing units at least in part in accordance with a plurality of demand expressions, each demand expression of the plurality of demand expressions corresponding to a different software application of the plurality of software applications, wherein

each demand expression of the plurality of demand expressions is based at least in part on a measure of an amount of the processing load input at one or more input buffers of the respective software application, wherein,

each software application of the plurality of software applications is provided one or more input buffers of a plurality of input buffers, each input buffer being provided for buffering processing load input directed to a respective software application of the plurality of software applications and being dedicated to the respective software application, wherein

a core fabric comprises the plurality of input buffers and the array of processing units, each buffer of the plurality of input buffers being deployed in the core fabric apart from the array of processing units, and

allocating results in, for at least some of the plurality of software applications, a respective one or more allocated processing units of the array of processing units;

(b) obtaining, by the hardware logic and/or software logic for each software application of the plurality of active software applications, identification of one or more tasks of the respective software application;

(c) assigning, by the hardware logic and/or software logic, a respective task of the one or more tasks of each application of the plurality of active software applications to at least one respective processing unit of the respective one or more allocated processing units in accordance with the allocating, wherein

for at least a portion of the plurality of active software applications, a number of the one or more allocated processing units allocated to the respective software application is less than a number of possible tasks of the respective software application available for assigning, and

assigning comprises,

for each software application of at least a portion of the plurality of active software applications, identifying at least one activating task of the one or more tasks of the respective software application not assigned to the array of processing units for execution during a current iteration a plurality of iterations, and

for each activating task of each software application of the portion of the plurality of active software applications, identifying at least one available unit of the array of processing units, each available unit corresponding to a respective deactivating task of at least one software application of the plurality of software applications, each deactivating task not assigned to the array of processing units for execution for a next iteration of the plurality of iterations, and

assigning the at least one activating task to the at least one available unit; and

(d) causing connection, by the hardware logic and/or software logic in accordance with the assigning, of the processing load input from each buffer of at least a portion of the plurality of input buffers to a different unit of the one or more allocated processing units of the respective software application to connect respective processing load input to a task of the one or more tasks of the respective software application that the respective input data is directed to;

wherein steps (a) through (d) are repeated for the plurality of iterations wherein, for consecutive iterations of the plurality of iterations and for at least one software application of the plurality of active software applications,

a number of the one or more allocated processing units allocated to the respective software application varies with the measure of the processing load input at the one or more input buffers of the respective software application for the respective iteration, and

the assigning comprises assigning a varying number of tasks of concurrent instances of the respective software application corresponding to variations in the number of processing units allocated to the respective application between the consecutive iterations.

10. The method of claim 9, wherein:

the assigning comprises storing mapping information identifying each mapping between a respective software application of the plurality of active software applications and a respective processing unit of the one or more allocated processing units of the respective software application; and

causing connection of the input data comprises automatically connecting the processing load input based on the mapping information.

11. The method of claim 9, further comprising identifying the measure of the amount of processing load input at the one or more input buffers of each respective software application of the plurality of software applications as a number of buffered data units.

12. The method of claim 9, wherein the hardware logic is operable to perform at least a portion of steps (a) through (d) without involvement of the software logic for at least a portion of the plurality of iterations.

13. The method of claim 9, wherein a length of each iteration of the plurality of iterations is set to a same predetermined interval.

14. The method of claim 9, wherein the respective demand expression is based at least in part on a number of ready-to-execute tasks of the one or more tasks of the respective software application.

15. The method of claim 9, wherein the obtaining comprises obtaining identification of a respective set of prioritized tasks of the one or more tasks of the respective software application.

16. The method of claim 9, wherein reconfiguring task allocation comprises, for at least one iteration of the plurality of iterations, reducing a number of the concurrent instances responsive to a reduction in the amount of the processing load input at the one or more input buffers of the respective software application.

17. The method of claim 9, wherein a plurality of executing tasks executing on at least a portion of a plurality of remaining units of the array of processing units exclusive of the at least one available unit continue processing from the current iteration through the next iteration of the plurality of iteration without interruption, wherein,

for each task of the plurality of executing tasks, a current assigned unit of the plurality of processing units during the current iteration is an upcoming assigned unit of the plurality of processing units for the next iteration.

18. The method of claim 17, wherein causing connection from the respective buffer of the one or more input buffers of the at least one software application to each unit of the one or more allocated processing units assigned one of the plurality of tasks of concurrent instances of the respective software application comprises maintaining the connection from the respective buffer to at least one executing task of the plurality of concurrent tasks to continue processing from the current iteration through the next iteration.

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

20. The method of claim 9, wherein, for at least some iterations of the plurality of iterations, one or more of the expressions of demand correspond to a previously inactive application of the plurality of software applications not included in the plurality of active software applications executing on the array of processing units during a current iteration of the plurality of iterations.