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

Due October 26 at 11:00 pm

Submit via Dropbox, view grades in Gradebook.

System Setup

For this project and the MPI project, you will need to use a virtual machine as outlined here:

Install VirtualBox or other VM software: VirtualBox Download

Install Vagrant: Vagrant Download

Create HW directory

mkdir hw
cd hw
mkdir hw1
cd hw1

Create Vagrant image and start using it

vagrant init hashicorp/precise64
vagrant up
vagrant ssh

Setting up mpi

sudo apt-get update
sudo apt-get install mpi

Files in the /vagrant/ directory of the virtual image will be synced between your host machine and the virtual image.
for instance if you create the file
~/hw/hw1/test.txt
this file will also be located in the virtual image under the path
/vagrant/test.txt
Please note that this is different from the default directory and you will need to switch directories to /vagrant/ after ssh-ing into the machine to ensure your files are synced.

Part A: Parallel Parallel Matrix Multiply

The first portion of the project requires you to implement dense matrix vector multiplication and parallelize it using pthreads. 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 using pthreads. 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:
./pthreads_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.