Systems and methods for managing resource allocation and concurrent program execution on an array of processor cores

• US 10,514,953 B2
• Filed: 09/23/2016
• Issued: 12/24/2019
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US15/273,731
• Publication Number:
  US 20170109208A1
• Time in Patent Office: 1,187 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 controlling access to an array of processor cores on behalf of a plurality of users, each user presenting one or more programs of a plurality of software programs for execution upon the array of processor cores, the system comprising:

a plurality of program specific data buffers, each buffer being dedicated to a respective program of the plurality of software programs such that each program of at least a portion of the plurality of software programs has a respective one or more buffers of the plurality of program specific data buffers dedicated to the respective program;

a plurality of multiplexers; and

a plurality of subsystems each implemented in hardware logic and/or software logic, the plurality of subsystems comprising

a first subsystem configured to allocate the array of processor cores among the plurality of software programs of the plurality of users, wherein

each user of the plurality of users submitted one or more software programs of the plurality of software programs for execution on the array of processor cores, and

allocating comprises allocating, to each program of the plurality of software programs, a respective number of cores of the array of processor cores as one or more allocated cores of the respective program,

a second subsystem configured to, at least in part based on said allocating, assign one or more instances of each program of at least a subset of the plurality of software programs as selected instances for execution on the one or more allocated cores of the respective program, wherein

each selected instance is assigned to a different core of the one or more allocated cores of the respective program corresponding to the respective instance,

for each program of at least a portion of the plurality of software programs, the number of cores allocated to the respective program is less than a number of possible instances of the respective program available for assigning,

and

number of the one or more selected instances equals number of the one or more allocated cores allocated to the respective program by the allocating, and

a third subsystem configured to, at least in part based on said assigning, establish connections between the array of processor cores and the plurality of program specific data buffers, wherein

establishing connections comprises, for each core of at least a portion of the array of processor cores, establishing, via one or more multiplexers of the plurality of multiplexers, a data read connection to the respective core from one or more data buffers of the plurality of program specific data buffers specific to a program of the plurality of software programs corresponding to the respective instance assigned to the respective core by the second subsystem of the one or more selected instances of the program, such that the one or more buffers of each program of the portion of the plurality of software programs are multiplexed, via one or more different multiplexers of the plurality of multiplexers, to respective one or more cores to which the one or more selected application instances of the respective program were assigned by the second subsystem;

wherein the allocating, the assigning, and the establishing are repeated over time to respond to demand expressions of the plurality of software programs for the array of processor cores.

2. The system of claim 1, wherein the first subsystem allocates the array of processor cores at least in part based on

(i) expressions of materialized demand for the array of processor cores by individual programs of the plurality of software programs, and

(ii) contractual entitlements for access to the array of processor cores by one or more programs of the plurality of software programs.

3. The system of claim 2, wherein the materialized demand for the array of processor cores by a given one of the plurality of software programs is expressed as a number of schedulable instances of the given program ready for execution during a core allocation period (CAP) following a present execution of the allocating.

4. The system of claim 3, wherein said number of schedulable instances equals a number of instances of the given program that have input data to process at a time of the allocating.

5. The system of claim 1, wherein the third subsystem is configured to identify, for each instance of a plurality of software instances assigned by the second subsystem, a core within the array of processor cores assigned to the respective instance.

6. The system of claim 1, wherein the third subsystem is configured to identify, for each core of the array of processor cores, an instance of a program of the plurality of software programs assigned to the respective core by the second subsystem.

7. The system of claim 1, wherein:

the plurality of multiplexers comprises a plurality of program instance specific multiplexers, each program instance specific multiplexer being specific to one instance of one of the plurality of software programs; and

establishing connections between the array of processor cores and the plurality of program specific data buffers comprises, for each core of at least a portion of the array of processor cores, establishing, using the program instance specific multiplexer of the instance assigned to the respective core, a connection between the respective core and the program specific data buffer of a program of the plurality of software programs corresponding to the instance assigned to the respective core.

8. The system of claim 1, further comprising:

a plurality of core specific multiplexers;

wherein establishing the read-mode connection comprises configuring a core specific multiplexer of the plurality of core specific multiplexers corresponding to the respective core to connect one of the program specific data buffers to the respective core.

9. The system of claim 1, wherein the plurality of program specific data buffers comprises a plurality of program instance specific data buffers, each dedicated to a respective instance of a respective program of the plurality of software programs.

10. A process, implemented on hardware logic and/or software logic, for managing execution of a set of software applications on an array of processing cores, the process comprising:

allocating, by the hardware logic and/or software logic, the array of processing cores among the set of software applications, wherein

each user of a plurality of users submitted one or more software applications of the set of software applications for execution on the array of processing cores, and

allocating comprises allocating, to each application of the set of software applications, a respective number of cores of the array of processing cores as one or more allocated cores of the respective application;

prioritizing, by the hardware logic and/or software logic for each application of the set of software applications, a set of executable instances of the respective application into an execution priority order;

selecting, by the hardware logic and/or software logic for each application of at least a subset of the set of software applications, one or more selected instances of the set of executable instances of the respective application for execution on the array of processing cores, wherein

number of the one or more selected instances equals the number of cores allocated to the respective application by the allocating,

the one or more selected instances are selected according to the execution priority order of the set of executable instances of the respective application, and

for each application of at least a portion of the set of software applications, the number of cores allocated to the respective application is less than a number of possible instances of the respective application available for selecting;

at least in part based on the selecting, assigning, by the hardware logic and/or software logic, each instance of a plurality of selected instances for execution on the array of processing cores, wherein,

for each software application of the set of software applications, each instance of the one or more selected instances is assigned to a different core of the one or more allocated cores of the respective software application; and

establishing connections, by the hardware logic and/or software logic, between the array of processing cores and a plurality of application specific data buffers, each buffer of the plurality of application specific data buffers being dedicated to a respective application of the set of software applications such that each application of at least a portion of the set of software applications has a respective one or more buffers of the plurality of program specific data buffers dedicated to the respective application,

wherein

establishing connections comprises, for each core of at least a portion of the array of processing cores, establishing a connection to the respective core from one or more data buffers of the plurality of application specific data buffers, wherein

the one or more data buffers are each specific to an application of the set of software applications corresponding to an instance assigned to the respective core, and

each of the plurality of application specific data buffers is accessible to the array of processing cores via multiplexed connections, such that the one or more buffers of each application of a portion of the set of software applications are multiplexed, via one or more different multiplexers of a plurality of multiplexers, to respective one or more cores to which the one or more selected application instances of the respective program were assigned;

wherein the process is repeated periodically.

11. The process of claim 10, further comprising assigning, by the hardware logic and/or software logic, particular cores of the array of processing cores for executing the plurality of selected instances, such that any active instances of the plurality of selected instances executing on the array of processing cores during a current period remain assigned to the one or more cores of the array of processing cores assigned to the active instances for a next period.

12. The process of claim 10, wherein:

each application of at least a portion of the set of software applications comprises an entitlement for access to the array of processing cores; and

the allocating seeks to meet a respective processing core demand of each application of the portion of the set of software applications up to the respective entitlement before allocating remaining cores of the array of processing cores among the set of software applications.

13. The process of claim 10, wherein the allocating comprises:

during a first round of allocation, allocating a subset of the array of processing cores among the set of software applications so that any materialized demand for the array of processing cores by each application of the set of software applications up to a respective entitled share of the array of processing cores is met; and

during a second round of allocation after the first round, allocating any cores of the array of processing cores remaining unallocated after the first round among any applications of the set of software applications having residual demand of the materialized demand not met during the first round;

wherein the materialized demand for the array of processing cores by each application of the set of software applications is expressed as a number of cores of the array of processing cores on which the respective application is presently able to execute concurrently.

14. The process of claim 10, wherein the prioritizing is based at least in part on respective amounts of input data for the one or more instances of the respective application.

15. The process of claim 10, wherein:

the allocating comprises allocating a respective number of cores of the array of processing cores to each application of the set of software applications in consideration of respective needs for resources of the array of processing cores of the other applications of the set of applications; and

after the allocating, the prioritizing and the selecting are performed for each application of the set of software applications independent of consideration of the other applications of the set of software applications.

16. The process of claim 10, wherein at least one of the allocating, the prioritizing, and the selecting is implemented by the hardware logic that operates, on at least some periods of performing the process, without active software involvement by the software logic.