Application load adaptive multi-stage parallel data processing architecture

• US RE47,945 E1
• Filed: 07/27/2018
• Issued: 04/14/2020
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Banankhah, Majid A
• Application Number:
  US16/047,761
• Time in Patent Office: 627 Days
• Field of Search: 370413, 370412, 370203
• CPC Class Codes: N/A

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 dynamic computing resource management, the system comprising:

a first hardware logic subsystem configured to periodically, for at least some of successive core allocation periods (CAPs), execute an allocation of an array of processing cores among a set of software programs, where each of the set of software programs has one or more instances of the corresponding program, said subsystem comprising;

(i) hardware logic configured to carry out a first round of the allocation, by which round a subset of the cores are allocated among the programs so that any actually materialized demands for the cores by each of the programs up to their respective entitled shares of the cores are met; and

(ii) hardware logic configured to carry out a second round of the allocation, by which round any of the cores that remain unallocated after the first round are allocated among the programs whose materialized demands for the cores had not been met by amounts of the cores so far allocated to them by the present execution of the allocation;

a second hardware logic subsystem for buffering input data for the instances of the set of programs at an array of program instance specific input data buffers, wherein a given buffer within said array buffers such input data that is directed to the program instance associated with the given buffer, and wherein the materialized demand for the cores by a given one of the programs, for an upcoming CAP, is expressed as a digital value that is formed at least in part based on numbers of non-empty input data buffers of the given program during the ongoing CAP; and

a third hardware logic subsystem for assigning individual program instances of the set to individual cores of the array in a manner that assigns each such instance of the programs, which was selected, following the allocation, for execution on the array of cores on consecutive CAPs, to same one of the cores for execution on each of such consecutive CAPs.

2. The system of claim 1, wherein the materialized demand for the cores by a given one of the programs is expressed as a number of schedulable instances that the given program has ready for execution during the ongoing CAP.

3. The system of claim 2, wherein the number of schedulable instances of the given program is determined at least in part based on a number of instances of the given program that have input data available for processing during the ongoing CAP.

4. The system of claim 3, wherein an instance of the given program has dedicated for it a set of hardware based input data buffers, and wherein said instance is deemed to have data available for processing when at least one of its dedicated input data buffers is non-empty.

5. The system of claim 1, wherein the number of schedulable instances that the given program has ready for execution for the CAP following the present execution of the allocation is formed independently of (1) the respective numbers for other programs of the set, (2) the other programs'"'"' utilizations of any cores allocated to them, and (3) utilization of the cores across the array.

6. The system of claim 1, wherein, on at least some executions of the allocation, the subset of the cores allocated by the first round comprises zero cores, whereas, on at least some of the other executions of the allocation, the subset of the cores allocated by the first round comprises at least one, and up to all, of the, cores.

7. The system of claim 1 further comprising hardware logic configured to carry out a third round of the allocation, by which round any of the cores that remain unallocated after the second round are allocated among the programs.

8. The system of claim 1 implemented by hardware logic.

9. The system of claim 1, wherein the second hardware logic subsystem and the third hardware logic subsystem are implemented by hardware logic that operates, at least on some of the CAPs, without software involvement.

10. A dynamic computing resource management process method comprising the steps of:

a sub-process for periodically, for at least some of successive core allocation periods (CAPs), executing, by first hardware logic, an allocation of an array of processing cores among a set of software programs, where each of the set of software programs has one or more instances of the corresponding program, said sub-process allocation comprising;

(i) a first round of the allocation, by which round a subset of the cores are allocated among the programs so that any actually materialized demands for the cores by each of the programs up to their respective entitled shares of the cores are met; and

(ii) a second round of the allocation, by which round any of the cores that remain unallocated after the first round are allocated among the programs whose materialized demands for the cores had not been met by amounts of the cores so far allocated to them by the present execution of the allocation; and

a sub-process for assigning, by second hardware logic, individual program instances of the set of programs to individual cores of the array in a manner that assigns each such instance of the programs, which was selected, at least in part based on the allocation, for execution on the array of cores on consecutive CAPs, to same one of the cores for execution on each of such consecutive CAPs,

wherein;

any given instance of a given one of the programs has an array of one or more input data buffers dedicated to the given instance, and

the materialized demand for the cores by the given program is determined at least in part based on a number of instances of the given program that have input data available in at least one buffer within their respective arrays of input data buffers during the ongoing CAP.

11. The process method of claim 10, further involving a sub-process for comprising buffering, by third hardware logic, input data for instances of the programs at an array of program instance specific input data buffers, wherein a given buffer within said array buffers such input data that is directed to the program instance associated with the given buffer.

12. The process method of claim 11, wherein the materialized demand for the cores by a given one of the programs, for an upcoming CAP, is expressed as a digital value that is formed at least in part based on numbers of non-empty input data buffers of the given program during the ongoing CAP.

13. The process method of claim 10, wherein the number of schedulable instances that the given program has ready for execution for the CAP following the present execution of the allocation is formed independently of (1) the respective numbers for other programs of the set, (2) the other programs'"'"' utilizations of any cores allocated to them, and (3) utilization of the cores across the array.

14. The process method of claim 10, wherein, on at least some executions of the allocation, the subset of the cores allocated by the first round comprises zero cores, whereas, on at least some of the other executions of the allocation, the subset of the cores allocated by the first round comprises at least one, and up to all of the, cores.

15. The process method of claim 10 implemented entirely by hardware logic.

16. The process of claim 10 implemented by hardware logic that operates, at least on some of the CAPs, without software involvement.

17. The process method of claim 10, wherein the sub-process for executing the allocation further comprises a third round of the allocation, by which round any of the cores that remain unallocated after the second round are allocated among the programs.

18. A system for computing resource management, comprising:

a first sub-system for periodically, for at least some of successive core allocation periods (CAPs), executing an allocation of an array of processing cores among a set of software programs, where each of the set of software programs has one or more instances of the corresponding program, said sub-system comprising;

(i) a module for carrying out a first round of the allocation, by which round a subset of the cores are allocated among the programs so that any actually materialized demands for the cores by each of the programs up to their respective entitled shares of the cores are met; and

(ii) a module for carrying out a second round of the allocation, by which round any of the cores that remain unallocated after the first round are allocated among the programs whose materialized demands for the cores had not been met by amounts of the cores so far allocated to them by the present execution of the allocation; and

a second sub-system for assigning individual program instances of the set of programs to individual cores of the array in a manner that assigns each such instance of the programs, which was selected, based at least in part on the allocation, for execution on the array of cores on consecutive CAPs, to same one of the cores for execution on each of such consecutive CAPs,

wherein;

at least one of said sub-systems each of the first sub-system and the second sub-system is implemented in hardware logic,

any given instance of a given one of the programs has an array of one or more input data buffers dedicated to the given instance, and

the materialized demand for the cores by the given program is determined at least in part based on a number of instances of the given program that have data available in at least one buffer within their respective arrays of input data buffers during the ongoing CAP.

19. The system of claim 18, wherein the first sub-system for executing the allocation further comprising comprises a module for carrying out a third round of the allocation, by which round any of the cores that remain unallocated after the second round are allocated among the programs.

20. The system of claim 18 implemented by hardware logic that, wherein each of the first hardware logic and the second hardware logic operates, at least on some of the CAPs, without software involvement.