Application Load Adaptive Multi-stage Parallel Data Processing Architecture

• US 20170109208A1
• Filed: 09/23/2016
• Published: 04/20/2017
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Mark Henrik Sandstrom
• Original Assignee: Mark Henrik Sandstrom
• Inventors: Sandstrom, Mark Henrik
• Granted Patent: US 10,514,953 B2
• Time in Patent Office: Days
• 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-21. -21. (canceled)

22. A control system for an array of processor cores, the system comprising:

a first subsystem for allocating the cores among a set of software programs;

a second subsystem for, at least in part based on said allocating, assigning instances of said programs for execution on the cores; and

a third subsystem configured to, at least in part based on said assigning, to connect the cores and program instance specific memory segments,

wherein at least one of said subsystems is implemented in hardware logic.

23. The system of claim 22 wherein the first subsystem allocates the cores at least in part based on (i) expressions of materialized demand for the cores by the individual programs of the set and (ii) the contractual entitlements for the cores by the individual programs of the set.

24. The system of claim 23 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 for a CAP following a present execution of the allocating.

25. The system of claim 24 wherein said number of schedulable instances that the given program has ready for execution equals a number of instances of the program that have input data to process at the time.

26. The system of claim 22 wherein the configuration for the third subsystem comprises an identification of a core within the array that is assigned to process a given instance of a given program of said set.

27. The system of claim 22 wherein the configuration for the third subsystem comprises an identification of an instance of a program of said set that is placed to a given core within the array for processing.

28. The system of claim 22 wherein:

the third subsystem comprises a group of multiplexers each of which is specific to one instance of the programs, said multiplexers referred to as program instance specific multiplexers, and

the second subsystem configures a given one of the program instance specific multiplexers to connect one of the cores of the array to such one of the program instance specific memory segments that is specific to the same program instance as the given multiplexer.

29. The system of claim 22 wherein:

the third subsystem comprises a group of multiplexers each of which is specific to one of the cores, said multiplexers referred to as core specific multiplexers, and

the second subsystem configures a given one of the core specific multiplexers to connect one of the program instance specific memory segments to such a core of the array that the given multiplexer is specific to.

30. A method for computing resource management configured to periodically, once for each successive core allocation period (CAP), execute an allocation of an array of processing cores among a set of software programs, said method 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;

(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

wherein the materialized demand for the cores by a given one of the programs is expressed as a number of cores that the program is able to execute on in parallel on said succeeding CAP, and, for at least some of the CAPs, exceeds a number of the cores assigned to the program prior to said succeeding CAP.

31. The method of claim 30 wherein said number of cores that the program is able to execute on in parallel corresponds to a number of schedulable instances that the given program has ready for execution for a CAP following a present execution of the allocation.

32. The method of claim 31 wherein one of the schedulable instances is a process, task, thread, actor, method or function of the program.

33. The method of claim 31 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.

34. The method of claim 30 further including a piece of 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.

35. The method of claim 30 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.

36. The method of claim 30 wherein at least one of the materialized demand values is digitally stored at a hardware device register accessible by the allocation logic of the method.

37. A control process for an array of processor cores comprising:

for each of a number of successive core allocation periods (CAPs), selecting, from a group of instances of a set of software programs, specific instances, referred to as selected instances, for execution on the cores of the array for a next CAP; and

at least in part based on the selecting, assigning the selected instances for execution on the array of cores for the next CAP,

wherein;

the selecting is done at least in part based on respective capacity demand indications of individual programs among the set; and

the capacity demand indications, in case of at least one of the programs, are based on at least one of;

i) a measure of input data that said one program presently has available for processing, ii) a number of instances of said one program that presently have input data available for processing.

38. The process of claim 37 wherein the capacity demand indications, for at least one of the programs, are formed by hardware logic that operates, on at least some of the CAPs, without software involvement.

39. The process of claim 37 wherein at least one of the selecting and the assigning is implemented by hardware logic.

40. The process of claim 37 wherein at least one of the selecting and the assigning is implemented by hardware logic that operates, on at least some of the CAPs, without active software involvement.

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