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

• US 10,620,998 B2
• Filed: 09/20/2019
• Issued: 04/14/2020
• 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/577,909
• Publication Number:
  US 20200034199A1
• Time in Patent Office: 207 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 method for managing execution of a plurality of software applications on an array of processing units, the method comprising:

providing, for each software application of the plurality of software applications, 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; and

repeatedly rearranging, by a controller comprising hardware logic and/or software logic, task assignment to the array of processing units and communication path connectivity for the array of processing units, wherein

the array of processing units comprises a plurality of processing units of a reconfigurable type, each being configurable in two or more application specific configurations, and

rearranging comprises, for each iteration of a plurality of iterations,

allocating, to each software application of at least a portion of a plurality of software applications as a set 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 a processing load input at the one or more input buffers of the respective software application,

assigning, for each application of the set of active software applications, one or more task instances of the respective active application to one or more processing units of the plurality of processing units in accordance with the allocating, wherein

at least one task instance of the one or more task instances is a ready-to-execute task instance of the respective software application for processing the data at the one or more input data buffers of the respective software application,

each task instance of the one or more task instances is assigned to a different processing unit of the one or more processing units such that assigning results in each processing unit of the plurality of processing units being assigned only one respective task instance for any given iteration of the plurality of iterations, and

assigning comprises, for at least one task instance of the one or more task instances of a given software application of the plurality of software applications, reconfiguring the respective processing unit to an application specific configuration of the two or more application specific configurations, wherein the application specific configuration is associated with the at least one task instance, 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 plurality of processing units to connect respective processing load input to the respective software application that the respective processing load input is directed to.

2. The method of claim 1, wherein the respective demand expression is based at least in part on a number of ready-to-execute task instance of one or more task instances of the respective software application.

3. The method of claim 2, wherein the assigning comprises:

identifying at least one activating task instance not allocated to the array of processing units for execution during a current iteration of the plurality of iterations, each activating task instance of the at least one activating task instance corresponding to one of the plurality of software applications;

identifying at least one available unit of the array of processing units, each available unit corresponding to a respective deactivating task instance of at least one deactivating task instance, each deactivating task instance of the at least one deactivating task instance corresponding to one of the plurality of software applications; and

mapping each activating task instance of the at least one activating task instance to a different unit of the at least one available unit.

4. The method of claim 1, wherein causing connection of the processing load input comprises, during the assigning, storing mapping information identifying each mapping between a respective software application of the set of active software applications and a respective processing unit of the plurality of processing units, wherein

the processing load input is automatically connected based on the mapping information.

5. The method of claim 1, wherein the reconfiguring further comprises identifying the amount of data at the input buffer of each respective software application of the set of active software applications as a number of buffered input units.

6. The method 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.

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

8. The method 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 processing load input.

9. The method 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.

10. The method of claim 1, wherein the array of processing units comprises at least two types of units including the units of a reconfigurable type.

11. The method of claim 1, wherein the plurality of software applications comprises two or more instances of a same application of the plurality of software applications.

12. The method of claim 1, wherein the plurality of software applications comprises at least one instance of a first software application and at least one instance of a second software application different than the first software application.

13. A method for managing execution of a plurality of software applications on an array of processing units, the method comprising:

providing a core fabric comprising

the array of processing units comprising a plurality of processing units of a reconfigurable type, each processing unit of the reconfigurable type being configurable in two or more application specific configurations, and

a plurality of input buffers, each input buffer being allocated 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 software application of the plurality of software applications is allocated one or more input buffers of the plurality of input buffers; and

repeatedly rearranging, by a controller comprising hardware logic and/or software logic, 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 set 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 measurement of an amount of processing load input at the one or more input buffers of the respective software application,

assigning, for each software application of the portion of the plurality of software applications, one or more task instances of the respective software application for execution on the number of units allocated to the respective software application, wherein assigning comprises, for at least one application of the portion of the plurality of software applications,

identifying at least one activating task instance not allocated to the array of processing units for execution during a current iteration of the plurality of iterations, each activating task instance of the at least one activating task instance corresponding to a particular software application of the plurality of software applications,

identifying at least one available unit of the array of processing units, each available unit corresponding to a respective deactivating task instance of at least one deactivating task instance,

mapping each activating task instance of the at least one activating task instance to a different unit of the at least one available unit, and

for one or more task instances of the at least one activating task instance, reconfiguring the respective available unit to an application specific configuration of the two or more application specific configurations, wherein the application specific configuration is associated with the at least one task instance, and

for each unit of the at least one available unit,

enabling connection between the respective unit and a respective input buffer of the one or more input buffers allocated to buffering processing load input for a respective software application of the task instance mapped to the respective unit.

14. The method of claim 13, wherein rearranging comprises:

obtaining, from each software application of at least a portion of the plurality of software applications, a respective set of prioritized task instances of one or more task instances of the respective software application; and

assigning, for each software application of the portion of the plurality of software applications, one or more task instances of the respective set of prioritized task instances for execution on the number of units allocated to the respective software application, wherein

the assigning comprises the identifying the at least one activating task instance, and the identifying the at least one available unit.

15. The method of claim 14, wherein each set of prioritized task instances represents a number of ready-to-execute task instances of the one or more task instances of the respective software application.

16. The method of claim 13, 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.

17. The method of claim 13, 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.

18. The method of claim 13, wherein the array of processing units comprises at least two types of processing units including the plurality of processing units of a reconfigurable type.

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

20. The method of claim 13, wherein the plurality of software applications comprises two or more instances of a same application of the plurality of software applications.

21. The method of claim 13, wherein the plurality of software applications comprises at least one instance of a first software application and at least one instance of a second software application different than the first software application.