Method for deadlock-free configuration of dataflow processors and modules with a two- or multidimensional programmable cell structure (FPGAs, DPGAs, etc.)

• US 6,571,381 B1
• Filed: 01/09/2001
• Issued: 05/27/2003
• Est. Priority Date: 02/25/1998
• Status: Expired due to Term

• Current Assignee: Scientia Sol Mentis AG (PACT XPP Schweiz AG)
• Original Assignee: Pact XPP Technologies, AG
• Inventors: Vorbach, Martin, Münch, Robert
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/623,113
• Time in Patent Office: 868 Days
• Field of Search: 716/1-18, 710/10, 710/52-57, 713/1-100
• US Class Current: 716/117
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture

Abstract

A method of deadlock-free, automatic configuration and reconfiguration of modules having a two- or multidimensional cell arrangement, in which a unit for controlling the configuration and reconfiguration manages a set of associated configurable elements, the set being a subset or the total set of all configurable elements, and the management takes place as follows: reconfiguration requests from the associated configurable elements are sent to the unit; the unit processes the requests; the unit processes the configuration data of the command sequence; and after the configuration data has been fully processed, new requests are accepted again, the configuration data still to be loaded of the existing previous requests being loaded from a buffer memory (FILMO) into the configurable elements until a new request occurs.

Claims

1. Method of deadlock-free, automatic configuration and reconfiguration of modules having a two-dimensional or multidimensional cell arrangement, including FPGAs, DPGAs, DFGs, characterized in that a unit for controlling the configuration and reconfiguration manages a set of associated configurable elements, the set being a subset or a total set of all configurable elements, and the management takes place as follows:

1.1 reconfiguration requests from the associated configurable elements are sent to the unit;

1.2 the unit processes the requests in that;

a) the instantaneous status of the configurable elements is saved;

b) configuration data still to be loaded of existing previous requests are loaded, if possible, from a buffer memory (FILMO) into the configurable elements;

c) a reconfiguration request is converted to an address of the configuration data to be loaded in a memory of the unit, if the configuration data exist in the memory of the unit;

d) the configuration data with a respective ID are requested from a higher level unit and loaded if the configuration data do not exist in the memory of the unit;

1.3 the unit processes the configuration data of a command sequence by;

a) loading the configuration data into the configurable elements if the configurable elements can accept the data;

b) loading the configuration data of the configurable elements that cannot accept the data into the buffer memory (FILMO) in chronological order;

1.4 after the configuration data has been fully processed, new requests are accepted again, the configuration data still to be loaded of the existing previous requests being loaded from a buffer memory (FILMO) into the configurable elements until a new request occurs.

2. Method according to claim 1, characterized in that configuration data that are not accepted by the configurable elements are written to the end of the buffer memory (FILMO).

3. Method according to claim 1, characterized in that configuration data to be written into the configurable elements are read from the beginning to the end of the buffer memory, the buffer memory always being run through completely.

4. Method according to claim 1, characterized in that configuration data written into the configurable elements at the beginning of the buffer memory are deleted in the buffer memory, so that a read pointer is set behind the written data.

5. Method according to claim 1, characterized in that configuration data written into the configurable elements from the middle of the buffer memory

a) are either marked as deleted in the buffer memory and thus skipped during a new read run,

b) or are deleted in the buffer memory (FILMO) in that the still existing configuration data are shifted from the memory location to be deleted to the beginning or to the end of the buffer memory (FILMO) so that the deleted memory location having the existing configuration data is filled and the pointers are adapted to the beginning or the end of the memory accordingly.

6. Method according to claim 1, characterized in that a state machine (garbage collector) manages the memory (CTR) of the unit so that no memory gaps are created by shifting memory gaps with existing configuration data from the beginning of the memory gap to the end of the memory (CTR) so that a deleted memory location having the existing configuration data is filled and a pointer is moved to the end of the memory and a translation of the ID is adapted to shifted memory locations accordingly.

7. Method according to claim 1, characterized in that requests received at the unit are translated into a unique identifier (ID) of a configuration routine, and the ID points to a memory location in the memory (CTR).

8. Method according to claim 1, characterized in that configuration data cause additional configuration data toube loaded (EXECUTE).

9. Method according to claim 1, characterized in that units are hierarchically arranged in a tree structure.

10. Method according to claim 9, characterized in that a highest unit in the tree structure shares a common memory with a higher level computer and the higher level computer controls sequences in the module via communication with a higher level unit.

11. Method according to claim 9, characterized in that units of the middle and highest hierarchical levels respond to requests from IDs in addition to conventional requests (triggers), wherein a translation of the ID into the address of the memory location of a referenced configuration routine takes place and a translation of a trigger into an ID being omitted.

12. Method according to claim 1, characterized in that configuration data cause other configuration data to be executed in other units upon request to another unit, the requests

a) being transmitted as a broadcast to all other units;

b) being only transmitted to an immediately higher level unit;

c) being only transmitted to an immediately lower level unit(s);

d) being transmitted to a certain addressed unit.

13. Method according to claim 1, characterized in that certain configuration data of the configurable elements which cannot accept data are loaded into the buffer memory (FILMO) and all subsequent configuration data of a command sequence are also loaded into the buffer memory.

14. Method according to claim 1, characterized in that certain configuration data of the configurable elements are only loaded into the configurable elements if all of the previous configuration data of a command sequence could be loaded into the configurable elements.

15. Method according to claim 1, characterized in that a fixed predefined configuration sequence is maintained within the command sequence by using the method according to claim 13 and/or claim 14.

16. Method according to claim 1, characterized in that the reconfiguration request received from the associated elements is translated into a unique identification number of a respective command sequence.

17. Method according to claim 1, characterized in that a reconfiguration request not referenced during translation into an identification number is recognized, marked as not referenced, and processed.

18. Method according to claim 1, characterized in that identification numbers are translated via a lookup table.

19. Method according to claim 1, characterized in that the reconfiguration request received from the associated elements is already provided with a unique identification number.

20. Method according to claim 19, characterized in that the unique identification number is translated into the address of the respective command sequence in the memory.

21. Method according to claim 1, characterized in that if no valid address exists, the corresponding command sequence is loaded into the memory and an address reference is formed.

22. Method according to claim 1, characterized in that a translation of the ID to the address takes place via a lookup table.

23. Method according to claim 1, characterized in that the buffer memory is not designed to separate memory, and the buffer memory corresponds exactly with the command sequence, wherein non-configurable configuration words are marked, so that when the command sequence is called up again, only the marked configuration words are processed again.

24. Method according to claim 1, characterized in that command sequences are linked via pointers so that a time sequence in loading a previously non-configurable configuration words into the configurable elements is maintained.

25. Method according to claim 1, characterized in that command sequences are fully linked via pointers, so that a garbage collector runs over all the command sequences using links and overwrites a command sequence to be removed with a subsequent command sequence, removing it from the pointer link.