M/A for compiling parallel program having barrier synchronization for programmable hardware

1. A method of compiling a first program code, the method comprising:

determining if the first program code is to program a programmable logic device to execute a second program code, wherein the first program code is a parallel program having a barrier function call for a group of threads; and

transforming the first program code by replacing the barrier function call with additional hardware control logic specified to be programmed into the programmable logic device to form a transformed program in response to determining that the first program code is to program the programmable logic device, wherein the transformed program code remains a parallel program and maintains synchronization among the group of threads.

2. The method of claim 1 further comprising determining whether the programmable logic device supports one of a single-threaded code execution and a concurrent code execution prior to transforming the first program code.

3. The method of claim 2 , wherein the additional hardware control logic also specifies data structures and instructions to be added and modification to be made to a control flow of the single threaded code execution in response to determining that the programmable logic device supports the single-threaded code execution.

4. The method of claim 2 , wherein the additional hardware control logic also specifies data structures and instructions to be added and modification to be made to a control flow of the single threaded code execution in response to determining that the programmable logic device supports the single-threaded code execution, wherein transforming the first program code further comprises:

adding data structures;

adding kernel function prologue;

adding a barrier prologue;

removing the barrier function call;

adding a return prologue;

adding a yield basic block;

adding an advance basic block; and

adding resume code to restart thread execution.

5. The method of claim 2 , wherein the additional hardware control logic also specifies modification to be made to programming of the programmable logic device in response to determining that the programmable logic device supports the concurrent code execution.

6. The method of claim 2 , wherein the additional hardware control logic also specifies modification to be made to programming of the programmable logic device by specifying data structures to be instantiated, updates to the data in response to signals and data from other modules, and what update signals and values for use by other parts of the transformed program code are to be generated.

7. The method of claim 6 , wherein transforming the first program code by replacing the barrier function call with the additional hardware control logic further comprises:

adding the data structures;

adding kernel function prologue;

adding a barrier prologue;

adding a return prologue;

removing the barrier function call;

inserting thread resumption logic; and

inserting barrier role-flipping logic.

8. The method of claim 1 , wherein transforming the first program code by replacing the barrier function call with the additional hardware control logic further comprises:

adding logic to save thread contexts of threads being executed that have reached the barrier function call into a first-in-first-out module to effectively suspends execution of the threads;

adding logic to save identity of the barrier function call;

adding logic to increment a first count that indicates a number of threads with their thread contexts saved and a second count that indicates a number of threads reaching the barrier function call;

adding logic to determine when the second count equals a third count representing a number of live threads; and

adding logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution when the second count equals the third count.

9. The method of claim 1 , wherein the programmable logic device is a field programmable gate array.

10. The method of claim 1 , wherein transforming the first program code by replacing the barrier function call with the additional hardware control logic further comprises:

adding logic to save thread contexts of threads being executed that have reached the barrier function call into a first-in-first-out module to effectively suspends execution of the threads; and

adding logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution.

11. The method of claim 1 , wherein replacing the barrier function call with the additional hardware control logic is performed by:

adding a counter and a first-in-first-out (FIFO) module to force wait and suspension during thread execution if the programmable logic device is determined to support a single-threaded code execution; and

adding a counter and a buffer to force stop, wait, and switch between threads during thread execution if the programmable logic device is determined to support concurrent code execution.

12. A compiler system, comprising:

a processor having:

compiler modules that compile a parallel first program code with a barrier function call for a group of threads, wherein the first program code is to program a programmable logic device to execute a second program code; and

barrier synchronization logic generator within the compiler modules to replace the barrier function call with additional hardware control logic specified to be programmed into the programmable logic device to form a transformed program when the compiler modules determine that the first program code is to programs the programmable logic device to execute the second program code, wherein the transformed program code remains a parallel program and maintains synchronization among the group of threads.

13. The compiler system of claim 12 , wherein the barrier synchronization logic generator receives system description information of the programmable logic device that describes whether the programmable logic device supports one of a single-threaded code execution and a concurrent code execution prior to inserting description of the additional hardware control logic specified to be programmed into the programmable logic device into the first program code.

14. The compiler system of claim 13 , wherein if the programmable logic device supports the single-threaded code execution, the barrier synchronization logic generator inserts the additional hardware control logic by:

adding data structures;

adding kernel function prologue;

adding a barrier prologue;

removing the barrier function call;

adding a return prologue;

adding a yield basic block;

adding an advance basic block; and

adding resume code to restart thread execution.

15. The compiler system of claim 13 , wherein if the programmable logic device supports the concurrent code execution, the barrier synchronization logic generator inserts the additional hardware control logic by:

adding data structures;

adding kernel function prologue;

adding a barrier prologue;

adding a return prologue;

removing the barrier function call;

inserting thread resumption logic; and

inserting barrier role-flipping logic.

16. The compiler system of claim 12 , wherein the additional hardware control logic further comprises:

first-in-first-out module;

logic to save thread contexts of threads being executed that have reached the barrier function call into the first-in-first-out module to effectively suspends execution of the threads;

logic to save identity of the barrier function call;

logic to increment a first count that indicates a number of threads with their thread contexts saved and a second count that indicates a number of threads reaching the barrier function call;

logic to determine when the second count equals a third count representing a number of live threads;

logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution when the second count equals the third count.

17. The compiler system of claim 12 , wherein the programmable logic device is a field programmable gate array.

18. The compiler system of claim 12 , wherein the additional hardware control logic further comprises:

first-in-first-out module;

logic to save thread contexts of threads being executed that have reached the barrier function call into the first-in-first-out module to effectively suspends execution of the threads; and

logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution.

19. The compiler system of claim 12 , wherein the additional hardware control logic further comprises:

a counter and a first-in-first-out (FIFO) module to force wait and suspension during thread execution if the programmable logic device is determined to support a single-threaded code execution;

a counter and a buffer to force stop, wait, and switch between threads during thread execution if the programmable logic device is determined to support concurrent code execution.

20. A non-transitory computer readable medium including a sequence of instructions stored thereon for causing a computer to execute a method of compiling a first program code comprising:

determining if the first program code is to program a programmable logic device to execute a second program code, wherein the first program code is a parallel program having a barrier function call for a group of threads;

transforming the first program code by replacing the barrier function call with additional hardware control logic specified to be programmed into the programmable logic device to form a transformed program in response to determining that the first program code is to programs the programmable logic device, wherein the transformed program code remains a parallel program and maintains synchronization among the group of threads.

21. The non-transitory computer readable medium of claim 20 , further comprising instructions to determine whether the programmable logic device supports one of a single-threaded code execution and a concurrent code execution prior to transforming the first program code.

22. The non-transitory computer readable medium of claim 21 , wherein if it is determined that the programmable logic device supports the single-threaded code execution, then the transforming the first program code further comprises:

adding data structures;

adding kernel function prologue;

adding a barrier prologue;

removing the barrier function call;

adding a return prologue;

adding a yield basic block;

adding an advance basic block; and

adding resume code to restart thread execution.

23. The non-transitory computer readable medium of claim 21 , wherein if it is determined that the programmable logic device supports the concurrent code execution, then the transforming the first program code further comprises:

adding the data structures;

adding kernel function prologue;

adding a barrier prologue;

adding a return prologue;

removing the barrier function call;

inserting thread resumption logic; and

inserting barrier role-flipping logic.

24. The non-transitory computer readable medium of claim 20 , wherein transforming the first program code by replacing the barrier function call with additional hardware control logic further comprises:

adding a first-in-first-out module;

adding logic to save thread contexts of threads being executed that have reached the barrier call into the first-in-first-out module to effectively suspends execution of the threads;

adding logic to save identity of the barrier function call;

adding logic to increment a first count that indicates a number of threads with their thread contexts saved and a second count that indicates a number of threads reaching the barrier function call;

adding logic to determine when the second count equals a third count representing a number of live threads; and

adding logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution when the second count equals the third count.

25. The non-transitory computer readable medium of claim 20 , wherein the programmable logic device is a field programmable gate array.

26. The non-transitory computer readable medium of claim 20 ,

wherein transforming the first program code by replacing the barrier function call with the additional hardware control logic further comprises:

adding logic to save thread contexts of threads being executed that have reached the barrier function call into a first-in-first-out module to effectively suspends execution of the threads; and

adding logic to fetch all the thread contexts stored in the first-in-first-out module in a first-in-first-out order and resume their execution.

27. The non-transitory computer readable medium of claim 20 , wherein replacing the barrier function call with the additional hardware control logic is performed by:

adding a counter and a first-in-first-out (FIFO) module to force wait and suspension during thread execution if the programmable logic device is determined to support a single-threaded code execution; and

adding a counter and buffer to force stop, wait, and switch between threads during thread execution if the programmable logic device is determined to support concurrent code execution.