How to pack matrices

There are various ways to pack up data in a matrix. In the context of project 2, you'll need to worry about how to send a submatrix. Furthermore, you will need to worry about sending several different submatrices within a matrix. Outlined below are 4 ways to approach this: 1) use MPI_Pack/MPI_UnPack, 2) use MPI_Type_vector, 3) use my pack_array/unpack_array routines, or 4) create your own packing routines. Also, I include a description of MPI_Type_indexed for the curious. I suggest using MPI_Type_vector for project 2 just because I think it is the most simple to understand. But read the description for my routines...it might help those of you who are having trouble understanding the concept of this assignment.
  1. MPI_Pack/MPI_UnPack 
         int MPI_Pack ( inbuf, incount, datatype, outbuf, outcount, position, comm )
     void         *inbuf;
     int           incount;
     MPI_Datatype  datatype;
     void         *outbuf;
     int           outcount;
     int          *position;
     MPI_Comm      comm;

     int MPI_Unpack ( inbuf, insize, position, outbuf, outcount, datatype, comm )
     void         *inbuf;
     int           insize;
     int          *position;
     void         *outbuf;
     int           outcount;
     MPI_Datatype  datatype;
     MPI_Comm      comm;
    The high level view of these routines is that you have some data that you want to send to a destination process. This data may consist of different types or they may all be the same type. Basically, you will fill this inbuf with anything you want using MPI_Pack. Then you send it off to the destination process using a send routine (e.g. MPI_Send) and MPI_PACKED as the datatype. The destination process will get the message using a receive routine (e.g. MPI_Recv) and MPI_PACKED as the datatype. Then the destination process will unpack the message using MPI_Unpack. It is extremely important that a process unpack the message in the order that it was packed.

    How to use MPI_Pack/MPI_Unpack to send a submatrix:
    Say you have a 4x4 matrix and you want to send the middle four elements: 
    
int main( int argc, char ** argv )
{
    int m[4][4] = { 5, 5, 5, 5, 5, 4, 4, 5, 5, 4, 4, 5, 5, 5, 5, 5 };
    int n[4][4] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int rank;
    MPI_Status mystatus;
    int i, j;
    char buffer[100];
    int position = 0;

    MPI_Init( &argc, &argv );

    MPI_Comm_rank( MPI_COMM_WORLD, &rank );

    if ( rank == 0 )
    {
        MPI_Pack( &m[1][1], 2, MPI_INT, buffer, 100, &position, MPI_COMM_WORLD ) ;
        MPI_Pack( &m[2][1], 2, MPI_INT, buffer, 100, &position, MPI_COMM_WORLD ) ;
        MPI_Send( buffer, 100, MPI_PACKED, 1, 0, MPI_COMM_WORLD );
    }
    else
    {   
        for (i = 0; i < 4; i++)
        {
            printf("\n" );
            for (j=0; j < 4; j++)
                printf("%i ", n[i][j] );
        }
        MPI_Recv( buffer, 100, MPI_PACKED, 0, 0, MPI_COMM_WORLD, &mystatus );
        MPI_Unpack( buffer, 100, &position, &n[1][1], 2, MPI_INT, MPI_COMM_WORLD);
        MPI_Unpack( buffer, 100, &position, &n[2][1], 2, MPI_INT, MPI_COMM_WORLD);
        printf("\n" );
        for (i = 0; i < 4; i++)
        {
            printf("\n" );
            for (j=0; j < 4; j++)
                printf("%i ", n[i][j] );
        }
    }    
     
    MPI_Finalize( );
    return 0;
}
    So, basically what you can do is pack one row at a time and then send it off. The output looks something like this: 
    
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 

0 0 0 0 
0 4 4 0 
0 4 4 0 
0 0 0 0
  2. MPI_Type_vector 
         int MPI_Type_vector( count, blocklen, stride, old_type, newtype )
     int          count;
     int       blocklen;
     int       stride;
     MPI_Datatype old_type;
     MPI_Datatype *newtype;

     int MPI_Type_commit ( datatype )
     MPI_Datatype *datatype;
    MPI_Type_vector will allow you to send submatrices. In a sense, you are creating a chunk type. Then you commit that chunk type with MPI_Type_commit. So, count is the height of the submatrix or number of rows, blocklen is the width of the submatrix or number of columns, and stride is the width of the matrix.

    How to use MPI_Type_vector to send a submatrix:
    Say you have a 4x4 matrix and you want to send the middle four elements: 
    int main( int argc, char ** argv )
{
    int vector[4][4] = { 5, 5, 5, 5, 5, 4, 4, 5, 5, 4, 4, 5, 5, 5, 5, 5 };
    int wvector[4][4] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    int blocklengths = 2;
    int stride = 4;
    int rank;
    MPI_Datatype mytype;
    MPI_Status mystatus;
    int i, j;

    MPI_Init( &argc, &argv );

    MPI_Type_vector( 2, 2, 4, MPI_INT, &mytype );

    MPI_Type_commit( &mytype );
    MPI_Comm_rank( MPI_COMM_WORLD, &rank );

    if ( rank == 0 )
    {
        MPI_Send( &vector[1][1], 1, mytype, 1, 0, MPI_COMM_WORLD );
    }
    else
    {   
        for (i = 0; i < 4; i++)
        {
            printf("\n" );
            for (j=0; j < 4; j++)
                printf("%i ", wvector[i][j] );
        }
        MPI_Recv( &wvector[1][1], 1, mytype, 0, 0, MPI_COMM_WORLD, &mystatus );
        printf("\n" );
        for (i = 0; i < 4; i++)
        {
            printf("\n" );
            for (j=0; j < 4; j++)
                printf("%i ", wvector[i][j] );
        }
    }    
     
    MPI_Finalize( );
    return 0;
}
    So, the other question is how do you use MPI_Type_vector when you are packing up submatrix and unpacking it into a smaller matrix?
    Basically, this amounts to type matching. So, MPI stores types by: 
    {(t0, d0), (t1, d1), (t2, d2), ..., (tn, dn)}
    where ti is the MPI type and di is the displacement in bytes from the start of the array. The following is referred to as a type signature 
    {t0, t1, t2, ... , tn}
    So, as long as the type signature of any user defined type matches, there is a type match. In the other words, the displacement (or stride) doesn't matter. The following code shows how to pack the 2x2 submatrix above into a 2x2 matrix. 
    int main( int argc, char ** argv )
{
    int vector[4][4] = { 5, 5, 5, 5, 5, 4, 4, 5, 5, 4, 4, 5, 5, 5, 5, 5 };
    int nvector[2][2];
    int blocklengths = 2;
    int stride = 4;
    int rank;
    MPI_Datatype mytype;
    MPI_Datatype wtype;
    MPI_Status mystatus;
    int i, j;

    MPI_Init( &argc, &argv );

    MPI_Type_vector( 2, 2, 4, MPI_INT, &mytype );
    MPI_Type_vector( 2, 2, 2, MPI_INT, &wtype );

    MPI_Type_commit( &mytype );
    MPI_Type_commit( &wtype );
    MPI_Comm_rank( MPI_COMM_WORLD, &rank );

    if ( rank == 0 )
    {
        MPI_Send( &vector[1][1], 1, mytype, 1, 0, MPI_COMM_WORLD );
    }
    else
    {
        for (i = 0; i < 4; i++)
        {
            printf("\n" );
            for (j=0; j < 4; j++)
                printf("%i ", wvector[i][j] );
        }
        MPI_Recv( &nvector[0][0], 1, wtype, 0, 0, MPI_COMM_WORLD, &mystatus );
        printf("\n" );
        for (i = 0; i < 2; i++)
        {
            printf("\n" );
            for (j=0; j < 2; j++)
                printf("%i ", nvector[i][j] );
        }
    }

    MPI_Finalize( );
    return 0;
}
  3. pack_array/unpack_array

    Here are my packing routines that I used only for my manager. Be sure you understand how to use them before you stick them into your program because there is no kind of checking in them...they assume correct inputs.

    The idea behind these routines is that a manager has chunks of work to send to various workers. I order my chunks from 0 to P-1, where P is the total number of chunks such as
    So, each chunk will consist of one or more elements. In order for a worker to be able to compute all of the elements in the chunk, it's going to need the ghostcells as discussed in section. So, the manager will send a chunk plus its ghostcells to an individual worker. This is the idea behind pack_array. Once each worker finishes computing the elements in a chunk, it can send the data back to the manager. But the manager only needs the chunk values (and not the ghostcells), so we send just the chunk values. This is illustrated in the picture below.
    Okay, now the details. 
    void pack_array( int *to_array, int *from_array, int chunk_x, int chunk_y, int width, int height, int num );
    • to_array is the chunk that you'll be sending to the worker. Therefore, it should be of size ( <width of chunk> + 2) * ( <height of chunk> + 2 )
    • from_array is your matrix of image values plus the ghostcells. Therefore, it should be of size ( <width of image> + 2) * ( <height of image> + 2 )
    • chunk_x is the width of our chunk
    • chunk_y is the height of our chunk
    • width is the width of our image
    • height is the height of our image
    • num is the chunk number we want to send 
    void unpack_array( int *to_array, int *from_array, int chunk_x, int chunk_y, int width, int height, int num );
    • to_array is your matrix of image values plus the ghostcells. Therefore, it should be of size ( <width of image> + 2) * ( <height of image> + 2 )
    • from_array is the chunk that you'll be sending to the worker. It doesn't include ghostcells. Therefore, it should be of size ( <width of chunk> ) * ( <height of chunk> )
    • chunk_x is the width of our chunk
    • chunk_y is the height of our chunk
    • width is the width of our image
    • height is the height of our image
    • num is the chunk number we want to send


    If you are wondering about my macro EL_G, here's my explanation. It was easier for me to picture things if I could reference elements within my image matrix (with ghostcells) if I could use the same indices to refer to elements as I would if the image didn't contain ghostcells. So, basically the picture looks something like this:


  4. Create your own routines:

    Don't in anyway feel obligated to use either of these methods. If you want to use something else that you feel is more efficient, go for it. Be creative!