laser.mpi.util.shuffle
Class TranspositionShuffler

java.lang.Object
  |
  +--laser.mpi.util.shuffle.Shuffler
        |
        +--laser.mpi.util.shuffle.TranspositionShuffler

public class TranspositionShuffler

extends Shuffler

A TranspositionShuffler provides functionality to move around elements of a distributed array using MPI. The context is as follows: each process in an MPI communicator has a local array which we will call localData. The user wishes to move these elements around, within and between processes. To do this, the user provides a map which tells precisely what is to be moved where. The map is specified using "coordinates." A coordinate is a pair of integers (proc, locPos), where proc is the process ID (or "rank" in MPIese), and locPos is the index in the localData array on proc. The map then consists of a list of pairs (source, target) of coordinates. The source is the coordinate for the item one wishes to move, and target is the coordinate for the position one wishes to move it to.

The relation defined by the map must be an injective function. For we do not allow one to move an item to two different locations, nor do we allow moving two distinct items to the same location. However, it is not required that the function be defined on the entire domain (i.e., on all possible coordinates), nor is it required that the function be onto. Therefore, it is possible to move an item from position p to position q, but not to move anything to position p. In this case, the data at position p will not be erased---it will still remain there, along with another copy at position q.

This is a concrete class extending the abstract class Shuffler. The algorithm defined here (described below) is very simple, but uses more Sends and Receives than are required. See the CycleShiftShuffler for an algorithm which minimizes the number of sends and receives.

The usual way to use this class is to invoke the static method shuffle. Every proc in the communicator must invoke this method, and with the same map.

This class has been written using the mpiJava package. You must have mpiJava installed to compile and execute this class. If .../mpiJava/lib/classes is in your CLASSPATH you should be able to compile this class normally using javac. To execute from the command line you say, for example, "prunjava 4 laser.mpi.util.shuffle.TranspositionShuffler". prunjava is a script which comes with mpiJava, and I am assuming it is in your PATH. This executes some tests which are in the test suite. The 4 means to create 4 procs. You can use any positive integer you want in place of 4, and the tests should all pass. For each test, you will see the map, the localData arrays before shuffling, and the localData arrays after shuffling. If everything comes out as expected, this is all you will see. If anything goes wrong, you will also get a message telling you what went wrong. If this happens, please email me with a bug report.

The algorithm: the basic idea is the following. First, one enumerates, using the integers 0,1,...,n-1 all the coordinates which occur as sources or targets in the map. In this enumeration, each coordinate occurs precisely once. Now we rewrite the map as a function from a subset of X={0,1,...,n-1} (the domain) to X. To do this we use a constant called UNDEFINED, and we represent the map as an array of length n with elements in X+{UNDEFINED}. We call this array p.

Now we construct an array q which is just the inverse of p. Hence the domain of p is the range of q, and the range of p is the domain of q, and, for all i in the domain of p and all j in the domain of q: p[i] == j iff q[j] == i.

Now, p and q will both be changing during reordering, but at each stage we will maintain the inverse relationship described above.

The algorithm essentially involves realizing the map as a product of transpositions. If the map were an actual permutation (i.e., if p were defined on all of X), then this is exactly what would happen. However, some care must be taken for the undefined values.

The easiest way to describe the algorithm is just to give the body of the reoder method:

      for (int i = 0; i < p.length; i++) {
          int j = q[i];
          int k = p[i];

          if (j == UNDEFINED) {
              if (k != UNDEFINED) {
                  int i2 = k;

                  k = p[k];
                  while (k != UNDEFINED) {
                      i2 = k;
                      k = p[k];
                  }
                  j = q[i2];
                  while (j != UNDEFINED) {
                      copyData(i2, j);
                      p[i2] = i2;
                      p[j] = UNDEFINED;
                      q[i2] = i2;
                      i2 = j;
                      j = q[j];
                  }
              }
          }
          else {
              p[i] = i;
              p[j] = k;
              if (k == UNDEFINED) {
                  copyData(i, j);
              }
              else {
                  switchData(i, j);
                  q[k] = j;
              }
              q[i] = i;
          }
      }
 

The idea is that, after each iteration through the outermost loop, the localData will have the correct values for global positions 0,...,i. The complexity of the j = UNDEFINED case is for dealing with "shifts", in which case one must search backwards for the beginning of the shift.

This performs, in the worst case 2n sends and 2n receives. This is really twice as many as is needed: the more complicated CycleShiftShuffler performs at most n sends and n receives.

Field Summary

private Coordinate[]	coordinates An array containing all the coordinates which occur as a source or target in map.
private int[][]	indices An array of length nProcs of arrays of ints.
private int[]	p This is the map, using the global indices instead of coordinates.
private int[]	q This is simply the inverse of p.
static int	UNDEFINED A constant used to represent an undefined value for the functions p or q.

Fields inherited from class laser.mpi.util.shuffle.Shuffler

debug, nSendrecvs, nSends

Constructor Summary

TranspositionShuffler()
Constructs a trivial instance of this class.

TranspositionShuffler(java.lang.String name, mpi.Intracomm comm, int tag, Mapping[] map, java.lang.Object[] localData)
Constructs a new instance of this class with the given name, communicator, tag, map and localData.

Method Summary

(package private) void	copyData(int i, int j) Copies the locaData entry at global index j to the localData entry with global index i.
static void	main(java.lang.String[] args) This simply executes a number of tests described in the test cases.
Shuffler	newInstance(java.lang.String name, mpi.Intracomm comm, int tag, Mapping[] map, java.lang.Object[] localData) Creates a new instance with the given name, communicator, tag, map and localData.
void	printState(int rank)
void	reorder() This is the main method which carries out the reordering.
static void	shuffle(mpi.Intracomm comm, int tag, Mapping[] map, java.lang.Object[] localData) This is the main static method which is the usual way for using this class.
(package private) void	switchData(int i, int j) Exchanges the localData with global indices i and j.

Methods inherited from class laser.mpi.util.shuffle.Shuffler

addSends, comm, debug, debug, globalNumSendrecvs, globalNumSends, lengths, localData, map, myAssert, myRank, name, nProcs, nSendrecvs, nSends, printArray, printLocalData, printMap, tag

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

UNDEFINED

public static final int UNDEFINED

A constant used to represent an undefined value for the functions p or q.

See Also:

Constant Field Values

indices

private int[][] indices

An array of length nProcs of arrays of ints. This array is built up using the information provided by map. The i-th element of this array is an array of length lengths[i]. The j-th element of that array is a unique integer (the "index") corresponding to the coordinate (i,j) (i.e., position j of localData on proc i).

coordinates

private Coordinate[] coordinates

An array containing all the coordinates which occur as a source or target in map. Each such coordinate occurs exactly once in this list. The position at which a coordinate occurs in this array is called its "index".

p

private int[] p

This is the map, using the global indices instead of coordinates. It means: move the data with global index i to position with global index p[i]. For those positions i for which there is no move, the value of p[i] will be UNDEFINED. By the domain of p, we mean the set of all i such that p[i] is not UNDEFINED. By the range of p, we mean the set of all integers of the form p[i] for some i in the domain of p. Notice that p will be changed in the process of reordering.

q

private int[] q

This is simply the inverse of p. I.e., the domain of q is the range of p, and the range of q is the domain of p, and for all i in the domain of p and all j in the domain of q: p[i] == j iff q[j] == i. Notice that q will be changed during reordering, but at each stage it will be the inverse of p.

Constructor Detail

TranspositionShuffler

public TranspositionShuffler(java.lang.String name,
                             mpi.Intracomm comm,
                             int tag,
                             Mapping[] map,
                             java.lang.Object[] localData)
                      throws mpi.MPIException

Constructs a new instance of this class with the given name, communicator, tag, map and localData. Keep in mind that each proc in the MPI system must create its own instance of this class, and when they do so they should all provide the same map. It is the user's responsibility to make sure this is so, or else anything could happen!

This constructor checks the map to make sure it defines an injective function and that there are no references into localData which exceed the length of that array. It also constructs the lengths array, and the indices array, and the permutation arrays p and q.

Parameters:

name - a name to be given to this Shuffler

comm - the MPI communicator to be used for all MPI calls

tag - the MPI tag to be used for all MPI communication

map - the array of Mappings describing how to shuffle the data

localData - the local data array for this proc

Throws:

mpi.MPIException - if an MPI call goes awry

java.lang.IllegalArgumentException - if name, comm, map, or localData is null, or if tag == MPI.ANY_TAG

TranspositionShuffler

public TranspositionShuffler()
                      throws mpi.MPIException

Constructs a trivial instance of this class.

Method Detail

shuffle

public static void shuffle(mpi.Intracomm comm,
                           int tag,
                           Mapping[] map,
                           java.lang.Object[] localData)
                    throws mpi.MPIException

This is the main static method which is the usual way for using this class. The user provides the communicator, tag, map, and the localData, and upon return the data will be moved around according to the instructions in the map. This method is to be called by all procs in the communicator, and with the same map and communicator, (although obviously with different localDatas).

It is best to choose a tag which is not being used by other program components.

Parameters:

comm - The MPI communicator

tag - the MPI tag to be used for all MPI communication in this class

map - the array of Mappings telling what is to be moved where

localData - the local data array for this proc

Throws:

mpi.MPIException - if an MPI call goes awry

java.lang.IllegalArgumentException - if name, comm, map, or localData is null, or if tag == MPI.ANY_TAG

main

public static void main(java.lang.String[] args)
                 throws mpi.MPIException

This simply executes a number of tests described in the test cases.

Parameters:

args - the command line arguments

Throws:

mpi.MPIException - if an MPI call goes awry

newInstance

public Shuffler newInstance(java.lang.String name,
                            mpi.Intracomm comm,
                            int tag,
                            Mapping[] map,
                            java.lang.Object[] localData)
                     throws mpi.MPIException

Creates a new instance with the given name, communicator, tag, map and localData. Keep in mind that each proc in the MPI system must create its own instance of this class, and when they do so they should all provide the same map. It is the user's responsibility to make sure this is so, or else anything could happen!

This method check the map to make sure it defines an injective function and that there are no references into localData which exceed the length of that array.

Specified by:

newInstance in class Shuffler

Parameters:

name - a name to be given to this Shuffler

comm - the MPI communicator to be used for all MPI calls

tag - the MPI tag to be used for all MPI communication

map - the array of Mappings describing how to shuffle the data

localData - the local data array for this proc

Throws:

mpi.MPIException - if an MPI call goes awry

java.lang.IllegalArgumentException - if name, comm, map, or localData is null, or if tag == MPI.ANY_TAG

printState

public void printState(int rank)

reorder

public void reorder()
             throws mpi.MPIException

This is the main method which carries out the reordering.

Specified by:

reorder in class Shuffler

Throws:

mpi.MPIException - if the MPI calls go awry

switchData

void switchData(int i,
                int j)
          throws mpi.MPIException

Exchanges the localData with global indices i and j.

Parameters:

i - the global index of one of the coordinates

j - the global index of the other coordinate

Throws:

mpi.MPIException - if the MPI calls go awry

copyData

void copyData(int i,
              int j)
        throws mpi.MPIException

Copies the locaData entry at global index j to the localData entry with global index i.

Parameters:

i - the global index of the datum to be copied

j - the global index of the position to which it is to be copied

Throws:

mpi.MPIException - if the MPI calls go awry