DE10240000A1 - Router for use in networked data processing has a configuration method for use with reconfigurable multi-dimensional fields that includes specifications for handling back-couplings - Google Patents

Abstract

Configuration method for multidimensional fields of reconfigurable networked data processing cells, whereby the necessary connections between cells are prioritized, then first connections that have a high priority are provided and subsequently remaining connections are provided. An Independent claim is made for a method for configuration or reconfiguration of a multidimensional field and or cell for data processing, in which the data is processed in cells and processing results are transmitted downstream for further processing. At least one set of data from a cell is transmitted upstream, with the cell position chosen so that the back coupling time of this connection is no greater that that of any other connection in the configuration.

Description

The present invention is concerned with methods and designs of bus systems for configurable Architectures. The optimization of the configuration and reconfiguration efficiency will especially considered.

The object of the invention is new for commercial To provide usage.

The solution to the problem is claimed independently. Preferred embodiments are in the subclaims.

Under a reconfigurable architecture Modules (VPU) with configurable function and / or networking understood, in particular integrated modules with a plurality of one-dimensional or multi-dimensional arithmetic and / or logical and / or analog and / or storing and / or networking Assemblies (hereinafter referred to as PAEs) and / or communicative / peripheral Assemblies (IO), directly or through one or more bus systems e) are connected to each other. PAEs are of any design, mix and hierarchy arranged. This arrangement is called the PAE array or called PA.

The category of these modules includes systolic arrays, neural networks, multiprocessor systems, processors with several arithmetic units and / or logical cells, networking and network modules such as crossbar switches, as well as known modules of the category FPGA, DPGA, XPUTER, etc. in particular in this context, the following property rights of the same applicant: P 44 16 881.0-53, DE 197 81 412.3 . DE 197 81 483.2 . DE 196 54 846.2-53 . DE 196 54 593.5-53 . DE 197 04 044.6-53 . DE 198 80 129.7 . DE 198 61 088.2-53 . DE 199 80 312.9 , PCT / DE 00/01869, DE 100 36 627.9-33 . DE 100 28 397.7 . DE 101 10 530.4 . DE 101 11 014.6 , PCT / EP 00/10516, EP 01 102 674.7 , PACT19, PACT20, PACT21, PACT27, PACT28, PACT15. These are hereby fully incorporated for disclosure purposes.

1. Structure of bus systems

A traditional implementation of the configuration requires synchronization between the objects. This synchronization becomes central about realized a FILMO (cf.PACT04, PACT05, PACT10, PACT17). Thereby pass between the end of an old configuration (reconfig event) and the start of a new configuration (Object goes in again the state "configured") at least as many measures as the pipeline CM test bus is long (there and back).

According to the invention, two methods are used for acceleration proposed:

• a) The required order is given by additional Logic ensured in the objects, e.g. Management of IDs,
• b) The objects are modified so that no order more needs to be considered but that the proper interconnection ensured by the architecture of the objects becomes.

For the following considerations, the modules available in a typical reconfigurable architecture are divided into two groups:
Buses This group comprises the connecting line between two segments. It is represented by the segment switch at its end.
Object This group summarizes all objects that have a connection to a bus or that communicate with their environment, ie any PAE (e.g. memory, RLUs), IO, etc.

Dependencies typically exist between all directly neighboring objects. In detail, these are:
Bus to bus A bus is represented by the segment switch at the end of a bus. Object to bus object can be selected freely from FREG, BREG, ALU and RAM. In this sense, everything that owns a Connect also counts as an object.
Object to object These are not directly adjacent, there is always a bus in between. There is no dependency here.

1.1 Bus to bus dependency

longer According to the prior art, buses are, for example, from behind configured forward. The last bus segment with open Switch configured, all others with the bus switch closed. Order compliance is required to prevent that data from a bus further ahead to another run behind, which is yet another configuration heard.

1.2 Bus to object dependency

According to the state of the art, a Object can only be configured if it is ensured that the buses used by the object are already configured. Also this dependency exists to ensure that no data is in a foreign configuration run (PAE output) or taken from an external configuration (PAE input).

In summary, it can be said that a dependence whenever there is an object connecting to another Object (connection mask or closed switch). there the connection may only be established when ensured is that the object to connect to is already belongs to the same configuration (i.e. already accordingly configured).

2. Control over ID management

The simplest approach is in everyone Object the id or array id (see PACT10) that the object is currently using. As soon as a connection between two objects is configured (e.g. between a PAE output and a bus), check in advance whether both objects have the same ID / array ID have. If this is not the case, the connection must not be established become.

Although this procedure is basically comparative is trivial, it requires a lot of hardware, since registers for every possible connection for the Storage of the ID / array ID and comparators for comparison of the ID / array ID of the two objects to be connected are necessary.

1 shows the two PAEs (0101, 0102), with their associated IDs, and a bus (0103) with ID. Each PAE / bus connection is checked via the comparators (0104, 0105). The figure is only intended to illustrate the basic principle. If all resources (inputs / outputs of the PAEs, buses) are taken into account, the complexity and the associated hardware expenditure increase considerably.

A technically more affordable and therefore preferred method is discussed in the following sections:

3. Control over network structure

Illustration 2 shows a bus segment that is required by configuration A and B. It is occupied by configuration A. Regardless of this, configuration B can already occupy the two neighboring bus sections. The double switches prevent data from configuration B from interfering with the data flow from configuration A. Likewise, no data runs from configuration A to B. Here, configuration B, as before, must also trust that configuration A has been implemented correctly and the switch at the output is open.

As soon as configuration A ends, the free bus is occupied by configuration B and configuration B starts to work.

In other words, there is a basic principle of Process in that each element is involved in a data transfer is actively involved in the corresponding data source or activates the data transmitter.

Bus to PAE entrance

Illustration 3 shows a PAE input (0301) to be connected to the bottom two of the three buses shown. The vertical switches correspond to a simple connection switch for connection to the bus that is managed by the PAE (0302), the horizontal switches (0303) are additionally configured via the bus to ensure correct connection.

In figure 3a the middle bus is still occupied by another configuration. Nevertheless, the object can be fully configured with the PAE input. Data from the middle bus cannot run into the object unintentionally as this is prevented by the configuration of the bus (switch 0303).

In figure 3b has terminated the old configuration and has been replaced by the new configuration. Both buses are now available. Only the vertical switches (0302) are used to determine which buses are actually switched on.

In figure 3c the upper bus is finally occupied by a third configuration, which also wants to use the PAE input shown. The bus is therefore already configured so that data can be extracted at this point. However, this has no effect on the object, since the PAE configuration does not provide a connection here. The connection is only established when the configuration of the PAE input changes.

Bus output PAE

This is the only connection where it makes sense to use two separate switches. In the other two cases, the functionality can also be implemented with a switch that is controlled by two config bits. Illustration 4 shows a PAE output to be connected to the bottom two of the three buses shown. The object is configured regardless of the availability of the buses; the switches on the left correspond to the connection mask.

In figure 4a the middle bus (0401) is still occupied by another configuration. A data packet can now be sent to the Connect from the output register. This is saved in the connected RdyHold (see PACT18) stages. The package cannot be transmitted through the opened switch of the middle bus and therefore cannot be JACKED. The object can therefore not transmit any further data packets.

In figure 4b the middle bus has now been reconfigured so that data can also be transmitted here. A possibly already saved package is now on the bus, otherwise everything works as before.

In figure 4c the upper bus (0402) is requested by a third configuration. Here, too, everything behaves as before.

Summary

With relatively little hardware let yourself significantly increase reconfiguration performance. It will possible, several complete Load configurations into the object FIFOs.

After reconfiguration, everyone needs Object locally only as many cycles as required for configuration words until it is configured again. This time can be through a second register set, approximately at 0 bars, to press.

The additional hardware expenditure is limited for an additional one Configuration bit and AND gate per switch and per number of buses * number PAE inputs. The PAE outputs may require a little more effort depending on the implementation, provided an additional one each Switch is necessary.

5. Reconfiguration control

Control of reconfiguration is triggered in the VPU technology by signals (Reconfig) that mostly with the data packets and / or trigger packets via the Bus systems are propagated and indicate that a particular resource is reconfigured can or should be, if necessary, the new configuration selected (see PACT08, PACT13).

If a reconfigurable module Reconfig is only required if it is to be partially reconfigured interrupt at certain points according to the algorithm. This interruption, which prevents Reconfig from being forwarded is called ReconfigBlock.

ReconfigBlock are usually sent to the Limits of one configuration introduced to the next separate them accordingly.

Insist on sending Reconfig different strategies that according to the requirement of Algorithm chosen become.

There are three possible preferred configurations described, which are used individually or in combination can and behave differently:

• a) ForcedReconfig: The simplest strategy is sending the reconfig over all interfaces of an object. This ensures that all connected Objects in the PA receive the signal. To restrict it must be blocked in suitable places become. This procedure or signal ensures that a configuration is completely removed. The signal is subsequently with ForcedReconfig designated. The signal should only be used after all Data in the objects concerned have been processed and removed, since there is no synchronization with data processing.
• b) SyncReconfig: A Reconfig is together with the corresponding Data and / or triggers sent. The dispatch takes place only together with active data and / or trigger packets. The signal is preferred forwarded together with the last data and / or trigger packets to be processed and shows the end of data processing after this data / trigger packet on. requires a PAE several cycles for processing, the forwarding of SyncReconfig delayed so long until the trigger and / or data packet is actually sent. Consequently behave this signal is synchronous with the last data processing.
• c) ArrayReset: As an extension of ForcedReconfig can ArrayReset can be used, which can not be blocked and leads to a reconfiguration of the complete array. This procedure is special then makes sense if e.g. an application is terminated or a Illegal opcode (see PACT19) or timeout of a configuration occurred and for proper scheduling of the configuration with other strategies is not can be guaranteed.

5.1 SyncReconfig

SyncReconfig is always with valid, propagates active data or triggers.

Problems now arise if, for example, the signal in a branch is propagated only in the active branch ( 5a ) or a fork is blocked by missing data or triggers ( 5b ).

To solve this problem the semantics of SyncReconfig are defined as follows: the signal indicates that after receipt and complete processing of the data / trigger all Data / trigger sources (sources) and buses to the entrance of the object to lead, that SyncReconfig received, can be reconfigured. This is the signal ReconfigEcho introduced. After SyncReconfig arrives at a target object, it ReconfigEcho generates as soon as the target object processes the data completely has arrived with the SyncReconfig. ReconfigEcho is sent to everyone Sources sent and leads to reconfigure the sources and the data or trigger transmitters Bus systems.

An object receives a ReconfigEcho will this over all still active inputs transmitted to the sources of the object.

Inputs / outputs that have already received a SyncReconfig become passive on arrival, they do not carry out any data / trigger transfers more through. Depending on the configuration, a SyncReconfig can only be used for passive switching of the input at which the signal arrived or passive switching all entrances the PAE.

For usually hits a ReconfigEcho at outputs from PAEs. This causes the forwarding of ReconfigEcho via the inputs the PAE, provided that it has not already been received by a SyncReconfig were switched passive.

In some cases, such as in the 5a-c , ReconfigEcho can also occur at the inputs. Depending on the configuration, this can lead to passive switching of the input at which the signal arrived or, in a preferred embodiment trigger the passive switching of all inputs of the PAE.

5.2 Trigger with reconfig semantics

In some cases (e.g. 5b ) implicit propagation of reconfig signals (ib SyncReconfig, ReconfigEcho) is not possible.

For the required explicit transfer of Any Reconfig signals can be triggered by the trigger system according to PACT08 are used, with the trigger semantics being expanded accordingly. Triggers can any status and control signals (such as carry, zero, Overflow, STEP, STOP, GO (see PACT08, PACT13, PACT18) transferred, as well as the implicit reconfig signals. Furthermore, a trigger accept the semantics SyncReconfig, ReconfigEcho, ForcedReconfig.

5.3 Block

At every interface that a SyncReconfig sends, can be set whether the dispatch should take place. The Preventing propagation leads no side effects. Provided that the SyncReconfig is accepted the receiving interface is blocked, the receiving one switches Object the interface that the SyncReconfig received passively (i.e. the interface no longer sends or receives data), otherwise the object does not respond to the signal, but can affect the resolution of the transmitting To enable the bus system Send ReconfigEcho back.

Furthermore, it is independent and / or together with a ReconfigBlock it is possible to block the ReconfigEcho.

5.4 Effect of SyncReconfig and ForcedReconfig on bus systems

To make sure that already after running a SyncReconfig over a bus, no more Transfer data e.g. come from a subsequent configuration, SyncReconfig will forward RDY / ACK (see PACT02) via the Bus blocked. However, the bus itself will not be demolished to the return by ReconfigEcho about to enable the bus system. First with the passage of ReconfigEcho the bus is dismantled.

Others equivalent in effect Methods can be used, e.g. could Data and trigger connections already when running SyncReconfig be demolished while the ReconfigEcho connection only when ReconfigEcho occurs is broken down.

This ensures that data and triggers of different, unrelated configurations falsely under the configurations can be exchanged.

5 shows an example of PAEs (0501) with differently configured networks. The following transfers are defined: data and / or trigger buses (0502), SyncReconfig (0503), ReconfigEcho (0504). ReconfigBlock (0505) is also shown. 0506 indicates that SyncReconfig is not forwarded.

In 5a a map is shown, such as can be created in a program by an IF-THEN-ELSE construct. After a PAE, the data is branched into two paths (0510, 0511), of which only one is ever active. In the case shown, a last data packet is transmitted together with SyncReconfig, branch 0510 is not active and therefore does not forward the data or SyncReconfig. Branch 0511 is active and forwards the data and SyncReconfig. The transmitting bus system can preferably be switched to inactive after the transmission and can only transmit the ReconfigEcho back. The PAE 0501b receives the SyncReconfig and sends it on to the PAE 0501c, it sends the ReconfigEcho back to 0501a, whereupon 0501a and the bus system between 0501a and 0501b are reconfigured. The transmission between 0501b and 0501c proceeds accordingly.

0501e also has the SyncReconfig of 0501a received, but the branch is not active. Therefore 0501e responds not, i.e. 0501e neither sends the SyncReconfig to 0501f nor that ReconfigEcho back to 0501a.

0501c processes the incoming Data and sends the SyncReconfig to 0501d. The process corresponds first again the transfer from 0501a to 0501b. 0501d generated after processing the Data a ReconfigEcho that due to the merger of the Branches are also sent to 0501f. Although 0501f is not a data operation conducted is reconfigured and sends the ReconfigEcho to 0501e is then also reconfigured without data processing.

The one transferred from 0501b to 0501a In a preferred embodiment, ReconfigEcho can also transmit to 0501e and arrives at an entrance there. This leads to Passive switching of the input and - in an extended version, if necessary also configurable - for Passive switching of all inputs.

To follow the examples in 5 To give a local character, the inputs / outputs of the representations were provided with a ReconfigBlock, which prevents the forwarding of SyncReconfig and ReconfigEcho.

5b behaves largely identical to 5a , which is why the same references are used. The right path is also active again, the left path is inactive. The main difference is that instead of merging the paths at 0501d, the paths now remain open and lead directly to a peripheral interface, for example. In such cases it is necessary to provide explicit wiring of ReconfigEcho via trigger lines between the PAEs (0501i and 0501j) (0507).

In 5c the exemplary execution of a loop is shown. The loop runs over the PAEs 0501m..0501r. The transmissions between the PAEs 0501m..0501r are obvious in accordance with the previous explanations, in particular to the transmissions between 0501b and OSOlc, since they are equivalent.

Particular attention should be paid to the transfer between 0501r and 0501m. When ReconfigEcho occurs on 0501m, the Bus (0508) between 0501m and 0501r through the transfer of ReconfigEcho reconfigured. ReconfigEcho is blocked at the output of 0501r, this does not reconfigure 0501r, the relevant output however, switched to passive when ReconfigEcho arrives, i.e. 0501r no longer routes results to the bus. This allows the bus from any other configuration.

As soon as 0501r the ReconfigEcho from 0501q receives 0501r is reconfigured at the end of data processing. The ReconfigBlock and / or prevent the passive connection of the bus connection to 0501m (0508) forwarding towards 0501m. 0501m and 0508 can now be used by another configuration.

6.0 SyncReconfig-II

Another optional and depending Application, area of application and / or configuration of the semiconductor or system-preferred method for controlling the SyncReconfig protocol is described below:

The procedure is defined as follows:

• 1. SyncReconfig is basically all connected (data and / or trigger) buses of a PAE are sent, also about those that currently (at the current clock) do not transmit any data and / or triggers.
• 2. In order for a PAE SyncReconfig to forward according to paragraph 1, have to previously all connected inputs the PAE has received the SyncReconfig.
• 2a. feedback in the data structure (e.g. loops) require an exception to the Postulates according to paragraph 2. The feedback is excluded, i.e. it is sufficient if all connected inputs a PAE apart from the one or more looped back the SyncReconfig received so that it is forwarded.
• 3. Processes a PAE data (possibly also, multi-cyclically, e.g. Division) becomes a SyncReconfig if this corresponds to 2 and 2a is present at the inputs, at the time of the final calculation and forwarding of the data and / or Trigger to the recipient (s) forwarded. In other words, no SyncReconfig overtakes the Data processing. Non-data processing PAEs direct SyncReconfig immediately to the connected recipients further.
• 4. SyncRekonfig is transmitted with handshake signals (e.g. RDY / ACK = ReaDY / ACKnowledge). A PAE sending SyncReconfig only goes into the reconfigurable state, if all recipients the receipt of SyncReconfig for confirmation by means of an ACK (nowledge) have acknowledged.

This procedure turns out to be in principle the question of what happens if a configuration is not yet fully configured is, but should already be reconfigured. Beyond consideration, whether such behavior of an application is not better Programming needs to be solved the problem as follows: A PAE tries the SyncReconfig on one to forward PAs that have not yet been configured, it receives no ACK until the PAE is configured and the SyncReconfig acknowledges. Thereby There may be a loss of performance, except for the complete configuration the one to be deleted Configuration is serviced before it is deleted. On the other hand occurs but this case is extremely rare and only among exceptional circumstances on.

Applicant: Pact XPP Technologies AG Muthmannstr. 1 80939 Munich

Representative: Patent Attorney Claus Peter Pietruk Heinrich-Lilienfein-Weg 5 D-76229 Karlsruhe representative no. 321 605

German patent application

Title: Bus systems and reconfiguration procedures

Claims (2)

Method for controlling bus systems, that an intrusion on a bus through the approval of the connection through Sender and receiver he follows. Process for the reconfiguration control of reconfigurable Elements, characterized in that signals with the data and / or Transfer trigger be the reconfiguration of the reconfigurable element and / or Busses controls.