Execution of data-parallel programs on coarse-grained reconfigurable architecture hardware

1. A method of computing, comprising the steps of:

for a coarse-grain fabric of processing units having interconnects therebetween, receiving a representation of a series of computing operations to be processed in the fabric as a control data flow graph having code paths, the computing operations comprising instructions to be executed in the fabric;

configuring the fabric by enabling and disabling selected ones of the interconnects to match the processing units to the code paths of the control data flow graph; and

while a configuration of the fabric remains unchanged, executing the instructions of the computing operations in the fabric in a pipelined sequence of simultaneous threads.

2. The method according to claim 1 , wherein configuring the fabric further comprises configuring one or more of the processing units in accordance with the control data flow graph.

3. The method according to claim 1 , wherein the threads comprise instructions to be executed in individual processing units, and wherein processing the computing operations comprises dynamically scheduling the instructions of at least a portion of the threads.

4. The method according to claim 3 , further comprising grouping the threads into epochs; wherein dynamically scheduling the instructions comprises deferring execution in one of the processing units of a current instruction of one of the epochs until execution in the one processing unit of all preceding instructions belonging to other epochs has completed.

5. The method according to claim 3 , further comprising the steps of:

making a determination that in the control data flow graph one of the code paths is longer than another code path; and

delaying the computing operations in processing units that are matched with the other code path.

6. The method according to claim 3 , wherein the computing operations comprise loops that each of the threads iterate.

7. The method according to claim 6 , wherein at least first and second different threads among the multiple threads perform different numbers of iterations of the loops.

8. The method according to claim 1 , further comprising:

partitioning the series of computing operations into a plurality of smaller series;

executing the instructions of the computing operations in one of the smaller series in the threads;

storing intermediate results of the computing operations; and

iterating the steps of configuring the fabric and executing the instructions of the computing operations, by at least some of the threads, with another of the smaller series.

9. The method according to claim 1 , wherein at least a portion of the processing units are interconnected by switches, further comprising configuring interconnections between the processing units by configuring the switches.

10. The method according to claim 9 , wherein the switches are crossbar switches.

11. The method according to claim 1 , wherein executing the instructions comprises executing a load instruction issued by a thread, and associating the load instruction with an identifier of the thread in order to subsequently associate a response to the load instruction with the thread.

12. The method according to claim 1 , wherein the control data flow graph comprises a split into first and second parallel code paths, and wherein configuring the fabric comprises configuring a processing unit to perform the split.

13. The method according to claim 1 , wherein the control data flow graph comprises first and second parallel code paths that join into a joint code path, and wherein configuring the fabric comprises configuring a processing unit to join the first and second parallel code paths, including enabling execution of the joint code path only after the completing execution of the first and second parallel code paths.

14. The method according to claim 1 , wherein executing the instructions comprises sending a poisoned token from a first processing unit to a second processing unit along the control data flow graph, the poisoned token instructing the second processing unit to disable a compute operation.

15. A computing apparatus, comprising:

a coarse-grain fabric of processing units; and

interconnects between the processing units, wherein the fabric is operative for:

receiving a representation of a series of computing operations to be processed in the fabric as a control data flow graph having code paths, the computing operations comprising instructions to be executed in the fabric;

configuring the fabric by enabling and disabling selected ones of the interconnects to match the processing units to the code paths of the control data flow graph; and

while a configuration of the fabric remains unchanged, executing the instructions of the computing operations in the fabric in a pipelined sequence of simultaneous threads.

16. The computing apparatus according to claim 15 , wherein the fabric is operative for configuring one or more of the processing units in accordance with the control data flow graph.

17. The computing apparatus according to claim 15 , wherein the threads comprise instructions to be executed in individual processing units, and wherein the fabric is operative for dynamically scheduling the instructions of at least a portion of the threads.

18. The computing apparatus according to claim 17 , wherein the fabric is further operative for grouping the threads into epochs; and for dynamically scheduling the instructions by deferring execution in one of the processing units of a current instruction of one of the epochs until execution in the one processing unit of all preceding instructions belonging to other epochs has completed.

19. The computing apparatus according to claim 17 , wherein the fabric is further operative for:

making a determination that in the control data flow graph one of the code paths is longer than another code path; and

delaying the computing operations in processing units that are matched with the other code path.

20. The computing apparatus according to claim 17 , wherein the computing operations comprise loops that each of the threads iterate.

21. The computing apparatus according to claim 20 , wherein at least first and second different threads among the multiple threads perform different numbers of iterations of the loops.

22. The computing apparatus according to claim 15 , wherein the fabric is further operative for:

partitioning the series of computing operations into a plurality of smaller series;

executing the instructions of the computing operations in one of the smaller series in the threads;

storing intermediate results of the computing operations; and

iterating the steps of configuring the fabric and executing the instructions of the computing operations, by at least some of the threads, with another of the smaller series.

23. The computing apparatus according to claim 15 , wherein at least a portion of the processing units are interconnected by switches, and wherein the fabric is operative for configuring the interconnections between the processing units by configuring the switches.

24. The computing apparatus according to claim 23 , wherein the switches are crossbar switches.

25. The computing apparatus according to claim 15 , wherein the fabric is operative for executing a load instruction issued by a thread, and associating the load instruction with an identifier of the thread in order to subsequently associate a response to the load instruction with the thread.

26. The computing apparatus according to claim 15 , wherein the control data flow graph comprises a split into first and second parallel code paths, and wherein the fabric is operative for configuring a processing unit to perform the split.

27. The computing apparatus according to claim 15 , wherein the control data flow graph comprises first and second parallel code paths that join into a joint code path, and wherein the fabric is operative for configuring a processing unit to join the first and second parallel code paths, including enabling execution of the joint code path only after the completing execution of the first and second parallel code paths.

28. The computing apparatus according to claim 15 , wherein the fabric is operative for sending a poisoned token from a first processing unit to a second processing unit along the control data flow graph, the poisoned token instructing the second processing unit to disable a compute operation.