Run-time node prefetch prediction in dataflow graphs

1. A method for run-time prediction of a next caller of a shared functional unit, wherein the shared functional unit is operable to be called by two or more callers out of a plurality of callers, the method comprising:

storing a caller history of the shared functional unit;

detecting a calling pattern of the plurality of callers of the shared functional unit, wherein said detecting comprises:

dividing the caller history into a first portion of the caller history and a second portion of the caller history, wherein the first portion and the second portion each hold an equal amount of the caller history; and

comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history;

predicting the next caller out of the plurality of callers of the shared functional unit; and

loading state information associated with the next caller out of the plurality of callers;

wherein the shared functional unit and the plurality of callers are operable to execute in parallel on a parallel execution unit.

2. The method of claim 1 , wherein the run-time prediction is performed for an application described by a dataflow graph.

3. The method of claim 1 , wherein the mn-time prediction is performed for an application programmed in a dataflow language.

4. The method of claim 1 ,

wherein said storing the caller history uses a history register, wherein the history register is operable to be divided into two equal portions.

5. The method of claim 4 ,

wherein said comparing operates to compare callers in the first portion part of the history register to the callers in the second portion of the history register.

6. The method of claim 4 ,

wherein, each of the plurality of callers has a unique identification wherein the unique identification is operable to be used in the caller history.

7. The method of claim 6 ,

wherein the history register is operable to store the unique identification of each of the two or more callers calling the shared functional unit by operating analogously to a shift register.

8. The method of claim 6 ,

wherein said comparing the callers comprises comparing the unique identifications of the callers in the first portion of the caller history to the unique identifications of the callers in the second portion of the caller history.

9. The method of claim 1 ,

wherein said comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history operates to select a periodic portion of the caller history.

10. The method of claim 9 , further comprising:

using a multiplexer to said predict the next caller of the shared functional unit after selecting the periodic portion of the caller history.

11. The method of claim 1 ,

wherein the parallel execution unit comprises one or more of

an FPGA;

a programmable hardware element:

a reconfigurable logic unit;

a nonconfigurable hardware element;

an ASIC;

a computer comprising a plurality of processors; or

any other computing device capable of executing multiple threads in parallel.

12. The method of claim 1 ,

wherein the state information comprises one or more of:

execution state;

values of any variable;

previous inputs;

previous outputs; or

any other information related to execution of a node in a dataflow diagram.

13. The method of claim 1 ,

wherein a dataflow program comprises a plurality of nodes, wherein the plurality of nodes comprises the shared functional unit, wherein the plurality of nodes further comprises the plurality of callers,

wherein the run-time prediction operates to optimize execution of the plurality of nodes in the dataflow program.

14. The method of claim 13 ,

wherein the shred functional unit and the plurality of callers are generated using the dataflow program.

15. A method for run-time call prediction for resolving resource contention between two or more callers of a shared node in a dataflow program, the method comprising:

storing a caller history of the shared node;

detecting a calling pattern by a plurality of callers of the shared node, wherein said detecting comprises:

dividing the caller history into a first portion of the caller history and a second portion of the caller history, wherein the first portion and the second portion each hold an equal amount of the caller history; and

comparing the callers in the first portion of the caller history to the caller in the second portion of the caller history;

predicting a next caller out of the plurality of callers of the shared node; and

loading state information associated with the next caller out of the plurality of callers;

wherein the shared node and the plurality of callers are operable to execute in parallel on a parallel execution unit.

16. The method of claim 15 ,

wherein the dataflow program comprises a plurality of nodes, wherein the plurality of nodes comprises the shared node, wherein the plurality of nodes further comprises the plurality of callers.

17. The method of claim 16 ,

wherein the run-time call prediction operates to optimize execution of the plurality of nodes in the dataflow program.

18. The method of claim 15 ,

wherein the dataflow program executes on the parallel execution unit wherein the parallel execution unit comprises one or more of

an FPGA;

a programmable hardware element;

a reconfigurable logic unit;

a nonconfigurable hardware element;

an ASIC;

a computer comprising a plurality of processors; or

any other computing device capable of executing multiple threads in parallel.

19. The method of claim 15 ,

wherein each of the plurality of callers has a unique identification, wherein the unique identification is operable to be used in the caller history.

20. The method of claim 19 ,

wherein the caller history is operable to store the unique identification of each of the two or more callers calling the shared node by operating analogously to a shift register.

21. The method of claim 19 ,

wherein said comparing the callers comprises comparing the unique identifications of the callers in the first portion of the caller history to the unique identifications of the callers in the second portion of the caller history.

22. The method of claim 15 ,

wherein said comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history operates to select a periodic portion of the caller history.

23. The method of claim 15 ,

wherein the stared node and the plurality of callers are generated by the dataflow program.

24. A memory medium comprising instructions to generate a program to perform run-time call prediction of a next caller of a shared functional unit, wherein the program is intended for deployment on a parallel execution unit, wherein the program is executable to:

store a caller history of the shared functional unit;

detect a calling pattern of a plurality of callers of the shared functional unit, wherein the shared functional unit is operable to be called by two or more callers out of the plurality of callers, wherein said detecting comprises:

dividing the caller history into a first portion of the caller history and a second portion of the caller history, wherein the first portion and the second portion are each operable to hold an equal amount of the caller history; and

comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history;

predict the next caller out of the plurality of callers of the shared functional unit; and

load state information associated with the next caller out of the plurality of callers;

wherein the shared functional unit and the plurality of callers are operable to execute in parallel on the parallel execution unit.

25. The memory medium of claim 24 ,

wherein a dataflow program comprises a plurality of nodes, wherein the plurality of nodes comprises the shared functional unit, wherein the plurality of nodes further comprises the plurality of callers,

wherein the run-time call prediction operates to optimize execution of the plurality of nodes in the dataflow program.

26. The memory medium of claim 24 ,

wherein the program executes on the parallel execution unit, wherein the parallel execution unit comprises one or more of:

an FPGA;

a programmable hardware element;

a reconfigurable logic unit;

a nonconfigurable hardware element;

an ASIC;

a computer comprising a plurality of processors; or

any other computing device capable of executing multiple threads in parallel.

27. The memory medium of claim 24 ,

wherein said storing th e caller history comprises storing the caller history in a history register;

wherein said comparing operates to compare callers in the first portion of the history register to the callers in the second portion of the history register;

wherein each of the plurality of callers has a unique identification.

28. The memory medium of claim 27 ,

wherein the history register is operable to store the unique identification of each of the two or more callers calling the shared functional unit by operating analogously to a shift register.

29. The memory medium of claim 27 ,

wherein said comparing the callers comprises comparing the unique identifications of the callers in the first portion of the caller history to the unique identifications of the callers in the second portion of the caller history.

30. The memory medium of claim 24 ,

wherein said comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history operates to select a periodic portion of the caller history.

31. The memory medium of claim 24 ,

wherein the program comprises one or more of:

program instructions;

digital logic; or

any type of hardware description used to configure the parallel execution unit.

32. The memory medium of claim 24 ,

wherein the shared functional unit and the plurality of callers are generated by the program.

33. The memory medium of claim 24 ,

wherein the program comprises a control and arbitration logic unit that is operable to said detect, said predict, and said load.

34. A system for run-time optimization of a dataflow program, the system comprising:

a parallel execution unit;

a plurality of callers;

a shared functional unit, wherein the shared functional unit is operable to be called by two or more callers out of the plurality of callers, wherein the shared functional unit and the plurality of callers are operable to execute in parallel on the parallel execution unit;

an optimization algorithm, wherein the optimization algorithm is operable to:

store a caller history of the shared functional unit;

detect a calling pattern of the plurality of callers of the shared functional unit, wherein said detecting comprises:

dividing the caller history into a first portion of the caller history and a second portion of the caller history, wherein the first portion and the second portion are each operable to hold an equal amount of the caller history; and

comparing the callers in the first portion of the caller history to the caller in the second portion of the caller history;

predict a next caller out of the plurality of callers of the shared functional unit; and

allocate state information associated with the next caller out of the plurality of callers.

35. The system of claim 34 ,

wherein the parallel execution unit comprises one or more of:

an FPGA;

a programmable hardware element;

a reconfigurable logic unit;

a nonconfigurable hardware element;

an ASIC;

a computer comprising a plurality of processors; or

any other computing device capable of executing multiple threads in parallel.

36. The system of claim 34 ,

wherein said storing the caller history comprises storing the caller history in a history register;

wherein said comparing operates to compare callers in the first portion of the history register to the callers in the second portion of the history register;

wherein each of the plurality of callers has a unique identification.

37. The system of claim 36 ,

wherein the history register is operable to store the unique identification of each of the two or more callers calling the shared functional unit by operating analogously to a shift register.

38. The system of claim 36 ,

wherein said comparing the callers comprises comparing the unique identifications of the callers in the first portion of the caller history to the unique identifications of the callers in the second portion of the caller history.

39. The system of claim 34 ,

wherein said comparing the callers in the first portion of the caller history to the callers in the second portion of the caller history operates to select a periodic portion of the caller history.

40. The system of claim 34 ,

wherein the shared functional unit and the plurality of callers are generated using the dataflow program.

41. The system of claim 34 ,

wherein the optimization algorithm is implemented on a control and arbitration logic unit that is operable to said detect, said predict, and said allocate.