1997-98
CS 284aHomework Six: Multithreaded All-Pairs Shortest-Paths Revisited
Handed out:
Tuesday, 19th November 1997.Introduction
In Homework Four, you solved the All-Pairs Shortest Paths problem using barriers. However, the speedup that can be achieved using barriers is limited by the idle time associated with each pass through the barrier. In this homework, implement a more efficient multithreaded version of the Floyd-Warshall algorithm in which more than one iteration of the outer loop is executed concurrently. Use flags and/or counters to synchronize the outer loop iterations. You will be graded entirely on how fast your program can find the shortest-paths in a 1000-node graph on a quad-processor Pentium Pro, as compared to the sequential Floyd-Warshall algorithm.
Details
Start with the same
shortest_paths project that we provided for Homework Four. The sequential algorithm has the following form:
void seq_shortest_paths(
int n, const unsigned int edge[N][N], unsigned int path[N][N])
{
int i, j, k;
unsigned int new_path;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
path[i][j] = edge[i][j];
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
new_path = path[i][k] + path[k][j];
if (new_path < path[i][j])
path[i][j] = new_path;
}
}
Multithreading of the inner (
i and j) loops (as in Homework Four) is moderately straightforward if a little care is taken to avoid illegal sharing of the elements of path. Multithreading of the outer (k) loop is more difficult because the iterations all read and write the entire path array. However, as discussed in class, it is clear that parts of at least two (and maybe more?) adjacent iterations of the k-loop can be executed concurrently. This removes the idle time between k-loop iterations. Write a multithreaded version of the algorithm in which the k-loop (as well as i and j loops) is multithreaded. Use flags and/or counters to synchronize the concurrency between the k-loop iterations.What to hand in
When you are ready to submit your program, create a folder called
homework_6 at the top level of your user directory. Copy your shortest_paths.c file into this directory. Send an email to cs284@cs telling us that you have completed the homework. In this email, tell us the value t (the number of threads) that you want us to use when we time your program on a randomly generated 1000-node graph. Do not change the shortest_paths.c file after you send us the email.Grading
Sequential all-pairs shortest-paths on a 1000-node graph takes approximately 45 seconds. First, we will test your program using an expanded test suite. If your program passes the test suite, we will time your program on a 1000-node graph on a quad-processor Pentium Pro, using the value of
t that you specify. We will time 4 trials and take the average of the median two trials to be your program’s time. Your grade (out of 20 points) will be given by the following formula:
points = 300/time
For example, if program runs in 15 seconds (a three-fold speedup over sequential), you will receive 20 points If your program does not pass the test suite, you will receive up to a maximum of 10 points, depending on our opinion of the quality of your incorrect program
Rules