Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706
Home Page
Parallel Computing II • 4003-532-70/4005-736-70 • Spring Quarter 2007
Course Page

4003-532-70/4005-736-70 Parallel Computing II
Programming Project 1

Prof. Alan Kaminsky -- Spring Quarter 2007
Rochester Institute of Technology -- Department of Computer Science

Instructions
The Heat Distribution Problem
Input Text File Format
Output Text File Format
Output Image File Format
Requirements
Questions
Instructor's Example
Grading

Instructions

Programming Project 1 is to write a parallel program for a SMP computer to solve a heat distribution problem. You must:

  1. Design a parallel version of the algorithm in Java using the Parallel Java Library to run on a SMP computer.
  2. Write and test a sequential program and a parallel program to meet the Requirements below.
  3. Measure your sequential program's and parallel program's running time for several test cases.
  4. Calculate your parallel program's speedup and efficiency based on your measurements.
  5. Submit a writeup of your design and measurements as a PDF file, along with your source code.

Your PDF file must be named "<username>.pdf", where <username> is the user name from your Computer Science Department account. Create a Java archive (JAR) file containing your PDF file and all your source code (".java") files. Your JAR file must be named "<username>.jar", where <username> is the user name from your Computer Science Department account. The command is:

jar cvf <username>.jar <username>.pdf *.java

Send your JAR file to me by email at ark­@­cs.rit.edu. Include your full name in the email message, and include the JAR file as an attachment.

When I receive your email message, I will:

  1. Verify whether the message includes your full name.
  2. Unpack your JAR file in its own directory.
  3. Verify whether I can read your PDF file.
  4. Compile your source files using the JDK 1.5.0 Java compiler. When compiling, the Java classpath will include the directory with your source files and the Parallel Java Library.
  5. Verify whether your project compiles with no errors.
I will then send you a reply email message stating whether I accepted your submission or not. If you have not received a reply within one business day (i.e., not counting weekends), please contact me. Your project is not successfully submitted until I have sent you an acknowledgment that I accepted it.

The submission deadline is Monday, April 9, 2007 at 11:59pm. The date/time when your email message arrives in my inbox (not when you sent the message) will determine whether your project meets the deadline.

You may submit your project multiple times before the deadline. I will keep and grade only your most recent successful submission.

If you submit your project before the deadline, but I do not accept it, and you cannot or do not submit it again before the deadline, the project will be late (see below). I strongly advise you to submit the project several days before the deadline, so there will be time to deal with any problems that may arise in the submission process.

Late projects: I will not accept a late project unless you arrange with me for an extension. See the Course Policies for my policy on extensions. Late projects will receive a grade of zero.

Plagiarism: The project must be entirely your own work. See the Course Policies for my policy on plagiarism.

The Heat Distribution Problem

The heat distribution program reads its input from a text file, prints its output into another text file, and generates a visualization of its output in a PNG image file. When finished, the heat distribution program prints its own running time on the standard output. The algorithm for the heat distribution program is described in a separate document:

heatdist.pdf (82,575 bytes)

Input Text File Format

The heat distribution program reads its input from a plain text file in the following format:

  1. First line -- The grid size N, an integer greater than or equal to 1. The grid consists of N+1 rows by N+1 columns.
     
  2. Next N+1 lines -- The temperatures of the upper boundary grid points, h[0,0] through h[0,N], one per line, each a double precision floating point number.
     
  3. Next N-1 lines -- The temperatures of the left boundary grid points, h[1,0] through h[N-1,0], one per line, each a double precision floating point number.
     
  4. Next N-1 lines -- The temperatures of the right boundary grid points, h[1,N] through h[N-1,N], one per line, each a double precision floating point number.
     
  5. Next N+1 lines -- The temperatures of the lower boundary grid points, h[N,0] through h[N,N], one per line, each a double precision floating point number.

Output Text File Format

The heat distribution program writes its output into a plain text file in the following format:

  1. First N+1 lines -- The temperatures of the grid points in row 0 of the solution, h[0,0] through h[0,N], one per line, each a double precision floating point number.
     
  2. Next N+1 lines -- The temperatures of the grid points in row 1 of the solution, h[1,0] through h[1,N], one per line, each a double precision floating point number.
     
  3. And so on, through row N of the solution.

Output Image File Format

The heat distribution program writes a visualization of its output into a full (24-bit) color PNG image file as follows:

  1. The image is N+1 pixels wide and N+1 pixels high.
  2. Each pixel in the image corresponds to one grid point.
  3. The upper left pixel corresponds to h[0,0].
  4. The lower right pixel corresponds to h[N,N].
  5. Each pixel's hue is determined by Equation (14) in the algorithm document.
  6. Each pixel's saturation is 1.0.
  7. Each pixel's brightness is 1.0.

Note: To create the image, use class edu.rit.image.ColorImage in the Parallel Java Library.

Requirements
    Sequential Program
     
  1. The sequential program must implement a sequential version of the heat distribution program described above, in Java.
     
  2. The program must use double precision floating point numbers for all quantities.
     
  3. The main program class must be named HeatDistSeq, and this class must not be in a package.
     
  4. The program must be run using this command: 
    java HeatDistSeq <infile> <outfile> <imagefile> <h_L> <h_U> <H_L> <H_U> <gamma>
    where:
    1. <infile> is the name of the input text file.
    2. <outfile> is the name of the output text file.
    3. <imagefile> is the name of the output PNG image file.
    4. <h_L> is the lower heat value.
    5. <h_U> is the upper heat value, hL < hU.
    6. <H_L> is the lower hue value, 0.0 <= HL <= 1.0.
    7. <H_U> is the upper hue value, 0.0 <= HU <= 1.0.
    8. <gamma> is the gamma exponent.
       
  5. The program must print an error message on the standard error and must terminate if there are any of the following problems. The error message must include a meaningful description of the problem. The error message may include an exception stack trace.
     
    1. Any required command line argument is missing.
    2. There are extraneous command line arguments.
    3. Any command line argument is invalid.
    4. The input file cannot be read.
    5. The contents of the input file are invalid.
    6. The output file cannot be written.
    7. The image file cannot be written.
    8. The program did not converge to a solution.
       
    Note: The wording of the error message is up to you.
     
  6. The program must read the grid size and boundary values from the input text file as described above (see "Input Text File Format").
     
  7. The program must print its results into the output text file as described above (see "Output Text File Format").
     
  8. The program must store a visualization of its results into the output image file as described above (see "Output Image File Format").
     
  9. The program must measure its own running time from beginning to end, including reading the input text file, computing the results, writing the output text file, computing the visualization, and writing the output image file.
     
  10. The program must print its running time on the standard output in this format: 
    <time> msec
    where <time> is replaced by the running time in milliseconds.
     
  11. The program must not print anything else on the standard output.
     
    Parallel Program
     
  12. The requirements for the parallel program are the same as for the sequential program, except as specified below.
     
  13. The parallel program must implement a parallel version of the heat distribution program described above, for an SMP parallel computer, in Java, using the Parallel Java Library.
     
  14. The main program class must be named HeatDistSmp, and this class must not be in a package.
     
  15. The program must be run using this command: 
    java -Dpj.nt=<K> HeatDistSmp <infile> <outfile> <imagefile> <h_L> <h_U> <H_L> <H_U> <gamma>
    where <K> is the number of parallel threads and the other command line arguments are the same as Requirement 4.

Questions

Answer the following questions. Put your answers in a PDF file named "<username>.pdf". I will not accept anything other than a PDF file. You may use any word processing software you wish, as long as it produces a PDF file. Some word processors can print to a PDF file directly. Another possibility is to print to a PostScript file, then use the ps2pdf command to convert the PostScript file to a PDF file. (The ps2pdf command is installed on the Computer Science Department systems and comes with most Linux distributions.)

  1. Describe how your parallel program is designed. As part of your description, address these points:
    1. What data structures did you use?
    2. How did you partition the computation among the parallel threads?
    3. Did you need to synchronize the threads, and if so, how did you do it?
    4. Did you need to do load balancing, and if so, how did you do it?
       
  2. Run your program with the first input data set posted below. Measure your sequential program's running time on the parasite.cs.rit.edu SMP computer. Do seven program runs with the same input data. Measure your parallel program's running time on the parasite.cs.rit.edu SMP computer for <K> = 1, 2, 3, 4, and 8 parallel threads. For each value of <K>, do seven program runs with the same input data. Provide a table of your sequential and parallel program measurements with the following columns: number of threads <K>; running time for first program run; running time for second program run; running time for third program run; running time for fourth program run; running time for fifth program run; running time for sixth program run; running time for seventh program run; median running time; measured speedup based on median running time; measured efficiency based on median running time. Calculate the parallel program's speedup and efficiency with respect to the sequential program.
     
    Use the Parallel Java job queue running on the paragon.cs.rit.edu computer to do your timing measurements. Note: This means that you must include the statement Comm.init(args); in both the sequential program and the parallel program. For further information, see "Parallel Java on the RIT CS Parallel Computers."
     
  3. Repeat Question 2 with the second input data set posted below.
     
  4. Repeat Question 2 with the third input data set posted below.
     
  5. Summarize your measurements from Questions 2-4. As part of your summary, address these points:
    1. How close to the ideal speedup and efficiency did your parallel program achieve as the number of parallel threads increased?
    2. What is causing the discrepancy if any between the ideal and the measured speedup and efficiency in your parallel program?
    3. Is this problem a good candidate for a SMP parallel program? Why or why not?
       
  6. Write a paragraph telling me what you learned from this project.

Input data sets:

  1. Input file: in01.txt (9,808 bytes)
    Command: java HeatDistSeq in01.txt out01.txt image01.png 0 100 0.666666 0.0 1.0
    Problem size: N = 500
     
  2. Input file: in02.txt (33,660 bytes)
    Command: java HeatDistSeq in02.txt out02.txt image02.png 0 100 0.333333 1.0 1.1
    Problem size: N = 600
     
  3. Input file: in03.txt (50,897 bytes)
    Command: java HeatDistSeq in03.txt out03.txt image03.png 0 100 0.9 0.1 0.8
    Problem size: N = 700

Note: I will not post the correct output for these input data sets.

Instructor's Example

My example is for a problem size of N = 800. Here is the command for running my example:

  • java HeatDistSeq in04.txt out04.txt image04.png 0 100 0.666666 0.0 0.9

The input file, the output file my program produced, and the image file my program produced are stored at the following locations in the CS file system:

  • /home/fac/ark/public_html/532/project01/in04.txt (9,604 bytes)
  • /home/fac/ark/public_html/532/project01/out04.txt (11,713,869 bytes)
  • /home/fac/ark/public_html/532/project01/image04.png (167,552 bytes)

Here is the running time data for my program running on the parasite.cs.rit.edu SMP computer: 

K    Running times (msec)                             Median  Speedup   Eff.
---  -----------------------------------------------  ------  -------  -----
seq  61304  60620  61029  60714  60941  61569  61553   61029
1    44409  44728  45131  44970  45041  44889  44019   44409    1.374  1.374
2    46656  46378  47918  46198  48771  49123  46185   46656    1.308  0.654
3    38944  39014  39274  39378  39092  39212  39031   39092    1.561  0.520
4    33643  34216  33899  33460  33671  33656  34298   33671    1.813  0.453
8    26797  27550  27159  27619  27752  27965  28508   27619    2.210  0.276

WARNING: Do not assume that your program is correct if it can reproduce the same output as my program on this one example. It is your responsibility to test your program thoroughly and make sure it will produce the correct output for any input file.

Grading

The project is worth a total of 70 points: 30 points for your answers to the Questions, 10 points for design, 30 points for test cases.

Questions 1-6 are each worth 5 points and will be graded as follows:

5 =  Satisfactory
4 =  Needs minor improvements
3 =  Needs major improvements
2 =  Unsatisfactory
0 =  Missing

I will evaluate the design of your parallel program for factors including but not limited to the following: adherence to the Requirements; adherence to principles of good object oriented design; appropriate usage of parallel design patterns studied in class; appropriate partitioning of the computation among the parallel threads; thread synchronization; load balancing; appropriate usage of the Parallel Java API. The design is worth 10 points and will be graded as follows:

10 =  Satisfactory
9 =  Needs minor improvements
7 =  Needs major improvements
5 =  Unsatisfactory

I will run your sequential and parallel programs on the three input data sets, measuring the running times as described above under Question 2. I will grade each test case using a test script that runs your program and examines the output text file and the standard output. When running your program, the Java classpath will include the directory with your project's compiled class files and the Parallel Java Library. If your programs do not run using the command lines in Requirements 4 and 15, so that my test script cannot run your programs, the test case will receive a grade of 0. If your program's output text file does not conform to Requirement 7, so that my test script cannot read your output text file, the test case will receive a grade of 0. If your program's standard output does not conform to Requirement 10, so that my test script cannot read your standard output, the test case will receive a grade of 0.

Each test case is worth 10 points. I will grade each test case for correct output file, for correct image file, and for performance. For correct output file, each test case will be graded as follows:

4 =  100% of the output values are correct.
3 =  90% or more of the output values are correct.
2 =  80% or more of the output values are correct.
1 =  70% or more of the output values are correct.
0 =  Otherwise

For each of your program's output values to be considered correct, the relative difference between your program's output value and the correct output value must be less than or equal to 1x10-3 (that is, correct to three decimal places).

WARNING: If the output file does not obey the required format exactly, the output will be considered incorrect. This includes extra spaces anywhere in the output, extraneous characters not called for in the requirements, and so on. The requirements specify exactly what the output is supposed to be, and there is no excuse for outputting anything different.

For correct image file, each test case will be graded as follows:

2 =  Image file looks the same "by eye" as the correct image file.
0 =  Otherwise

For performance, each test case will be graded as follows:

4 =  Measured median running time <= 120% of my solution for all values of <K>.
3 =  Measured median running time <= 150% of my solution for all values of <K>.
2 =  Measured median running time <= 200% of my solution for all values of <K>.
1 =  Measured median running time <= 300% of my solution for all values of <K>.
0 =  Otherwise

After grading your project I will put your grade and any comments I have in your encrypted grade file. For further information, see the Course Grading and Policies and the Encrypted Grades.

Parallel Computing I • 4003-531-01/4005-735-01 • Spring Quarter 2013
Course Page
Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706
Home Page
Copyright © 2007 Alan Kaminsky. All rights reserved. Last updated 05-Apr-2007. Please send comments to ark­@­cs.rit.edu.