Concurrency Assignment

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

Machine resources

You will be running this assignment on niagara1.csug.rochester.edu and niagara2.csug.rochester.edu.  Each of these machines 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 or memory 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.) 

For the moment, feel free to use either of the CSUG niagara machines.  As the due date approaches, we will reserve niagara2 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 Java 6 language feature—the ConcurrentSkipListSet library class—and must therefore be compiled by, and run on, a Java 6 implementation.  Unfortunately, many systems have yet to upgrade to Java 6.  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 installation.  Downloads are available at java.sun.com

Execution modes

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:

-a  [0123]
Animation mode. 
0   (default from the command line) =>
print run time to standard output, but nothing else
1 =>
print list of created, destroyed, and selected (tree) edges, plus run time
2 =>
create a GUI that shows the triangulation and MST, and allows the user to re-run with additional sets of points
3   (default as an applet) =>
animate the algorithm on the screen as it runs. 
-n  num
Number of points.  Default = 50.  More than a couple hundred becomes too dense to look good when animated.  You’ll need to run big numbers (more than 10,000) to get multi-second execution times. 
-s  num
Seed for pseudorandom number generator.  Every value of the seed produces a different set of points. 
-t  num
Number of threads (max) that should be running at any given time.  This argument is currently unused; it’s it’s here to support your parallelization efforts. 

You can run the application remotely in animation modes 2 and 3, with X 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 spends all its time generating output, and you aren’t really 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.) 

Analyzing speedup

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? 

Division of labor and parallelization strategy

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 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 on 8 cores of 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. 

On-line resources

Please don’t print the Java documentation files; they’re big.  You should be able to get along just fine reading them in a browser. 

Extra credit suggestions

  1. Modify the program so that it can read start-up configurations from a file when running in command-line mode.  Use this to experiment with non-random distributions of points. 

  2. As noted above, the cores of the first-generation niagara processor share a single floating-point unit.  Does this impose a bottleneck on your code, or is there always 8 times as much non-FP work to do?  If FP is a bottleneck, can you modify the program to use integer math instead? 

  3. Creating a (Java 2) thread is a moderately expensive operation.  Creating a task in Java 5 is cheaper, but still far from free.  You don’t want to do either unless there is a nontrivial amount of work to be done.  (So, for example, it doesn’t make sense to create a thread or task to triangulate a region with only one or two points in it.)  Experiment with different strategies to decide when to create a new thread.  Discuss the effect of your strategies on program run time. 

  4. Can you devise a parallel solution to the triangulation problem that doesn’t require the sequential, O(n) “stitching-up” phase (and that therefore doesn’t appear to slow down toward the end)? 

  5. Modify your triangulation code to construct the Voronoi diagram

  6. You’ll notice with many example sets of points that you end up with some very skinny triangles, either because there are two points very close together, with all others far away, or because three points are nearly co-linear, so the triangle among them is very flat.  Look into the possibility of Delaunay refinement, which introduces new points to eliminate narrow triangles.  Two possible refinement algorithms, one due to Ruppert, the other to Chew, are described on pages 50–60 of Jonathan Shewchuk’s course notes from UC-Berkeley

  7. The naive parallelization of Kruskal’s algorithm requires that subtrees be merged in order of the lengths of their connecting edges.  Explore the possibility of creating a more highly parallel algorithm by allowing edges to be selected out of order.  This will require that you be willing to de-select edges when you find a better alternative. 

  8. Translate the code into C# and experiment with that language’s concurrency features. 

Trivia assignment

Before the beginning of class on Tuesday, November 10, send e-mail to to cs254 containing answers to the following questions: 

  1. Are you working alone or in a group of two?  If the latter, who is your partner? 
  2. Why doesn’t the declaration of variable points in class Surface specify the number of elements in the array? 
  3. Class Animation has a repaint() method.  Where is this method defined?  What is its purpose? 
  4. If you look Kruskal’s algorithm up in a textbook or on-line, you’ll find that it begins by sorting the edges of the graph.  Method KruskalSolve() in the given code, however, contains no such sort.  Why not? 

MAIN DUE DATE:

Wednesday November 25, at 12:00 noon; no extensions. 
Last Change: 06 November 2009 / Michael Scott's email address