laser.mpi.util.shuffle
Class Shuffler

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

Direct Known Subclasses:

CycleShiftShuffler, TranspositionShuffler

public abstract class Shuffler

extends java.lang.Object

A Shuffler 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 an abstract class which provides some basic functionalitiy common to any Shuffler. A concrete class will have to define the reorder method which does the main work. The other abstract method here is newInstance which should just be defined to return a new instance of the concrete class.

Field Summary

private mpi.Intracomm	comm The communicator in which the reordering is to take place.
static boolean	debug The debugging flag.
private int	globalNumSendrecvs
private int	globalNumSends
private int[]	lengths An array of length nProcs.
private java.lang.Object[]	localData This is the array which contains this proc's portion of the data.
private Mapping[]	map An array of Mappings.
private int	myRank The rank (ID) of this process.
private java.lang.String	name A name for this Shuffler, which is especially useful for debugging.
private int	nProcs The total number of processes.
protected int	nSendrecvs The total number of Sendrecvs that were executed.
protected int	nSends The total number of sends (including those that were part of a Sendrecv) executed in the course of reordering.
private int	tag This is the tag that will be used for all of the MPI communication in this class.

Constructor Summary

protected	Shuffler(java.lang.String name) Constructs a trivial instance of this class.
protected	Shuffler(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

void	addSends() Adds up the global number of Sends and Sendrecvs that have taken place.
mpi.Intracomm	comm() Returns the MPI communicator, comm.
void	debug(int proc, java.lang.String s) Same as debug, but only prints the message if proc == myRank (and debug == true).
void	debug(java.lang.String s) If debug == true, prints the given message to stdout along with the proc ID (rank).
int	globalNumSendrecvs()
int	globalNumSends()
int[]	lengths() Returns an array lengths of length nProcs.
java.lang.Object[]	localData() Returns the localData array for this proc.
Mapping[]	map() Returns the map, which is array of Mapping telling exactly what is to be moved where.
(package private) void	myAssert(boolean b) My cheap assertion checker.
int	myRank() Returns the rank (i.e., process ID) of this process.
java.lang.String	name() Returns the name of this Shuffler.
abstract 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.
int	nProcs() Returns the number of processes in the system.
int	nSendrecvs() Returns the total number of local Sendrecvs that were executed.
int	nSends() Returns the total number of local sends (including those that were part of a Sendrecv) executed in the course of reordering.
(package private) static void	printArray(java.io.PrintStream out, java.lang.Object[] array) A utility method for printing out the elements of an array.
void	printLocalData(java.io.PrintStream out) Prints out the given state of all the localData arrays to the given PrintStream.
void	printMap(java.io.PrintStream out) Prints out a readable view of the map on proc 0 to the given PrintStream out.
abstract void	reorder() This is the main method which carries out the reordering.
int	tag() Returns the MPI tag, tag.

Methods inherited from class java.lang.Object

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

Field Detail

debug

public static final boolean debug

The debugging flag. Set this to true and recompile and get lots of messages sent to stdout.

See Also:

Constant Field Values

nProcs

private int nProcs

The total number of processes.

myRank

private int myRank

The rank (ID) of this process. It lies between 0 and nProcs-1 (inclusive).

comm

private mpi.Intracomm comm

The communicator in which the reordering is to take place. Example: MPI.COMM_WORLD.

tag

private int tag

This is the tag that will be used for all of the MPI communication in this class. The user provides the tag. It is probably a good idea if this tag is not used elsewhere. The tag cannot be MPI_ANY_TAG!

map

private Mapping[] map

An array of Mappings. This is the main information provided by the user. Each Mapping gives a coordinate for a source location and a coordinate for the target location. This means: move the datum at source to target. It should be the case that this map is injective; if not, an exception will be thrown. This is the global map, meaning that it should contain all the maps for all procs. It should be the same on all procs.

lengths

private int[] lengths

An array of length nProcs. For each proc p, lengths[p] gives the maximum position to occur for proc p in map (as a source or target), plus 1. It had better be the case that localData has length at least lengths[myRank], else an exception will be thrown.

localData

private java.lang.Object[] localData

This is the array which contains this proc's portion of the data. Note: the elements of this array must implement java.io.Serializable, or else javaMpi will not be able to send and receive them. The elements could be instances of Integer, or Float, or they could be instance of int[] or float[], for example.

name

private java.lang.String name

A name for this Shuffler, which is especially useful for debugging.

nSends

protected int nSends

The total number of sends (including those that were part of a Sendrecv) executed in the course of reordering.

nSendrecvs

protected int nSendrecvs

The total number of Sendrecvs that were executed.

globalNumSends

private int globalNumSends

globalNumSendrecvs

private int globalNumSendrecvs

Constructor Detail

Shuffler

protected Shuffler(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.

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

Shuffler

protected Shuffler(java.lang.String name)
            throws mpi.MPIException

Constructs a trivial instance of this class. The communicator will be MPI.COMM_WORLD, the tag 0, the mapping will be empty (have length 0), and the localData will be an array of length 0 of Object.

Parameters:

name - the name to give this trivial instance

Method Detail

printArray

static void printArray(java.io.PrintStream out,
                       java.lang.Object[] array)

A utility method for printing out the elements of an array. The elements are separated by a single space.

Parameters:

out - The PrintStream where the output should be sent

array - the array to print

newInstance

public abstract 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 should 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.

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

comm

public mpi.Intracomm comm()

Returns the MPI communicator, comm.

Returns:

the MPI communicator, comm.

tag

public int tag()

Returns the MPI tag, tag.

Returns:

the MPI tag, tag.

map

public Mapping[] map()

Returns the map, which is array of Mapping telling exactly what is to be moved where.

Returns:

map

lengths

public int[] lengths()

Returns an array lengths of length nProcs. For each proc p, lengths[p] gives the maximum position to occur for proc p in map (as a source or target), plus 1. It had better be the case that localData has length at least lengths[myRank], else an exception will be thrown. The array is constructed during in the constructor, and it is used durring shuffling.

Returns:

lengths

localData

public java.lang.Object[] localData()

Returns the localData array for this proc.

Returns:

the localData array for this proc.

nProcs

public int nProcs()

Returns the number of processes in the system.

Returns:

the number of processes in the system.

myRank

public int myRank()

Returns the rank (i.e., process ID) of this process.

Returns:

the rank of this process.

name

public java.lang.String name()

Returns the name of this Shuffler.

Returns:

the name of this Shuffler.

nSends

public int nSends()

Returns the total number of local sends (including those that were part of a Sendrecv) executed in the course of reordering.

Returns:

the total number of local sends executed

nSendrecvs

public int nSendrecvs()

Returns the total number of local Sendrecvs that were executed.

Returns:

the total number of local Sendrecvs that were executed

globalNumSends

public int globalNumSends()

globalNumSendrecvs

public int globalNumSendrecvs()

printMap

public void printMap(java.io.PrintStream out)

Prints out a readable view of the map on proc 0 to the given PrintStream out. If myRank != 0, this returns without doing anything.

Parameters:

out - the PrintStream to which to print the map.

printLocalData

public void printLocalData(java.io.PrintStream out)
                    throws mpi.MPIException

Prints out the given state of all the localData arrays to the given PrintStream. It starts with proc 0, then proc 1, ..., to proc nProcs-1. This is accomplished by having all the procs with rank greater than 0 send their entire localData to proc 0, who receives them all in the correct order and prints them out. For this to work, all the procs in the communicator must call their copy of this method.

Parameters:

out - the PrintStream

Throws:

mpi.MPIException - if something goes awry in the MPI calls

addSends

public void addSends()
              throws mpi.MPIException

Adds up the global number of Sends and Sendrecvs that have taken place. Each proc sends its local information to proc 0, who adds them up and stores the results in the fields globalNumSends and globalNumSendrecvs.

Throws:

mpi.MPIException - if something goes awry in MPI

reorder

public abstract void reorder()
                      throws mpi.MPIException

This is the main method which carries out the reordering.

Throws:

mpi.MPIException - if the MPI calls go awry

debug

public void debug(java.lang.String s)

If debug == true, prints the given message to stdout along with the proc ID (rank).

Parameters:

s - The message to print

debug

public void debug(int proc,
                  java.lang.String s)

Same as debug, but only prints the message if proc == myRank (and debug == true). Otherwise does nothing.

Parameters:

proc - the rank of the proc which is to print a message

s - the message to print

myAssert

void myAssert(boolean b)

My cheap assertion checker. If b is true, this returns and does nothing. Otherwise, it prints a message saying what myRank is and that an assertion has been violated.

Parameters:

b - the boolean condition

Throws:

java.lang.RuntimeException - if b is false.