Method, apparatus, and computer-readable medium for parallelization of a computer program on a plurality of computing cores

1. An apparatus for parallelization of a computer program on a plurality of computing cores, the apparatus comprising:

one or more processors; and

one or more memories operatively coupled to at least one of the one or more processors and having instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

receive the computer program comprising a plurality of commands;

decompose the plurality of commands into a plurality of node networks, wherein each node network corresponds to a command in the plurality of commands and includes one or more nodes corresponding to execution dependencies of the command;

map the plurality of node networks to a plurality of systolic arrays, wherein each systolic array comprises a plurality of cells and wherein each non-data node in each node network is mapped to a cell in the plurality of cells; and

map each cell in each systolic array to a computing core in the plurality of computing cores, wherein at least some of the plurality of computing cores are on a single chip and are coupled to one another by a network connector on the chip.

2. The apparatus as recited in claim 1 , wherein the plurality of computing cores is coupled, by the network connector, to another plurality of computing cores on another chip.

3. The apparatus of claim 1 , wherein at least some of the computing cores are on separate devices which are coupled to one another over a network.

4. The apparatus of claim 3 , wherein the network is a cloud network.

5. The apparatus of claim 3 , wherein the separate devices are all part of a server farm.

6. The apparatus of claim 1 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to decompose the plurality of commands into a plurality of node networks further cause at least one of the one or more processors to, for each command:

parse the command using a lexical analyzer to identify one or more components of the command;

store the command as header node in a node network corresponding to the command; and

store the one or more components as nodes under the header node.

7. The apparatus of claim 6 , wherein the lexical analyzer is implemented in hardware by one or more systolic arrays.

8. The apparatus of claim 6 , wherein the lexical analyzer is generated based at least in part on a language definition file corresponding to a programming language of the computer program.

9. The apparatus of claim 6 , wherein the one or more components comprise one or more of a sub-command and a data value.

10. The apparatus of claim 1 , wherein the instructions, when executed by at least one of the one or more processors, further cause at least one of the one or more processors to decompose the plurality of commands into a plurality of node networks further cause at least one of the one or more processors to, for each command:

identify one or more sub-commands in the one or more components using the lexical analyzer;

parse the one or more sub-commands using the lexical analyzer to identify one or more sub-components of the one or more sub-commands; and

store the one or more sub-components as nodes under one or more nodes corresponding to the one or more sub-commands.

11. The apparatus of claim 1 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to map the plurality of node networks to a plurality of systolic arrays further cause at least one of the one or more processors to, for each node network:

map a plurality of non-data nodes in the node network to a plurality of cells in a systolic array;

connect the plurality of cells in the systolic array based at least in part on connections between the nodes in the node network; and

connect one or more cells in the plurality of cells to one or more other systolic arrays.

12. The apparatus of claim 11 , wherein at least one cell in the plurality of cells corresponds to a command or sub-command and wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to connect the plurality of cells in the systolic array further cause at least one of the one or more processors to:

connect the at least one cell corresponding to the command or sub-command to one or more other cells in the plurality of cells based at least in part on a determination that output of the one or more other cells is input to the command or sub-command.

13. The apparatus of claim 12 , wherein the determination that the output of one or more other nodes corresponding to the one or more other cells is input to the command or subcommand is made based on a language definition file corresponding to a programming language of the computer program.

14. The apparatus of claim 11 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to map the plurality of non-data nodes in the node network to a plurality of cells in a systolic array further cause at least one of the one or more processors to add one or more of an input port and an output port to at least one cell in the plurality of cells.

15. The apparatus of claim 14 , wherein the one or more of an input port and an output port is added based at least in part on a language definition file corresponding to a programming language of the computer program.

16. The apparatus of claim 15 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to connect one or more cells in the plurality of cells to one or more other systolic arrays further cause at least one of the one or more processors to:

identify each cell in the plurality of cells in the systolic array which corresponds to a subcommand; and

connect each identified cell to another other systolic array corresponding to the subcommand for respective identified cell.

17. The apparatus of claim 16 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to connect one or more cells in the plurality of cells to one or more other systolic arrays further cause at least one of the one or more processors to recursively connect all cells corresponding to sub-commands in the one or more other systolic arrays to additional systolic arrays corresponding to the sub-commands until no unconnected cells corresponding to sub-commands remain.

18. The apparatus of claim 1 , wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to map each cell in each systolic array to a computing core in a plurality of computing cores further cause at least one of the one or more processors to:

traverse the plurality of cells in each of the plurality of systolic arrays according to an execution order of the plurality of cells and the plurality of systolic arrays; and

map each traversed cell to a computing core in the plurality of computing cores, wherein each traversed cell is mapped in the order of traversal.

19. The apparatus of claim 18 , wherein the execution order comprises a critical path.

20. The apparatus of claim 1 , wherein each cell in each systolic array is mapped to the corresponding computing core based at least in part on an order of execution of the plurality of cells in the systolic array and an order of execution of the systolic array in the plurality of systolic arrays.

21. The apparatus of claim 1 , wherein the plurality of computing cores comprise one or more field-programmable gate arrays (FPGAs) and wherein the instructions that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to map each cell in each systolic array to a computing core in the plurality of computing cores further cause at least one of the one or more processors to configure an FPGA in the one or more of FPGAs to correspond to the logic of the cell.

22. A method performed by at least one computing device for parallelization of a computer program on a plurality of computing cores, the apparatus comprising:

receiving the computer program comprising a plurality of commands;

decomposing the plurality of commands into a plurality of node networks, wherein each node network corresponds to a command in the plurality of commands and includes one or more nodes corresponding to execution dependencies of the command;

mapping the plurality of node networks to a plurality of systolic arrays, wherein each systolic array comprises a plurality of cells and wherein nodes in each node network are mapped to a cell in the plurality of cells; and

mapping each cell in each systolic array to a computing core in the plurality of computing cores, wherein at least some of the plurality of computing cores are on a single chip and are coupled to one another by a network connector on the chip.

23. The method recited in claim 22 , wherein the plurality of computing cores is coupled, by the network connector, to another plurality of computing cores on another chip.

24. The method of claim 22 , wherein at least some of the computing cores for a systolic array are on separate devices which are coupled to one another over a network.

25. The method of claim 24 , wherein the network is a cloud network.

26. The method of claim 24 , wherein the separate devices are all part of a server farm.

27. The method of claim 22 , wherein the decomposing step comprises, for each command:

parsing the command using a lexical analyzer to identify one or more components of the command;

storing the command as header node in a node network corresponding to the command; and

storing the one or more components as nodes under the header node.

28. The method of claim 27 , wherein the lexical analyzer is implemented in hardware by one or more systolic arrays.

29. The method of claim 27 , wherein the lexical analyzer is generated based at least in part on a language definition file corresponding to a programming language of the computer program.

30. The method of claim 27 , wherein the one or more components comprise one or more of a sub-command and a data value.

31. The method of claim 22 , wherein the decomposing step comprises, for each command:

identifying one or more sub-commands in the one or more components using the lexical analyzer;

parsing the one or more sub-commands using the lexical analyzer to identify one or more sub-components of the one or more sub-commands; and

storing the one or more sub-components as nodes under one or more nodes corresponding to the one or more sub-commands.

32. The method of claim 22 , wherein the mapping step comprises, for each node network:

mapping a plurality of non-data nodes in the node network to a plurality of cells in a systolic array;

connecting the plurality of cells in the systolic array based at least in part on connections between the nodes in the node network; and

connecting one or more cells in the plurality of cells to one or more other systolic arrays.

33. The method of claim 32 , wherein at least one cell in the plurality of cells corresponds to a command or sub-command and wherein the step of connecting the plurality of cells in the systolic array further comprises:

connecting the at least one cell corresponding to the command or sub-command to one or more other cells in the plurality of cells based at least in part on a determination that output of the one or more other cells is input to the command or sub-command.

34. The method of claim 33 , wherein the determination that the output of one or more other nodes corresponding to the one or more other cells is input to the command or subcommand is made based on a language definition file corresponding to a programming language of the computer program.

35. The method of claim 33 , wherein the step of mapping the plurality of non-data nodes in the node network to a plurality of cells in a systolic array further comprises adding one or more of an input port and an output port to at least one cell in the plurality of cells.

36. The method of claim 35 , wherein the one or more of an input port and an output port is added based at least in part on a language definition file corresponding to a programming language of the computer program.

37. The method of claim 36 , wherein the step of connecting one or more cells in the plurality of cells to one or more other systolic arrays further comprises:

identifying each cell in the plurality of cells in the systolic array which corresponds to a subcommand; and

connecting each identified cell to another other systolic array corresponding to the subcommand for respective identified cell.

38. The method of claim 37 , wherein the step of connecting one or more cells in the plurality of cells to one or more other systolic arrays further comprises recursively connecting all cells corresponding to sub-commands in the one or more other systolic arrays to additional systolic arrays corresponding to the sub-commands until no unconnected cells corresponding to sub-commands remain.

39. The method of claim 22 , wherein the step of mapping each cell in each systolic array to a computing core in a plurality of computing further comprises:

traversing the plurality of cells in each of the plurality of systolic arrays according to an execution order of the plurality of cells and the plurality of systolic arrays; and

mapping each traversed cell to a computing core in the plurality of computing cores, wherein

each traversed cell is mapped in the order of traversal.

40. The method of claim 39 , wherein the execution order comprises a critical path.

41. The method of claim 22 , wherein each cell in each systolic array is mapped to the corresponding computing core based at least in part on an order of execution of the plurality of cells in the systolic array and an order of execution of the systolic array in the plurality of systolic arrays.

42. The method of claim 22 , wherein the plurality of computing cores comprise one or more field-programmable gate arrays (FPGAs) and wherein the step of mapping each cell in each systolic array to a computing core in the plurality of computing cores further cause at least one of the one or more processors to configure an FPGA in the one or more of FPGAs to correspond to logic of the cell.