Partitioning dataflow operations for a reconfigurable computing system through recursive candidate generation
A method for partitioning executable operations for a reconfigurable computing system includes receiving a set of expressions comprising a plurality of operations and dependencies for those operations, partitioning the plurality of operations into selected executable partitions wherein each selected executable partition conforms to resource constraints for a reconfigurable unit of the reconfigurable computing system. Partitioning the plurality of operations into selected executable partitions may include seeding a candidate partition with an operation, recursively generating an additional candidate partition for each operation adjacent to the candidate partition whose dependent operations are already within the candidate partition or a previously selected partition, and selecting a best candidate partition based on resource cost. A corresponding system and computer-readable medium are also disclosed herein. The system includes a partitioning module that that partitions the plurality of operations into selected executable partitions according to the method describe above.
1. A system for partitioning executable operations for a reconfigurable computing system, the system comprising:
a parsing module configured to receive a set of expressions for a reconfigurable computing system comprising a plurality of reconfigurable units and parse the set of expressions into a plurality of operations and dependencies for those operations;
a partitioning module configured to partition the plurality of operations into selected executable partitions wherein each selected executable partition conforms to resource constraints for a reconfigurable unit of the plurality of reconfigurable units;
wherein partitioning the plurality of operations into selected executable partitions comprises:
seeding a candidate partition with an operation,
recursively generating an additional candidate partition for each operation adjacent to the candidate partition whose dependent operations are already within the candidate partition or a previously selected partition, and
selecting a best candidate partition based on resource cost.
2. The system of claim 1 , wherein partitioning module is configured to continue partitioning until each of the plurality of operations is assigned to a selected executable partition.
3. The system of claim 1 , wherein partitioning module is configured to generate a tree of possible partitions.
4. The system of claim 1 , wherein the partitioning module is configured to determine if the candidate partition is redundant.
5. The system of claim 1 , wherein the partitioning module is configured to determine if the candidate partition is unlikely to produce a solution.
6. The system of claim 1 , wherein the partitioning module is configured to determine if the candidate partition has a lower resource cost than previous candidate partitions.
7. The system of claim 1 , wherein the partitioning module is configured to determine if the best candidate partition fits within a configurable unit.
8. The system of claim 1 , wherein the plurality of reconfigurable units comprise a plurality of compute units, a plurality of memory units and a plurality of address generation units.
9. The system of claim 1 , further comprising an assignment module configured to allocate one or more corresponding reconfigurable units for each selected executable partition.
10. The system of claim 1 , further comprising a configuration module for configuring a set of reconfigurable units of the plurality of reconfigurable units using the selected executable partitions.
11. The system of claim 3 , wherein generating the tree of possible partitions comprises adding a node to the tree of possible partitions for each operation adjacent to a candidate partition.
12. A method for partitioning executable operations for a reconfigurable computing system, the method comprising:
receiving expressions for a reconfigurable computing system comprising a plurality of reconfigurable units, wherein the expressions comprise a plurality of operations and dependencies for those operations;
partitioning the plurality of operations into selected executable partitions wherein each selected executable partition conforms to resource constraints for a reconfigurable unit of the plurality of reconfigurable units; and
wherein partitioning the plurality of operations into selected executable partitions comprises:
seeding a candidate partition with an operation,
recursively generating an additional candidate partition for each operation adjacent to the candidate partition whose dependent operations are already within the candidate partition or a previously selected partition, and
selecting a best candidate partition based on resource cost.
13. The method of claim 12 , wherein partitioning is continued until each of the plurality of operations is assigned to a selected executable partition.
14. The method of claim 12 , wherein partitioning the plurality of operations into selected executable partitions comprises generating a tree of possible partitions.
15. The method of claim 12 , further comprising determining if the candidate partition is redundant.
16. The method of claim 12 , further comprising determining if the candidate partition is unlikely to produce a solution.
17. The method of claim 12 , further comprising determining if the candidate partition has a lower resource cost than previous candidate partitions.
18. The method of claim 12 , further comprising determining if the best candidate partition fits within a configurable unit.
19. The method of claim 12 , further comprising adding the candidate partition to a set of visited partitions.
20. The method of claim 12 , further comprising allocating one or more corresponding reconfigurable units of the plurality of reconfigurable units for each of the selected executable partitions.
21. The method of claim 14 , wherein generating the tree of possible partitions comprises adding a node to the tree of possible partitions for each operation adjacent to a candidate partition.
22. The method of claim 15 , further comprising terminating recursion on the candidate partition in response to determining the candidate partition is redundant.
23. The method of claim 16 , further comprising terminating recursion on the candidate partition in response to determining the candidate partition is unlikely to produce a solution.
24. The method of claim 17 , further comprising saving the candidate partition as the best candidate partition for a corresponding reconfigurable unit responsive to determining that the candidate partition has a lower resource cost than previous candidate partitions.
25. The method of claim 20 , further comprising configuring each of the one or more corresponding reconfigurable units using a corresponding executable partition of the selected executable partitions to produce a plurality of configured units.
26. The method of claim 25 , further comprising processing data using the plurality of configured units.
27. The method of claim 25 , wherein configuring each corresponding reconfigurable unit comprises providing configuration instructions.
28. The method of claim 27 , wherein the plurality of reconfigurable units comprise a plurality of compute units.
29. The method of claim 27 , wherein the plurality of reconfigurable units comprise a plurality of memory units.
30. The method of claim 27 , wherein the plurality of reconfigurable units comprise a plurality of address generation units.
31. The method of claim 27 , wherein the configuration instructions are generated by compiling a user program.
32. The method of claim 27 , wherein the configuration instructions are generated by a user.
33. The method of claim 27 , wherein the configuration instructions conform to a domain-specific language for configuring reconfigurable units.
34. The method of claim 28 , wherein the configuration instructions comprise compute-related configuration instructions.
35. The method of claim 29 , wherein the configuration instructions comprise memory-related configuration instructions.
36. The method of claim 30 , wherein the configuration instructions comprise configuration instructions for address generation.