Method and apparatus for a general-purpose multiple-core system for implementing stream-based computations

• US 10,073,700 B2
• Filed: 09/22/2014
• Issued: 09/11/2018
• Est. Priority Date: 03/22/2001
• Status: Active Grant

• Current Assignee: Cornami, Inc.
• Original Assignee: Cornami, Inc.
• Inventors: Furtek, Frederick, Master, Paul
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US14/492,705
• Publication Number:
  US 20150012725A1
• Time in Patent Office: 1,450 Days
• Field of Search: None
• CPC Class Codes: G06F 15/17362 hierarchical topologies
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method and system of efficient use and programming of a multi-processing core device. The system includes a programming construct that is based on stream-domain code. A programmable core based computing device is disclosed. The computing device includes a plurality of processing cores coupled to each other. A memory stores stream-domain code including a stream defining a stream destination module and a stream source module. The stream source module places data values in the stream and the stream conveys data values from the stream source module to the stream destination module. A runtime system detects when the data values are available to the stream destination module and schedules the stream destination module for execution on one of the plurality of processing cores.

Claims

1. A system to convert stream-based computer source code to efficiently operate a multi-core computer system to perform runtime operations, the conversion system comprising:

a plurality of cores

a memory device storing the stream-based computer source code, wherein the source code includes one or more module definitions for creating tasks running on the plurality of cores, each module definition having a list of input streams, a list of output streams, and a body, the body including code for executing a task on at least one of the plurality of cores;

a conversion system including at least one of the plurality of cores, the conversion system creating and assigning a collection of tasks for execution on one or more of the plurality of processing cores from the stream-based computer source code, wherein each task is an executable version of a module definition with a stream expression in the source code, the stream expression containing module input streams and output streams and the stream expression further defining how output-stream data values are computed from input-stream data values, each task further having input streams and output streams corresponding to the input streams and output streams of the source-code module definition wherein at least one of the input streams has an output stream of another task of the collection of tasks as a stream source and at least one of the output streams has an input stream of another task of the collection of tasks as a stream destination, wherein at least one task consumes an array of multiple separate streams by conveying data elements from each respective stream in the array concurrently to input streams of the at least one task.

2. The system of claim 1, wherein the source code includes a function definition having variables as inputs and outputs, wherein the function definition and module definition are distinguishable from each other.

3. The system of claim 1, wherein each task corresponding to a source-code module definition:

causes a data value to be consumed, when it becomes available, from a task-input-stream first-in-first-out queue when the task thread of control encounters an instruction for obtaining a data value from the task input stream,

causes a data value to be placed into a task output stream when the task thread of control encounters an instruction for placing a data value into the output stream, and

causes the data value to be placed in the first-in-first-out queue corresponding to the destination of the corresponding source-code stream.

4. The system of claim 1, wherein each task corresponding to a stream expression:

causes a data value to be consumed, when it becomes available, from a task-input-stream first-in-first-out queue,

causes a data value to be placed into the task output stream each time the stream expression is evaluated, and

causing the data value to be placed in the first-in-first-out queue corresponding to the destination of the corresponding source-code stream.

5. The system of claim 1, wherein the stream-based computer source code specifies an interconnection of module definitions and stream expressions, the module definitions being instances of modules defined in the computer source code or in an included library, the stream expressions being identical to ordinary computer-program expressions except having variables replaced by streams, and the interconnection consisting of streams connecting one or more of:

an input stream of the module definition to an input stream of a module instance or stream expression, an output stream of a module instance or stream expression to an input stream of a module instance or stream expression, or an output stream of a module instance or stream expression to an output stream of the module definition.

6. The system of claim 1, wherein the conversion system assigns each processing core zero or more tasks to be performed;

and wherein each processing core includes a task manager managing the execution of each of the tasks assigned to the respective processing core.

7. The system of claim 6, wherein the task manager manages execution of tasks on multiple processing cores.

8. The system of claim 6, wherein the task manager maintains a consumer count for each input stream of each task, a producer count for each output stream of each task, a ready-to-run queue of tasks ready to executed, an input count for each task that determines the number of task input streams that are required to be enabled in order for a task to be ready to run, and an output count for each task that determines the number of task output streams that are required to be enabled in order for a task to be ready to run.

9. The system of claim 1, wherein the stream-based computer source code includes a stream that is elevated to first-class status permitting the stream to be bound to be an identifier, an input parameter of a function, an output of a function, a parameter within an expression or an output of an expression.

10. The system of claim 1, wherein the stream-based computer source code includes a ping stream that conveys pings having no associated data values from a ping-stream source to a ping-stream destination, wherein the ping stream provides synchronization for one or more tasks of the collection of tasks.

11. The system of claim 1, wherein the stream-based computer source code includes an assignment statement causing the output stream of the stream expression to become a source of a second previously declared stream.

12. The system of claim 1, further comprising an interconnection network coupled to the memory device and the plurality of processing cores, the interconnection network conveying data values between the memory device and the plurality of processing cores, and wherein the interconnection network and the plurality of processing cores constitute a runtime system.

13. A method to convert stream-based computer source code to efficiently operate a multi-core computer system including a plurality of processing cores to perform runtime operations, the method comprising:

storing a stream-based computer source code in a memory device, wherein the source code includes one or more module definitions for creating tasks running on the plurality of cores, each module definition having a list of input streams, a list of output streams, and a body, the body including code for executing a task on at least one of the plurality of cores;

creating and assigning a collection of tasks for execution on one or more of a plurality of processing cores from the stream-based computer source code, wherein each task is an executable version of a module definition with a stream expression in the source code, the stream expression containing module input streams and output streams and the stream expression further defining how output-stream data values are computed from input-stream data values, each task further having input streams and output streams corresponding to the input streams and output streams of the source-code module definition, wherein at least one of the input streams has an output stream of another task of the collection of tasks as a stream source and at least one of the output streams has an input stream of another task of the collection of tasks as a stream destination, wherein at least one task consumes an array of multiple separate streams by conveying data elements from each respective stream in the array concurrently to input streams of the at least one task; and

executing the collection of tasks on the plurality of processing cores to perform runtime operations.

14. The method of claim 13, further comprising conveying via an interconnection network data values between the plurality of processing cores and the memory device.

15. The method of claim 13, wherein the stream-based computer source code includes a function definition having variables as inputs and outputs, wherein the function definition and module definition are distinguishable from each other.

16. The method of claim 13, wherein each task corresponding to a source-code module definition:

causes a data value to be consumed, when it becomes available, from a task-input-stream first-in-first-out queue when the task thread of control encounters an instruction for obtaining a data value from the task input stream,

causes a data value to be placed into a task output stream when the task thread of control encounters an instruction for placing a data value into the output stream, and

causes the data value to be placed in the first-in-first-out queue corresponding to the destination of the corresponding source-code stream.

17. The method of claim 13, wherein each task corresponding to a stream expression:

causes a data value to be consumed, when it becomes available, from a task-input-stream first-in-first-out queue,

causes a data value to be placed into the task output stream each time the stream expression is evaluated, and

causing the data value to be placed in the first-in-first-out queue corresponding to the destination of the corresponding source-code stream.

18. The method of claim 13, wherein the stream-based computer source code specifies an interconnection of module definitions and stream expressions, the module definitions being instances of modules defined in the computer source code or in an included library, the stream expressions being identical to ordinary computer-program expressions except having variables replaced by streams, and the interconnection consisting of streams connecting one or more of:

an input stream of the module definition to an input stream of a module instance or stream expression, an output stream of a module instance or stream expression to an input stream of a module instance or stream expression, or an output stream of a module instance or stream expression to an output stream of the module definition.

19. The method of claim 13, wherein the stream-based computer source code includes a stream that is elevated to first-class status permitting the stream to be bound to be an identifier, an input parameter of a function, an output of a function, a parameter within an expression or an output of an expression.

20. A programmable computing device comprising:

a plurality of processing cores;

a memory device storing the stream-based computer source code, wherein the source code includes one or more module definitions for creating tasks running on the plurality of processing cores, each module definition having a list of input streams, a list of output streams, and a body, the body including code for executing a task on at least one of the plurality of processing cores;

a converter coupled to the memory device, the converter creating and assigning a collection of tasks for execution on one or more of the plurality of processing cores from the stream-based computer source code, wherein each task is an executable version of a module definition with a stream expression in the source code, the stream expression containing module input streams and output streams and the stream expression further defining how output-stream data values are computed from input-stream data values, each task further having input streams and output streams corresponding to the input streams and output streams of the source-code module definition, wherein at least one of the input streams has an output stream of another task of the collection of tasks as a stream source and at least one of the output streams has an input stream of another task of the collection of tasks as a stream destination, wherein at least one task consumes an array of multiple separate streams by conveying data elements from each respective stream in the array by concurrently to input streams of the at least one task; and

wherein the converter selects one of the plurality of processing cores for each of the collection of tasks, and the plurality of cores executes the collection of tasks in parallel to perform a runtime operation.