CS 4234 Project 2
Due 11:59 p.m., Wednesday December 10

1. Implement and evaluate the performance of the two matrix multiplication algorithms described in Chapter 11 of Quinn, i.e., the block-row algorithm and Cannon's algorithm.

2. Implement and evaluate the performance of a version of the block-row algorithm that uses non-blocking message passing.

3. Implement and evaluate the performance of a version of Cannon's algorithm that uses non-blocking message passing.

Details:

• Your code(s) should take 3 file names as command-line arguments, e.g.:

    mpirun -np l6 a.out fileA fileB fileC
  

  Your program should compute C = A*B, where the matrices are stored in the corresponding files. Assume C is initially all zero. You only have to read fileA and fileB, and you have to write fileC.

• For the block-row algorithm, your code should work for any number of processors, but you may assume that the number of matrix rows is evenly divisible by the number of processors. For Cannon's algorithm, you may assume the number of processes is a perfect square, and you may assume that the number of matrix rows and columns is evenly divisible by the square root of the number of processors.

• Your code(s) should be robust enough to check for the following simple errors and exit gracefully: wrong number of command-line arguments, fileA or fileB doesn't exist or isn't readable, can't open fileC for writing, dimensions of matrices A and B aren't compatible, number of processes is not a perfect square.

• You should use Quinn's read_row_striped_matrix() to read matrices for the block row algorithm, and read_checkerboard_matrix() for Cannon's algorithm. You should use print_row_striped_matrix() and print_checkerboard_matrix() for printing.

• You can develop and debug your codes anywhere, but you will do the performance evaluation studies on the Anantham (AMD) cluster in Torgersen, beginning December 1.

• Performance evaluation means the following:

  • Traditional (fixed problem-size) parallel speedup. For the block-row algorithm, use p = 1, 2, 4, 8, 16, 32 processors. For Cannon's algorithm, use p = 1, 4, 9, 16, 25, 36 processors. Use 3 different problem sizes that show something interesting.

  • Isogranularity. Report total megaflops (or megaflops/processor) for fixed local problem size. For the block-row algorithm, use p = 1, 2, 4, 8, 16, 32 processors. For Cannon's algorithm, use p = 1, 4, 9, 16, 25, 36 processors. Choose 3 local problem sizes that show something interesting.

• You should use the recursive block matmul described in Quinn for the block matrix multiplies. You may modify this code to meet your needs, e.g., by making a, b, and c parameters. Use THRESHOLD=10000.

• You must prepare a report summarizing your performance results and with a brief discussion of these results. You do not have to turn in hardcopies of your programs. However, you should email your source files to Dr. Ribbens by the deadline given above. We prefer a single attachment containing all the files, tar'd and gzip'd, e.g., attach proj2.tgz created by:

  tar czf proj2.tgz Makefile blockrow.c cannon.c blockrow_nonblocking.c cannon_nonblocking.c