CSSE 220 – Object-Oriented Software Development

Homework 15

Objectives

Experiment with function objects and the Java Fork/Join Framework for parallel computing.

Tasks

1. Complete the assigned reading for this session (Java ForkJoin Intro ), according to the course schedule.
   • As you read, see if you can answer the self-check questions.
   • Bring your questions to next class!
 
2. Complete the assessment exercises over this reading on ANGEL (under Lessons → Assignments).

3. Science! For the rest of this homework you’ll write a little code, run several experiments, and write up a brief lab report.

   We encourage you to work in pairs for this homework. We have not set up pair repositories, so just choose one person’s machine for the project and do your work there. (Consistently using one machine will also reduce the sources of variation in your experimental results.)

   Complete the following tasks in the project ForkJoinIntro that you checked out in class.

   1. Get started with the fork/join framework.

      1. Open the class useless.Main. Run the class as a Java application; it will probably give you an error. Read the big comment block at the top of the file that describes how to run programs that use the fork/join framework. Follow those instructions and get help if the program still won’t run. (Eclipse may hide, or fold, this comment for us. Click the + symbol next to NOTE WELL to see the whole comment.)

         (This extra step is because the framework isn’t included in Java 6. If you are using Java 7, this step is not necessary.)

      2. Modify the Incrementor class so the program correctly prints The answer is 42.

   2. Visualizing the processors It can be fun to visualize how the fork-join code uses additional processors. The Resource Monitor program in Windows 7 can help with that.

      1. Open the Windows menu
      2. Type Resource in the Search box
      3. Choose Resource Monitor in the list
      4. Within Resource Monitor, switch to the CPU tab.
      5. Watch what happens to the CPU graphs as you run parallel code.

   3. A useful experiment, part 1. Next you’ll conduct two experiments with the code in the useful package. For this first experiment, you’ll vary the size of the array

      1. Run the class useful.Main, using your new knowledge from task a.
      2. Study the code in useful.Main and useful.ArraySummer. It’s based on the reading for today. Make sure you understand what the code is doing. In particular:
         • Notice that ArraySummer is a function object that recursively creates more function objects.
         • Observe the pattern of forks and joins in ArraySummer’s compute() method. Review Grossman’s Beginner’s Introduction to the Java ForkJoin Framework and ask questions if ArraySummer doesn’t make sense to you.
         • Study the use of StopWatch in useful.Main to collect timing information.
      3. Run your experiment!
         • Decide a range of array sizes that you want to test.
         • Try the largest one first to make sure your memory allocation is big enough. Record the memory allocation that you’re using. (The big comment on how to run the programs also says how to change the memory allocation.)
         • Now run your program for each of the sizes and carefully note the size and the time reported. You’ll make a table and graph of these for your lab report (see step 3.i below).
         • Quickly sketch a graph of your data. Does anything seem unusual about the results? Can you explain why they look like they do? Jot down any notes that seem like they would be helpful for your lab report.

   4. A useful experiment, part 2. Continuing with the useful package, next you’ll vary the cut-off point where the ArraySummer switches from parallel recursive tasks, to old-school sequential code.

      • Choose a single array size for this experiment and note what you chose. (Be sure to choose large enough value so that you can get meaningful results and have room to vary the sequential threshold.)
      • Vary the SEQUENTIAL_THRESHOLD in ArraySummer, carefully noting the threshold and the time reported. Be sure to investigate thresholds near 1 (fully parallel) and near the array size (fully sequential). As before, you’ll make a table and graph of these for your lab report (see step 3.i below).
      • Quickly sketch a graph of your data. Does anything seem unusual about the results? Can you explain why they look like they do? Jot down any notes that seem like they would be helpful for your lab report.

   5. Programming Interlude. The provided mergesort package contains a sequential implementation of merge sort in the class SequentialMergeSorter. The package also provides the skeletons for a Main class and a parallel merge sorter.

      Before you can conduct the last two experiments, you need to complete ParallelMergeSorter. To do this:

      1. Study the classes mergesort.Main and SequentialMergeSorter.
      2. Also study the compute() method in ArraySummer.
      3. Now implement the compute() method in ParallelMergeSorter by combining the sorting algorithm from SequentialMergeSorter’s sort() method, with the fork/join technique and sequential threshold used in ArraySummer.
      4. Test your implementation by running mergesort.Main.

   6. Build your test fixture. To conduct the last two experiments, you also need to write some code to execute and time the tests. Use the timing code in useful.Main as a model, but carefully note the following differences:

      • You’ll want to use two different StopWatch objects, one that times sequential tests and one that times parallel tests.

      • Inside your TEST_ITERATIONS loop, you should generate a new random array and make a copy of it each iteration, like the code at the beginning of mergesort.Main’s main() method does.

        Why?!? Because the sorters mutate the array that they are sorting. If we want unique timing data for each test iteration, we need a new test array.

      • Note that StopWatch objects can be restarted after they are stopped. So, you’ll want to start the appropriate stop watch immediately before sequential sorting and stop it immediately after. Then do the same with the other stop watch and sorter. Make sure you don’t have a stop watch running while generating and copying the new random array (unless you want to add a third StopWatch object for that purpose).
   7. Sort and size. Conduct an experiment where you vary the size of the array to be sorted. This is just like task c above, except you should record both the sequential sorting time and the parallel sorting time for each size.
   8. Sort and threshold. Conduct an experiment where you hold the array size fixed and vary the sequential cut-off of your merge sort algorithm. This is just like task d above, except you should record both the sequential sorting time and the parallel sorting time for each threshold value. Be sure to note the fixed array size that you used.

   9. Lab Report. Prepare a brief report summarizing the experiments you performed. For each experiment,

      • say which package you were working on,
      • say which variables you held constant and their values,
      • say which variable you varied,
      • give a table showing the results,
      • sketch a graph showing how the timing varied as you changed the variable, and
      • give a brief (one or two paragraph) explanation of the behavior you observed. It’s OK if you aren’t sure of the answer; just give your best guess.

      Reports will be graded for accuracy and professionalism, including proper use of English.

   10. Be sure to email a copy of all code to the lab partner whose machine you didn’t use. We want both of you to have all the code.

Turn-in Instructions

Turn in your programming work by committing it to your SVN repository. If you worked in pairs, only one of you needs to commit the work, but be sure to put both your names in the comments of the files you edit.

Turn in your lab report by committing a pdf copy to your repository. If you worked in pairs, only one of you needs to commit the work, but be sure to put both your names in the report. Note: If you did your sketches using pencil and paper, there is a scanner in the CSSE Lab (Moench F217) you are welcome to use.