CSEP 524 Autumn 2016 - Parallel Computation (PMP) - Project 4

Due December 12 at 11:00 pm

Submit via Dropbox, view grades in Gradebook.

System Setup

For this assignment we would prefer if you used Spark or Disco, but we will accept assignments written in other Map/Reduce frameworks.

Part A: Parallel Parallel Matrix Multiply

The first portion of the project requires you to implement dense matrix vector multiplication and parallelize it. Your program should take as input a file containing the matrix and vector to be multiplied. The program should write out the solution vector into a file.
Here is an example input file: Input File. The first line of this file contains the matrix dimensions (in this case the matrix is 64x64). The next 64 lines are then the 64 rows of the matrix. The 64 lines following the matrix rows each contain one integer corresponding to the values of the input vector. With this example case, your output file would have 64 lines, with each line containing one integer corresponding to the values of your result vector.

Part B: Parallel Breadth First Search

The second portion of the project requires you to implement breadth first search and parallelize it. Your program should take as input a binary file describing the graph and a root node. Each edge is described in the file as a pair of 64 bit integers.
Here is an example binary graph input file: Input File.
Your Program should run as follows:
./mpi_bfs <input file> <root node>
Your program will return the following statement: Graph vertices: <vertices> with total edges <edges>. Reached vertices from <root> is <reached_vertices> and max level is >max_level>.
Here is a sequential version of BFS. You should just parallelize the BFS portion of the code. BFS Sequential
Graph Generator Code if you would like to test your code on other input sizes. Generator is located in generator directory, after running make, run:
./generator_test_seq log_size filename

Both portions of this homework should be turned in with your source code for that portion, a Makefile and a README explaining the expected behavior and output of the programs.
For example for the parallel BFS, the files you turn in should be something along the lines of bfs.c, Makefile, and README.