Concurrent program execution optimization

• US 10,318,353 B2
• Filed: 09/16/2016
• Issued: 06/11/2019
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Mark Henrik Sandstrom
• Original Assignee: Mark Henrik Sandstrom
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): O Connor, Brian T
• Application Number:
  US15/267,153
• Publication Number:
  US 20170004017A1
• Time in Patent Office: 998 Days
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 8/656 while running
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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: H04L 47/78 Architectures of resource allocation

Abstract

An architecture for a load-balanced groups of multi-stage manycore processors shared dynamically among a set of software applications, with capabilities for destination task defined intra-application prioritization of inter-task communications (ITC), for architecture-based ITC performance isolation between the applications, as well as for prioritizing application task instances for execution on cores of manycore processors based at least in part on which of the task instances have available for them the input data, such as ITC data, that they need for executing.

Claims

1. A system for processing a set of computer program instances, comprising:

a plurality of processing stages, at least one of the plurality of processing stages comprising multiple processing cores, wherein,

each given task of a plurality of tasks of a given program instance of the set of program instances is hosted at a different stage of the plurality of processing stages as a local task of the given program instance at the respective stage, and

for at least one of the multiple processing cores of a given processing stage of the plurality of processing stages, a local task of one of the program instances is assigned as an active task instance for execution for a period of time; and

a group of multiplexers each connecting inter-task communications (ITC) data to a respective stage of the plurality of processing stages, wherein at least one multiplexer of the group of multiplexers is a hardware resource dedicated to the local task, wherein

the at least one multiplexer is configured to connect ITC data to any processing core of the multiple processing cores to which the local task is assigned for execution for the period of time.

2. The system of claim 1, further comprising a buffer located at a given one of the plurality of processing stages, the buffer provided to a first task of the plurality of tasks of the given program instance and being specific to another task of the plurality of tasks of the given program instance, wherein

the buffer buffers the ITC data originating from said another task to the first task.

3. The system of claim 1, further comprising:

a set of source task specific buffers each for buffering data destined for a respective task of the plurality of tasks of the given program instance located at a given stage of the plurality of processing stages; and

hardware logic for forming a hardware signal indicating whether sending ITC data is presently permitted to a given buffer of the source task specific buffers, wherein

the hardware signal is formed based at least in part on a fill level of the given buffer, and

the hardware signal is provided for a particular task of the plurality of tasks for which the given buffer is specific to.

4. The system of claim 1, wherein a destination task of the plurality of tasks of the given program instance, the destination task being located at a given processing stage of the plurality of processing stages, provides ITC prioritization information for other tasks of the plurality of tasks of the given program instance each located at a respective processing stage of the plurality of processing stages.

5. The system of claim 4, wherein:

the ITC prioritization information is provided by the destination task via one or more hardware registers, wherein

each register of the one or more hardware registers is specific to a respective task of the plurality of tasks of the given program instance, and

each register of the one or more hardware registers is configured to store a value specifying a prioritization level of respective task for purposes of communicating ITC data to the destination task.

6. The system of claim 1, further comprising an arbitrator controlling from which source task of the plurality of tasks of the given program instance a first multiplexer of the at least one multiplexer will read a next ITC data unit for the given program instance.

7. The system of claim 6, wherein the arbitrator prioritizes one of the plurality of source tasks of the program instance for selection by the first multiplexer to read the next ITC data unit based at least in part on at least one of:

i) source task specific ITC prioritization information provided by a task of the plurality of tasks of the program instance located at a destination processing stage of the next ITC data unit, and

ii) source task specific availability information of ITC data destined for the task of the plurality of tasks of the program instance from other tasks of the plurality of tasks of the program instance.

8. A method for managing execution of a plurality of instances of a program on a parallel processing system comprising an array of processor cores and a control system, the method comprising:

classifying the plurality of instances into a set of priority classes based at least in part on determining, for each instance of the plurality of instances,

(i) whether the respective instance is waiting for arrival of input data at one or more input buffers of the respective instance, and

(ii) whether the respective instance is waiting for completion of memory content transfers to update one or more fast-access memories of the respective instance; and

selecting a subset of the plurality of instances for execution on a subset of the array of processor cores based at least in part based on the classifying, wherein

at least one of the classifying and the selecting is performed by the control system.

9. The method of claim 8, wherein, for each instance of the plurality of instances:

each of the one or more input buffers of the respective instance is specific to a different one of one or more possible data sources for the respective instance;

the method further comprises ranking said one or more possible data sources into two or more priority levels including (i) a high priority data source level, and (ii) one or more other priority levels; and

the classifying, based at least in part on whether the respective instance is waiting for arrival of input data at one or more input buffers, comprises classifying based at least in part on whether the respective instance is waiting for arrival of input data at an empty input buffer of the one or more input buffers ranked into the high priority data source level.

10. The method of claim 9, wherein ranking the one or more possible data sources comprises ranking a given data source of the one or more possible data sources at the high priority data source level at a given time based on determining that the respective instance is expecting data from the given data source to enable the respective instance to execute.

11. The method of claim 9, wherein ranking the one or more possible data sources comprises ranking, at a given time, at least one data source of the one or more possible data sources at the high priority data source level according to a determination that the respective instance needs input data from the at least one data source to produce processing outputs.

12. The method of claim 8, wherein classifying the plurality of instances further comprises determining that a respective fill level of at least one of the one or more input buffers of the respective instance is above a defined threshold.

13. The method of claim 8, wherein:

a subset of the one or more input buffers of the respective instance are designated high priority input data buffers; and

classifying the plurality of instances based at least in part on whether the respective instance is waiting for arrival of input data comprises determining whether the respective instance has input data at the subset of the input buffers.

14. The method of claim 8, wherein:

a subset of the one or more input buffers of the respective instance are designated high priority input data buffers; and

classifying the plurality of instances comprises determining whether a respective fill level of at least one of the high priority input buffers of the given instance is above a defined threshold.

15. The method of claim 8, wherein:

the classifying and the selecting are each repeated for a plurality of time intervals; and

at least one of the classifying and the selecting is implemented by a hardware logic subsystem of the control system, wherein the hardware logic subsystem is capable of operating, on at least some time intervals of the plurality of time intervals, without software involvement.

16. The method of claim 8, wherein:

the classifying and the selecting are each repeated over time; and

the classifying and the selecting are implemented by a hardware logic subsystem of the control system, wherein the hardware logic subsystem is capable of operating, for at least a portion of the time, without software involvement.

17. A control system for an array of processing cores shared among a set of software programs, the control system comprising:

a plurality of fast-access memories, wherein each memory of the plurality of fast-access memories is a hardware resource constantly dedicated to an associated instance of a plurality of instances of the set of software programs;

a subsystem for

updating contents of one or more of the plurality of fast-access memories, and

indicating whether contents of any given memory of the plurality of fast-access memories are updated, wherein

indicating that the contents of a respective memory of the plurality of fast-access memories are updated comprises indicating that the contents are updated when the contents are ready for execution of the associated instance; and

a controller for allocating the array of processing cores among the set of software programs, for execution of one or more instances of each of the set of software programs, wherein allocating comprises allocating based at least in part on a respective number of instances of each program of the set of software programs having a respective dedicated fast-access memory indicated as updated.

18. The system of claim 17, wherein the numbers of the instances of each program of the set of software programs having the respective dedicated fast-access memories indicated as updated, for a given time period, include both one or more instances executing during a prior time period, and one or more instances not executing during the prior time period.

19. The system of claim 17, wherein:

the classifying and the selecting are each repeated for a plurality of time intervals; and

at least one of (i) the subsystem and (ii) the controller is implemented by hardware logic capable of operating, on at least some time intervals of the plurality of time intervals, without software involvement.

20. The system of claim 17, wherein:

the classifying and the selecting are each repeated for a plurality of time intervals; and

the subsystem and the controller are implemented by hardware logic capable of operating, on at least some time intervals of the plurality of time intervals, without software involvement.

21. A system for managing execution of a plurality of instances of a program on an array of processor cores, the system comprising:

a subsystem for classifying the plurality of instances into a set of priority classes based at least in part on determining, for each instance of the plurality of instances,

(i) whether the respective instance is waiting for arrival of input data at one or more input buffers of the respective instance, and

(ii) whether the respective instance is waiting for completion of memory content transfers to update one or more fast-access memories of the respective instance; and

a subsystem for selecting a subset of the plurality of instances for execution on a subset of the array of processor cores based at least in part on the classifying;

wherein at least one of the subsystem for classifying and the subsystem for selecting comprises digital hardware logic.

22. The system of claim 21, wherein, for each instance of the plurality of instances:

each of the one or more input buffers of the respective instance is specific to a different one of one or more possible data sources for the respective instance, wherein

the one or more input buffers include, for at least a portion of the plurality of instances, at least one input buffer having a high priority data source level; and

the classifying, based at least in part on whether the respective instance is waiting for arrival of input data at one or more input buffers, comprises classifying based at least in part on whether the respective instance is waiting for arrival of input data at an input buffer of the one or more input buffers having the high priority data source level.

23. The system of claim 21, wherein classifying the plurality of instances further comprises determining that a respective fill level of at least one of the one or more input buffers of the respective instance is above a defined threshold.

24. The system of claim 21, wherein:

a subset of the one or more input buffers of the respective instance are designated high priority input data buffers; and

classifying the plurality of instances based at least in part on whether the respective instance is waiting for arrival of input data comprises determining whether the respective instance has input data at the subset of the input buffers.

25. The system of claim 21, wherein:

the classifying and the selecting are each repeated over time; and

the digital hardware logic is capable of operating, for at least a portion of the time, without software involvement.