Method for interleaving a program over a plurality of cells

• US 8,230,411 B1
• Filed: 06/13/2000
• Issued: 07/24/2012
• Est. Priority Date: 06/10/1999
• Status: Active Grant

• Current Assignee: Scientia Sol Mentis AG (PACT XPP Schweiz AG)
• Original Assignee: Maren Krass, Thomas Richter
• Inventors: Nückel, Armin, Vorbach, Martin
• Primary Examiner(s): DAO, THUY CHAN
• Application Number:
  US10/009,649
• Time in Patent Office: 4,424 Days
• Field of Search: 717/156, 717/149, 712/25, 712/225, 712/236, 709/250, 709/231, 711/149
• US Class Current: 717/156
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

For programming of modules which can be reprogrammed during operation and for partitioning of code sequences, a control and/or data flow graph may be extracted from a program and separated into a plurality of subgraphs, which may be distributed among the modules. The separation of the flow graph may be such that connections between different ones of the subgraphs are minimized. During execution of the program, after a first module completes execution of a first part of one of the subgraphs, the first module may be reconfigured for execution of a first part of a second subgraph, while a second module executes a second part of the first subgraph.

Claims

1. A method for programming a system having a hardware cellular structure of runtime reconfigurable cells, comprising:

extracting a control flow graph of a program to be executed by the cellular structure of runtime reconfigurable cells;

separating the control flow graph into a plurality of subgraphs, such that each of the plurality of subgraphs corresponds to a respective single configuration of each of a respective plurality of the runtime configurable cells, an entirety of each of the subgraphs thereby being executable by the cellular structure of runtime reconfigurable cells without reconfiguration of any of the runtime reconfigurable cells;

distributing the plurality of subgraphs among the runtime reconfigurable cells for execution of the subgraphs by the runtime reconfigurable cells;

determining state information, by at least some of the runtime reconfigurable cells, via execution of each of at least a subset of the subgraphs; and

using, by one or more of the at least some of the runtime reconfigurable cells and via execution of one of the at least the subset of the subgraphs, a portion of the state information as a trigger of conditional processing, wherein the portion of the state information was determined by execution of another of the at least the subset of the subgraphs that occurred prior to the execution of the one of the at least the subset of the subgraphs.

2. A method for programming a system having a cellular structure of runtime reconfigurable cells, comprising:

extracting, by a hardware circuitry arrangement, a data flow graph of a program to be executed by the cellular structure of runtime reconfigurable cells and that includes a loop;

partitioning, by the hardware circuitry arrangement, the data flow graph, thereby forming a plurality of subgraphs, such that the loop is split into several of the subgraphs due to a partitioning constraint that each of the plurality of subgraphs corresponds to a respective single configuration of each of a respective plurality of the runtime configurable cells, an entirety of each of the subgraphs thereby being executable by the cellular structure of runtime reconfigurable cells without reconfiguration of any of the runtime reconfigurable cells; and

distributing, by the hardware circuitry arrangement, the plurality of subgraphs among the runtime reconfigurable cells for execution of the subgraphs by the runtime reconfigurable cells.

3. A method for programming a system having a cellular structure of runtime reconfigurable cells, comprising:

extracting, by a hardware circuitry arrangement and from a program, to be executed by the cellular structure of runtime reconfigurable cells, at least one of a data flow graph and a control flow graph;

separating, by the hardware circuitry arrangement, the at least one of the graphs into a plurality of subgraphs, such that each of the plurality of subgraphs corresponds to a respective single configuration of each of a respective plurality of the runtime configurable cells, an entirety of each of the subgraphs thereby being executable by the cellular structure of runtime reconfigurable cells without reconfiguration of any of the runtime reconfigurable cells; and

distributing, by the hardware circuitry arrangement, the plurality of subgraphs among the runtime reconfigurable cells for execution of the subgraphs by the runtime reconfigurable cells;

wherein the separating includes providing communication arrangements adapted for storage of all data to be processed in a subsequent runtime reconfigurable cell according to connections between the plurality of subgraphs.

4. The method of claim 3, wherein the separating includes separating the at least one the graphs into the plurality of subgraphs so that data transmission between the plurality of subgraphs is minimized.

5. The method of claim 3, wherein the separating includes separating the at least one of the graphs into the plurality of subgraphs so that no loop-back is obtained between the plurality of subgraphs.

6. The method of claim 3, wherein the separating includes separating the at least one of the graphs into the plurality of subgraphs so that the subgraphs match resources of the hardware modules.

7. The method of claim 3, wherein memory elements are inserted between the plurality of subgraphs, the memory elements adapted to save data passed between subgraphs.

8. The method of claim 3, wherein each of the plurality of subgraphs includes nodes, the method further comprising:

transmitting status signals between nodes within one of the subgraphs so that a state of each individual one of the nodes of the one of the subgraphs is available to each of the other nodes of the one of the subgraphs.

9. The method of claim 3, wherein each of the plurality of subgraphs includes nodes, the method further comprising:

transmitting status signals from a first node of at least one of the plurality of subgraphs to a higher-level unit adapted to control configuration of the plurality of hardware modules so as to trigger reconfiguration.

10. The method of claim 3, wherein the extracting includes, for a conditional instruction, extracting a plurality of different subgraphs, different instruction paths of the conditional instruction being represented by different sets of one or more of the subgraphs, one of the different sets of one or more of the subgraphs being executed depending on an evaluation of the conditional instruction.

11. A method of executing a single program on a system having a hardware array of runtime reconfigurable cells, comprising:

separating the single program into several subgraphs, such that each of the subgraphs corresponds to a respective single configuration of each of a respective plurality of the runtime configurable cells, an entirety of each of the subgraphs thereby being executable by the array of runtime reconfigurable cells without reconfiguration of any of the runtime reconfigurable cells;

distributing the several subgraphs among the reconfigurable cells; and

executing the several subgraphs via the reconfigurable cells, the executing including;

transmitting a data signal from a first cell via which a first one of the subgraphs is executed to a second cell via which a second one of the subgraphs is executed; and

transmitting a status with the data signal, the status indicating whether the data signal is valid.

12. The method of claim 11, further comprising:

receiving a valid data signal at the second cell; and

acknowledging receipt of the valid data signal.

13. The method of claim 12, further comprising,

transmitting by the second cell an indication that a signal is expected.

14. The method of claim 13, further comprising:

transmitting by the first cell an indication that the first cell is transmitting the expected signal.

15. A method of executing a program on hardware array of runtime reconfigurable cells, the method comprising:

forming, a plurality of subgraphs based on a program, the forming of the subgraphs being performed according to a constraint that each of the plurality of subgraphs corresponds to a respective single configuration of each of a respective plurality of the runtime configurable cells, an entirety of each of the subgraphs thereby being executable by the array of runtime reconfigurable cells without reconfiguration of any of the runtime reconfigurable cells;

performing, by a first one of the reconfigurable cells, a function corresponding to a first part of a first one of the subgraphs while the first cell is configured according to the configuration to which the first subgraph corresponds;

after the computing, reconfiguring the first cell for performing a function corresponding to a first part of a second one of the subgraphs, the reconfiguration being to the configuration to which the second subgraph corresponds; and

simultaneously with the reconfiguring, performing, by a second one of the reconfigurable cells, a function corresponding to a second part of the first subgraph while the second cell is configured according to the configuration to which the first subgraph corresponds;

wherein state information determined for one of the subgraphs is transferred from the one of the subgraphs to a subsequently executed subgraph.

16. The method of claim 15, further comprising:

storing configuration definitions for the first one of the subgraphs and the second one of the subgraphs in configuration registers associated with the first cell.

17. The method of claim 16, further comprising:

marking unconfigured ones of the configuration registers as unconfigured.

18. The method of claim 15, further comprising:

selecting a configuration for the first cell based on a status signal generated by the cell structure.

19. The method of claim 15, further comprising:

selecting a configuration for the first cell based on a status signal generated by a higher-level loading unit.

20. The method of claim 15, further comprising:

selecting a configuration for the first cell based on an externally generated status signal.

21. The method of claim 15, further comprising:

selecting a configuration for the first cell as a function of a present configuration of the first cell and a received status signal.

22. The method of claim 15, further comprising:

activating an unconfigured configuration register in the first cell;

requesting a configuration from a higher-level load unit when the unconfigured configuration register is activated; and

suspending execution of a subgraph until the requested configuration is fully loaded.

23. The method of claim 15, further comprising:

triggering a loading of a configuration of the first cell when a status signal generated by the cell structure is received by the first cell.