Abstract:
A data processor having a plurality of coarse-grained data processing elements arranged in rows and columns, an interconnect structure comprising both global and direct interconnects, the global interconnects interconnecting the coarse-grained data processing elements globally and the direct interconnects interconnecting adjacent data processing elements.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of and claims priority to U.S. patent application Ser. No. 12/389,274, filed on Feb. 19, 2009, which is a continuation of U.S. patent application Ser. No. 10/570,173, filed on Nov. 10, 2006, which is the national stage of International Application Serial No. PCT/EP04/09640, filed on Aug. 30, 2004, which claims priority to German Patent Application Serial No. DE 030 19 428.6, filed on Aug. 28, 2003, the entire contents of each of which are expressly incorporated herein by reference. 
     
    
     FIELD OF INVENTION 
       [0002]    The present invention relates to reconfigurable computing. In particular, the present invention relates to improvements in the architecture of reconfigurable devices. 
       BACKGROUND INFORMATION 
       [0003]    Reconfigurable data processing arrays are known in the art. Reference is being made to the previous applications and/or publications of the present applicant/assignee all of which are incorporated herein by way of reference. Accordingly, the devices described hereinafter may be multidimensional (n&gt;1) arrays comprising coarse grained computing and/or data operation elements allowing for runtime reconfiguration of the entire array or parts thereof, preferably in response to a signal indicating reconfigurability to a loading unit (CT, CM or the like). 
         [0004]    Now, several of these data processing arrays have been built (i.e. Xpp1, XPP128, XPP2, XPP64). It is however desirable to improve the known device further as well as to improve methods of its operation. 
       SUMMARY OF THE INVENTION 
       [0005]    Accordingly, in order to achieve this object there will be described a number of improvements allowing separately or in common to improve the performance and/or power consumption and/or cost of the device. 
         [0006]    A first way to improve the known devices is to improve the functionality of each single processor element. It has been previously suggested to include a ring-memory (RINGSPEICHER) in the array, to store instructions in the ring-memory and to provide a pointer that points to one of the ring-memory addresses so as to select an instruction to be carried out next. Furthermore, it has been suggested to provide at least one “shadow configuration” and to switch over between several configurations/shadow configurations. Another or additional suggestions has been designated as “wave reconfiguration”. 
         [0007]    While these known methods improve the performance of a reconfigurable device, there seems to be both a need and a possibility for further improvements. 
         [0008]    It is to be understood that while in the following description, a detailed example is given, for example with respect to the number of registers given associated with each PAE, it is not deemed necessary to provide an ALU with exactly this number of registers. Rather, it will be understood by the average skilled person that deviations from the explicitly described embodiment are easily feasible and that the detailed level of description stems from an effort to provide an exemplary PAE and not from the wish to restrict the scope of invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  shows an ALU-PAE architecture. 
           [0010]      FIG. 2  shows function folding. 
           [0011]      FIG. 3  shows a sequencer model. 
           [0012]      FIG. 4  shows Method A: FF PAE program pointer. 
           [0013]      FIG. 5  shows Method B: FF PAE program pointer. 
           [0014]      FIG. 6  shows a test logic. 
           [0015]      FIG. 7  shows an overview of the entire circuitry of  FIGS. 5 and 6 . 
           [0016]      FIG. 8  shows a VPU architecture. 
           [0017]      FIG. 9  shows a PAE implementation. 
           [0018]      FIG. 10  shows a bus system. 
           [0019]      FIG. 11  shows a modified PAE structure. 
           [0020]      FIG. 12  shows an ALU-PAE having inputs and outputs in both directions. 
           [0021]      FIG. 13  shows a modified bus system. 
           [0022]      FIG. 14  shows a PAE exchanging data without latency. 
           [0023]      FIG. 15  shows an optimised PAE arrangement. 
           [0024]      FIG. 16  shows superscalar FF ALU-PAEs. 
           [0025]      FIG. 17  shows a datapath architecture. 
           [0026]      FIG. 18  shows another datapath architecture. 
           [0027]      FIG. 19  shows a configurable sequencer. 
           [0028]      FIG. 20  shows an enhanced version of an ALU-PAE. 
           [0029]      FIG. 21  shows an overview of the RAM-PAE. 
           [0030]      FIG. 22  shows PAE Structure and Arrangement V2.0 and PAE Structure and Arrangement V2.2. 
           [0031]      FIG. 23  shows an enhanced DF or Bypass (PB) part within the PAEs. 
           [0032]      FIG. 24  shows an enhancement of RAM-PAEs. 
           [0033]      FIG. 25  shows a memory organization. 
           [0034]      FIG. 26  shows another memory organization. 
           [0035]      FIG. 27  shows address generators. 
           [0036]      FIG. 28  shows a parameter stack mode. 
           [0037]      FIG. 29  shows multi-config mode. 
           [0038]      FIG. 30  shows multi-config mode for long configurations. 
           [0039]      FIG. 31  shows parameter broadcast and update. 
           [0040]      FIG. 32  shows code bank, data bank, stack bank, and auxiliary bank. 
           [0041]      FIG. 33  shows the memory layout. 
           [0042]      FIG. 34  shows the memory layout. 
           [0043]      FIG. 35  shows an advanced valid checking scheme. 
           [0044]      FIGS. 36 to 44  show an improved way of routing. 
           [0045]      FIG. 45  shows a simplified structure of an XPP array. 
           [0046]      FIG. 46  shows a function folding processing element. 
           [0047]      FIGS. 47A and 47B  show an address generation data flow graph. 
           [0048]      FIG. 48  shows an extended XPP tool flow. 
           [0049]      FIGS. 49A and 49B  show a complex FIR filter cell. 
           [0050]      FIG. 50  shows data and control flow. 
           [0051]      FIG. 51  shows a PAE-like Petri-Net. 
           [0052]      FIG. 52  shows data duplication in the output path of the Petri-Net. 
       
    
    
     DETAILED DESCRIPTION 
     1 Overview of Changes vs. XPP XPP-II 
     1.1 ALU-PAE Architecture 
       [0053]    In the suggested improved architecture, a PAE might e.g. comprise 4 input ports  100  and 4 output ports  104 . Embedded with each PAE is the FREG path newly named DF  135  with its dataflow capabilities, like MERGE, SWAP, DEMUX as well as ELUT. 
         [0054]    2 input ports Ri0 and Ri1 are directly connected to the ALU. 
         [0055]    Two output ports receive the ALU results. 
         [0056]    Ri2 and Ri3 are typically fed to the DF path which output is Ro2 and Ro3. 
         [0057]    Alternatively Ri2 and Ri3 can serve as inputs for the ALU as well. This extension is needed to provide a suitable amount of ALU inputs if Function Folding (as described later) is used. 
         [0058]    In this mode Ro2 and Ro3 serve as additional outputs. 
         [0059]    Associated to each data register (Ri or Ro) is an event port (Ei or Eo). 
         [0060]    It is possible, albeit not necessary to implement an additional data and event bypass BRi0-1  125 , BEi0-. The decision depends on how often Function Folding will be used and how many inputs and outputs are required in average. 
         [0000]    (see  FIG. 1  now) 
       1.1.1 Other Extensions 
       [0061]    SIMD operation is implemented in the ALUs to support 8 and 16 bit wide data words for i.e. graphics and imaging. 
         [0062]    Saturation is supported for ADD/SUB/MUL instructions for i.e. voice, video and imaging algorithms. 
       1.2 Function Folding 
     1.2.1 Basics and Input/Output Paradigms 
       [0063]    Within this chapter the basic operation paradigms of the XPP architecture are repeated for a better understanding based on Petri-Nets. In addition the Petri-Nets will be enhanced for a better understanding of the subsequently described changes of the current XPP architecture. 
         [0064]    In most arrays each PAE operates as a data flow node as defined by Petri-Nets. (Some arrays might have parts that have other functions and should thus be not considered as a standard PAE). A Petri-Net supports a calculation of multiple inputs  5200  and produces one single output  5202 . Special for a Petri-Net is that the operation is delayed until all input data is available. 
         [0065]    For the XPP technology this means:
       1. all necessary data is available   2. all necessary events are available       
 
         [0068]    The quantity of data—and events is defined by the data and control flow, the availability is displayed at runtime by the handshake protocol RDY/ACK. 
         [0000]    (see  FIG. 50  now) 
         [0069]    Here, the thick arbor indicates the operation, the dot on the right side indicates that the operation is delayed until all inputs  5300  are available. 
         [0070]    Enhancing the basic methodology function folding supports multiple operations—maybe even sequential—instead of one, defined as a Cycle. It is important that the basics of Petri-Nets remain unchanged. 
         [0000]    (see  FIG. 51  now) 
         [0071]    Here, typical PAE-like Petri-Nets consume one input packet  5400  per one operation. For sequential operation multiple reads of the same input packet are supported. However, the interface model again keeps unchanged. 
         [0072]    Data duplication occurs in the output path  5402  of the Petri-Net, which does not influence the operation basics again. 
         [0000]    (see  FIG. 52  now) 
       1.2.2 Method of Function Folding 
       [0073]    One of the most important extensions is the capability to fold multiple PAE functions onto one PAE and execute them in a sequential manner. It is important to understand that the intention is not to support sequential processing or even microcontroller capabilities at all. The intention of Function Folding is just to take multiple dataflow operations and map them on a single PAE, using a register structure instead, of a network between each function. 
         [0074]    One goal may be to save silicon area by rising to clock frequency locally in the PAE&#39;s. An additional expectation is to save power since the busses operate at a fraction of the clock frequencies of the PAEs. Data transfers over the busses, which consume much power, are reduced. 
         [0000]    (see  FIG. 2  now) 
         [0075]    The internal registers can be implemented in different ways, e.g. in one of the following two: 
       1. Dataflow Model 
       [0076]    Each register (r′) has a valid bit which is set as soon as data has been written into the register and reset after the data has been read. Data cannot be written if valid is set, data can not-be read if valid is not set. This approach implements a 100% compatible dataflow behaviour. 
       2. Sequencer Model 
       [0077]    The registers have no associated valid bits. The PAE operates as a sequencer, whereas at the edges of the PAE (the bus connects) the paradigm is changed to the XPP-like dataflow behaviour. 
         [0078]    Even if at first the dataflow model seems preferable, it has major down sides. One is that a high amount of register is needed to implement each data path and data duplication is quite complicated and not efficient. Another is that sometimes a limited sequential operation simplifies programming and hardware effort. 
         [0079]    Therefore it is assumed consecutively that sequencer model is implemented. Since pure dataflow can be folded using automatic tools the programmer should stay within the dataflow paradigm and not be confused with the additional capabilities. Automatic tools must take care i.e. while register allocation that the paradigm is not violated. 
         [0080]      FIG. 3  now shows that using sequencer model only 2 registers (instead of 4) are required. 
         [0081]    For allowing complex function like i.e. address generation as well as algorithms like “IMEC”-like data stream operations the PAE has not only 4 instruction registers implemented but 8, whereas the maximum bus-clock vs. PAE-clock ration is limited to a factor of 4 for usual function folding. 
         [0082]    It is expected that the size of the new PAE supporting Function Folding will increase by max. 25%. On the other hand 4 PAEs are reduced to 1. 
         [0083]    Assuming that in average not the optimum but only about 3 functions can be folded onto a single PAE a XPP64 could be replaced by a XPP21. Taking the larger PAEs into account the functionality of a XPP64 XPP-II should be executable on a XPP XPP-III with an area of less than half. 
         [0084]    The function folding method and apparatus as well as other further improvements will be described in even more detailed hereinafter. 
       Equality of Internal Data Registers and Bus Transfers 
       [0085]    The function fold concept realizes two different models of data processing:
       a) Sequential model, wherein within the PAE the same rules apply as in von-Neuman- and Harvard-processors.   b) PACT VPU-model, wherein data are calculated or operated upon in arbitrary order according to the PETRI-Net-Model (data flow+synchronization).       
 
         [0088]    Due to the unpredictability of the arrival of data at the input registers (IR) a deadlock or at a least significant reduction in performance could occur if the commands in RC0 . . . RCn  108  were to be performed in a linear manner. In particular, if feed-backs of the PAE outputs to the inputs of the PAE are present, deadlocks might occur. This can be avoided if the instructions are not to be processed in a given order but rather according to the possibility of their processing, that is, one instruction can be carried out as soon as all conditions of the VPU-model are fulfilled. Therefore, for example, once all RDY-handshakes of incoming data, ACK-handshakes of outgoing data and, if necessary, triggers, (including their handshakes) are valid, then the instruction can be carried out. As the FF PAE has data additionally stored in internal registers, their validity and status has to be checkable as well in a preferred embodiment. Therefore, every internal data register (RD0 . . . RDn)  110  is separately assigned a valid bit indicating whether or not valid data are present in the register. When writing data into the register, valid is set; when reading, valid is reset. Data can be read only if “valid” is set and can be written only if “valid” is not set. Accordingly, the valid flag corresponds most closely to the status that is produced in the state machines of bus systems by the transmittal of RDY/ACK-handshakes. It is a preferred embodiment and considered to be inventive to provide a register with a status bit in that way. 
         [0089]    It is therefore possible to carry out instructions at the time when all conditions for the execution—again very similar to PETRI-nets are fulfilled. 
         [0090]    Basically, there are two methods available for selection of instruction and control of their execution described herein after. 
       Method a: FF PAE Program Pointer (Finite State Machine &amp; Program Pointer—Approach) 
       [0091]    (see  FIG. 4  now) 
         [0092]    According to the control principle of sequential processors, a program counter is used to select a certain instruction within the instruction memory. A finite state machine  400  controls the program counter. This finite state machine now checks whether or not all conditions for the instruction in RC (PC), that is the instruction, onto which the PC. (Program Counter)  402  points, are fulfilled. To do so, the respective RDY- and/or ACK-handshakes of the in- and/or outputs needed for the execution of the instructions are checked. Furthermore, the valid-flags of the internal registers to be read (RD0 . . . RDn)  404  are checked so as to control whether or not they are set, and the valid-flags of those internal registers (RD0 . . . RDn) into which is to be written, are checked whether they are not set. If one of the conditions is not fulfilled, the instructions will not be carried out. PC is controlled to count further, the instruction is skipped and the next instruction is selected and checked as described. 
         [0093]    The advantage of this method is the compatibility with sequential processor models. The disadvantage resides in the necessity to test and to skip instructions. Both of which might result in significant losses of performance under certain circumstances. 
       Method B: FF PAE Program Pointer (Enabler &amp; Arbiter-Approach) 
       [0094]    (see  FIG. 5 . now) 
         [0095]    This method is based upon the possibility to test all instructions in Rc0 . . . Rcn  502  in parallel. In order to save the expense of the complete decoding of array instructions, each RC is assigned an entry in an evaluation mask field, the length of which corresponds to the maximum number of states to be tested; therefore, for every possible RDY- or ACK-trigger-signal (as well the RDY/ACKs of the triggers) as well as for every valid bit in RD0 . . . RDn  404  two bits are available indicating whether or not the respective signal is to be set or not set; or, whether the state of the signal is unimportant for the execution of the instruction. 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 InData-RDY 
                 OutData-ACK 
                 InTrigger 
                 OutTrigger-ACK 
                 Rd Data Valid 
               
             
          
           
               
                 Rdy 
                 don&#39;t 
                 Ack 
                 don&#39;t 
                 trigger 
                 rdy 
                 don&#39;t 
                 ack 
                 don&#39;t 
                 valid 
                 don&#39;t 
               
               
                 value 
                 care 
                 value 
                 care 
                 value 
                 value 
                 care 
                 value 
                 care 
                 value 
                 care 
               
               
                   
               
             
          
         
       
     
         [0096]    The mask shows only some entries. At In-Trigger, both the state of the trigger (set, not set) as well as the value of the trigger (trigger value) can be tested via RDY-value. 
         [0097]    A test logic testing  500  via for example the Line Control described herein after all instructions in parallel. Using an arbiter  650 , an instruction of the set of all executables is selected. The arbiter controls the instruction multiplexer via ISel according to the transferral of the selected instructions to the PAE. 
         [0098]    The Line Control has one single line of Boolean test logic for every single instruction. By means of an ExOR-gate (e)  600  the value of the signal to be tested against the setting in em of the line is checked. By means of an OR-gate (+)  602  respectively, a selection is carried out, whether the checked signal is relevant (don&#39;t care). The results of all checked signals are ANDed. A logic 1 at the -output of the AND-gates (&amp;)  604  shows an executable instruction. For every RC, a different test-line exists. All test-lines are evaluated in parallel. An arbiter having one of a number of possible implementations such as a priority arbiter, Round-Robin-Arbiter and so forth, selects one instruction for execution out of all executable instructions. There are further implementations possible obvious to the average skilled person. Those variants might be widely equivalent in the way of operation and function. In particular, the possibility of using “negative logic” is to be mentioned. 
         [0000]    (see  FIG. 6  now) 
         [0099]      FIG. 7  now gives an overview of the entire circuitry. 
         [0100]    Advantages of the method are:
       Significantly fast, in view of the fact that one instruction can be carried out in every single clock   Reduced power consumption, since no energy is wasted on discarded cycles which is in particular advantageous to the static power dissipation.   Similar hardware expense as in the sequential solution when using small and medium sized configuration memories (RC) therefore similar costs.       
 
         [0104]    Disadvantages:
       Likely to be significantly more expensive on large RC; therefore, an optimisation is suggested for a given set of applications.   In order to implement the sequencer mode (compare other parts of the application) the program counter having an FSM must be provided for. The FSM then is restricted to the tasks of the sequencer so that the additional expenses and the additional costs are relatively low.       
 
         [0107]    Depopulated Busses According to the State of the Art 
         [0108]    All busses assigned to a certain PAE are connected to the input registers (IR) or the output registers of the PAE are connected to all busses respectively (compare for example DE 100 50 442.6 or the XPP/VPU-handbooks of the applicant). 
         [0109]    It has been realised that PAEs, in particular FF PAEs, allow for a depopulation of bus interconnects, in particular, if more IR/OR will be available compared to the State of the Art of the XPP as previously known. The depopulation, that is the reductions of the possibilities to connect the IR or ER onto the busses can be symmetrically or asymmetrically. The depopulation will typically amount to 20 to 70%. It is significant that the depopulation will not or not significantly affect the interconnectability and/or the routability of an algorithm in a negative way. 
         [0110]    The method of depopulation is particularly relevant in view of the fact that several results can be achieved. The hardware-expense and thus the costs of the bus systems can be reduced significantly; the speed of the busses is increased since the gate delay is reduced by the minimisation of connecting points; simultaneously, the power consumption of the busses is reduced. 
         [0111]    A preferred depopulation according to the VPU-architecture according to the State of the Art, however, with more IR/OR is shown in  FIG. 8  now. 
         [0112]    In particular, reference is being made to an optional extension of the bus architecture allowing for a direct next neighbour data transfer of two adjacent PAEs, in particular two PAEs placed one onto the other. Here, the outputs (OR) of one PAE are directly connected to a dedicated bus which is then directly connected to the inputs (IR) of a neighbouring PAE (compare  FIG. 9  now). The figure only shows a horizontal next neighbour bus, however, in general, vertical busses are possible as well. 
         [0113]    In  FIG. 8  now, the shaded circles stand for possible bus connects: MUX. Double circuits stand for a connection from the bus: DeMUX. 
       Changes of the PAE IO 
       [0114]      FIG. 9  now shows the State of the Art of a PAE implementation as known from XPU 128, XPP64A and described in DE 100 50 442.6 
         [0115]    The known PAE has a main data flow in the direction from top to bottom to the main ALU  10  in the PAE-core. At the left and right side, data channels are placed additionally transmitting data along the main data flow direction, once the same direction as the main data flow (FREG)  800  and once in the reverse direction (BREG)  802 . On both sides of the PAE, data busses are provided that run in the reverse direction of the main data flow of the PAE and onto which the PAE as well as FREG and BREG are connected. The architecture of the State of the Art requires eight data busses for each PAE side as well as four transfer channels for FREG/BREG for typical applications. 
         [0116]    The bus system of the State of the Art has switching elements, register elements (R)  1000 , each at the side of the PAEs. The switching elements allow for the disruption of a bus segment or disconnection to a neighbouring bus, the register elements allow the construction of an efficient pipelining by transferring data through the register, so as to allow for higher transferral band-width. The typical latency in vertical direction for next-neighbour-transmitting is 0 per segment, however is 0.5-1 in horizontal direction per segment and higher frequencies. 
         [0000]    (see  FIG. 10  now) 
         [0117]    Now, a modified PAE structure is suggested, wherein two ALUs  10   a ,  10   b , each having a different main data flow direction are provided in each PAE, allowing for significantly improved routability. On one hand, the tools used for routing are better and simpler; on the other hand, a significant reduction in hardware resources is achieved. First tests show that the number of busses necessary in horizontal direction is reduced by about 25% over the State of the Art. The vertical connects in FREG/BREG (=BYPASS) can even be reduced by about 50%. Also, it is no more necessary to distinguish between FREG and BREG as was necessary in DE 100 50 442.6. 
         [0000]    (see  FIG. 11  now) 
         [0118]    The double-ALU structure has been further developed to an ALU-PAE  10  having inputs and outputs in both directions. Using automatic routers as well as hand-routed applications, further additional significant improvements of the network topology can be shown. The number of busses necessary seems to be reduced to about 50% over the State of the Art, the number of vertical connects in the FREG/BREG (=BYPASS) can be reduced by about 75%. 
         [0000]    (see  FIG. 12  now) 
         [0119]    For this preferred embodiment which can be used for conventional as well as for function fold ALUs, it is possible to place register and switching elements  1000  in the busses in the middle of the PAE instead of at the sides thereof (see  FIG. 13  now). 
         [0120]    In this way, it is possible even for high frequencies to transmit data in horizontal direction to the respective neighbouring PAE without having to go through a register element. Accordingly, it is possible to set, up next neighbour connections in vertical and horizontal directions which are latency free (compare State of the Art and drawings referring to depopulated busses). The example of the interconnections shown in the respective figure allows transferral having zero latency in vertical direction and horizontally from left to right. Using an optimisation of PAE interface structure a latency free next neighbouring transmission in both horizontal directions can be achieved. If in every corner of the PAE input register (IR, arrow of bus into PAE)  1405  from bus and output register (OR, arrow from PAE to bus)  1400  to the bus are implemented, each neighbouring PAE can exchange data without latency. 
         [0000]    (see  FIG. 14  now) 
         [0121]    It is possible to further optimise the above disclosed PAE arrangement. This can be done by using no separate bypass at all in all or some of the PAEs. The preferred embodiment comprises two ALUs  1500 ,  1502 , one of these being “complete” and having all necessary functions, for example multiplication and BarrelShift while the second has a reduced instruction set eliminating functions that require larger arrays such as multiplication and BarrelShift. The second ALU is in a way replacing BYPASS (as drawn). There are several possible positions for the register in switching elements per bus system, and two of the preferred positions per bus are shown in  FIG. 15  in dotted lines. 
         [0122]    Both ALUs comprise additional circuits to transfer data between the busses so as to implement the function of the bypass. A number of possible ways of implementations exist and two of these shall be explained as an example. 
       a) Multiplexer 
       [0123]    Configurable multiplexers within the ALU are connected so that ALU inputs are bypassing the ALU and are directly connected to their outputs. 
       b) MOVE Instruction 
       [0124]    A MOVE instruction, stored in Rc0 . . . Rcn is transferring within the respective processing clock of the function fold the data according to the input specified within the instruction to the specified output. 
       Superscalarity/Pipelining 
       [0125]    It is possible and suggested as first way of improving performance to provide roughly superscalar FF ALU-PAEs which calculate for example 2, 4, 8 operations per bus clock @ FF=2, 4, 8, even while using the MUL opcode. 
         [0126]    The basic concept is to make use of the VALID-flags of each internal register. MUL is implemented as one single opcode which is pipelined over two stages. 
         [0127]    MUL  1704  takes its operands from the input registers Ri and stores the results into internal data registers Rd. VALID is set if data is stored into Rd. ADD (or any other Opcode, such as BSFT  1706 ) uses the result in Rd if VALID is set; if not the execution is skipped according to the specified VALID behaviour. In addition the timing changes for all OpCodes, if the MUL instruction is used inside a PAE configuration. In this case all usually single cycle OpCodes will change to pipelined 2 cycle, OpCodes. The change is achieved by inserting a bypass able multiplexer into the data stream as well as into control. 
         [0128]    The following program will be explained in detail:
       MUL (Rd0, Rd1), Ri0, Ri1;   ADD Ro0, Rd1, Ri2;       
 
         [0131]    In the first bus-cycle after configuration (t 0 ) MUL is executed (assuming the availability of data at Ri0/1). The register pair Rd0/1 is invalid during the whole bus-cycle, which means during both FF-PAE internal clock cycles. Therefore ADD is not executed in the 2 nd  clock cycle. After t 0  the result of MUL is written into the register pair, which VALID flags are set at the same time. 
         [0132]    In t 1  new data is multiplied. Since the VALID is set for Rd0/1 now the ADD command is executed in the 2 nd  clock cycle, but takes 2 clock cycles for over all execution. Therefore operand read and result write is inline for both operations, MUL as well as ADD. 
         [0133]    The result of a MUL-ADD combination is available with 2 clocks latency in a FF=2 ALU-PAE. For FF&gt;=6 no latency is inserted. 
         [0000]    (see  FIG. 16  now) 
         [0134]    However since multiplication and all other commands are processed in parallel the machine streams afterwards without any additional delays. 
         [0000]    (see  FIG. 17  now) 
         [0135]    If there are OpCodes besides MUL which require 2 clock cycles for execution (e.g. BSTF) the architecture must be modified to allow at least 3 data writes to registers after the second internal clock cycle. 
         [0136]    The data path output multiplexer gets 2 times larger as well as the bus system to the output registers (OR)  1702  and the feedback path to the internal data registers (Rd). 
         [0137]    If accordingly defined for the OpCodes, more than 4 internal registers can be used without increasing the complexity by using enables (en) to select the specific register to write in the data. Multiple registers are connected to the same bus, e.g. Rd0, Rd4, Rd8, Rd12. However not all combinations of register transfers are possible with this structure. If e.g. MUL uses Rd0 and Rd1 the following registers are blocked for the OpCode executed in parallel: Rd4, 5, 8, 9, 12, 13. 
       Register Map: 
       [0138]      
         [0000]                                            Rd0           Rd1           Rd2           Rd3           Rd4           Rd5           Rd6           Rd7           Rd8           Rd9           Rd10           Rd11           Rd12           Rd13           Rd14           Rd15                        
Datapath Architecture: See  FIG. 18  Now. The Sequencer PAEs
 
         [0139]    Since there is a need to be able to run control flow dominated applications on the XPP III as well, Sequencer PAEs will be introduced. Such a PAE can be thought of as a very simple kind of processor which is capable to run sequential code within the XPP. This allows the efficient implementation of control flow oriented applications like the H.264 Codec on the array whereas with SEQ-PAEs missing the realization would be more difficult and resource consuming. 
         [0140]    The SEQ-PAEs are not built from scratch. Instead such a tile will be built up by a close coupling of a ALU-PAE  1902  and neighboring RAM-PAE  1900 , which can be seen in  FIG. 19  now. 
         [0141]    Therefore the functionality of the ALU—as well as RAM-PAE has to be enhanced to be able to fulfill the requirements of such a SEQ-PAE. This information will be given next. 
       ALU-PAE Enhancements 
       [0142]    The extended version of the ALU-PAE is given in  FIG. 20  now. To the right border the registers which are controlling the different modules can be seen. Those registers will be used in normal—as well as in SEQ-mode. Therefore the appropriate control signals from the local configuration manager and the RAM-PAE are first merged by OR-Gates and then are forwarded to the register whereas it has to be ensured that in normal mode the signals from the RAM-PAE are 0 and vice versa. 
         [0143]    Furthermore, since the ALU-PAE marks the execution part of the tiny processor, there is a need to transfer values to and from the internal register directly to the RAM. Therefore, an additional multiplexer AM1  2000  is inserted in the multiplexer hierarch of section 2. In the normal mode this multiplexer feeds the word from its predecessor to the next stage whereas in the SEQ mode an immediate value provided by the Imm. Register will be delivered. In addition in SEQ mode a value of one of the internal registers can be delivered to the RAM-PAE via the output of the multiplexer. However, it has also to be considered to provide a “LOAD reg, imm” since this is not much slower than “ADD reg, reg, imm” 
         [0144]    To enable the RAM-PAE to write data to the internal register of the ALU-PAE another multiplexer is inserted in the multiplexer chain of section 4. Similar to the scenario given above this multiplexer will only be activated in SEQ mode whereas in normal mode this multiplexer will just forward the data of its predecessor. In one preferred embodiment, it is suggested to place RS2 behind BSFT-Mux in view of the delay. Data could be written into the internal registers via this. (LOAD reg, imm)] 
         [0145]    As it has already been discussed, data can be processed during one or two cycles by the ALU-PAE depending on the selected arithmetic function. Due to the auto synchronization feature of the XPP and due to the fact that in normal mode a successive operation will not start before the previous one is finished, it does not really care if an operation lasts one or two clock cycles. Whereas the tile is working in SEQ mode there is a difference since we assume to have a pipeline character. This means that a one cycle operation could run in parallel with a two cycle module where the operation would be executed in stage two at this time. Due to the limited multiplexing capacities of a word—16 Bit—only one result could be written to the connected registers whereas the other one would be lost. In general there are three possibilities to solve this problem. 
         [0146]    The first one could be that the compiler is capable to handle this problem. This would mean that it has to know about the pipeline structure of the whole SEQ-PAE as well as of a tile in detail. To prohibit a parallel execution the compile would have to add a NOP to every two cycle instruction for the structure given above. However this idea seems not to be convenient due to the strong relation between the hardware structure and the compiler. The drawback would be that every time changes are made to the hardware the compile would most likely have to be trimmed to the new structure. 
         [0147]    The second idea could be to recognize such a situation in the decode stage of the pipeline. If a two cycle instruction is directly followed by an instruction accessing a one stage arithmetic unit it has to be delayed by one clock cycle as well. 
         [0148]    The last possibility is to make the complete ALU-PAE look like a two stage execution unit. Therefore only one register has to be included in the multiplexer chain of section four right after the crossover from the multiplexer separating the one stage of the two stage modules. Obviously, this is preferred. 
         [0149]    Comparing the last to ideas the third one seems to be the best one since only one register has to be inserted If we a closer look to the second solution special logic would be needed for analyzing the disallowed combination of instructions as well as logic for stopping the program counter (PC) and the instruction retardation. It has to be assumed that this logic would require much more area than the registers as well as the fact that the delay of the logic would possibly increase the critical path. 
         [0150]    Since it has to be distinguished between the SEQ and the normal mode where a one cycle execution should still be available. This possibility is given by a multiplexer which allows bypassing the RS2 Register as shown in the corresponding figure ( FIG. 20  now). 
       the RAM-PAE A Short Description of the Stages 
       [0151]    To get the SEQ-PAE working there still has to be provided more functionality. Right now the RAM-PAE  2100  will take care of it. As a first approach for realizing the sequencer a four stage pipeline has been chosen. The stages are, as it can be seen in  FIG. 21  now:
       The fetch stage  2102     The decode stage  2104     The execution stage 1  2106     The execution stage 2  2108         
 
         [0156]    In the fetch stage the program counter for the next clock cycle will be calculated. This means that it will be either incremented by 1 via a local adder or one of the program counters from the decode or execution stage 2 will be selected. The program counter of the execution stage thereby provides the address if a call instruction occurred whereas the program counter of the execution stage provides the PC if there has been a conditional jump. Right now the branch address can either be calculated out of the current PC and a value which either is an immediate value or a value from internal registers of the ALU-RAM—indirect addressing mode—or an absolute value. This e.g. is necessary if there is return from a subroutine to the previous context whereas the according absolute PC will be provided by the stack bank. 
         [0157]    In the decode stage the instruction coming from the code bank will be decoded. Necessary control signals and, if needed, the immediate value, for the internal execution stage 1 as well as for the execution stage 1 of the ALU-PAE will be generated. The signals include the control information for the multiplexers and gating stages of section two of the ALU-PAE, the operation selection of the ALU&#39;s tiles, e.g. signed or unsigned multiplication, and the information whether the stack pointer (SP) should be in/decremented or kept unchanged in the next stage depending on the fact if the instruction is either a call or jump. In case a call instruction occurred a new PC will be calculated in parallel and delivered to the fetch stage. 
         [0158]    Furthermore the read address and read enable signal to the data bank will be generated in case of a load instruction. In the execution stage 1, which by the way is the first stage available on the ALU as well as on the RAM-PAE, the control signals for execution stage 2 of the ALU-PAE are generated. Those signals will take care that the correct output of one of the arithmetical tiles will be selected and written to the enabled registers. If the instruction should be a conditional jump or return the stack pointer will be modified in this stage. In parallel the actual PC will be saved to the stack bank at the address give by the Rsp EX1 register in case of a branch. Otherwise, in case of a return, the read address as well as the read enable signal will be applied to the stack bank. 
         [0159]    In execution stage 2 the value of the PC will be calculated and provided to the multiplexer in the fetch stage in case of a jump. At the time write address and write enable signal to the data bank are generated if data from the ALU have to be saved. 
         [0160]    Instead of two adders, it is possible to provide only one in the rpp path. 
       Pipeline Actions 
       [0161]    In the following section a short overview of the actions that are taking place in the four stages will be given for some basic instructions. It should help to understand the behaviour of the pipeline. Since the instruction which is going to be discussed will be available at the instruction register the actins of the fetch stage will be omitted in this representation. 
       IR: Instruction Register DR: Data Register DB: Data Bank SBR: Store/Branch Register 
       [0162]    Instruction: Load Value from Data Bank to R[n] 
         [0000]                                                                                                                    ALU-PAE   RAM-PAE                                        decode stage                    IR_ex1 &lt;- IR_ex2                Control Registerset EXS1 &lt;- 0 × 0               Imm. EXS1 &lt;- 0 × 0               Rpp_ex1 &lt;- Rpp_de               DB_radr &lt;0 imm                Execution stage 1                    IR_ex2 &lt;- IR_ex1                Control Registerset EXS2 &lt;- enable R, set               mux section 4               Rpp_ex2 &lt;- Rpp_ex1               DR &lt;- DB_radr [imm]               Rsp_ex2 &lt;- Rsp_ex1                Execution stage 2                R[n] &lt;- DR                            
Instruction: Store Value from R[n] to Data Bank
 
         [0000]    
       
         
               
               
               
             
               
             
               
               
             
               
             
               
               
               
             
               
             
               
               
             
           
               
                   
                   
               
               
                   
                 ALU-PAE 
                 RAM-PAE 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 decode stage 
               
             
          
           
               
                   
                 IR_ex1 &lt;- IR_ex2 
               
               
                   
                 Control Registerset EXS1 &lt;- enable mux 
               
               
                   
                 section 2 
               
               
                   
                 Imm. EXS1 &lt;- 0x0 
               
               
                   
                 Rpp_ex1 &lt;- Rpp_de 
               
             
          
           
               
                 Execution stage 1 
               
             
          
           
               
                   
                 SBR &lt;- R[n] 
                 1R_ex2 &lt;- IR_ex1 
               
               
                   
                   
                 Control Registerset EXS2 &lt;- 0x0 
               
               
                   
                   
                 Rpp_ex2 &lt;- Rpp_ex1 
               
               
                   
                   
                 Rsp_ex2 &lt;- Rsp_ex1 
               
             
          
           
               
                 Execution stage 2 
               
             
          
           
               
                   
                 DB_wradr &lt;- imm 
               
               
                   
                 DB_wrdata &lt;- SBR 
               
               
                   
                   
               
             
          
         
       
     
       1.3 Array Structure 
       [0163]    First advantages over the prior art are obtained by using function folding PAEs. These as well as other PAEs can be improved. 
         [0164]    The XPP-II structure of the PAEs consumes much area for FREG and BREG and their associated bus interfaces. In addition feed backs through the FREGs require the insertion of registers into the feedback path, which result not only in an increased latency but also in a negative impact onto the throughput and performance of the XPP. 
         [0165]    A new PAE structure and arrangement is proposed with the expectation to minimize latency and optimize the bus interconnect structure to achieve an optimized area. 
         [0166]    The XPP-III PAE structure does not include BREGs any more. As a replacement the ALUs are alternating flipped horizontally which leads to improved placement and routing capabilities especially for feedback paths i.e. of loops. 
         [0167]    Each PAE contains now two ALUs and two BP paths  2200 , one from top to bottom and one flipped from bottom to top. 
         [0000]    (see  FIG. 22  now) 
       1.4 Bus Modifications 
       [0168]    Within this chapter optimizations are described which might reduce the required area and the amount of busses. However, those modifications comprise several proposals, since they have to be evaluated based on real algorithms. It is possible to e.g. compose a questionnaire to collect the necessary input from the application programmes. 
       1.4.1 Next Neighbour 
       [0169]    In XPP-II architecture a direct horizontal data path between two PAEs block a vertical data bus. This effect increases the required vertical busses within a XPP and drives cost unnecessarily. Therefore in XPP-III a direct feed path between horizontal PAEs is proposed. 
         [0170]    In addition horizontal busses-of different length are proposed, i.e. next neighbour, crossing 2 PAEs, crossing 4 PAEs. 
       1.4.2 Removal of Registers in Busses 
       [0171]    In XPP-II registers are implemented in the vertical busses which can be switched on by configuration for longer paths. This registers can furthermore be preloaded by configuration which requires a significant amount of silicon area. It is proposed to not implement registers in the busses any more, but to use an enhanced DF or Bypass (PB) part within the PAEs which is able to reroute a path to the same bus using the DF or BP internal registers instead. 
         [0000]    (see  FIG. 23  now) 
         [0172]    Here, it might be to decide how many resources are saved for the busses and how many are needed for the PAEs and/or how often must registers be inserted, are 1 or max. 2 paths enough per PAE (limit is two since DF/BP offers max. 2 inputs) 
         [0000]    1.4.3 Shifting n:1, 1:n Capabilities from Busses to PAEs 
         [0173]    In XPP-II n:1 and 1:n transitions are supported by the busses which require a significant amount of resources i.e. for the sample-and-hold stage of the handshake signals. 
         [0174]    Depending on the size of n two different capabilities are provided with the new PAE structure: 
         [0000]    
       
         
               
               
             
           
               
                   
               
             
             
               
                 n ≦ 2 
                 The required operations are done within the DF path of the 
               
               
                   
                 PAE 
               
               
                 2 ≦ n ≦ 4 
                 The ALU path is required since 4 ports are necessary 
               
               
                 n &gt; 4 
                 Multiple ALUs have to be combined. 
               
               
                   
               
             
          
         
       
     
         [0175]    This method saves a significant amount of static resources in silicon but requires dedicated PAE resources at runtime. 
         [0176]    Here, it might be worthwhile to evaluate how much silicon area is saved per bus how often occurs n=2, 2≦n≦4, n&gt;4 the ratio between saved silicon area and required PAE resource and to decide on the exact bus structure in response to one or all of said criteria. 
       1.5 FSM in RAM-PAEs 
       [0177]    In the XPP-II architecture implementing control structures is very costly, a lot of resources are required and programming is quite difficult. 
         [0178]    However memories can be used for a simple FSMs implementation. The following enhancement of the RAM-PAEs offers a cheap and easy to program solution for many of the known control issues, including HDTV. 
         [0000]    (see  FIG. 24  now) 
         [0179]    Basically the RAM-PAE is enhanced by a feedback from the data output to the address input through a register (FF)  2402  to supply subsequent address within each stage. Furthermore additional address inputs from the PAE array can cause conditional jumps; data output will generate event signals for the PAE array. Associated counters  2404  which can be reloaded and stepped by the memory output generate address input for conditional jumps (i.e. end of line, end of frame of a video picture). 
         [0180]    A typical RAM PAE implementation has about 16-32 data bits but only 8-12 address bits. To optimize the range of input vectors it is therefore suggested to insert some multiplexers at the address inputs to select between multiple vectors, whereas the multiplexers are controlled by some of the output data bits. 
         [0181]    One implementation for an XPP having 24 bit wide data busses is sketched in  FIG. 25  now.  4  event inputs are used as input, as well as the lower for bits of input port Ri0. 3 counters are implemented, 4 events are generated as well as the lower 10 bits of the Ro0 port. 
         [0182]    The memory organisation suggested here may be as follows:
       8 address bits   24 data bits (22 used)
           4 next address   8 multiplexer selectors   6 counter control (shared with 4 additional next address)   4 output   (see  FIG. 25  now)   
               
 
         [0190]    It is to be noted that the typical memory mode of the RAM-PAE is not sketched in the block-diagram mentioned above. 
         [0191]    The width of the counters is according to the bus width of the data busses. 
         [0192]    For a 16 bit implementation it is suggested to use the carry signal of the counters as their own reload signal (auto reload), also some of the multiplexers are not driven by the memory but “hard wired” by the configuration. 
         [0193]    The proposed memory organisation is as follows:
       8 address bits   16 data bits (16 used)
           4 next address   4 multiplexer selectors   3 counter control (shared with 3 additional next address)   4 output   (see  FIG. 26  now)   
               
 
         [0201]    It is to be noted that actually the RAM-PAEs typically will not be scaleable any more since the 16-bit implementation is different from the 24-bit implementation. It is to decide whether the striped down 16-bit implementation is used for 24-bit als 
       1.6 IOAG Interface 1.6.1 Address Generators and Bit Reversal Addressing 
       [0202]    Implemented within the IO interfaces are address generators  2700  to support e.g. 1 to 3 dimensional addressing directly without any ALU-PAE resources. The address generation is then done by 3 counters; each of them has e.g. configurable base address, length and step width. 
         [0203]    The first counter (CNT1) has a step input to be controlled by the array of ALU-PAEs. Its carry is connected to the step input of CNT2, which carry again is connected to the step input of CNT3. 
         [0204]    Each counter generates carry if the value is equal to the configured length. Immediately with carry the counter is reset to its configured base address. 
         [0205]    One input is dedicated for addresses from the array of ALU-PAEs which can be added to the values of the counters. If one or more counters are not used they are configured to be zero. 
         [0206]    In addition CNT1 supports generation of bit reversal addressing by supplying multiple carry modes. 
         [0000]    (see  FIG. 27  now) 
       1.6.2 Support for Different Word Width 
       [0207]    In general it is necessary to support multiple word width within the PAE array. 8 and 16 bit wide data words are preferred for a lot of algorithms i.e. graphics. In addition to the already described SIMD operation, the IOAG allows the split and merge of such smaller data words. 
         [0208]    Since the new PAE structure allows 4 input and 4 output ports, the IOAG can support word splitting and merging as follows: 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 I/O 0 
                 I/O 1 
                 I/O 2 
                 I3 
               
               
                   
               
             
             
               
                 16/24/32-bit data 
                   
                   
                 address 
               
               
                 word 
               
               
                 16-bit data word 
                 16-bit data word 
                   
                 address 
               
               
                  8-bit data word 
                  8-bit data word 
                 8-bit data word 
                 address 
               
               
                   
               
             
          
         
       
     
         [0209]    Input ports are merged within the IOAG for word writes to the JO. 
         [0210]    For output ports the read word is split according to the configured word width. 
       1.7 Multi-Voltage Power Supply and Frequency Stepping 
       [0211]    PAEs and busses are built to perform depending on the workload. Therefore the clock frequency is configurable according to the data bandwidth, in addition clock gating for registers is supported, busses are decoupled using row of AND gates. Dynamically clock pulses are gated, whenever no data can be processed. 
         [0212]    Depending on the clock frequency in the PAEs and the required bandwidth for the busses the voltage is scaled in an advanced architecture. Within the 4S project such methods are evaluated and commercially usable technologies are researched. 
       1.8 XPP/μP Coupling 
       [0213]    For a closed coupling of a μP and a XPP a cache and register interface would be the preferable structure for high level tools like C-compilers. However such a close coupling is expected not to be doable in a very first step. 
         [0214]    Yet, two different kind of couplings may be possible for a tight coupling:
       a) memory coupling for large data streams: The most convenient method with the highest performance is a direct cache coupling, whereas an AMBA based memory coupling will be sufficient for the beginning (to be discussed with ATAIR)   b) register coupling for small data and irregular MAC operations: Preferable is a direct coupling into the processors registers with an implicit synchronisation in the OF-stage of the processor pipeline. However coupling via load/store- or in/out-commands as external registers is acceptable with the penalty of a higher latency which causes some performance limitation.       
 
       2 Specification of ALU-PAE 2.1 Overview 
       [0217]    In a preferred embodiment, the ALU-PAE comprises 3 paths:
       ALU arithmetic, logic and data flow handling   BP bypass       
 
         [0220]    Then, each of the paths contains 2 data busses and 1 event bus. The busses of the DF path can be rerouted to the ALU path by configuration. 
       2.2 ALU Path Registers 
       [0221]    The ALU path comprises 12 data registers:
       Ri0-3 Input data register 0-3 from bus   Rv0-3 Virtual output data register 0-3 to bus   Rd0-3 Internal general purpose register 0-3   Vi0-3 V event input 0-3 from bus   Ui0-3 U event input 0-3 from bus   Ev0-3 Virtual V event output register 0-3 to bus   Eu0-3 Virtual U event output register 0-3 to bus   Fu0-3   Fv0-3 Internal Flag u and v registers according to the XPP-II PAE&#39;s event busses   Acc Accumulator       
 
         [0232]    Eight instruction registers are implemented; each of them is 24 bit wide according to the opcode format.
       Rc0-7 Instruction registers       
 
         [0234]    Three special purpose registers are implemented:
       Rlc Loop Counter, configured by CM, not accessible through ALU-PAE itself.
           Will be decremented according to JL opcode. Is reloaded after value 0 is reached.   
           Rjb Jump-Back register to define the number of used entries in Rc[0 . . . 7]. It is not accessible through ALU-PAE itself.
           If Rpp is equal to Rjb, Rpp is immediately reset to 0. The jump back can be bound to a condition i.e. an incoming event. If the condition is missing, the jump back will be delayed.   
           Rpp Program pointer       
 
       2.3 Data Duplication and Multiple Input Reads 
       [0240]    Since Function Folding can operate in a purely data stream mode as well as in a sequential mode (see 1.2) it is useful to support Ri reads in dataflow mode (single read only) and sequential mode (multiple read). The according protocols are described below: 
         [0241]    Each input register Ri can be configured to work in one of two different modes: 
       Dataflow Mode 
       [0242]    This is the standard protocol of the XPP-II implementation: 
         [0243]    A data packet is taken read from the bus if the register is empty, an ACK handshake is generated. If the register is not empty ACK the data is not latched and ACK is not generated. If the register contains data, it can be read once. Immediately with the read access the register is marked as empty. An empty register cannot be read. 
         [0244]    Simplified the protocol is defined as follows: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 RDY &amp; empty 
                 → full 
               
               
                   
                   
                 → ACK 
               
               
                   
                 RDY &amp; full 
                 → notACK 
               
               
                   
                 READ &amp; empty 
                 → stall 
               
               
                   
                 READ &amp; full 
                 → read data 
               
               
                   
                   
                 → empty 
               
               
                   
                   
               
             
          
         
       
     
         [0245]    Please note: pipeline effects are not taken into account in this description and protocol. 
       Sequencer Mode 
       [0246]    The input interface is according to the bus protocol definition: A data packet is taken read from the bus if the register is empty, an ACK handshake is generated. If the register is not empty ACK the data is not latched and ACK is not generated. 
         [0247]    If the register contains data it can be read multiple times during a sequence. A sequence is defined from Rpp=0 to Rpp=Rjb. During this time no new data can be written into the register. Simultaneously with the reset of Rpp to 0 the register content is cleared an new data is accepted from the bus. 
         [0248]    Simplified the protocol is defined as follows: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 RDY &amp; empty 
                 → full 
               
               
                   
                   
                 → ACK 
               
               
                   
                 RDY &amp; full 
                 → notACK 
               
               
                   
                 READ &amp; empty 
                 → stall 
               
               
                   
                 READ &amp; full 
                 → read data 
               
               
                   
                 (Rpp == Rjb) 
                 → empty 
               
               
                   
                   
               
             
          
         
       
     
         [0249]    Please note: pipeline effects are not taken into account in this description and protocol. 
       2.4 Data Register and Event Handling 
       [0250]    Data registers are directly addressed, each data register can be, individually selected. Three address opcode form is used, r t ←r s1 , r s0 . An virtual output register is selected by adding ‘o’ behind the register. The result will be stored in r t  and copied to the virtual output register r v  as well according to the rule op out (r v , r t )←r s1 , r s0 . 
         [0251]    Please note, accessing input and (virtual) output registers follow the rules defined in chapter 2.3. 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Source 
                 r t   
                 Notation 
               
               
                   
                   
               
             
             
               
                   
                 000 
                 0 
                 Rd0 
               
               
                   
                 001 
                 1 
                 Rd1 
               
               
                   
                 010 
                 2 
                 Rd2 
               
               
                   
                 011 
                 3 
                 Rd3 
               
               
                   
                 100 
                 0 
                 Ri0 
               
               
                   
                 101 
                 1 
                 Ri1 
               
               
                   
                 110 
                 2 
                 Ri2 
               
               
                   
                 111 
                 3 
                 Ri3 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 Target 
                 r t   
                 r v   
                 Notation 
               
               
                   
               
             
             
               
                 000 
                 0 
                 — 
                 Rd0 
               
               
                 001 
                 1 
                 — 
                 Rd1 
               
               
                 010 
                 2 
                 — 
                 Rd2 
               
               
                 011 
                 3 
                 — 
                 Rd3 
               
               
                 100 
                 0 
                 0 
                 Ro0 
               
               
                 101 
                 1 
                 1 
                 Ro1 
               
               
                 110 
                 2 
                 2 
                 Ro2 
               
               
                 111 
                 3 
                 3 
                 Ro3 
               
               
                   
               
             
          
         
       
     
         [0252]    Events are used equal to data registers. All input and internal events can be addressed directly, output events are used whenever an ‘o’ is added behind the event. 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 Etp 
                 ep t   
                 ep v   
                 Notation 
               
               
                   
               
             
             
               
                 000 
                 0 
                 — 
                 Fu0, Fv0 
               
               
                 001 
                 1 
                 — 
                 Fu1, Fv1 
               
               
                 010 
                 2 
                 — 
                 Fu2, Fv2 
               
               
                 011 
                 3 
                 — 
                 Fu3, Fv3 
               
               
                 100 
                 0 
                 0 
                 Eou0, Eov0 
               
               
                 101 
                 1 
                 1 
                 Eou1, Eov1 
               
               
                 110 
                 2 
                 2 
                 Eou2, Eov2 
               
               
                 111 
                 3 
                 3 
                 Eou3, Eov3 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 Es4/et4 
                 e t   
                 e v   
                 Notation 
               
               
                   
               
             
             
               
                 0000 
                 0 
                 — 
                 v0 
               
               
                 0001 
                 1 
                 — 
                 v1 
               
               
                 0010 
                 2 
                 — 
                 v2 
               
               
                 0011 
                 3 
                 — 
                 v3 
               
               
                 0100 
                 0 
                 0 
                 vo0 
               
               
                 0101 
                 1 
                 1 
                 vo1 
               
               
                 0110 
                 2 
                 2 
                 vo2 
               
               
                 0111 
                 3 
                 3 
                 vo3 
               
               
                 1000 
                 0 
                 — 
                 u0 
               
               
                 1001 
                 1 
                 — 
                 u1 
               
               
                 1010 
                 2 
                 — 
                 u2 
               
               
                 1011 
                 3 
                 — 
                 u3 
               
               
                 1100 
                 0 
                 0 
                 uo0 
               
               
                 1101 
                 1 
                 1 
                 uo1 
               
               
                 1110 
                 2 
                 2 
                 uo2 
               
               
                 1111 
                 3 
                 3 
                 uo3 
               
               
                   
               
             
          
         
       
     
       2.4.1. ACCumulator Mode 
       [0253]    To achieve low power consumption and for better supporting DSP-like algorithms an accumulator register is available which can be addressed by just one set bit for the result register (ao) and operand register (ai). 
         [0254]    For commutative operations always operand register 1 is replaced by ai. For non commutative operations as SUBtract operand register 1 selects, whether ai is the first or second operand. register 2 defines the accordingly other operand. 
         [0255]    It is to be noted that it has to be clarified whether a real ACCumulator mode makes sense or just a MAC-command should be implemented to handle the multiply accumulate in a single command consuming two clock cycles with an implicit hidden accumulator access. 
       2.4.2. Parameter Stack Mode (PSTACK) 
       [0256]    Unused entries in the Opcode Registers Rc can operate as stack for constants and parameters. At Rpp==0000 the Rps PStack registers points to Rjb+1, which means the PStack area starts immediately behind the last entry in the Opcode register file. 
         [0257]    To access the PStack, the FF-PAE must be in the Fast-Parameter Mode. Each read access to Ri3 is redirected to read from the PStack, whereas after each read access the pointer incremented with one. There is no check for an overflow of the PStack pointer implemented; an overflow is regarded as a program bug. 
         [0000]    (see  FIG. 28  now) 
       2.4.3 n:1 Transitions 
       [0258]    n:1 transitions are not supported within the busses any more. Alternatively simple writes to multiple output registers Ro and event outputs Eo are supported. The Virtual Output registers (Rv) and Virtual Event (Ev) are translated to real Output registers (Ro) and real Events (Eo), whereas a virtual register can be mapped to multiple output registers. 
         [0259]    To achieve this a configurable translation table is implemented for both data registers and event registers: 
         [0000]    
       
         
               
               
               
               
               
             
               
               
             
           
               
                   
               
               
                 Rv 
                 Ro0 
                 Ro1 
                 Ro2 
                 Ro3 
               
               
                 Ev 
                 Eo0 
                 Eo1 
                 Eo2 
                 Eo3 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 0 
                   
               
               
                 1 
               
               
                 2 
               
               
                 3 
               
               
                   
               
             
          
         
       
     
       EXAMPLE 
       [0260]    Rv0 mapped to Ro0, Ro1
 
Rv1 mapped to Ro2
 
Rv2 mapped to Ro3
 
Rv3 unused
 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
               
               
                 Rv 
                 Ro0 
                 Ro1 
                 Ro2 
                 Ro3 
               
               
                   
               
             
             
               
                 0 
                 1 
                 1 
                 0 
                 0 
               
               
                 1 
                 0 
                 0 
                 1 
                 0 
               
               
                 2 
                 0 
                 0 
                 0 
                 1 
               
               
                 3 
                 0 
                 0 
                 0 
                 0 
               
               
                   
               
             
          
         
       
     
       2.4.4 Accessing Input and Output Registers (Ri/Rv) and Events (Ei/Ev) 
       [0261]    Independently from the opcode accessing input or output registers or events is defined as follows: 
       Reading an Input Register: 
       [0262]      
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Register 
                   
               
               
                   
                 status 
                 Operation 
               
               
                   
                   
               
             
             
               
                   
                 empty 
                 Wait for data 
               
               
                   
                 full 
                 Read data and continue operation 
               
               
                   
                   
               
             
          
         
       
     
       Writing to an Output Register: 
       [0263]      
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Register 
                   
               
               
                   
                 status 
                 Operation 
               
               
                   
                   
               
             
             
               
                   
                 empty 
                 Write data to register 
               
               
                   
                 full 
                 Wait until register is cleared and can accept new data 
               
               
                   
                   
               
             
          
         
       
     
       2.4.5. Multi-Config Mode 
       [0264]    The Multi-Config Mode allows for selecting 1 out of maximum 4 stored configurations. Incoming events on Fui0,1 and Fvi0,1 select one of the 4 configurations. Only one Event shall be active at a clock cycle. 
         [0265]    The selection is done by a simple translation, each event points to a specific memory address. 
         [0000]    (see  FIG. 29  now) 
         [0266]    Long configurations may use more than 3 opcode by using the next code segments as well. In this case, the according events can not be used. 
         [0000]    (see  FIG. 30  now) 
       2.5 Opcode Format 
       [0267]    24 bit wide 3 address opcodes are used in a preferred embodiment: 
         [0000]      op r t ←r a , r b  
 
         [0268]    Source registers can be Ri and Rd, target registers are Rv and Rd. A typical operation targets only Rd registers. If the source register for r a  is Ri[x] the target register will be Rd[x]. 
         [0269]    The translation is shown is the following table: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Target 
                 Source r a   
               
               
                   
                   
               
             
             
               
                   
                 Rd0 
                 Rd0 
               
               
                   
                 Rd1 
                 Rd1 
               
               
                   
                 Rd2 
                 Rd2 
               
               
                   
                 Rd3 
                 Rd3 
               
               
                   
                 Rd0 
                 Ri0 
               
               
                   
                 Rd1 
                 Ri1 
               
               
                   
                 Rd2 
                 Ri2 
               
               
                   
                 Rd3 
                 Ri3 
               
               
                   
                   
               
             
          
         
       
     
         [0270]    Each operation can target a Virtual Output Register Rv by adding an out tag ‘o’ as a target identifier to the opcode: 
         [0000]      op(r t , ro t )←r a , r b  
 
         [0271]    Data is transferred to the virtual output register and to the according internal register as well: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Rv 
                 Rd 
               
               
                   
                   
               
             
             
               
                   
                 Rv0 
                 Rd0 
               
               
                   
                 Rv1 
                 Rd1 
               
               
                   
                 Rv2 
                 Rd2 
               
               
                   
                 Rv3 
                 Rd3 
               
               
                   
                   
               
             
          
         
       
     
       2.5.1 Conditional Execution 
       [0272]    The SKIPE command supports conditional execution. Either an event or ALU flag is tested for a specific value. Depending on the check either the next two addresses are executed (Rpp+1) or skipped (Rpp+3). If an incoming event is checked, the program execution stops until the event is arrived at the event port (RDY handshake set). 
         [0273]    SKIPE supports conditional execution of any OpCode which is not larger than two memory entries. 
         [0274]    In SEQ-PAEs, which support CALL and RET OpCodes, also stack based subroutine calls are supported. 
       2.6 Clock 
       [0275]    The PAE can operate at a configurable clock frequency of
       1×Bus Clock   2×Bus Clock   4×Bus Clock
           [8×Bus Clock]   
               
 
       2.7 The DF Path 
       [0280]    The DataFlow path comprises the data registers Bri0 . . . 3 and Bro0 . . . 3 as well as the event register Bui/Bvi0 . . . 3 and Buo/Bvo0 . . . 3. 
         [0281]    The main purpose of the DF path is to establish bus connections in the vertical direction. In addition the path includes a  4  stage FIFO for each of the data and event paths. 
         [0282]    The DF path supports numerous instructions, whereas the instruction is selected by configuration and only one of them can be performed during a configuration, function folding is not available. 
         [0283]    The following instructions are implemented in the DF path:
       1. ADD, SUB   2. NOT, AND, OR, XOR   3. SHL, SHR, DSHL, DSHR, DSHRU   4. EQ, CMP, CMPU   5. MERGE, DEMUX, SWAP   6. SORT, SORTU   7. ELUT       
 
       2.9 Parameter Broadcast and Update 
       [0291]    Parameters and constants can be updated fast and synchronous using input register Ri3 and event input Ei7. 
         [0000]    (see  FIG. 31  now) 
         [0292]    Depending on the update mode, data packets at the input register Ri3 are copied subsequently into Rd3, Rd2 and Rd1 at each access of the according register by the PAE, if the event Ei7 is set. Afterwards all input data at Ri3 is propagated to the output register Ro3, also the Eo7 event output is set, to indicate following PAEs the occurrence of a fast parameter update, which allows to chain PAEs, together (i.e. in a multi-TAP FIR filter) and updating all parameters in the chain. 
         [0000]    
       
         
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                   
                   
                 UPM1 
                 UPM2 
                 UPM3 
               
               
                   
                 Register 
                   
                 Upmcfg = 
                 upmcfg = 
                 upmcfg = 
               
               
                   
                 access 
                 Ei7 
                 0100 
                 1000 
                 1100 
               
               
                   
                   
               
             
             
               
                   
                 — 
                 0 
                 — 
                 — 
                 — 
               
               
                   
                 read Rd3 
                 1 
                 Ri3 -&gt; Rd3 
                 Ri3 -&gt; Rd3 
                 Ri3 -&gt; Rd3 
               
               
                   
                 read Rd2 
                 1 
                 Ri3 -&gt; Ro3 
                 Ri3 -&gt; Rd2 
                 Ri3 -&gt; Rd2 
               
               
                   
                   
                   
                 1 -&gt; Eo7 
               
               
                   
                 read 
                 1 
                 Ri3 -&gt; Ro3 
                 Ri3 -&gt; Ro3 
                 Ri3 -&gt; Rd1 
               
               
                   
                 Rd1 
                   
                 1 -&gt; Eo7 
                 1 -&gt; Eo7 
               
               
                   
                 — 
                 1 
                 Ri3 -&gt; Ro3 
                 Ri3 -&gt; Ro3 
                 Ri3 -&gt; Ro3 
               
               
                   
                   
                   
                 1 -&gt; Eo7 
                 1 -&gt; Eo7 
                 1 -&gt; Eo7 
               
               
                   
                   
               
             
          
         
       
     
         [0293]    Also the OpCode UPDATE updates all registers subsequently if Ei7 is set, depending on the Update Parameter Mode (upmcfg=nn10). 
         [0294]    Also the register update can be configured to occur whenever Rpp==0 and Ei7 is set by upmcfg=nn01. 
         [0295]    In both cases nn indicates the number of registers to be updated (1-3). 
         [0296]    Ei7 must be 0 for at least one clock cycle to indicate the end of a running parameter update and the start of a new update. 
       3 Input Output Address Generators (IOAG) 
       [0297]    The IOAGs are located in the RAM-PAEs and share the same registers to the busses. An IOAG comprises 3 counters with forwarded carries. The values of the counters and an immediate address input from the array are added to generate the address. One counter offers reverse carry capabilities. 
       3.1 Addressing Modes 
       [0298]    Several addressing modes are supported by the IOAG to support typical DSP-like addressing: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Mode 
                 Description 
               
               
                   
                   
               
             
             
               
                   
                 Immediate 
                 Address generated by the PAE array 
               
               
                   
                 xD counting 
                 Multidimensional addressing using IOAG 
               
               
                   
                   
                 internal counters xD means 1D, 2D, 3D 
               
               
                   
                 xD circular 
                 Multidimensional addressing using IOAG 
               
               
                   
                   
                 internal counters, after overflow counters- 
               
               
                   
                   
                 reload with base address 
               
               
                   
                 xD plus immediate 
                 xD plus a value from the PAE array 
               
               
                   
                 Stack 
                 decrement after “push” operations 
               
               
                   
                   
                 increment after “read” operations 
               
               
                   
                 Reverse carry 
                 Reverse carry for applications such as FFT 
               
               
                   
                   
               
             
          
         
       
     
       3.1.1 Immediate Addressing 
       [0299]    The address is generated in the array and directly fed through the adder to the address output. All counters are disabled and set to 0. 
       3.1.2 xD Counting 
       [0300]    Counters are enabled depending on the required dimension (x-dimensions require x counters). For each counter a base address and the step width as well as the maximum address are configured. Each carry is forwarded to the next higher and enabled counter; after carry the counter is reloaded with the start address. 
         [0301]    A carry at the highest enabled counter generates an event, counting stops. 
       3.1.3 xD Circular 
       [0302]    The operation is exactly the same as for xD counting, with the difference that a carry at the highest enabled counter generates an event, all counters are reloaded to their base address and continue counting. 
       3.1.4 Stack 
       [0303]    One counter (CNT1) is used to decrement after data writes and increment after data reads. The base value of the counter can either be configured (base address) or loaded by the PAE array. 
       3.1.5 Reverse Carry 
       [0304]    Typically carry is forwarded from LSB to MSB. Forwarding the carry to the opposite direction (reverse carry) allows generating address patterns which are very well suited for applications like FFT and the like. The carry is discarded at MSB. 
         [0305]    For using reverse carry a value larger than LSB must be added to the actual value to count, wherefore the STEP register is used. 
       Example 
     Base=0h 
     Step=1000b 
       [0306]      
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Step 
                 Counter Value 
               
               
                   
                   
               
             
             
               
                   
                 1 
                 B0 . . . 00000 
               
               
                   
                 2 
                 B0 . . . 01000 
               
               
                   
                 3 
                 B0 . . . 00100 
               
               
                   
                 4 
                 B0 . . . 01100 
               
               
                   
                 5 
                 B0 . . . 00010 
               
               
                   
                 . . . 
                 . . . 
               
               
                   
                 16  
                 B0 . . . 01111 
               
               
                   
                 17  
                 B0 . . . 00000 
               
               
                   
                   
               
             
          
         
       
     
         [0307]    The counter is implemented to allow reverse carry at least for STEP values of −2, −1, +1, +2. 
       4. ALU/RAM Sequencers—SEQ-PAEs 
       [0308]    Each ALU-PAE at the left or right edge of the array can be closely coupled to the neighbouring RAM-PAEs as an IP option, thus allowing for configure a sequencer. For compatibility reasons, the data and opcode width of the sequencer is 16 bits. 
         [0000]    (see  FIG. 19  now) 
         [0309]    The ALU-PAEs can operate exactly as array internal ALU-PAEs but have several extensions. Operation is Sequencer mode the register file is 8 data registers wide, Fu and Fv flags are, used as carry, sign, null, overflow and parity ALU flag word  112 . 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Event 
                 Processor 
               
               
                   
                 Registers 
                 Registers 
               
               
                   
                 FF-Mode 
                 SEQ-Mode 
               
               
                   
                   
               
             
             
               
                   
                 Fu0 
                 carry 
               
               
                   
                 Fu1 
                 sign 
               
               
                   
                 Fu2 
                 null 
               
               
                   
                 Fu3 
                 overflow 
               
               
                   
                 Fv0 
                 parity 
               
               
                   
                   
               
             
          
         
       
     
         [0310]    The address width is accordingly 16 bit. However since the RAM-PAE size is limited it is segmented into 16 segments. Those segments are used for code, data and stack  3300  and must be individually preloaded by the compiler. 
       4 Segment Registers Point to the Specific Segments: 
       [0311]      
         [0000]                                                CodeBank   Points to the actual code segment           DataBank   Points to the actual data segment           StackBank   Points to the actual stack segment           AuxiliaryBank   Points to any Segment (but code),               allowing copy operations between               segments                        
(see  FIG. 32  now)
 
         [0312]    The compiler has to take care that necessary data segments are preloaded and available. For cost reasons there is no automatic TLB installed. 
         [0313]    Also segments have to be physically direct addressed due to the absence of TLBs. This means that the compiler has to implement range checking functions for according addresses. 
         [0314]    Code segments behave accordingly to data segments. The compiler has to preload them before execution jumps into them. Also jumps are physically direct addressed, due to the absence of TLBs again. 
         [0315]    A relocation of any segments is not possible; the mapping is fixed by the compiler. 
         [0316]    The memory layout is shown in  FIG. 33  now. A simple check mechanism is implemented to validate or invalidate memory segments. 
         [0317]    At least the CodeBank (CB) and StackBank (SB) must be set. The first CodeBank must start at location 0000 h. For all other banks 0000 h is an illegal entry. Loading segments to the memory validates them, accordingly flushing invalidates them. 
         [0318]    Memory banks  3500  are updates in terms of loaded or flushed in the background by a DMA engine controlled by the following opcodes 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 LOADDSEG 
                 Loads and validates a data/auxiliary/stack 
               
               
                   
                   
                 bank 
               
               
                   
                 STOREDSEG 
                 Stores and invalidates a data/auxiliary/stack 
               
               
                   
                   
                 bank 
               
               
                   
                 LOADCSEG 
                 Loads and validates a code bank 
               
               
                   
                   
               
             
          
         
       
     
         [0319]    The address generators  3502  in the IOAG interfaces can be reused as DMA engine. 
         [0320]    Memory Banks can be Specifically Validated or Invalidated as Follows: 
         [0000]    
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 VALIDATESSEG 
                 Validates a bank 
               
               
                   
                 INVALIDATESEG 
                 Invalidates a bank 
               
               
                   
                   
               
             
          
         
       
     
         [0321]    The bank pointers are added to the address of any memory access. Since the address pointer can be larger than the 6 bits addressing a 64 line range, segment boarders are not “sharp”, which means, can be crossed without any limitation. However the programmer or compiler has to take care that no damage occurs while crossing them. If an invalid segment is reached a flag or trap is generated indicating the fault, eventually just wait states are inserted if a segment preload is running already in the background. 
         [0000]    (see  FIG. 34  now) 
         [0322]    Alternatively a more advanced valid checking scheme can be implemented as shown in  FIG. 35  now. 
         [0323]    In difference to PAEs which require 24-bit instructions sequencers use 16-bit instructions only. To use the same instruction set and to keep the decoders simple, just the last 8 bits are discarded in sequencer mode. 
       4.1 IOAGs 
       [0324]    IOAGs may comprise a 4-8 stage data output buffer to balance external latency and allow reading the same data address directly after the data has been written, regardless of external bus or memory latencies (up to the number of buffer stages). 
         [0325]    In the following, a number of OpCodes and their meanings is suggested: 
         [0326]    In the following, an example for the use of function folding is given: 
         [0327]    Function Folding and Fast Parameter Update Example FIR Ri0=x Ri1=y 
       3-Folded FIR Using Acc 
     Fast Parameter Update for Registers Rd1, Rd2, Rd3 
     Example 1 
     UPM3, Updates Parameters with Each Access to Rd3, 2, 1 (if Ei7 is Set) 
       [0328]    upmcfg=1100
 
# stage 1
       mul acc, Ri0, Rd3;   add Rd0, acc, Ri1;
 
# stage 2
   mul acc, Ri0, Rd2;   add Rd0, acc, Rd0;
 
# stage 3
   mul acc, Ri0, Rd1;   add Ro1, acc, Rd3;   write Ro0, Ri0;       
 
         [0336]    Alternative using MAC opcode, parameter pop and looping
       read Rd0, Ri1;
 
1 h, 1 t[3]: mac Rd0, Ri0, pop;
   write Ro1, Rd0;   write Ro0, Ri0;       
 
       Example 2 
     UPM3, Uses Command UPDATE for Parameter Update 
       [0340]    upmcfg=1110
 
# stage 1
       mul acc, Ri0, Rd3;   add Rd0, acc, Ri1;
 
# stage 2
   mul acc, Ri0, Rd2;   add Rd0, acc, Rd0;
 
# stage 3
   mul acc, Ri0, Rd1;   add Ro1, acc, Rd3;   write Ro0, Ri0;   update 3       
 
       Example 3 
     UPM3, Updates Parameters at Rpp==0 
       [0349]    upmcfg=1101
 
# stage 1
       mul acc, Ri0, Rd3;   add Rd0, acc, Ri1;
 
# stage 2
   mul acc, Ri0, Rd2;   add Rd0, acc, Rd0;
 
# stage 3
   mul acc, Ri0, Rd1;   add Ro1, acc, Rd3;   write Ro0, Ri0;       
 
         [0357]    In the above, an improved data processor array has been described. Although only in some instances, it has been pointed out that reference to a certain number of registers, bit width etc. is for explanation only, it is to be understood that this also holds where such reference is not found. 
         [0358]    If the array is to be very large or in case a real time process is run where two different fragments of an array unknown at compile time have to communicate with each other so as to enable data processing, it is advantageous to improve the performance by ensuring that a communication path can be set up. Several suggestions have been made already, e.g. Lee-Routing and/or the method described in PACT  7 . It is to be understood that the following part of an improved array design might result in an improved circuitry for certain applications but that it is not deemed absolutely and inevitably necessary to implement it with e.g. a function fold PAE. Rather, the other suggestions for improvement will result in significant improvements on their own as will be understood by the average skilled person. 
       Routing Improvement 
       [0359]    The suggested improvement described hereinafter concerns the static routing network for reconfigurable array architectures. Hereby this static network is enhanced by implementing additional logic to adaptive runtime routing. 
         [0360]      FIG. 1  depicts a cut-out of a reconfigurable array with a set of functional units (FU). Each functional unit encloses one routing unit (RU) and additional functional modules (FMs). The enclosed functional modules are used to manipulate data and characterize the type of the FU. The RU contains an interconnect matrix which is able to route each input port to any desirable output ports. All FUs are connected through point-to-point links whereas each is composed of two half-duplex links and able to transport the data in both directions at the same time. 
         [0361]    The routing technique described in this document is instruction based which means that each routing process must be started by an instruction. If the user wants to establish a routing between two cells, he has to bring a specific instruction into the source cell. The hardware within the array calculates based on the instruction fields values the desired routing direction and establishes the logic stream. The routing process happens stepwise from one functional unit to another whereby each cell decides which direction should be taken next. On the way to an established route we defined three valuable states of the routing resources. The first state is the physical route or link. This means that the resources of this route are not used and available to routing processes. The second state is named temporal route or link. This state describes the temporarily not available link, which means that this link is in use for routing purposes but the mentioned routing is not confirmed yet. The problem here is that this route can be confirmed in the future or released if the successor cells are able to realise the desired routing. The last state is the logical route or link. This state represents an established route on the array which is able to transport calculation data. 
         [0362]    This routing technique uses coordinates on the array to calculation routings. Each FU possesses unique coordinate&#39;s and on the basis of this information it is able to determine the routing direction to each desired cell Within the array. This concept is the basis for the adaptive runtime routing described in this document. The needed control logic for adaptive routing is implemented within the routing unit, especially within the routing controller which controls the interconnect matrix at runtime. Therefore the routing controller is able to analyze the incoming data of all input ports of the concerned FU and come to a decision what to do next. 
       Routing Establishment 
       [0363]    For the purpose of incoming data analyzing and data buffering each input port owns so called in-registers (InReg). Additional to those standard registers there are InReg-controllers implemented (InRegCtrl). Those finite state machines (FSMs) have the job to store the actual state of the input links and in dependency of the actual state to trigger routing requests or release not required routings. To fulfill its job each InRegCtrl is connected to an in-controller (InCtrl) which is implemented exactly once per FU. Important requirement for requesting of new routings is that the mentioned input resource (InReg, InRegCtrl) are not used and so in the state of physical link. 
         [0364]    InCtrl gets requests of all InRegCtrls all over the time and forwards one request after another to the routing controller (RoutCtrl). The selection which InRegCtrl should be served first is dependant on the routing priority of the input link and/or which input link was served last. Based on the coordinate information of the target cell and the coordinates of the actual FU the RoutCtrl calculates the forward direction for the requested input link. Thereby the RoutCtrl takes into account additional parameters like optimum bit (will be described later), the network utilisation towards the desired direction, etc. 
         [0365]    If the direction calculation within the RoutCtrl was successful the RoutCtrl forwards the request with additional information about the output port to the interconnect matrix, which connects the input port with calculated output port. If this is done the RoutCtrl signals the successful routing operation to InCtrl. Because the actual reached routing state is not final it is necessary to store the actual state. This happens within the queue-request-registerfile (QueueRRF). Therefore the InCtrl is directly connected to the QueueRRF and is able to store the desired information. At this point the related input and output links reach the temporal link state and are temporarily not available for other routing processes. 
         [0366]    Due the fact that the QueueRRF is able to store more than one routing entry, the InCtrl is able to hold multiple routing processes at the same time. But for the purpose of high hardware area consumption the direction calculation is realized once within the RoutCtrl. 
         [0367]    The established temporal routing stays stored within the QueueRRF till the point the successor cell acknowledges the routing. In this case the InCtrl clear the according entry in the QueueRRF and signals the successful routing to the InCtrl. The InRegCtrl changes into the state logical route and signal the predecessor cell the successfully finished routing process. 
         [0368]    The other case can happen if the successor cell is not able to establish the desired route. In this case the InCtrl forwards a new request to the RoutCtrl based on the QueueRRF-entry. This request leads to new routing suggestion which will be stored within the QueueRRF. 
         [0369]    If all available and expedient directions are checked and routing trials failed the InCtrl signals to InRegCtrl the failed routing. The InCtrl signals the same routing miss to the predecessor cell and finishes the routing process in the current cell. 
         [0370]    Within the routing process there are two exceptions how the routing unit establishes a desired routing. Those exceptions affect the source and the target cell. The exception in both cases is that as well the source cell as the target cell do not need to route the started/ending routing through the interconnect matrix. To connect the FMs to the output links of cells simple multiplexers are used. Those multiplexers are implemented after the interconnect matrix and have to be switched explicitly. This happens after the routing process is finished. The exception lies in the finishing state. Here the InRegCtrl doesn&#39;t have to acknowledge the successful routing the predecessor it just has to consume the actual routing instruction in the InReg instead. This happens after the InCtrl signals the successful routing. Additionally the InReg switches the output multiplexer associated to the output port of the FM and finishes the routing establishment. The information needed the switch the right output multiplexer gets the InCtrl from the RoutCtrl. 
         [0371]    Otherwise if the routing fails the InCtrl asserts cell specific interrupt line and signals the failure to the system. 
         [0372]    The second exception concerns the target routing cell. Here it is important to connect the new route with the input ports of the local FM. Therefore simple multiplexers are used which are implemented before the interconnect matrix. If an ongoing routing process reaches the target cell the InCtrl identifies the target achievement and switches the associated input multiplexer to forward the incoming data to the input port of the FM. This is the point where, the successful route establishment signal is generated by the InRegCtrl after InCtrl signals the success. Here the InRegctrl has the last job to finish the routing process by deleting the routing instruction and going to logical state. 
       Releasing Established Routing 
       [0373]    For releasing of the logically established routings we introduced special instructions, so called end packets. The only purpose of those instructions is the route-dissolving by inject the necessary end packet into the logic established routing. There are two ways how the routings can be released. The first possibility is the global releasing. This means that all routes which are following the route where the end packet is injected will be released. This function is useful to delete whole configurations with one single instruction. For this purpose it is important that the FMs are able to forward the end packet unaltered through the internal datapaths. 
         [0374]    The second way for route releasing is the local route releasing. Here it is possible to release single established routes between output and input ports of FMs. The end packets are not propagated through the FMs. In this case the end packet will be consumed by the last InRegCtrl. 
         [0375]    The internal RU communication is similar to the routing process. If the InRegCtrl determines incoming end packet and the InRegctrl is in the logic route state, the InRegCtrl forwards the route release request to the InCtrl. The InCtrl clears the entries either within the interconnect matrix or within the input multiplexers registers or within the output multiplexer registers. Meanwhile the InRegCtrl consumes (in case of the local end packet and last cell in the chain) the instruction and goes to the idle state. If the end packet was a global instruction the InRegCtrl forwards always the end packet to the successor. 
       Additional Features 
       [0376]    For the purpose of priority control, we introduced a priority system to influence the order in which the RU serves the incoming routing requests. Therefore the instructions contain priority fields which describe the priority level. Higher values in this field result in higher priority and will be preferred by the RU during the runtime-routing. The priority field has direct influence on the selection of the incoming routing requests from the InRegCtrls to InCtrl. 
         [0377]    Some inner configuration communication streams require strictly defined latency to reach the desired performance. Therefore it is very important to keep the maximum register chain length. To decrease the latency of the routed streams its is necessary to ensure that the array chose always the best routing between source and target, but this requirement may lead to not routable streams if this feature will be always required. To ease this problem we introduced a special bit within the routing instruction, so called optimum bit (OptBit). This bit has to be activated if the optimum routing is definitely required. In this case the array tries to reach this requirement and delivers an interrupt if fails. 
         [0378]    The alternative to reach the required latency is the speed path counter. This counter gives the possibility to bypass a specific number of registers before buffering again. Therefore we defined a reference value and the counter value. Both numbers are stored within the instruction field. Each passed cell respective the RU compares the counter value and the reference value. If both values are equal then the actual cell buffers the stream and resets the counter. If the counter is smaller than the reference value the current buffer will be bypassed and the counter incremented by one. In this way it is possible to bypass a number of buffers which equals exactly to reference value. 
       Multi-Grained Communication Links 
       [0379]    In addition to the coarse-grained point-to-point links we introduced more flexible multi-grained point-to-point links. Hereby one single point-to-point link connects two neighbor cells respective the RUs within those cells. One coarse-grained link consists of a set of wires, e.g. 32 wires for one 32 link, and additionally protocol signals. The whole vector is handled by a single set of control signals which makes this communication resource not usable for multi-grained communication. 
         [0380]    To reach this requirement we divided the whole 32 bit vector into single strips, e.g. with groups of 8 times 1 bit strips and 3 times 8 bit strips. Each strip obtained separate control signals and is able to operate independently from other strips. 
         [0381]    The idea behind this division is to combine those strips to logical multi-grained sub-links. If you have one multi-grained link you can use the whole vector as one interrelated 32 bit vector or split the whole vector into sub-channels. In this configuration each strip can be one single sub-channel or a group of strips can be gathered to a single sub-channel of desired bit-width. You just have—in respect of hardware costs—to consider that one sub-channel has to fit into one multi-grained link. 
       Multi-Grained Routing 
       [0382]    In order to route multi-grained channels its necessary to use the coarse grained links to support the routing process. The idea is to route two links in parallel, one coarse-grained link to support multi-grained routing and one multi-grained link, which will contain the final multi-grained stream. Therefore we defined a two packet routing instruction with needed data fields. The first instruction packet contains—compared to coarse-grained routing instruction—additional bit mask to specify used multi-grained sub-links and multi-grained link ID to identify the associated multi-grained link. The other features like described above—optimum bit, speed path, priority routing—are support in this routing mode as well. The routing process within the RU is performed similar to the coarse-grained routing. 
         [0383]    The first packet which arrives in a cell is analyzed by the InRegCtrl and a request is generated and forwarded to the InCtrl. InCtrl forwards the request to the RoutCtrl and wait for the acknowledgement. If RoutCtrl finds one possible routing direction, the InCtrl gets the successful acknowledgement and the temporal routing will be established by the RoutCtrl. Next, the actual job will be stored within the QueueRRP and the InCtrl waits for the acknowledgement from the successor cell. If RoutCtrl is not able to find a possible routing, the InCtrl gets negative acknowledgement and which will be forwarded to the associated InRegCtrl, which generates the route unable signal to the predecessor cell and quits the routing process within this cell. 
         [0384]    If the successor cell signals successful routing, the InRegCtrl clears the related entry in the QueueRRP and finishes the routing. If the successor cell is not able to establish a rout to the destination cell, it generates negative acknowledgement signal. Hereupon, the InCtlr starts new request to the RoutCtrl and handle the responses as described above. 
         [0385]    The difference between the coarse-grained routing and multi-grained routing lies in the handling of the multi-grained interconnect matrix. Each strip of a multi-grained link is handled separately. The RoutCtrl forwards the switch request to the strip matcher. Strip matcher has the job to analyze the input strips and to match them to the output link according to already used strips. What strip matcher is doing is to map the problem of strip matching into the time domain and switches the needed switchboxes for each strip separately one after another. 
       Routing Packet for Coarse-Grained Streams: 
       [0386]      
         [0000]    
       
         
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
               
               
                   
                 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
               
               
                   
                   
               
             
          
           
               
                   
                   
                   
                 Value 
                 Comments 
               
               
                   
               
               
                 32 
                   
                   
                  1 
                 instruction-packet 
               
               
                 31 
                 30 
                   
                 00 
                 ID: Routing-packet for coarse-grained streams 
               
               
                 29 
                 28 
                   
                 XX 
                 Priority-level: higher value results in higher 
               
               
                   
                   
                   
                   
                 priority 
               
               
                 27 
                 26 
                   
                 XX 
                 Speed path: Reference value 
               
               
                 25 
                 24 
                   
                 XX 
                 Speed path: Counter 
               
               
                 23 
                   
                   
                 X 
                 Optimum bit (OptBit): 1 enabled; 0 disabled 
               
               
                 22 
                 . . . 
                 19 
                 XXXX 
                 FM output address within the source cell 
               
               
                 18 
                 . . . 
                 15 
                 XXXX 
                 FM input address within the destination cell 
               
               
                 14 
                   
                   
                 X 
                 Use fine-grained links: 1 = yes, 0 = no 
               
               
                 13 
                 . . . 
                 8 
                   
                 Reserved 
               
               
                 7 
                 . . . 
                 4 
                 X . . . X 
                 Destination cell coordinates: x-coordinate 
               
               
                 3 
                 . . . 
                 0 
                 X . . . X 
                 Destination cell coordinates: y-coordinate 
               
               
                   
               
             
          
         
       
     
       Routing Instruction for Multi-Grained Streams (First Packet): 
       [0387]      
         [0000]    
       
         
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
               
               
                   
                 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
               
               
                   
                   
               
             
          
           
               
                   
                   
                   
                 Value 
                 Comments 
               
               
                   
               
               
                 32 
                   
                   
                  1 
                 Instructions-packet 
               
               
                 31 
                 30 
                   
                 01 
                 ID: Routing-instruction multi-grained streams 
               
               
                   
                   
                   
                   
                 (first packet) 
               
               
                 29 
                 28 
                   
                 XX 
                 Priority-level: higher value results in higher 
               
               
                   
                   
                   
                   
                 priority 
               
               
                 27 
                 26 
                   
                 XX 
                 Speed path: Reference value 
               
               
                 25 
                 24 
                   
                 XX 
                 Speed path: Counter 
               
               
                 23 
                   
                   
                 X 
                 Optimum bit (OptBit): 1 enabled; 0 disabled 
               
               
                 22 
                   
                   
                 — 
                 Reserved 
               
               
                 21 
                 . . . 
                 19 
                 XXX 
                 ID of the input stream of the multi-grained link 
               
               
                 18 
                 . . . 
                 16 
                 XXX 
                 8 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 15 
                 . . . 
                 8 
                 X. . . X 
                 1 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 7 
                 . . . 
                 4 
                 XXXX 
                 Destination cell coordinates: x-coordinate 
               
               
                 3 
                   
                 0 
                 XXXX 
                 Destination cell coordinates: y-coordinate 
               
               
                   
               
             
          
         
       
     
       Second Packet of the Routing Instruction for Multi-Grained Streams: 
       [0388]      
         [0000]    
       
         
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
               
               
                   
                 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
               
               
                   
                   
               
             
          
           
               
                   
                   
                   
                 Value 
                 Comments 
               
               
                   
               
               
                 32 
                   
                   
                  1 
                 Instructions-packet 
               
               
                 31 
                 . . . 
                 30 
                 10 
                 ID: Routing-instruction multi-grained streams 
               
               
                   
                   
                   
                   
                 (first packet) 
               
               
                 29 
                 28 
                   
                 X 
                 Reserved 
               
               
                 27 
                 . . . 
                 25 
                 XXX 
                 Destination cell 8 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 24 
                 . . . 
                 17 
                 X . . . X 
                 Destination cell 1 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 16 
                 . . . 
                 14 
                 XXX 
                 Multi-grained FM input port address of the 
               
               
                   
                   
                   
                   
                 destination cell 
               
               
                 13 
                 . . . 
                 11 
                 XXX 
                 Source cell 8 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 10 
                 . . . 
                 3 
                 X . . . X 
                 Source cell 1 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 2 
                 . . . 
                 0 
                 XXX 
                 Multi-grained FM output port address of the 
               
               
                   
                   
                   
                   
                 source cell 
               
               
                   
               
             
          
         
       
     
       End Packet Instruction: 
       [0389]      
         [0000]    
       
         
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
               
               
                   
                 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
               
               
                   
                   
               
             
          
           
               
                   
                   
                   
                 Value 
                 Comments 
               
               
                   
               
               
                 32 
                   
                   
                  1 
                 Instruktions-Paket 
               
               
                 31 
                 . . . 
                 30 
                 11 
                 ID: End packet for logical stream releasing 
               
               
                 29 
                   
                   
                 X 
                 Coarse-/fine-grained releasing: 1 coarse-grained, 
               
               
                   
                   
                   
                   
                 0 fine-grained 
               
               
                 28 
                   
                   
                 X 
                 Local/global route release process: 1 = local, 
               
               
                   
                   
                   
                   
                 0 = global 
               
               
                 27 
                 . . . 
                 23 
                 - . . . - 
                 Reserved 
               
               
                 22 
                 . . . 
                 19 
                 XXXX 
                 FM output address within the source cell 
               
               
                 18 
                 . . . 
                 14 
                 - . . . - 
                 Reserved 
               
               
                 13 
                 . . . 
                 11 
                 XXX 
                 Source cell 8 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 10 
                 . . . 
                 3 
                 X . . . X 
                 Source cell 1 bit strips mask: 1 = selected; 
               
               
                   
                   
                   
                   
                 0 = not selected 
               
               
                 2 
                 . . . 
                 0 
                 XXX 
                 Multi-grained FM output port address of the 
               
               
                   
                   
                   
                   
                 source cell 
               
               
                   
               
             
          
         
       
     
       Data Packet: 
       [0390]      
         [0000]    
       
         
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 
               
               
                   
                 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
               
               
                   
                   
               
             
          
           
               
                   
                   
                   
                 Value 
                 Comments 
               
               
                   
               
               
                 32 
                   
                   
                 0 
                 Data packet 
               
               
                 31 
                 . . . 
                 0 
                 X . . . X 
                 Application data 
               
               
                   
               
             
          
         
       
     
         [0391]      FIGS. 36 to 44  relate to an improved way of routing. 
       Using Function Folding to Improve Silicon Efficiency of Reconfigurable Arithmetic Arrays 
       [0392]    This section presents Function Folding, a design principle to improve the silicon efficiency of reconfigurable arithmetic (coarse-grain) arrays. Though highly parallel implementations of DSP algorithms have been demonstrated on these arrays, the overall silicon efficiency of current devices is limited by both the large numbers of ALUs required in the array and by the only moderate speeds which are achieved. The operating frequencies are mainly limited by the requirements of non-local routing connections. We present a novel approach to overcome these limitations; In Function Folding, a small number of distinct operators belonging to the same configuration are folded onto the same ALU, i.e. executed sequentially on one processing element. The ALU is controlled by a program repetitively executing the same instruction sequence. Data only required locally is stored in a local register file. This sequential approach uses the individual ALU resources more efficiently, while all processing elements of the array work in parallel as in current devices. Additionally, the ALUs and local registers can be clocked with a higher frequency than the (non-local) routing connections. Overall, a higher computational density than in current devices results. 
       1 INTRODUCTION 
       [0393]    Field-Programmable Gate Arrays (FPGAs) are used as a flexible, programmable alternative to Application Specific Integrated Circuits (ASICs) for bit-oriented applications. They combine low NRE costs with fast time-to-market. See R. Hartenstein, “A Decade of Reconfigurable Computing: A Visionary Retrospective,” In Proc. Design, Automation and Test in Europe, 2001 (“Hartenstein”). Similarly, reconfigurable arithmetic arrays—based on coarse-grain ALUs rather than bit-level lookup tables—are such an alternative for word-level, arithmetic applications. There are several research projects (e.g., Rapid (see D. C. Cronquist et al., “Architecture design of reconfigurable pipelined datapaths,” In Pros. 20th Anniversary Conference on Advanced Research in VLSI, Atlanta, Ga., March 1999), KressArray (see Hartenstein and see R. Hartenstein et al., “A New FPGA architecture for word-oriented datapaths, In Proc. Field-Programmable Logic, 4th International Workshop, Springer-Verlag, September 1994 (“Hartenstein et al.”))) as well as commercial developments (e.g., PACT XPP Technologies (see V. Baumgarte et al., “PACT XPP—A Self-Reconfigurable Data Processing Architecture,” The Journal of Supercomputing, 26(2), September 2003 (“Baumgarte et al.”), Morphotech (see M. H. Lee et al., “Design and Implementation of the MorphoSys Reconfigurable Computing Processor,” Journal of VLSI and Signal Processing Systems for Signal, Image and Video Technology, March 2000 (“Lee et al.”)), Elixent (see T. Stansfield, “Using Multiplexers for Control and Data in D-Fabrix, In Field Programmable Logic and Applications, LNCS 2778, pp. 416-425, Springer, 2003)) in this area. However, these architectures have not seen widespread use yet though highly parallel implementations of DSP algorithms have been demonstrated on them. One apparent reason for this is the limited silicon efficiency of current devices, resulting in both a large number of ALUs required in the array and in only moderate speeds being achieved. The operating frequencies are mainly limited by the requirements of non-local routing connections. 
         [0394]    We present an extension of PACT XPP Technologies&#39; eXtreme Processing Platform (XPP) (see Baumgarte et al.) which overcomes these limitations: Rather than executing a fixed operation on an ALU for the entire duration of a configuration, a small number of distinct operators belonging to the same configuration are folded onto the same ALU, i.e. executed sequentially on the same processing element (PE). The ALU is controlled by a program repetitively executing the same instruction sequence. Data only required locally is stored in a local register file. This sequential approach uses the individual ALU resources more efficiently, while all processing elements of the array work in parallel as in current devices. Since external data transfers are not required in every PE clock cycle, the ALUs and local registers can be clocked with a higher frequency than the (non-local) routing connections. This ALU overclocking technique is also justified by the continuous trend to higher integration densities: New technology generations provide smaller and smaller transistors, but the wires have higher relative capacities which make the busses slower and more power-consuming. 
         [0395]    Despite these significant architectural changes, existing XPP programs can be automatically mapped to this extended architecture. Overall, a higher computational density than in current devices results. 
         [0396]    The remainder of this section is organized as follows: 
         [0397]    First, we describe the current PACT XPP architecture. Next, Section 3 describes the functionality and hardware design of the new Function Folding PE, Section 4 elaborates the application mapping methods, and Section 5 presents preliminary results. Finally, our approach is compared to related work, conclusions are drawn, and future work is outlined. 
       2 XPP ARCHITECTURE OVERVIEW 
       [0398]    The current XPP architecture (see Baumgarte et al.) is based on a 2-D array of coarse-grain, adaptive processing elements (PEs), internal memories, and interconnection resources. A 24-bit prototype chip with 64 ALUs and 16 internal memories was built by PACT XPP Technologies. A development board for this XPP64A chip is available. 
         [0399]    PACT also provides a complete development tool suite consisting of a placer and router, a simulator, and a visualizer. The tools use the proprietary Native Mapping Language (NML), a structural language with reconfiguration primitives. A C frontend is provided as well. 
       2.1 Array Structure 
       [0400]      FIG. 45  shows the basic structure of a simple XPP core. For demonstration purposes, it contains only 9 PEs  4502  and 6 internal RAMs  4504 . The core comprises a 3×3 square of PEs in the center and one column of independent internal memories on each side. There are two I/O units  4506  which can either be configured as ports for streaming data or as interfaces for external RAM access. The core of a PE is an ALU which performs common arithmetic and logical operations, comparisons, and special operations such as counters. In each configuration, each PE performs one dedicated operation. Each line in the figure represents a set of segmented busses which can be configured to connect the output of a PE with other PEs&#39; inputs. The array is attached to a Configuration Manager (CM)  4508  responsible for the runtime management of configurations, i.e. for downloading configuration data from external memory into the configurable resources of the array. Besides a finite state machine  4510 , the CM has cache memory  4512  for storing or pre-fetching configuration data. 
       2.2 Data and Event Synchronization 
       [0401]    The interconnection resources consist of two independent sets of busses: data busses (with a device specific bit-width) and one-bit wide event busses. The XPP busses are not just wires to connect logic: a ready/acknowledge protocol implemented in hardware synchronizes the data and events processed by the PEs. Hence a PE operation is performed as soon as all necessary input values are available and the previous result has been consumed. Thus it is possible to map a dataflow graph directly to the array, and to pipeline input data streams through it. No data is lost even during pipeline stalls. Special dataflow operations for stream merging, multiplexing etc. are provided as well. 
       2.3 Configuration 
       [0402]    Compared to FPGAs, XPP cores can be configured rapidly due to their coarse-grain nature: Only opcodes and connections have to be set. Furthermore, only those array objects actually used need to be configured. 
         [0403]    The configuration time can be reduced by prefetching mechanisms: during the loading of a configuration onto the array another configuration can be loaded to the CM cache. Thus it must not be loaded from external memory when it is requested. The same is true if a configuration has been used before and its configuration data is still in the CM cache. 
       3 FUNCTION FOLDING PE 
       [0404]    We now describe the functionality and hardware design of an extended XPP PE, the Function Folding Processing Element. 
       3.1 Function Folding Example 
       [0405]    Let us first consider a simple example: An address adr is computed from a constant offset offs and coordinates x and y as follows: adr=offs+x+256*y. In an XPP implementation based on simple PEs as shown in  FIG. 45 , this computation is normally directly mapped to the dataflow graph in  FIG. 47A . Each adder and multiplier is mapped to its own ALU. Therefore a new address can be computed every cycle. However, as mentioned in Section 1, the operating frequency is limited by the bus connections, not by the ALU itself. 
         [0406]    For a higher silicon efficiency, i.e. for more operations per square millimeter and second, the ALUs have to be clocked faster. This could be achieved by more pipeline registers in the busses. But they unfortunately increase the chip area and power consumption and reduce the throughput if the dataflow graph contains cycles. In our approach, we rather operate the busses at a moderate frequency (as in the current XPP cores) and increase the ALU&#39;s clock rate locally inside a PE. This n-fold overclocking allows to schedule n ALU operations in one bus cycle (for a small number n). We call these groups of operations clusters. The significant reduction in the number of PEs required justifies the hardware overhead incurred. While sticking to the successful paradigm of reconfigurable “computing in space”, this locally sequential approach optimizes the usage of the ALU resources. 
         [0407]    By allowing different overclocking factors in the same device (e.g. n=2 and n=4), different local time-space tradeoffs are possible. For n=4, in our example, all operations in the dataflow graph can be clustered, i.e. executed on the same ALU, even if the multiplication requires two cycles. For n=2, only the two adders can be clustered. This results in twice the area, but also doubles the throughput compared to n=4. 
         [0408]    Apart from a program controller executing the n instructions repetitively, a small internal register file to feed intermediate results back to the ALU inputs is required in the PE. This local feedback loop allows implementing dataflow graphs with cycles containing up to n operators without reducing the overall throughput. 
       3.2 Hardware Design 
       [0409]    The hardware design sketched in  FIG. 46  performs Function Folding as described above. As the simple PEs in  FIG. 45 , the new PE communicates with the interconnect network via data and event input and output ports which follow the ready/acknowledge protocol. The ports also synchronize the fast internal PE clock with the n-times slower bus clock. Input data is stable during the entire bus clock cycle, i.e. can be sampled in any of the internal PE clock cycles. And output data is copied to the bus registers at the beginning of a bus cycle. A Function Folding PE requires more ports than a simple PE since it executes an entire cluster of operations. But it does not require n-times more ports than the simple PE since the number of external connections is often quite limited due to constant inputs (which can be loaded to internal registers at configuration time) and local connections within a cluster. A good clustering algorithm minimizes the number of external connections. As illustrated by the dotted box around the operators in  FIG. 47B , only two input ports and one output port are required for the example cluster for n=4. 
         [0410]    In detail, the PE in  FIG. 46  works as follows: A small program counter (PC)  4602  repeatedly iterates through the configured instructions in the instruction store  4604 . In each PE cycle it selects the ALU opcode and controls the multiplexors selecting the ALU inputs. Either an input port or an entry of the internal register file  4606  can be used. The ALU outputs can be written back to the internal register file or to an output port or to both. The entire design is kept as simple and small as possible to just support function folding. No other control structures are possible. Both the number of input and output ports and the number of internal registers will be about n. Therefore we can choose a very fast implementation of the register file just using registers and multiplexors. Given the small number of ports and registers, the entire fetch/execute/store process can be performed in one cycle. The only exception is the multiplier operation which takes two cycles. The controller (FSM)  4608  stalls the program execution if an external input is not available or if an external output port is full due to a downstream pipeline stall. Note that event ports and registers are omitted in  FIG. 46  for clarity. Events can be used and stored internally and externally like data. 
         [0411]    Returning to  FIG. 47B , we can now present the simple PE program for the address generation cluster. The mapping of connections to ports and registers is indicated in the figure. We assume that registers r1 and r2 have been initialized with the constant values offs and 256, respectively, at configuration time. The following assembler code, executed repetitively, describes the cluster:
       add r3&lt;-r1, i1   mul r4&lt;-r2, i2   add o1&lt;-r3, r4       
 
       4 APPLICATION MAPPING 
       [0415]      FIG. 48  shows the tool flow of the extended XPP architecture. It is very similar to the current tool flow implemented in the xmap program (see Baumgarte et al.). Only the phases represented by the shaded boxes are added. The following phases already exist in the current XPP tool flow:
       Cfrontend (optional): Generates structural NML code (cf. Section 2) from a subset of standard C.   NML parser: Parses the input NML file and maps it to XPP operators.   Place and Route: Places the PEs (i.e. operators in the current architecture) on the XPP array and routes the connections.   Binary Generation: Generates an XBIN binary file.       
 
         [0420]    For Function Folding, an additional Operator Clustering phase is required which defines the operators mapped to one PE. Though the clusters could be defined manually by annotations in the NML file, an automatic clustering algorithm is required to simplify programming, to use the C frontend, and to map existing NML code. It is described in the next section. Furthermore, PE program code needs to be generated for each cluster as described in Section 4.2. Obviously the Place and Route and Binary Generation phases have to be adapted, too. 
       4.1 Operator Clustering 
       [0421]    The operator clustering problem for Function Folding PEs is similar to the graph covering problems encountered in code generators for conventional processors and module mapping for FPGAs, e.g. T. J. Callahan et al., “Fast Module Mapping and Placement for Datapaths in FPGAs,” In Proc. FPGA &#39;98, Monterrey, Calif., 1998 (“Callahan et al.”). Therefore we investigated these algorithms first. The efficient dynamic-programming algorithm used in Callahan et al. and similar approaches is actually a tree-covering algorithm. It generates optimal coverings for operator trees. But it cannot handle arbitrary dataflow graphs. Hence a preprocessing phase which removes feedback cycles and fanout edges from the original graph is required. The result is a forest of trees which can be covered efficiently. However, the optimal tree covering results are not optimal for the original dataflow graph. 
         [0422]    Now consider the operator clustering problem at hand: We need to find a solution with the minimal number of clusters which conforms to the restrictions of the Function Folding PEs, i.e. the over-clocking factor n, and the number of ports and internal registers. Additionally, cycles should be processed within a cluster whenever possible (to avoid reduced throughput caused by external routing delays), and the number of external connections should be minimized. Unfortunately these quality criteria are not visible in the output of the tree covering preprocessing phase, i.e. after the removal of cycles and fanout edges. Hence we do not apply tree covering for operator clustering. 
         [0423]    Instead, we developed an algorithm operating on the original graph. To reduce the complexity, we only consider clustering operators which are connected since only these clusters use internal registers and reduce the number of external ports. In an additional postprocessing phase, unconnected clusters can be merged later if they are placed next to each other. 
         [0424]    In the first algorithm phase, all connected clusters are explicitly generated. Note that the number of possible unconnected clusters would be exponential in the number of operators. 
         [0425]    In the second phase, the optimal combination of clusters covering the entire input graph has to be determined. Unfortunately the number of all possible combinations of clusters is exponential. Hence it cannot be searched exhaustively. Instead, the main loop of the algorithm operates on an increasing subset of the operators, generating and storing an optimal clustering of the subset, until the optimal clustering of the entire operator graph has been computed. The algorithm exploits the fact that partial optimal solutions are contained in the complete optimal solution. In this way we do not need to compute optimal clusterings for all subsets. Because the optimal clustering of a new subset depends on other subsets which might not have been computed before, some recursive calls which may lead to an exponential runtime are required. However, we found that the runtime is in the range of a few minutes for an overclocking factor n&lt;=4 and for an operator number k&lt;50. For larger problem sizes we tested the following heuristics:
       Remove large feedback cycles (with more than n operators) from the graph. Then small cycles are still executed within a cluster and only a few possible clusters are excluded, but the number of recursive calls is largely reduced.   Do not compute the best solution in recursive calls, but only the first clustering of the subset which is computed. By applying larger clusters before smaller ones, the algorithm computes a nearly optimal solution anyway.       
 
         [0428]    With these extensions we could quickly cluster realistic dataflow graphs with up to 150 operators. For the cases we tested, the heuristics produced clusterings which were very near or equal to the optimum (i.e. they had only a few more clusters). 
         [0429]    Note that we restricted the number of operations in a PE program to n in the previous discussions. This is reasonable since we normally do not want to extend the PE program execution over more than one bus cycle. However, if a PE can be programmed to execute more than n operations, those operations which are not throughput-critical can be combined in larger clusters. This further reduces the required number of PEs without impacting the overall throughput. 
       4.2 PE Code Generation 
       [0430]    After operator clustering, the PE program code for every cluster is generated; cf. the assembler code in the example in Section 3. A simplified version of conventional register allocation is used to map internal connections to internal registers. The instructions can be directly extracted from the dataflow graph of the cluster. 
       5 RESULTS 
     5.1 PE Speed and Area 
       [0431]    The area of a Function Folding PE is estimated to be about 15% to 25% larger than the area of the corresponding simple PE, depending on the number of ports and registers. For 16-bit datapaths, preliminary synthesis results achieve a PE frequency of 400-500 MHz for a 130 run silicon process. 
       5.2 Complex FIR Application Analysis 
       [0432]    This section demonstrates the implementation of a typical DSP algorithm, a FIR filter operating on complex numbers, on Function Folding PEs. Consider one FIR filter cell which computes the output Z=X*C+Y from a constant C and inputs X and Y. All values are complex, i.e. (Zre,Zim)=(Xre*Cre−Xim*Cim+Yre, Xre*Cim+Xim*Cre+Yim).  FIG. 49A  shows the corresponding dataflow graph. It contains eight operators which can be folded to three clusters for an overclocking factor of n=4, as indicated by the dotted boxes C11, C12, C13.  FIG. 49B  shows the resulting cluster dataflow graph. All clusters fully utilize the PEs, i.e. use all four PE clock cycle. 
         [0433]    Let us now compare the silicon efficiency of an implementation on a current XPP device (FIRcurr) with one based on Function Folding PEs (FIRnew), As outlined above, we estimate F PE =400 MHz and F bus =100 MHz for n=4. F bus  is also the operating frequency of the current architecture. Filters built from the given FIR cells can easily be fully pipelined for both implementations, as can be seen from  FIGS. 49A and 49B . Hence both implementations have the same performance: They generate outputs at a rate of 100 MHz. 
         [0434]    The area of a Function Folding PE is estimated as A FFPE =1.2×A currPE , i.e. 20% larger than current PEs. The area ratio for the two filter implementations is as follows: 
         [0000]    
       
         
           
             
               
                 A 
                 FIRnew 
               
               
                 A 
                 FIRcurr 
               
             
             = 
             
               
                 
                   3 
                   × 
                   
                     A 
                     FFPE 
                   
                 
                 
                   8 
                   × 
                   
                     A 
                     currPE 
                   
                 
               
               = 
               
                 
                   
                     3 
                     × 
                     1.2 
                     × 
                     
                       A 
                       currPE 
                     
                   
                   
                     8 
                     × 
                     
                       A 
                       currPE 
                     
                   
                 
                 = 
                 0.45 
               
             
           
         
       
     
         [0435]    This rough estimation shows that the new implementation is more than twice as area-efficient as the old one without requiring more pipelining registers in the external busses. The overall silicon efficiency is more than doubled. 
       5.3 Benchmark Mapping Results 
       [0436]    In order to determine the general applicability of Function Folding, the algorithm described in Section, 4.1 was applied to a benchmark of 43 legacy XPP configurations from a wide range of application areas. We determined the average cluster utilization, i.e. the number of PE cycles being used by the repetitive PE program. This value is a good indication of the effectiveness of Function Folding. Note that a high cluster utilization does not guarantee that the PE program can be executed every bus cycle. The overall PE utilization in an application also depends on the availability of input data and on the overall throughput of all PEs. 
         [0437]    Table 1 shows the results for n=2 and n=4 with varying port numbers. The number of internal registers was not yet restricted for this evaluation. The results for four input and output data and event ports (1.78 for n=2 and 3.05 for n=4) show that the Function Folding PE resources can be exploited efficiently for average XPP configurations. The table shows that using six data ports increases the cluster utilization only insignificantly. On the other hand, using fewer data ports distinctly decreases the utilization. We will combine hardware implementation results detailing the area requirements of the ports with the cluster utilization numbers to determine the PE parameters which yield the best overall silicon efficiency. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Average cluster utilization (CU) in XPP benchmark, n: 
               
               
                 overclocking factor; DI/DO: number of data input/output ports; 
               
               
                 EI/EO: number of event input/output ports. 
               
             
          
           
               
                   
                 n 
                 DI 
                 DO 
                 EI 
                 EO 
                 CU 
               
               
                   
                   
               
               
                   
                 2 
                 6 
                 6 
                 4 
                 4 
                 1.79 
               
               
                   
                 2 
                 4 
                 4 
                 4 
                 4 
                 1.78 
               
               
                   
                 2 
                 2 
                 2 
                 4 
                 4 
                 1.57 
               
               
                   
                 2 
                 4 
                 4 
                 2 
                 2 
                 1.75 
               
               
                   
                 2 
                 2 
                 2 
                 2 
                 2 
                 1.53 
               
               
                   
                 4 
                 6 
                 6 
                 4 
                 4 
                 3.06 
               
               
                   
                 4 
                 4 
                 4 
                 4 
                 4 
                 3.05 
               
               
                   
                 4 
                 2 
                 2 
                 4 
                 4 
                 2.25 
               
               
                   
                 4 
                 4 
                 4 
                 2 
                 2 
                 2.80 
               
               
                   
                 4 
                 2 
                 2 
                 2 
                 2 
                 2.12 
               
               
                   
                   
               
             
          
         
       
     
       6 RELATED WORK 
       [0438]    Though there are several projects on reconfigurable arithmetic arrays as mentioned in Section 1, to our knowledge there are no solutions similar to Function Folding in the literature. The following architectures differ considerably from our approach, but also allow to quickly change the operations performed by a PE. 
         [0439]    The RAW microprocessor (see M. B. Taylor et al., “The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs,” IEEE Micro, March/April 2002) also contains a cluster of processing elements, but they are rather complex processors. Therefore their programs cannot be generated automatically as easily as the Function Folding PE programs. The RAW architecture resembles more a multiprocessor on a chip. 
         [0440]    On the other hand, the MorphoSys architecture (see Lee et al.) follows a SIMD approach. All PEs in a row or column are controlled by a (global) program and execute the same instruction. This makes the PEs simpler, but the SIMD principle considerably restricts the available computations which can be executed. The array is also much harder to program. 
         [0441]    Finally, multi-context devices provide two or more complete configuration contexts (see B. Salefski et al., “Re-configurable Computing in Wireless, In Proc. 38th Design Automation Conference, Las Vegas, Nev., June 2001). This technique is adapted from multi-context FPGAs. However, it does not allow frequent reconfigurations since the shadow configurations first have to be loaded completely. The configurations are completely independent. Multicontext devices hide the configuration latency to a certain extent, but do not overcome the general efficiency problems of coarse-grain reconfigurable architectures. 
       7 CONCLUSIONS AND FUTURE WORK 
       [0442]    We have presented the architecture and functionality of the Function Folding Processing Element for an enhanced PACT XPP architecture. Preliminary analyses of both a hardware implementation and applications mapped to this architecture indicate that Function Folding significantly increases the silicon efficiency compared to current reconfigurable arithmetic arrays and has the potential to reduce the power consumption. 
         [0443]    After the implementation of a Function Folding PE and the analysis of its parameters, future work will include the evaluation of paths which are not throughput-critical as mentioned at the end of Section 4.1. Integrated clustering and place-and-route algorithms will be explored. We also consider developing a direct compiler from C to Function Folding PEs which might exploit their capabilities better then the current design flow via NML.