Parallel Project — n-Bodies and Collisions
Assignment due:
Email: group names or solo decision by: Friday, March 14th.
Due: Programs (electronic) and reports (electronic) due: 8:00 pm, Monday, April 7th.
This project is worth 15% of your final grade.
You may work solo on this project, or with a partner. If you choose to work with a partner, understand that means you will be working together for both parts: the development of the programs and the timing report. The final project for the course can also be done in teams of two; however, you do not have to be on the same team for the final project. Email your group members (and CS logins), or your decision to work solo by March 14th.
This project involves solving the n-body problem. The textbook provides an explanation of this problem. See section 11.2, 11.2.1, and 11.2.2, pages 553 to 559. (Section 11.2.3 covers distributed versions of this problem). The textbook also explains optimizations that take advantage of  the inverse-square nature of the gravity equation (see section 11.2.4).
Place the objects in a 3-dimensional space (note that the textbook’s examples are in a 2-dimensional space).
For this problem, we will use bodies that are relatively close together, so the approximate methods will be necessary. Instead, to make the problem more “interesting”, your solution will check for collisions among the objects.  Assume elastic collisions. An elastic collision is one in which two objects bounce off each other without deformation or loss of total energy. The directions of travel for both objects will be different after the collision. You can assume that all objects are the same size (this will be a command-line parameter, see below).
You will turnin your programs and a report presenting the results of your timing runs and experiments. You will also make an oral presentation of your project and results. The presentations will be scheduled during the week following the due date.
Programs:
Write a good sequential program for this problem. Look specifically for optimizations that you can apply to the sequential program to improve its performance. Include a description of these optimizations in your report.
Develop a parallel solution for the problem from your sequential solution. You will need an efficient barrier to synchronize your workers. Your solution should work for any number of workers from two through eight. In your report, include a discussion of the barrier that you used and optimizations that you applied to the parallel algorithm.
Both your sequential and parallel solutions will take the following command-line arguments:
  1. •number of workers, 1 to 8. This argument will be ignored by the sequential solution.
  2. •number of bodies.
  3. •size of each body.
  4. •number of time steps.
You may add additional command-line arguments as needed to help in your experimentation. Provide default values for these additional arguments when they are not present. Examples can include a random seed, a
The output of each program should be the execution time for the computational part. Read the clock after you have initialized all the bodies. Read the clock just before you create the processes (in the parallel program). Read the clock again as soon as you have completed the time steps and the worker processes have terminated (in the parallel programs).
Write to standard out:
computation time: xxxx milliseconds
and the number of collisions detected.
Write the final positions and velocities to a file.
Different languages:
Write solutions to this problem using two of the following three choices:
  1. •MPD
  2. •C and pthreads, or C++ and pthreads, or Objective-C and pthreads.
  3. •Java threads
Note that the second bullet is one choice: you cannot use two different versions of C as your two languages.
Timing Experiments:
For one of your sequential programs, use a test case that will take a few minutes to complete on voltron. Now, use the same test case for your parallel solution and your other language implementations. Run tests to determine the computation time needed for one, two, three, four workers in each language. You should run each individual test more than once to get an average (and to allow you to filter out occasional timing fluctuations that occur due to system routines).
Tuesday, April 1st through Monday, April 7th, we will provide a schedule of times on voltron. Each time period will be one hour in length and assigned to one specific group or individual. You will then be able to run timing experiments during your assigned time slots without having to worry about others running test cases during this time.
Additional Experiments:
The experimental method consists of making, then testing hypotheses — asking questions and determining their answers. There are lots of different questions one might want to ask about the above programs, such as:
  1. •Overheads. How long does it take to perform a barrier for 2, 3, 4 workers?
  2. •Time/Space Trade-offs. Is false sharing happening for the barrier synchronization variables, and if so, can you get rid of it by padding the declarations?
  3. •Optimizations. What is the effect of turning on compile time optimizations (using the -O option for the mpd compiler, or the -Olevel option for the gcc compiler). How much faster are the programs? What happens to the speedups for the parallel programs?
  4. •Busy waiting vs. semaphores/monitors. Try two different approaches for the waits that are needed in the barrier synchronization, such as busy-waiting vs. semaphores (there are other ways that you can try as well). Does one technique show a marked improvement over another?
There are other questions you might ask. Pick at least two nontrivial questions and set up experiments to determine the answer. The choice of what to do is up to you, but do not choose just the simplest things. You might look at three different kinds of topics — such as overhead, time/space, and load-balancing — go into depth on one topic, or do a combination. You are welcome to discuss these options with us, if you wish.
Reports:
Once you have done the timing and other experiments, write a report to explain what you have done and what you have learned. Your report should be a few pages of text plus tables and/or figures. It should have four or five sections, as follows:
  1. •Introduction. Briefly describe the problem and what your report will show.
  2. •Programs. Describe your programs, stating what each does and how. Here is where you can describe your program-level optimizations for the sequential and parallel versions. Also, describe any differences in your solutions between the two languages.
  3. •Timing Experiments. Present the results from the timing experiments. Use tables to present the raw data and graphs to show speedups and comparisons. Also explain your results. Do not just present the output data. What do the results show? Why?
  4. •Other Experiments. Describe the questions that you set out to answer, the experiments you conducted, the results you got, and your analysis of the results. Present the results in whatever form seems most compelling to you. Your analysis should explain why you think you got the results you did.
  5. •Conclusion. Briefly summarize what your report has sown. Also, describe what you have learned from this project.
Turnin:
Turn in your programs. Include a Makefile that supports the command make all that will create all the programs in both of the languages you used. You do not need to turn in the actual output from any of your tests. Instead, turnin a README file that gives examples of commands that  you used in your tests. The idea is to tell us what commands so we can duplicate your results. We will not exhaustively test your programs. We will selectively run tests to verify that your programs work as you describe.
Use the assignment name 422parallel for this turnin.
You can turnin a printed copy of your report in class, or you can submit a pdf file of it electronically. If you use the electronic option, please name the file: report.pdf.
Demonstration:
You will demonstrate your project for me. You will need to prepare the demonstration. Plan a presentation that will last about 10 minutes. This will be followed by my questions. The total time for demonstration and questions will be no longer than 20 minutes. If doing a two-person project, both members of the group must be present. A sign-up sheet will be available for times during the period April 8 to 11. You can also make an appointment for a demonstration time prior to the 8th. I will have a sign-up sheet available in class on Thursday, April 3rd.