CSC 145 Final Assignment: Solving a PDE


For the final assignment, I've decided to give you an easier
alternative to the program I first described.  Instead of arranging
the processors into an efficient 2D mesh, you can just use a 1D
configuration.  That is, the matrix can be sliced into equal portions
like in the matrix-multiplication program.  You are still encouraged
to do the mesh version, because otherwise you may end up feeling
inferior all your life :(

*********************************
You can either work in groups of two or three.  IF YOU WORK IN A GROUP OF
THREE, YOU MUST CHOOSE THE MESH VERSION.
*********************************
   

On the homepage (or in /home/beowulf/liang2) you will find the following files:

  for the MESH version:  mesh.h, meshskl.c
  for the SLICE version: slice.h, sliceskl.c

In addition, download "threed.c" for the 3D graphical routines that I
built on top of MPE.  You should read the description of the mesh version
even if you don't intend to do it, because the slice version is just
a simplification of the mesh version, and inherits many of the same
attributes.

To compile these programs, do not use mpicc, but use the alias "mpecc",
as in

  mpecc mesh.c -o mesh

The definition of mpecc can be found in /home/beowulf/.bashrc - it's just
mpicc with certain addtional libraries.

When running a mpe program, use only one machine: -machinefile 
/home/beowulf/host1, when using graphical visualization.


  ===============================================================

1. Understanding the .h file:

It is crucial that you familiarize yourself with what's already inside
mesh.h (or slice.h):

Macros:

   EPSILON : the threshold at which two double values are considered
   equal.  That is, a and b are considered equal if |a-b|<EPSILON

   The algorithm (all worker processes) stop when the matrix stops
   changing, where "change" is defined by EPSILON.

   N: The size of the data-portion of the matrix.  The size of the
      entire matrix is (N+2) by (N+2).  The first and last rows/columns
      are pre-defined and do not change throughout the program.

   P: There are P*P worker processes plus 1 coordinator/master process.

   M: set to 2+(N/2), for the mesh, intended for use by 2x2 mesh.  
      It indicates the size of a quadrant of the matrix that each
      worker is responsible for, including the "ghost vectors" (first
      and last rows/columns).  For the slice version, M is (N/4)+2, 
      which assumes that there will be four slices.

      HOWEVER, YOUR CODE NEED TO BE SCALABLE: it should be simple to
      use a 3x3 or 4x4 mesh instead.


   NORTH,SOUTH,EAST,WEST,SND,RCV are just convenient names that allow
   easy access into vectors.

Data variables:

   Data:  This array will only be used by the master process and will
   represent the entire N+2xN+2 array.  The array itself will only
   be created by the master.

   Q, R:  these are the "work arrays" used by your worker process.

     Initially, data is sent to Q.  As you make a new round of 
     calculations, the results are stored into R.  That is,

     for each i,j:
        R[i][j] = (Q[i-1][j]+Q[i+1][j]+Q[i][j-1]+Q[i][j+1]) * 0.25;

     After each round, the POINTERS Q and R should be swapped.  

   WORKERS, MESH:

     These are communicators.  The WORKERS communicator is
     MPI_COMM_WORLD minus the master process.  The MESH communicator
     is WORKERS rearranged into a mesh.  The slice version need only
     use WORKERS, whereas the mesh version will use MESH.

   QUAD,COLUMN: 

     User-defined MPI datatypes for non-contiguous data.  QUAD is one
     MxM quadrant within the larger matrix.  COLUMN is one column
     (including ghost cells) within one submatrix.

   mycoord:  
     a vector of two integers, y,x that indicates the
     coordinates of your worker process within the MESH.  The
     macros YCORD, XCORD provide symbolic access.  For the slice
     version, this is replaced by a simple mrank variable.

   locate: 

     This 2x2 matrix plays an important if subtle role.  When a worker
     communicates with the master process, they must still use the
     MPI_COMM_WORLD communicator, and therefore needs to know
     eachother's rank within this communicator.  For example, if the
     master wants to send something to process 1,0 in mesh, it
     still needs to know the rank of this process relative to COMM_WORLD.
     In this situation, locate[1][0] will contain this value.  It
     stores the COMM_WORLD-rank of each mesh process.  This matrix
     is setup at the start by the functions "registercoord" (called 
     by worker) and "registerworkers" (called by master).

     For the slice version, locate becomes a 1D array.

   CVN

     This number (default 40) is the number of rounds of computatations
     before a "convergence vote".  EVERY worker must agree to stop before
     the whole program stops.  A worker votes to stop if it nolonger
     observes any changes (defined by EPSILON) in its submatrix.  To 
     conduct the vote, use MPI_Allreduce with operation MPI_LOR.
     The difference between MPI_Allreduce and MPI_Reduce (which you
     used for the prime number program) is that every process, not
     just the root, is given the result of the operation.  

     If graphics are being used, the CVN is also the number of rounds
     between display updates.  Note if graphics are being used, then
     each process must send its entire sub-matrix back to the master
     after every CVN loops.  Otherwise, the sub-matrices are only sent
     back after convergence.  Study the master() function carefully
     to undertand what it expects from the workers.

   ------

   There are a number of constants and variables related to graphics
   
   GRAPHICS - 1 for yes, 0 for no.  Use only one physical processor
   when using graphics.

   rotation - angle of view.  not all values will give you good results
   however.

   mousesynch - if 1, requires mouse click between display udpates.


  =================================================================   


2.  The master-worker protocol:

   When master and worker seperates in main, master calls master(),
   which I wrote, and worker calls worker(), which you will complete.

   The master does the following, which the worker needs to mirror:

     call registerworkers, which sets up the locate[][] matrix.

     creates and generates Data matrix, and send each quadrant/slice
     to workers.

     Loop until all workers vote to stop:

          Call Allreduce,
          if (GRAPHICS), receive quadrants from each process and
          reconstructs the Data matrix, carefully factoring out
          the ghost vectors (alternativelly, you can elect not to
          send the ghosts back to the master, but programming this
          option will be tricky).

     When convergence is reached, the master expects workers to send
     it their submatrices one more time (if graphics is not beging used).

  =================================================================   

3. Worker to Worker communication.

   The most important and trickiest part of the assignment is to setup
   the communication between workers. For both the mesh and slice versions,
   you need to use asynchronous communications and the MPI_Send_init,
   MPI_Recv_init, and MPI_Startall/Waitall commands.  

   Each Send/Recv_init requires a pointer to an MPI_Request structure.
   This structure is also needed when calling Startall/Waitall.  

   I suggest the following 3D matrix of requests:

     MPI_Request req[2][2][4];

     The first coordinate determines if the Q or R matrix should be
     the src/dest of the communication.

     The second coordinate can determine if it's a send or receive
     operation.  

     The third coordinate indicates which of the up-to 4 directions
     the communication is to take place. (please remember that not
     all process will have 4 neighbors).  This number should be
     reduced to 2 for the slice version.

     For example,  if ms is the number of neighbors of your worker
     process,  then,

     MPI_Waitall(ms,req[active][SND],stat);

     will wait for all send operations to complete, where the current
     active matrix is determined by the variable active (which flips
     between 0 and 1).  

  Before your main worker loop starts, you need to call MPI_Send/Recv_init
  to set up all the communications that are going to take place, and
  associate each with the appropriate request object, for example:

    // send last row of Q to south neighbor
    MPI_Send_init(Q[M-2],M,MPI_DOUBLE,srank,SOUTH,MESH,&req[0][SND][ms]);
    ...
    // Recv ghost vector from north neighbor:
    MPI_Recv_init(Q[0],M,MPI_DOUBLE,nrank,SOUTH,MESH,&req[0][RCV][ms]);

  Note that srank is the rank of the south neighbor, whereas SOUTH
  is the used as the TAG of this communication.  Your south neighbor
  should also Recv by from you (it's north neighbor) using the same tag.
  Be careful that you don't create deadlock, which is REALLY easy to do
  with this program!  Also remember that not everybody has a north
  neighbor!.

  After setting up the communication threads, the worker will
  repeatedly run in a loop where it 

     initiate communications 
     wait for receives to complete:

     computes the values for its matrix (but do not change the
     ghost vectors)

     wait for send to complete

     swap Q and R pointers.

     You can also be clever by trying to maximize asynch work by
     starting the computation part before the ghost vectors are received.
      
If you're stuck, see professor and get him to show you his code :)

------------------------------------------------

Other hints and points to watch out for:

   1. When first receiving the submatrix, copy the ghost vectors
      to the R matrix as well (intially it's only sent to the Q matrix).

   2. When receiving a quadrant (mesh version) from the root, the
      send operation uses the user-defined type QUAD.  However, the
      recieve operation will need to receive into a contiguous array (Q).

   3. use a variable "active" to keep track which is the current
      active matrix.  Also, don't get confused by the pointers Q and R
      and the matrices.  For example, Q can always point to the
      "active matrix", but the Q and R pointers should be swapped after
      each round of averages.

   3. Use a variable to keep track of how many neighbors your process
      needs to exchange ghost vectors with.  This value is needed in
      the Startall/Waitall commands.