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

• US 8,843,928 B2
• Filed: 01/21/2011
• Issued: 09/23/2014
• Est. Priority Date: 01/21/2010
• Status: Active Grant

• Current Assignee: Cornami, Inc.
• Original Assignee: QST Holdings LLC
• Inventors: Master, Paul, Furtek, Frederick
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US13/011,763
• Publication Number:
  US 20110179252A1
• Time in Patent Office: 1,341 Days
• Field of Search: None
• US Class Current: 718/100
• 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 programmable computing device comprising:

a plurality of processing cores coupled to each other;

a memory storing stream-domain code, the stream-domain code including a plurality of modules and a stream construct defining a stream source module and a stream destination module, wherein each module has one or more input streams or one or more output streams and each module is convertible into a task either consuming data values from an input stream or producing data values in an output stream and wherein each module has an identifier sufficient to allow access to the module;

a compiler selecting the stream source module and the stream destination module from the plurality of modules, based on the stream construct and converting the stream source module into a stream source task, the stream destination module into a stream destination task and the stream construct into a data stream originating at the stream source task and terminating at the stream destination task; and

a runtime system to select one of the plurality of processing cores and schedule the stream source task for execution on the selected one of the plurality of processing cores, detect when data values placed into the data stream by the stream source task are available to the stream destination task, select another of the plurality of processing cores and schedule the stream destination task with the data values for parallel execution on the selected another one of the plurality of processing cores.

2. The computing device of claim 1, wherein the stream-domain code includes a stream expression including an input stream and an output stream, the stream expression to cause a data value to be consumed from the input stream and a data value to be produced in the output stream of the stream expression.

3. The computing device of claim 2, wherein the stream expression includes a call to a function, the stream expression causing the function to be called with the data value retrieved from the input stream and the result returned by the function call is placed into the output stream associated with the function call.

4. The computing device of claim 3, wherein the function call is one of a plurality of function calls.

5. The computing device of claim 2, wherein the stream-domain code includes an assignment statement causing the output stream of the stream expression to become a source of a second previously declared stream.

6. The computing device of claim 2, wherein the stream expression is one of a plurality of stream expressions and wherein each of the plurality of stream expressions is executed on a corresponding separate processing core.

7. The computing device of claim 1, wherein each module is executed on a separate one of the plurality of processing cores.

8. The computing device of claim 1, wherein at least one of the modules includes thread-domain code executed sequentially.

9. The computing device of claim 8, wherein the thread-domain code retrieves a data value from a first stream and places a computed data value into a second stream.

10. The computing device of claim 1, wherein the output stream is one of a plurality of output streams of the module.

11. The computing device of claim 1, wherein the input stream is one of a plurality of input streams of the module.

12. The computing device of claim 1, wherein the stream-domain code includes a module array having a plurality of modules, wherein each of the plurality of modules is one module in the module array.

13. The computing device of claim 12, wherein the stream-domain code includes an array of streams identified with one or more array indices, each stream in the array of streams conveying data values from a source module of an array of stream source modules to a destination module of an array of stream destination modules and each stream accessible via an array index or array indices.

14. The computing device of claim 1, wherein the memory stores a thread-domain code instance executed sequentially.

15. The computing device of claim 1, wherein the runtime system is implemented in one or more instructions stored on a non-transitory medium that may be executed by a processing core, hardware, or reconfigurable hardware.

16. The computing device of claim 1, wherein the runtime system is implemented on two or more of the plurality of processing cores.

17. The computing device of claim 1, wherein the runtime system has a first-in-first-out queue at the stream destination module.

18. The computing device of claim 17, wherein the runtime system prevents the overflow of the first-in-first-out queue.

19. The computing device of claim 17, further comprising:

assigning each processing core zero or more tasks to be performed, each task implementing either a stream expression or an instance of thread-domain code appearing in the computer program; and

managing the execution of each of the tasks assigned to each processing core via a task manager local to each core.

20. The computing device of claim 19, wherein each processing core assigned a task includes the task manager.

21. The computing device of claim 19, wherein the task manager manages execution of tasks on multiple processing cores.

22. The computing device of claim 19, 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.

23. The computing device of claim 19, wherein the task manager is implemented in one or more instructions stored on a non-transitory medium that may be executed by a processing core, hardware, or reconfigurable hardware.

24. The computing device of claim 17 wherein the first-in-first-out queue is initialized with an initial value specified in the stream-domain code.

25. The computing device of claim 1, wherein the stream-domain code includes a keyword indicating that an identifier denotes a stream.

26. The computing device of claim 1, wherein the stream-domain 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.

27. The computing device of claim 26, wherein the function and expression are executed on different processing cores.

28. The computing device of claim 1, wherein the stream construct conveys data values from a plurality of stream sources to a plurality of stream destinations, and wherein the data values placed into the stream construct by the plurality of stream sources are interleaved before reaching each stream destination.

29. The computing device of claim 1, wherein the stream-domain code references a quasi-constant stream, the quasi-constant stream conveying data values from a stream source to a stream destination storing a data value of a type associated with the quasi-constant stream, and wherein a task at the stream destination uses and reuses the data value until a new data value inserted at a stream source is conveyed to the stream destination.

30. The computing device of claim 1, wherein the stream-domain code includes a ping stream that conveys pings having no associated data values from a ping-stream source to a ping-stream destination.

61. The method of claim 1, wherein the stream-domain code includes a ping stream that conveys pings having no associated data values from a ping-stream source to a ping-stream destination.

31. A method of programming a computer system including a plurality of processing cores, the method comprising:

providing stream-domain code for execution on the plurality of processing cores, the stream-domain code including a plurality of modules and a stream construct having an associated stream source module and a stream destination module, wherein each module has one or more input streams or one or more output streams and each module is convertible into a task either consuming data values from an input stream or producing data values in an output stream and wherein each module has an identifier sufficient to allow access to the module;

selecting the stream source module and the stream destination module from the plurality of modules, based on the stream construct;

converting the stream source module into a stream source task and the stream destination module into a stream destination task;

converting the stream construct into a data stream originating at the stream source task and terminating at the stream destination task;

selecting one of the plurality of processing cores and scheduling the stream source task for execution on the selected one of the plurality of processing cores via a runtime system;

detecting when data values placed into the data stream by the stream source task are available to the stream destination task; and

selecting another one of the plurality of processing cores and scheduling the stream destination task with the data values for parallel execution on the selected another one of the plurality of processing cores via the runtime system.

32. The method of claim 31, wherein the stream-domain code includes a stream expression including an input stream and an output stream, the stream expression causing a data value to be consumed from the input stream and a data value to be produced in the output stream of the stream expression.

33. The method of claim 32, wherein the stream expression includes a call to a function, the stream expression causing the function to be called with the data value retrieved from the input stream and the result returned by the function call is placed into the output stream associated with the function call.

34. The method of claim 33, wherein the function call is one of a plurality of function calls.

35. The method of claim 34, wherein the plurality of functions calls include at least two function calls corresponding with the function.

36. The method of claim 32, wherein the stream-domain code includes an assignment statement causing the output stream of the stream expression to become a source of a second previously declared stream.

37. The method of claim 32, wherein the stream expression is one of a plurality of stream expressions and wherein each of the plurality of stream expressions is executed on a corresponding separate processing core.

38. The method of claim 31, wherein each module is executed on a separate one of the plurality of processing cores.

39. The method of claim 31, wherein at least one of the modules includes thread-domain code executed sequentially.

40. The method of claim 31, wherein the output stream is one of a plurality of output streams of the module.

41. The method of claim 31, wherein the input stream is one of a plurality of input streams of the module.

42. The method of claim 31, wherein the stream-domain code includes a module array having a plurality of modules, wherein each of the plurality of modules is one module in the module array.

43. The method of claim 42, wherein the stream-domain code includes an array of streams identified with one or more array indices, each stream in the array of streams conveying data values from a source module of an array of stream source modules to a destination module of an array of stream destination modules and each stream accessible via an array index or array indices.

44. The method of claim 31, further comprising providing a thread-domain code instance executed sequentially.

45. The method of claim 44, wherein the thread-domain code retrieves a data value from a first stream and places a computed data value into a second stream.

46. The method of claim 31, wherein the runtime system is implemented in one or more instructions stored on a non-transitory medium that may be executed by a processing core, hardware, or reconfigurable hardware.

47. The method of claim 31, wherein the runtime system is implemented on two or more of the plurality of processing cores.

48. The method of claim 31, wherein the runtime system has a first-in-first-out queue at the stream destination module.

49. The method of claim 48, wherein the runtime system prevents the overflow of the first-in-first-out queue.

50. The method of claim 48, further comprising:

assigning each processing core zero or more tasks to be performed, each task implementing either a stream expression or an instance of thread-domain code appearing in the computer program; and

managing the execution of the tasks assigned to each processing core via a task manager.

51. The method of claim 50, wherein each processing core assigned a task includes the task manager.

52. The method of claim 50, wherein the task manager manages execution of tasks on multiple processing cores.

53. The method of claim 50, 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.

54. The method of claim 50, wherein the task manager is implemented in one or more instructions stored on a non-transitory medium that may be executed by a processing core, hardware, or reconfigurable hardware.

55. The method of claim 48 wherein the first-in-first-out queue is initialized with an initial value specified in the stream-domain code.

56. The method of claim 31, wherein the stream-domain code includes a keyword indicating that an identifier denotes a stream.

57. The method of claim 31, wherein the stream-domain 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.

58. The method of claim 57, wherein the function and expression are executed on different processing cores.

59. The method of claim 31, wherein the stream construct conveys data values from a plurality of stream sources to a plurality of stream destinations, and wherein the data values placed into the stream construct by the plurality of stream sources are interleaved before reaching each stream destination.

60. The method of claim 31, wherein the stream-domain code references a quasi-constant stream, the quasi-constant stream conveying data values from a stream source to a stream destination storing a data value of a type associated with the quasi-constant stream, and wherein a task at the stream destination uses and reuses the same data value until a new data value inserted at a stream source is conveyed to the stream destination.

62. A method of programming a computer system having a plurality of processing cores, the method comprising:

receiving stream-domain code specifying a plurality of module instances and/or stream expressions and a stream, each module instance and each stream expression having one or more input streams and/or one or more output streams, wherein each module instance and stream expression is convertible into a task either consuming data values from an input stream or producing data values in an output stream and wherein each module instance and stream expression has an identifier sufficient to allow access to the module instance and the stream expression, and the stream having a stream source and a stream destination, the stream source being selected from among the module and stream-expression output streams and the stream destination being selected from the module and stream-expression input streams;

converting the stream source module or stream expression into a first task running on a core selected from the plurality of cores;

converting the stream destination module or stream expression into a second task;

converting the streams in the stream-domain code into data streams originating at the first task and terminating at the second task, wherein the data streams are organized in the same pattern as the streams in the stream-domain code and allowing the tasks to pass data amongst each other;

detecting when data values placed into the data stream by the first task are available to the second task; and

running the second task with the data value in parallel with the first task on a different core selected from the plurality of cores.

63. A programmable computing device comprising:

a plurality of processing cores coupled to each other;

a memory storing stream-domain code specifying a plurality of module instances and/or stream expressions and a stream, each module instance and each stream expression having one or more input streams and/or one or more output streams, wherein each module instance and stream expression is convertible into a task either consuming data values from an input stream or producing data values in an output stream and wherein each module instance and stream expression has an identifier sufficient to allow access to the module instance and the stream expression, and the stream having a stream source and a stream destination, the stream source being selected from among the module and stream-expression output streams and the stream destination being selected from the module and stream-expression input streams;

a compiler converting the stream source module or stream expression into a first task, converting the stream destination module or stream expression into a second task, and converting the streams in the stream-domain code into data streams originating at the first task and terminating at the second task; and

a runtime system to select a first processing core from the plurality of processing cores to execute the first task, detecting when data values placed into the data stream by the first task are available to the second task and select a second processing core from the plurality of processing cores to execute the second task with the data values in parallel with the first task, wherein the data streams are organized in the same pattern as the streams in the stream-domain code and allowing the tasks to pass data amongst each other.