|
Blackboard
|
|
|
Your task in this assignment is to parallelize an existing sequential program, written in Java, that finds the shortest paths to all vertices from a distinguished source vertex in a graph. This is the single-source shortest path (SSSP) problem.
The fastest known sequential SSSP algorithm is due to Dijkstra. It runs in time O((m + n) log n) time, where n is the number of vertices and m is the number of edges (0 ≤ m ≤ (
Unfortunately, Dijkstra’s algorithm doesn’t parallelize very well: it’s what is known as a label-setting algorithm—we only select an edge when we’re sure it constitutes part of the shortest-path tree, and we never change our mind. The priority queue, which allows us to make correct decisions, serves as a central bottleneck. It turns out that there are label-correcting algorithms with comparable sequential performance that are more amenable to parallelization. These algorithms admit the possibility of de-selecting an edge when a better route is found; this ability to change means that threads can work in parallel on the basis on incomplete local knowledge, confident that any mistakes they make will be corrected later.
The best known label-correcting SSSP algorithm is known as Δ-stepping, due to Meyer and Sanders [J. Algorithms, 2003]. Instead of a strict priority queue, it maintains an array of buckets, where bucket i holds vertices whose currently best-known paths have lengths i × Δ ≤ l < (i+1) × Δ. Initially only the source is present in the array, in bucket 0. At each step of the algorithm, we consider the first non-empty bucket B. For each vertex v in B, we relax each neighbor w that is connected to v by an edge of weight ≤Δ—that is, we check to see if connecting through v will improve w’s path to the source, and if so, we move w to the appropriate new bucket, which might be B or one of its successors. Because we might move w into B, we iterate until B is empty; then we relax all the neighbors connected to v by edges of weight >Δ, for all edges v that we have removed from B. Finally, we move on to the next nonempty bucket. As it turns out, given a maximum weight W for edges, we can be sure that all vertices currently in the array will live within W/Δ buckets of each other. If we create a few more buckets than this, we can safely use the array in a circular fashion; we don’t actually need max-path-length/Δ of them.
Over time, w’s preferred edge back to the source may
be updated several times. Crucially, however, iteration over the
neighbors w of v can be done in parallel for all
vertices v in B. This is the source of
potential parallelism.
Harvesting this parallelism isn’t trivial, however.
Threads must always work on the same bucket at the same point in time,
and must synchronize their access to all shared data structures.
While there are many ways to parallelize Δ-stepping, the following
is perhaps the easiest: We statically partition the n
vertices so that each of our t threads is
responsible for approximately n/t of them. Each thread then
maintains its own, separate array of buckets.
We use a barrier (e.g., Java’s
CyclicBarrier) to make
sure that each thread works on its ith bucket during step
i (perhaps each part of step i). We
also create a set of
message queues (e.g., instances of Java’s
ConcurrentLinkedQueue) that
allow threads to pass work to one another. When thread j
discovers an opportunity to relax vertex w, which belongs to
thread k, it does not do so directly; rather, it enqueues a
message asking k to do so. (For efficiency, j may
“batch” together requests being sent to the same
destination.)
As a starting point, we are giving you sequential code for both Dijkstra’s algorithm and a straightforward version of Δ-stepping. The program is designed to be run from the command line, where you can specify various start-up parameters (see below). In interactive modes, it opens a square display containing n−1 blue dots (vertices), a green dot (the source), and various edges among these. At the bottom of the display is a series of control buttons.
Source code is in the files
SSSP.java and
Coordinator.java,
which you can view in, and save from, your browser.
Executable code lies in approximately 30 .class files, many
of which are for the user interface. These are generated by running
SSSP.java through the Java compiler,
javac.
You will be running this assignment on
node2x14a.csug.rochester.edu
and
node2x18a.csug.rochester.edu.
These machines have two processor chips each, with 14 or 18 cores per
chip, as suggested by the names.
Each core has 2 hardware contexts (hyperthreads). This means
the machines can execute up to 56 or 72 threads in parallel.
For large graphs, you should be able to obtain significant speedup,
though you will probably find that there is a point of diminishing
returns at which the overhead of creating and managing additional
threads (all of which compete for bus and cache bandwidth) outweighs any
additional performance improvements.
Note that the node machines are visible only inside the
csug firewall.
Only cycle1, cycle2, and cycle3
are visible from outside.
Thus to run timing experiments from outside the firewall you must first
ssh to one of the cycle machines and
then ssh from there to
node2x14a or
node2x18a.
If you’re already in the majors lab or the Hylan lab, you can
ssh directly from your desktop.
As the due date approaches, we will reserve much of the time on
one of the node machines
for timing experiments, with a sign-up system that
allows you to obtain exclusive access to the machine (watch Blackboard for announcements). Note that you
will almost certainly not be able to get last-minute exclusive access, and
since results of timing experiments are required for full credit on the
assignment, you will need to plan to have your code debugged and ready
for benchmarking several days ahead of the due date.
The code we are giving you accepts seven command-line arguments:
You can run the application remotely in animation modes 2 and 3, with X11
forwarding over ssh, but it will be choppy. You will
probably get better results with -Y (insecure) forwarding
rather than -X.
You will want to use mode 0 for timing tests—otherwise the program
will spend all its time generating output, and you won’t really
be measuring anything of interest.
Note that for larger graphs the reported times will be much shorter than
wall-clock time.
That’s because the program is spending much of its time
creating the graph rather than actually finding shortest paths.
You are welcome to do development on a personal machine
(Java code is very portable), but you will need to
test your code and collect performance results at csug.
You’ll almost certainly want to use a 64-bit Java installation;
otherwise you’ll risk running out of
heap space on large problems.
And you’ll need to go large:
my core i7 laptop can solve a million-vertex graph (with Δ-stepping)
in half a second. For 10 million vertices it takes just under 10
seconds.
Note that building the graph becomes a time-consuming process
when the number of vertices is large; don’t get worried if the
program takes a while to start.
The write-up requirements are more extensive for this assignment.
In addition to parallelizing the code and describing what you did, you
must evaluate the success of your parallelization. Using
one of the node machines,
for some convenient number of vertices, create a graph
that plots execution time as a function of the number of threads, varying
that number from 1 to 48.
(Don’t try to plot every possible thread
count—that would take a lot of experimentation
time! Thread counts of, say, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32,
and 48 should suffice.)
On this same graph, for comparison, indicate the run time of
Dijkstra’s algorithm.
On a second graph, plot the speedup of your
code: the run time of the sequential version
divided by the run time of your parallel version. Ideally,
you’d see a speedup of k with k threads. How
close do you come? What bottleneck(s) keep you from doing
better?
Full disclosure: getting parallel speedup in computationally demanding applications is hard. The task is complicated in this assignment by the fact that you will need to use very large graphs—larger than the last-level cache—to get multi-second execution times; at that point, your run time may be dominated by memory access costs, not by computation. (As of Nov. 3, on a million-node graph, my parallel solution has modest speedup on 2, 4, or 8 threads. At 16 it’s slower again, and it never beats Dijkstra’s algorithm—which it would have to in order to be useful.) You will receive full credit if you get the parallel version of Δ-stepping working correctly and it doesn’t slow down dramatically with increasing numbers of threads. Significant parallel speedup is worth significant extra credit.
As in previous assignments, you may work alone or in teams of two.
Beware that debugging parallel programs tends to be much harder
than debugging sequential programs, so be sure to leave enough
time. Be sure to follow all the rules on the Grading page. As with all assignments,
use the turn-in script:
~cs254/bin/TURN_IN. Put your write-up in a
README.pdf file in the directory in
which you run the script. Be sure to describe any
features of your code that the TAs might not immediately notice.
Before end of day on Friday, November 4, each student should complete the T4 trivia assignment found on Blackboard.
