Your task in this assignment is to parallelize an existing sequential program, written in Java, that constructs a (Euclidean) minimum spanning tree (MST) for a collection of points in the plane.
As you may recall from a data structures or algorithms class, there are well-known MST algorithms that run in time O(n2), where n is the number of nodes, and others that run in time O(m log n), where m is the number of edges. The latter is better, of course, if and only if m << n2. For points in the plane, with Euclidean distance and no explicitly specified edges, one might be inclined to assume that O(n2) is the best we can do, but this is not the case. It can be proven that the edges of the MST must be a subset of the edges in the Delaunay triangulation of the given points.
A triangulation of points in the plane is a maximal set of line
segments whose endpoints are among the given points and which do not
otherwise intersect. If one were to stretch a
rubber band around the given points, a triangulation divides the
interior space into triangles; hence
the name.
The Delaunay triangulation (example at left) has the property
that the circumcircle of the vertices of a triangle (the unique
circle on which all three vertices lie) contains no other point in the
set. One can prove that the Delaunay triangulation of a set is unique
if no four points lie on the same circle and no three points lie on the
same line. One can also prove that the
Delaunay triangulation maximizes the minimum corner angle across all
triangles. Delaunay triangulations tend to be pleasing to the eye.
They are used in graphics rendering and mechanical simulation.
They are also related in interesting ways to the notions of convex
hull and Voronoi diagram.
Note that the number of edges in a triangulation is O(n).
The program we are giving you includes an implementation of Dwyer’s Delaunay triangulation algorithm (a refinement of the earlier algorithm of Guibas & Stolfi), which runs in time O(n log n). Using the resulting mesh, the program then runs Kruskal’s algorithm to create the MST. Kruskal’s algorithm, given the linear number of edges, is also O(n log n), but the constant is much smaller: in the sequential program, creation of the mesh takes almost 95% of the total run time.
The program can be run in a web browser (click here for a demo), but is better run from the command line, where you can specify various start-up parameters (see below). It opens a square display containing N blue dots (nodes), and a series of control buttons.
Source code is in the files
MST.java and
Coordinator.java,
which you can view in, and save from, your browser.
The page for applet-based execution, which you can see by selecting “view
source” in your
browser while running the program, is a trivial HTML file that identifies
the location of Java byte code. That code lies in 30-some
.class files, many of which are for the user interface.
They are generated by running MST.java through
the Java compiler, javac.
You will be running this assignment on
niagara1.csug.rochester.edu.
This machine has a single processor chip containing 8 cores,
each of which has 4 hardware contexts (what Intel
would call hyperthreads). This means the machine can execute 32 threads in
parallel. You will probably find that your code runs faster with 2, 4, or
even 8 threads, but probably slows down again before it gets to 32, due to
thread creation overhead, lack of available concurrency, and/or bus,
memory, or ALU contention. You will also find that
sequential code, running on a single niagara thread, is pretty
slow. That’s because the machine is optimized for 8-core
throughput rather than single-core performance. Each core has a
single, in-order, 8-stage, 1GHz pipeline, and all 8 cores share a single
floating-point ALU. (The second generation processor, of which
we have a two-chip version on the research network, has 8 hardware
contexts, two pipelines, and a separate FPU per core.)
As the due date approaches, we will reserve much of the time on
niagara1 for timing experiments, with a sign-up system that
allows you to obtain exclusive access to the machine. 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 ready for testing
several days ahead of the due date.
The code we are giving you makes use of at least one feature
added in Java 6—the ConcurrentSkipListSet
class—and must therefore be compiled by, and run on, a Java 6
or later implementation.
On the CSUG niagara machines, you will need to use
/usr/staff/bin/javac and /usr/staff/bin/java; be
sure these are on your PATH before
/usr/bin.
In a similar vein, if you want to do initial development work on your own
machine, you’ll need to make sure you have a Java 6 compliant
installation. Downloads are available at oracle.com/java.
The code we are giving you, when run from the command line (rather than as an applet in a browser), accepts four 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.
If you use a 32-bit Java 6 implementation, you’ll find you run out of heap space with more than about 70,000 points. The Java 6 installation we have created for the niagara machines runs in 64-bit mode, but 70,000 points already takes about 15 seconds to complete on a single niagara core, so you probably won’t want to go much larger anyway. (1,000,000 points takes about 6 1/2 minutes.)
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 the niagara machines, for some convenient number of points, create a graph that plots execution time as a function of the number of threads, varying that number from 1 to 30. Also plot the speedup of your code: the run time of the original (unmodified!) 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?
As in previous assignments, you may work alone or in teams of two. If you choose to work in pairs, a natural division of labor is for one partner to parallelize the Dwyer (triangulation) stage of the program and the other to parallelize the Kruskal (MST) stage. You’ll find that the Dwyer code is much more complicated, but it has a natural divide-and-conquer parallelization. The Kruskal code is much simpler—you’ll find it easy to understand—but parallelization is more challenging. The easiest strategy is probably to retain the serial iteration over edges, allow threads to identify the subtrees they want to merge (an O(log n) operation) in parallel, and then force the merges to actually complete in order (possibly starting over if they discover that a previous merge has changed which edges are in which subtrees). You may discover, however, that the condition synchronization for this strategy consumes more time than it saves; you’ll want to address this in your write-up.
(I've coded up a solution along the lines described in the previous paragraph. For 10,000 points, running 8 threads on a niagara machine, the sequential execution takes about 3.1 seconds; the parallel execution takes about 1.3, a speedup of about 2.4. Your mileage may vary.)
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 TA might not immediately notice.
Before the beginning of class on Tuesday, November 13, send
e-mail to to cs254 containing answers to the following
questions:
points in class
Surface specify the number of elements in the array?
Animation has a repaint() method.
Where is this method defined?
What is its purpose?
KruskalSolve() in the given code, however, contains no
such sort. Why not?
