CS 385 Homework 2, Spring 2013

Links: [Course Home] [Schedule] [Moodle]

Due Tuesday, Feb. 19 at 10:45 AM. No late submissions accepted.

Instructions

Complete the following problems. In order to receive credit, you must show enough work to make it clear how you arrived at your answer.

For written solutions, you may submit your assignment via hard copy (in class or office hours) or as a PDF or .doc/.docx/.txt via Moodle. If you do submit via Moodle, it is your responsibility to verify that your submitted file is correctly formatted. Corrupted or unreadable files will not receive any credit.

For code submissions, please submit your source file(s) via Moodle. If you have more than once source file, please include a makefile.

You may work in groups of up to three students and turn in one solution for the group. Make sure that all group members' names are on all submitted documents.

Short answer [20 points]

1. [15 points] Problem 3.6 (all parts), Pacheco pp. 140-141
2. [5 points] Problem 3.16, Pacheco p. 143

MPI programming [50 points]

Turn in an MPI program that implements Programming Assignment 3.2 (pp. 147-148) in the textbook, with the following additional specifications:

Getting Started

These directions assume that you will be using cwolf. You are welcome to use some other system, but you're on your own with the MPI installation.

Add the following lines to the .bash_profile (notice the dot) file in your home directory on cwolf:

alias mpicc=/usr/lib64/openmpi/bin/mpicc
alias mpiexec=/usr/lib64/openmpi/bin/mpiexec

Then type

source ~/.bash_profile

followed by

which mpiexec

You should see something like

alias mpiexec='/usr/lib64/openmpi/bin/mpiexec'
	/usr/lib64/openmpi/bin/mpiexec

Copy an MPI "Hello World" program (from your textbook or elsewhere) and compile it:

mpicc -o hello.out hello_world.c

Run it with 4 processes:

mpiexec -n 4 ./hello.out

Getting the user's input

Process 0 should ask the user for the number of throws to simulate and then broadcast that answer to the other processes.

Define a function

long long int get_input(int my_rank, int size)

The simulation

Next, implement the simulation code. Some cautionary notes on obtaining a random double:

• One of the standard techniques for getting a random number between 0 and 1 is to do

  (double)rand() / (double)RAND_MAX

  This has some flaws, but I'm OK with you using it.
• On the other hand, you should think carefully about what you pass to

  srand()

  to seed the random number generator. It should be something that's not the same for every process -- otherwise, what's the point?

Combining results

Use MPI_Reduce to send all of the results back to Process 0, and print the result.

Timing

Insert timing code that uses the MPI_Wtime library. The timing should start just after get_input returns, and it should end after the call to MPI_Reduce. Use MPI_Reduce again to print the maximum time across all of the processes.

Documentation

Document your code. In your initial comment, include a discussion of how you seeded the random number generator and any other pertinent issues.

Performance analysis [30 points]

This section is based on your MPI program from the previous section.

To start, find a number of throws that takes a few minutes (2-10) for 1 process to complete. Let's call the runtime T and the number of throws N.

Submit a writeup that includes the following information:

• [if you are not running on cwolf] A brief description of your hardware (especially processor and memory) and which MPI library you are using
• A table with the runtimes, speedups, and efficiencies for N throws with 1, 2, 4, and 8 processes.
• A graph with the speedup vs. number of threads for this value of N.
• Show a table with the runtimes for p * N throws with 1, 2, 4, and 8 processes, where p is the number of processes. In other words, each process will do as much work as your single sequential process.
• Based on all of your data, make an argument about the scalability of this problem.