Granted Patent B2

US 6,964,029 · App. 10/285,298 · Granted Nov 8, 2005

Abstract

Claims (33)

1. A method of partitioning a control-dataflow graph representation comprising:

dividing the control-dataflow graph into two or more partition blocks and edges, the partition blocks each comprising a sub-graph of the control-dataflow graph and the edges representing connections between code in the partition blocks;

after the dividing, obtaining an estimated performance of at least one of the partition blocks as reconfigurable logic and as instruction processor code;

comparing the estimated performance of at least one of the partition blocks as reconfigurable logic versus instruction processor code; and

assigning said at least one of the partition blocks to reconfigurable hardware or an instruction processor based on said comparing step.

2. The method of claim 1 , comprising assigning at least one of the partition blocks to the reconfigurable hardware based on partitioning syntax input from a programmer.

3. The method of claim 1 , comprising enumerating candidate partition blocks from sub-graphs of the control-dataflow graph that have not been assigned to the reconfigurable hardware based on programmer instructions.

4. The method of claim 1 , comprising ordering the partition blocks based on profiling data from a microprocessor profiler.

5. The method of claim 1 , comprising ordering the partition blocks based on profiling data from dataflow graph emulation profiling.

6. The method of claim 1 , comprising ordering the partition blocks based on a degree of parallelism in each of the partition blocks.

7. The method of claim 1 , comprising measuring data flow between a candidate partition block and adjoining partition blocks.

8. The method of claim 1 , wherein said assigning said at least one of the partition blocks to reconfigurable hardware or an instruction processor comprises defining an execution location for said partition block in the reconfigurable hardware or instruction processor.

9. The method of claim 1 , comprising forming an output control-dataflow graph from said partition blocks assigned to the reconfigurable hardware.

10. The method of claim 9 , wherein the output control-dataflow graph comprises at least one edge, wherein said edge represents a physical connection between assigned resources.

11. A method of partitioning a control-dataflow graph representation comprising:

partitioning sub-graphs of a control-dataflow graph into partition blocks and edges representing connections between the sub-graphs; and

ordering said partition blocks based on order of potential as instruction processor code or reconfigurable hardware logic, wherein the ordering comprises:

comparing estimated performance for each partition block as the reconfigurable hardware logic versus the instruction processor code; and

assigning the partition blocks to reconfigurable hardware or an instruction processor based on said comparing step; and

ordering the assigned partition blocks by the estimated performance.

12. The method of claim 11 , comprising assigning at least one of said sub-graphs to a partition block based on partitioning syntax input from a programmer.

13. The method of claim 12 , wherein said partitioning syntax input from a programmer comprises a pragma.

14. The method of claim 12 , wherein said partitioning syntax input from a programmer comprises a directive.

15. The method of claim 12 , wherein said partitioning syntax input from a programmer comprises an assertion.

16. The method of claim 11 , comprising forming an output control-dataflow graph from said partition blocks assigned to the reconfigurable hardware.

17. The method of claim 16 , wherein the output control-dataflow graph comprises at least one edge, wherein said edge represents a physical connection between assigned resources.

18. A computer program product comprising:

a computer useable medium having a computer readable program code embodied therein for causing a partitioning of a control-dataflow graph, the computer readable program code comprising:

computer readable program code for causing a computer to divide the control-dataflow graph into two or more partition blocks and into edges representing connections between the partition blocks;

computer readable program code for causing the computer to compare after the dividing of the control-dataflow graph estimated performance of at least one of the partition blocks as reconfigurable logic versus instruction processor code; and

computer readable program code for causing the computer to assign said at least one of the partition blocks to reconfigurable hardware or an instruction processor based on said comparing step.

19. The computer program product of claim 18 , wherein said reconfigurable hardware comprises a field programmable gate array.

20. The computer program product of claim 18 , wherein said instruction processor comprises a microprocessor.

Assignments (8)