1997-98
CS 284aHomework Four: Multithreaded All-Pairs Shortest-Paths
Handed out:
Wednesday, 5th November 1997.Introduction
There are two parts to this homework, each worth 10 points. Part 1 is to time the execution overhead of multithreaded regular
for loops and barrier operations. Part 2 is to develop an efficient multithreaded implementation of the Floyd-Warshall all-pairs shortest-paths algorithm. For Part 2, 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. Your results from the Part 1 will help you make the right programming decisions in Part 2.Part 1.1
What is the execution time of the multithreaded implementation of the following multithreadable regular
for loop running on a single Pentium Pro processor?
#pragma multithreadable chunk_size(1) mapping(simple)
for (i = 0; i < t; i++)
;
Present a table and graph showing the execution time (in milliseconds) of the
for loop for t = 1, 2, 5, 10, 20, 50, 100, 200, 500, and 1000.Part 1.2
What is the execution time of the barrier implementation of the following adjacent multithreadable regular
for loops running on a single Pentium Pro processor?
#pragma multithreadable chunk_size(1) mapping(simple)
for (i = 0; i < t; i++)
;
#pragma multithreadable chunk_size(1) mapping(simple)
for (i = 0; i < t; i++)
;
The execution time of the barrier is given by the difference between the execution time of the single
for loop (from Part 1.1) and the execution time of the barrier implementation of the adjacent for loops (from Part 1.2). Present a table and graph showing the execution time (in milliseconds) of the barrier for t = 1, 2, 5, 10, 20, 50, 100, 200, 500, and 1000.Part 2
Start with the
shortest_paths project that we provide. This project consists of three files: shortest_paths.h, shortest_paths.c, and main.c. Implement the multi_shortest_paths function in shortest_paths.cWhat to hand in
Hand your results from Part 1 into the homework box in the lab. Write the date and time at the top of the front page of your Part 1 results. When you are ready to submit your program from Part 2, create a folder called
homework_4 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.Part 2 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 for Part 2 (out of 10 points) will be given by the following formula:
points = 150/time
For example, if program runs in 15 seconds (a three-fold speedup over sequential), you will receive 10 points. If it runs in 22.5 seconds (a two-fold speedup), you will receive 7 points. If it runs in 11.25 seconds (a four-fold speedup), you will receive 14 points. If your program does not pass the test suite, you will receive up to a maximum of 5 points, depending on our opinion of the quality of your incorrect program
Rules