1.6. Structured Data Exchange

Data exchanges between processors can be accomplished with simple symbolic names, thanks to the network declaration described earlier. Data exchange of a local vector variable between all or just a group of PEs can be invoked by calling system function MOVE with the name of a previously defined connection. Only active PEs participate in a data exchange operation. Figure 7 shows an example of a data exchange in the grid structure defined earlier. The expression returns vector variable x shifted one step (one PE) to the east.

y := MOVE. east(x);

Figure 7 Synchronous data exchange

For the data exchange operation shown above, sender-PE and receiver-PE of a data exchange have to be active. For the operations SEND and RECEIVE shown below, it is sufficient for only the sender (or only the receiver, respectively) to be active. These operations are especially needed for the data exchange between different topologies, since due to the SIMD model only one PE structure can be active at a time.

SEND.east(4*x, y);
y := RECEIVE.north(x);

The following comparison shows the differences in data exchange operations by using a simple list topology. In figures, an arrow represents data transport, while a white space marks an inactive PE. Let us assume that for the context of the following data exchange operations that all PEs are active but one (e.g. the data exchange might occur inside an IF-selection, which deactivated one of the PEs).

CONFIGURATION list[1..max];
CONNECTION right: list[i] -> list[i+1];
VAR x,y: list OF INTEGER; (* assume x=y before data exchange *)

a) Only the sender has to be active.
All active PEs, which have a successor, send data.
SEND.right(x,y);

active inactive active active 

	Example x before:      1 2 3 4
          	y after:       1 1 3 3
b) Only the receiver has to be active.
All active PEs, which have a predecessor, receive data.
y := RECEIVE.right(x);
	Example x before:       1 2 3 4
      	 	y after:       1 2 2 3
c) Both sender and receiver have to be active.
All active PEs, which have an active successor, send data.
y := MOVE.right(x);
	Example x before:       1 2 3 4
         	y after:        1 2 3 3

d) Neither sender nor receiver have to be active.
All PEs, which have a successor, send data - independent of their activation status.
This version does not seem to make much sense, so it is not included in Parallaxis (use ALL statement instead).

Please note:

Two additional data exchange modifiers may be specified for any of the data exchange operations. One is for multiple data movement steps and one is for an implicit reduction; both are separated by colons.

A data exchange operation may be executed several steps (subsequently) in a specified direction: 

VAR x,y: grid OF INTEGER; 
...
y := MOVE.east:2 (x);   move data two steps to the east
A problem might occur, if several PEs are connected to a single one (many-to-one connection). There are two possibilities to avoid an undetermined result (any of the incoming data values could be chosen). One can either deactivate unwanted PEs (IF-selection), so they cannot participate in a data exchange, or one can use a reduction function with the data exchange.

For example, in the tree network shown before, one might want to send only the left children's data to the parents and discard the right children's data: 

VAR u,v,w: tree OF INTEGER; 
... 
v := u; initializes all components of v 
IF EVEN(ID(tree)) THEN  moves only the left children's data up thetree
	SEND.parent (u,v)  
END;
Now assume, one does not want to discard information, but one would like to add the left and right child's data before sending to the parent node: 
w := MOVE.parent:#SUM (u);	moves data from both children to the parent,
                           	resolving multiple arriving data by adding

Figure 8 Move without and with reduction

There is a number of system-defined operations to do this reduction, and also user-defined operations may be specified (see section on reduction below).

Configuration boundaries often cause trouble in SIMD programming, for they frequently require special treatment to avoid undefined data. This is not the case for Parallaxis. Here, it is allowed to send data off the edge and try to receive data from beyond the edge of a configuration. Data sent offside a configuration is deleted, while an attempt to read from beyond leaves the particular PE's data unchanged. Therefore, undefined values cannot occur in a data exchange operation.

[ Previous Page | Table of Contents | Next Page ]