1.1.Specifying Virtual Processors and Connections

One or several `virtual machines' consisting of processors and a connection network may be defined for every Parallaxis program. This is done in two simple steps. First, the keyword CONFIGURATION is used to specify the number of PEs and their arrangement in analogy to an array declaration. However, at this point, no specification has been made as to the connection structure between the PEs. This follows by specifying mapping relations, introduced by the keyword CONNECTION (this second step may be omitted if no connections are required). Every connection has a symbolic name and defines a mapping from a PE (any PE) to the corresponding neighbor PE. The specification of this relative neighbor is accomplished by providing an arithmetic expression for the index of the destination PE. Data exchanges can now be carried out using these symbolic connection names in the parallel program.

Figure 1 shows a PE arrangement as a two-dimensional grid structure in a simple Parallaxis example. The CONFIGURATION declaration provides 4 x 5 virtual processors, which are virtually connected to one another in the following CONNECTION declaration In the figure, PE 1,1 is in the upper left corner; however, you may also choose to put the `origin' in the lower left corner - it does not matter as long as you use it consistently in your program. Since homogeneous connection structures or topologies are easy to declare, four connection declarations are sufficient to construct a grid of any size. One connection is defined for each cardinal direction. The connection to the north, for example, decrements the first index. Some connections from the border PEs lead `nowhere', which means that these connections do not exist, and will not participate in any data exchange operation.

CONFIGURATION gid [1..4],[1..5]; 
CONNECTION north:    grid[i,j] ->  grid[i-1,j];
           south:    grid[i,j] ->  grid[i+1,j];
           east :    grid[i,j] ->  grid[i, j+1]; 
           west :    grid[i,j] ->  grid[i, j-1];
Figure 1 Two-dimensional grid topology with representative PE

In case one prefers a wrapped-around torus instead of an open grid for some application, this can be easily accomplished by using the modulo-operator (remainder). Identifiers h and w denote constants: 

CONFIGURATION torus [0..h-1],[0..w-1]; 
CONNECTION north: torus[i,j] ->  torus[(i-1) MOD h, j];
           south: torus[i,j] ->  torus[(i+1) MOD h, j]; 
           east : torus[i,j] ->  torus[i, (j+1) MOD w]; 
           west : torus[i,j] ->  torus[i, (j-1) MOD w];
There is a list of extensions to this simple process of defining virtual machine structures: Connections may be parameterized, as with the hypercube in Figure 2. With these, it is possible to perform a data exchange in a computed direction. For the definition of the binary tree network, also in Figure 2, bi-directional connections (`<->' or `<- >' in ASCII notation) have been used instead of uni-directional connections (`->' or `- >'). A bi-directional connection is an abbreviation for two uni-directional connections and, therefore, requires a second connection name on the right hand side of the connection.

CONFIGURATION  TREE [1..15];
CONNECTION
  lchild:  tree[i] <-> tree[2*i] :parent;
   rchild:  tree[i] <-> tree[2*i+1] :parent; 

CONFIGURATION hyper [0..1],[0..1],[0..1],[0..1];
CONNECTION
go[1]: hyper[i,j,k,l] -> hyper[(i+1)MOD 2, j,k,l]; 
go[2]: hyper[i,j,k,l] -> hyper[i, (j+1)MOD 2,  k,l]; 
go[3]: hyper[i,j,k,l] -> hyper[i,j, (k+1)MOD 2, l]; 
go[4]: hyper[i,j,k,l] -> hyper[i,j,k, (l+1)MOD 2];
Figure 2 Tree and hypercube topology

So-called `compound connections' may be used to have a case distinction inside a connection. The following example connects local pairs of PEs:

CONFIGURATION list  [1..100];
CONNECTION next:  list[i] -> {IDD  (i)} list [i+1],
                             {EVEN(i)} list[i-1];
Figure 3 Compound connections

A case distinction is made for the next connection. If the PE-number is odd, a connection to the right neighbor is established, while if it is even, a connection to the left neighbor is established. Using compound connections, arbitrary connection structures, even with irregularities, may be defined. If several parts of a compound connection evaluate to TRUE for a particular PE, then for this PE all of these connections are defined (one-to-many or 1:n connection).

The connection structures as defined by the CONNECTION declaration do not have to be 1:1 (one-to-one) connections. For 1:n connections, an implicit broadcast is executed. In the following example, the first element of each row is connected to all elements in this row. 

CONFIGURATION grid [1..100],[1..100]; 
CONNECTION one2many: grid[i,1] ->   grid[i,1..100];
If a one-to-many connection is to be established to all PEs of a dimension, the range may be substituted by an asterisk `*'. So the following is equivalent to the previous example. 
CONFIGURATION grid [1..100],[1..100];  
CONNECTION one2many: grid[i,1] ->  grid[i,*];
However, for n:1 (many-to-one) connections (and the general m:n connections, many-to-many) one must ensure that only a single value arrives at any PE's entry port. Therefore, each data exchange operation may include a vector reduction, as will be discussed later. In the following example, all elements of a row are connected to the first element in their column.

CONFIGURATION grid [1..100],[1..100]; 
CONNECTION many2one: grid[i,j] ->  grid[i,1];

Figure4 Multiple connections

[ Previous Page | Table of Contents | Next Page ]