Abstract:
A method of synchronizing and reconfiguring configurable elements in a programmable unit is provided. A unit has a two- or multi-dimensional, programmable cell architecture (e.g., DFP, DPGA, etc.), and any configurable element can have access to a configuration register and a status register of the other configurable elements via an interconnection architecture and can thus have an active influence on their function and operation. By making synchronization the responsibility of each element, more synchronization tasks can be performed at the same time because independent elements no longer interfere with each other in accessing a central synchronization instance.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a division of U.S. Ser. No. 08/946,812, filed Oct. 8, 1997 now U.S. Pat. No. 6,081,903. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to a method of synchronization and reconfiguration of configurable elements in a programmable unit. 
     BACKGROUND INFORMATION 
     Synchronization of configurable elements in conventional units (e.g., FPGAs, DPGAs, etc.) is usually based on the clock pulse of the unit. This type of time-controlled synchronization poses many problems. One problem is that the amount of time a task will require is often not known until a final result is achieved. Another problem with time-controlled synchronization is that the event upon which the synchronization occurs is triggered by an independent element instead of the element to be synchronized itself. In this case, two different elements are involved in the synchronization which leads to high management overhead. 
     SUMMARY OF THE INVENTION 
     The present invention relates to a method for synchronization based on the elements to be synchronized themselves. In accordance to an exemplary embodiment according to the present invention, synchronization is no longer implemented or administered by a central instance. By making synchronization the responsibility of each element, more synchronization tasks can be performed at the same time because independent elements no longer interfere with each other in accessing the central synchronization instance. 
     In a unit with a two- or multi-dimensional, programmable cell architecture (e.g., DFP, DPGA, etc.), any configurable element can have access to the configuration and status register of the other configurable elements via an interconnection architecture and can thus have an active influence on their function and operation. Thus, in addition to the usual method, the configuration may also take place from a processing array (see PACT02: PA) through a primary logic unit. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows an exemplary loop construct implemented using triggers in accordance with the present invention. 
     FIG. 2 shows an exemplary comparator construct implemented using multiple triggers in accordance with the present invention. 
     FIG. 3 shows an exemplary comparator construct with multiple outputs implemented by using multiple triggers and interleaving them in accordance with the present invention. 
     FIG. 4 shows exemplary extensions in comparison with a device from PACT02. 
    
    
     DETAILED DESCRIPTION 
     The present invention includes a run-time programmable, run-time reconfigurable unit. The configurable elements on the chip have one or more configuration registers for different tasks. Read and write access to these configuration registers may be provided. In describing the present invention, it is assumed that a configuration can be set in an element to be configured for the following information: 
     Interconnection register. The type of connection with other cells is set in this register. 
     Command register. The function to be carried out by the configurable element is entered in this register. 
     Status register. The cell stores its current status in this register. This status provides information to the other elements of the component regarding which processing cycle the cell is in. 
     A cell is configured by a command which determines the function of the cell that is to be carried out. In addition, configuration data are entered to set the interconnection with other cells and the contents of the status register. The cell is then ready for operation after this procedure. 
     To permit a flexible and dynamic interaction of multiple cells, each cell can have read or write access to all the configuration registers of another cell. The type of command with which a specific cell has been configured will determine to which of the many configuration registers the cell has read or write access. Each command that can be executed by the cell exists in as many different modes of address as there are different independent configuration registers in an element to be configured. 
     For example, assume that a cell has the configuration registers indicated above (i.e., interconnection, command and status) and is set to execute an ADD command, which performs addition. Through the various types of ADD commands, the present invention allows a selection of where the result of this function is to be transferred. The following are examples of some possibilities: 
     ADD-A. The result is transmitted to operand register A of the target cell. 
     ADD-B. The result is transmitted to operand register B of the target cell. 
     ADD-V. The result is transmitted to the interconnect register of the target cell. 
     ADD-S. The result is transmitted to the status register of the target cell. 
     ADD-C. The result is transmitted to the command register of the target cell. 
     In addition to generating the result, each cell can also generate a number of trigger signals. The trigger signals need not necessarily be transmitted to the same target cell that receives the result of processing the configured command. One trigger signal or a combination of multiple trigger signals triggers a certain action in the target cell or puts the cell in a certain status. A description of the states can be found in the following text. The following are some exemplary trigger signals: 
     GO trigger. The GO trigger puts the target cell in a READY status. 
     RECONFIG trigger. The RECONFIG trigger sets the target cell in a RECONFIG status, so that the cell can be reprogrammed. This trigger is especially appropriate in conjunction with switching tables. If it is assumed that the data to be processed is loaded into the operand registers at the rising edge of the clock pulse, processed in the period of the H level, and written to the output register at the trailing edge, then reconfiguration of the cell is possible at the trailing edge. The new configuration data is written to the command register at the trailing edge. The period of the L level is sufficient to successfully conclude the reconfiguration. 
     STEP trigger. The STEP trigger triggers a single execution of the configured command by the target cell that is in a WAIT status. 
     STOP trigger. The STOP trigger stops the target cell by setting the cell in a STOP status. 
     The ability to indicate, in the processing cell, which register of the target cell the result is to be entered and which type of trigger signal is to be generated, a quantity of management data can be generated from a data stream. This management data is not a result of the actual task to be processed by the chip, but instead serves only the function of management (e.g., synchronization, optimization, etc.) of the internal status. 
     Each cell can assume the following states, which are represented by appropriate coding in the status register: 
     READY. The cell has been configured with a valid command and can process data. Processing takes place with each clock cycle. The data is entered into the register of the target cell on the basis of the addressing type of the cell sending the data. 
     WAIT. The cell has been configured with a valid command and can process data. Processing takes place in part on the basis of a trigger signal which can be generated by other elements of the unit. The data is entered into the register of the target cell on the basis of the addressing type of the cell sending the data. 
     CONFIG. The cell has not been configured with a valid command. The data packet which is sent to the cell with the next clock cycle is entered into the command register. The data packet is entered into the command register, regardless of which addressing type has been used by the cell sending the data. 
     CONFIG WAIT. The cell has not been configured with a valid command. A data packet is entered with the next trigger signal which can be generated by other elements of the unit and can be written to the command register. The data packet is entered into the command register, regardless of which addressing type has been used by the cell sending the data. 
     RECONFIG. The cell has been configured with a valid command, but it is not processing any data at the moment. The data is accepted by the cell (transferred to the input register) but is not processed further. 
     STOP. The cell is configured with a valid command, processed, but with no data so far. The data is received by the cell (transmitted to the input register) but not further processed. 
     Due to these various states and the possibility of read and write access to the various registers of the other cells, each cell can assume an active management role. In contrast, conventional units of this type have a central management instance which must always know and handle the overall status of the unit. 
     To achieve greater flexibility, there is another class of commands which change in type after the first execution. Using the example of the ADD command, the command may have the following format: 
     ADD-C-A. The result of the ADD function is written to the command register of the target cell with the first execution of the command. With each subsequent execution, the result is written to operand register A. 
     This possibility can be expanded as much as desired, so that commands of the type ADD-C-V-A-C- . . . B are also conceivable. Each command can assume all permutated combinations of the different addressing and triggering types. 
     The following are hardware expansions that may be required to implement an exemplary embodiment according to the present invention using a base device described in PACT02. In addition, a complete illustration of the necessary hardware is also provided in FIG.  4 . 
     Additional Registers 
     A status register and a configuration register are added to the registers described in PACT02. Both registers are triggered by the PLU bus and have a connection to the state machine of the SM UNIT (PACT02, FIG.  2 :  0213 ). 
     Change in the PLU Bus 
     In PACT02, the configurable registers M/F-PLUREG are managed exclusively over the PLU bus (PACT02, FIG.  2 :  0210 ). To ensure the functional capabilities provided by the present invention, there must also be an additional possibility of access through the normal system bus (PACT02, FIG.  2 :  0201 ). The same thing is true of the new status and configuration registers. 
     Only the part of the system bus that is interconnected with the PAE over the BM UNIT (PACT02, FIG.  2 :  0210 ) is relevant for the registers. Therefore, the bus is relayed from the BM UNIT to the registers, where upstream multiplexers or upstream gates assume the switching between the PLU bus and the system bus relevant for the PAE. 
     The multiplexers or gates are wired so that they always switch through the system bus relevant for the PAE except after a reset of the unit (RESET) or when the ReConfig signal (PACT02, FIG.  3 :  0306 ) is active. 
     Expansion of the System Bus 
     The system bus (PACT02, FIG.  2 :  0201 ) is expanded to the extent that the information about the target register is transmitted together with the data. This means that an address which selects the desired register at the data receiver is also sent at the same time. 
     In the example shown in FIG. 1, macro  0103  will be executed 70 times. A single execution of the macro  0103  requires 26 clock cycles. This means that counter  0101  may be decremented by one only once in every 26 clock cycles. One problem with freely programmable units is that it is not always possible to guarantee that the execution of macro  0103  will actually be concluded after 26 clock cycles. A delay can occur, for example, due to the fact that a macro which is supposed to deliver input data for macro  0103  suddenly needs ten clock cycles longer. For this reason, the cell in macro  0103  sends a trigger signal to counter  0101  which determines when the result of the computation is sent to another macro. At the same time, processing of macro  0103  is stopped by the same cell. This cell “knows” exactly when the condition for termination of a computation has been reached. 
     The trigger signal sent in this case is a STEP trigger which causes counter  0101  to execute its configured function once. The counter decrements its count by one and compares whether it has reached the value zero. If this is not the case, a GO trigger is sent to macro  0103 . This GO trigger signal causes macro  0103  to resume its function again. 
     This process is repeated until counter  0101  has reached a value of zero. Then a trigger signal is sent to macro  0102 , where it triggers a function. 
     A very precise synchronization can be achieved by this interaction of triggers. 
     FIG. 2 is similar to FIG. 1 except, in this case, the function in element  0202  is not a counter but a comparator. Macro  0201  sends a comparison value to comparator  0202  after each processing run. Depending on the output of the comparison, different triggers are again activated to, for example, cause an action in macros  0203 . The construct shown in FIG. 2 corresponds to that of an IF query in a conventional program language. 
     In FIG. 3, several comparators  0301 ,  0302  are implemented in a construction of an IF-ELSE-ELSE construct (or a multiple choice). By using various types of triggers and connections of these triggers to macros  0303 ,  0304 , a very complex sequences can be easily implemented. 
     FIG. 4 shows the differences in FIG. 2 in comparison with PACT02 with the differences shown with shading. The configuration register  0401  and the status register  0402  are connected to the SM UNIT over the bus  0407 . Registers  0401 ,  0402 , F- and M-PLUREG are connected to a gate  0403  over an internal bus  0206  that connects the internal bus  0406  to the PLU bus  0405  (e.g., to permit configuration by the PLU), or to the BM UNIT over a bus  0408 . Depending on the addressing on data bus  0404 , the BM unit relays the data to the O-REG or to the addressed register  0401 ,  0402 , F- or M-PLUREG. 
     GLOSSARY OF TERMS 
     Definition of Terms 
     BM UNIT: Unit for sending data on the bus systems outside the PAE. The data is sent over multiplexers for the data inputs and gates for the data outputs. OACK lines are implemented as open-collector drivers. The BM UNIT is controlled by the M-PLUREG. 
     Data receiver: The unit(s) that further process(es) the results of the PAE. 
     Data transmitter: The unit(s) that make(s) data available for the PAE as operands. 
     Data string: A data string consists of a bit sequence of any length. This bit sequence is a processing unit for a system. Commands for processors and similar units as well as strictly data can be coded in a data string. 
     DFP: Data flow processor according to (unexamined) German Patent Application DE 44 16 881. 
     DPGA: Dynamically programmable gate array. Known. 
     EALU: Expanded arithmetic and logic unit. An ALU that has been expanded by adding special functions that are needed or appropriate for operation of a data processing system according to German Patent Application DE 441 16 881 A1. These are counters in particular. 
     Elements: Collective term for all types of self-contained units which are used as one piece in an electronic unit. Elements are thus: 
     Configurable cells of all types 
     Clusters 
     RAM blocks 
     Logic units 
     ALUs 
     Registers 
     Multiplexers 
     I/O pins of a chip 
     Event: An event can be analyzed by a hardware element in any appropriate manner for the application and it can trigger a conditional action as a response to this analysis. Events are thus, for example: 
     Clock cycle of a data processing system, 
     Internal or external interrupt signal, 
     Trigger signal from other elements within the unit, 
     Comparison of a data stream and/or a command stream with a value, 
     Input/output events, 
     Running, overrunning, resetting, etc. a counter, 
     Analysis of a comparison. 
     FPGA: Field-programmable gate array. Known. 
     F-PLUREG: Register in which the function of the PAEs is set. Likewise, the one-shot and sleep modes are set. The PLU writes into the register. 
     H level: Logic 1 level, depending on the technology used. 
     Configurable element: A configurable element is an element of a logic unit which can be set by a configuration string for a specific function. Configurable elements are thus all types of RAM cells, multiplexers, arithmetic and logic units, registers and all types of internal and external interconnection description, etc. 
     Configurable cell: See logic cells. 
     Configure: Setting the function and interconnection of a logic unit, a (FPGA) cell or a PAE (see reconfigure). 
     Configuration data: Any quantity of configuration strings. 
     Configuration memory: The configuration memory contains one or more configuration strings. 
     Configuration string: A configuration string consists of a bit sequence of any length. This bit sequence represents a valid setting for the element to be configured, so the result is a functional unit. 
     Primary logic unit: Unit for configuring and reconfiguring the PAE. Embodied by a microcontroller adapted specifically to its task. 
     Logic cells: Configurable cells used in DFPs, FPGAs, DPGAs which fulfill simple logical or arithmetic tasks according to their configuration. 
     L level: Logic 0 level, depending on the technology used. 
     M-PLUREG: Register in which the interconnection of the PAEs is set. The register is written by the PLU. 
     O-REG: Operand register for storing the operands of the EALU. Permits chronological and functional independence of the PAEs from the data transmitters. This simplifies the transfer of data because it can take place asynchronously or packet-oriented. At the same time, this creates the possibility of reconfiguring the data transmitters independently of the PAEs or reconfiguring the PAEs independently of the data transmitters. 
     PLU: Unit for configuring and reconfiguring the PAEs. Embodied by a microcontroller adapted specifically to its function. 
     SM UNIT: State machine UNIT. State machine that controls an EALU. 
     Switching table: A switching table is a ring memory which is addressed by a control. The entries in a switching table may contain any configuration strings. The control can execute commands. The switching table responds to trigger signals and reconfigures the configurable elements on the basis of an entry in a ring memory. 
     Reconfigure: Reconfiguring any quantity of PAEs while any remaining quantity of PAEs continue their own functions (see configure). 
     Processing cycle: A processing cycle describes the period of time needed by a unit to go from a defined and/or valid state to the next defined and/or valid state. 
     Cells: Synonym for configurable elements. 
     Naming conventions 
     Subassembly:UNIT 
     Operating mode:MODE 
     Multiplexer:MUX 
     Negated signal:not 
     Register for PLU visible: PLUREG 
     Register internal:REG 
     Shift registers: sft 
     
       
         
               
             
               
               
               
             
               
             
               
               
               
             
               
             
               
               
               
             
               
             
               
               
               
             
           
               
                   
               
               
                 Function conventions 
               
               
                   
               
             
             
               
                 AND function &amp; 
               
             
          
           
               
                 A 
                 B 
                 Q 
               
               
                   
               
               
                 0 
                 0 
                 0 
               
               
                 0 
                 1 
                 0 
               
               
                 1 
                 0 
                 0 
               
               
                 1 
                 1 
                 1 
               
               
                   
               
             
          
           
               
                 OR function # 
               
             
          
           
               
                 A 
                 B 
                 Q 
               
               
                   
               
               
                 0 
                 0 
                 0 
               
               
                 0 
                 1 
                 1 
               
               
                 1 
                 0 
                 1 
               
               
                 1 
                 1 
                 1 
               
               
                   
               
             
          
           
               
                 NOT function ! 
               
             
          
           
               
                   
                 A 
                 Q 
               
               
                   
                   
               
               
                   
                 0 
                 1 
               
               
                   
                 1 
                 0 
               
               
                   
                   
               
             
          
           
               
                 GATE function G 
               
             
          
           
               
                 EN 
                 D 
                 Q 
               
               
                   
               
               
                 0 
                 0 
                 — 
               
               
                 0 
                 1 
                 — 
               
               
                 1 
                 0 
                 0 
               
               
                 1 
                 1 
                 1