For example, each component of a two-dimensional vector (a matrix) is to be sent to a destination address, which is being computed at run-time. When only structured data exchange, e.g. via a grid, is possible, one has to program a communication procedure, which shifts the matrix elements in several steps over the grid. This approach will work, however, some parallel computer systems (like the MasPar MP-1 and MP-2 [MasPar 91] and the Connection Machine CM-2 [Thinking Machines 89]) have a global connection structure, which allows an arbitrary unstructured data exchange. In this case, specifying direct destination addresses for each component of a vector variable may result in a faster program. Please note, that despite the availability of specialized commands for unstructured data exchange, execution of those may be quite expensive. For example, a grid operation at the MasPar MP-1 requires about the same time as a simple arithmetic operation (addition), but a non-grid data exchange takes about 100 times longer to execute. Please note that the unstructured data exchange is nevertheless a machine-independent operation. If a certain SIMD architecture does not provide a general communication structure, then this data exchange will be routed transparently over the simpler network provided (e.g. a grid or a ring) taking several execution steps.
In Parallaxis, the SEND and the RECEIVE operations may take an index expression instead of a connection name. As before, when using SEND, only active PEs send data, and when using RECEIVE, only active PEs receive data. However, these two operations differ in their index semantics, as is shown for an example in Figure 9. In order to avoid confusion, operation MOVE may not be used with an index expression.
VAR x,y,index: grid OF INTEGER;
...
| SEND.<<index>>(x,y); | sends data from all components of x a to destination, determined by vector index |
| y := RECEIVE.<<index>>(x); | receives data from all components of x to a
destination, determined by vector index, however, on the receiver's side |
| SEND.<<index>> (x,y) ; | y := RECEIVE.<<index>> (x) ; |
Figure 9 Unstructured data exchange
Besides using a single index, referring to the ID position of PEs, several indices referring to DIM positions may be used as well. Also, this kind of data exchange does not have to be a one-to-one correspondance. If several indices refer to the same PE position, for RECEIVE (one-to-many) this results in a broadcast, while for SEND (many-to-one) an arbitrary component is selected -unless a reduction operation is specified for resolving collisions.
CONFIGURATION grid [1..2],[1..3];
VAR x,y, index,d1,d2: grid OF INTEGER;
...
| SEND.<:d2,d1:> (x,y); | sends data from all components of x to a
destination, determined in the first dimension by d1, and in the second dimension by d2 |
SEND.<<index>>:#SUM (x,y); in case the expression index does notprovide a 1:1 permutation, it may be desirable to perform a reduction of multiple values arriving in one port, in order to avoid the assignment of an arbitrary one of
these; positions not indexed get the sender's original elements
Two kinds of abbreviations are possible for data exchanges with index expressions:
a) If the positions in one dimension are to remain unchanged, one should use the expression DIM(conf_name, dim_no) as an index. This may be abbreviated with the symbol `*'.
SEND.<:DIM(grid,2),d1:> (x,y) ; is equivalent to:
SEND.<:*,d1:> (x,y) ;
b) If a dimension is to be collapsed, a many-to-one data exchange may be used in combination with a reduction. For example, a matrix may be collapsed to a single column by reducing all of its rows. This can be done by sending all row elements to the first element in the same row with a reduction operation. This may be abbreviated by using a reduction operation (e.g. #SUM) instead of an index expression.
| SEND.<:d2,1:> :#SUM (x,y); | is equivalent to the general: |
| SEND.<:d2,LOWER(grid,1):> :#SUM (x,y); | is equivalent to: |
| SEND.<:d2,#SUM:> (x,y); | dimension 1 is reduced by addition (rows accumulate data in their first positions) with permutation in dimension 2 according to d2 |
If different reductions are used instead of indices in the same data exchange operation, these are executed subsequently from right to left (that is, starting with the lower dimension).
SEND.<:#MIN,#SUM:> (x,y);
