4003-531-01/4005-735-01 Parallel Computing I Programming Project 1 Prof. Alan Kaminsky -- Spring Quarter 2013 Rochester Institute of Technology -- Department of Computer Science Instructions Jacobi Iteration Input Parameters Output Printout Requirements Questions Instructor's Example Grading Resubmission Instructions Programming Project 1 is to write a program for an SMP parallel computer that solves a linear system of equations using the Jacobi iteration algorithm. You must: Design a parallel version of the algorithm in Java using the Parallel Java Library to run on an SMP parallel computer. Write and test a sequential program and a parallel program to meet the Requirements below. Measure your sequential program's and parallel program's running time for several test cases. Calculate your parallel program's speedup, efficiency, and EDSF based on your measurements. 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 of 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 of your Computer Science Department account. The command to create the JAR file 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: Verify whether the message includes your full name. Unpack your JAR file in its own directory. Verify whether I can read your PDF file. Compile your source files using the JDK 1.5 Java compiler. When compiling, the Java classpath will include the directory with your source files and the Parallel Java Library. 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. Note that if your project does not compile with the JDK 1.5 Java compiler, I will not accept your submission. See "You Must Use JDK 1.5" for further information. The submission deadline is Monday, April 1, 2013 at 11:59pm. (No fooling!) 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 submission that arrived before the deadline. There is no penalty for multiple submissions. 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. Jacobi Iteration The Jacobi iteration algorithm for solving a linear system of equations is explained in a separate document. Read this document now: jacobi.pdf Input Parameters The problem sizes we will be dealing with for this project -- matrix dimensions on the order of several thousand by several thousand -- preclude reading the matrix from a file. Instead, the Jacobi iteration program will itself generate a diagonally dominant matrix A and a right hand side vector b with random elements, then proceed to solve the resulting linear system. The Jacobi iteration program's two input parameters come from the command line: The matrix dimension n ≥ 1, type int. Random seed, type long. The matrix A and vector b must be initialized with the following code (or equivalent code that produces the identical result): import edu.rit.util.Random; ... // int n = Matrix dimension // long seed = Random seed double[][] A = new double [n] [n]; double[] b = new double [n]; Random prng = Random.getInstance (seed); for (int i = 0; i < n; ++ i) { for (int j = 0; j < n; ++ j) A[i][j] = prng.nextDouble()*9.0 + 1.0; A[i][i] += 10.0*n; b[i] = prng.nextDouble()*9.0 + 1.0; } Use type double for all calculations with the matrix and vector elements. Output Printout The Jacobi iteration program prints its results on the standard output (console). There is no whitespace at the beginning or the end of any line. If the matrix dimension n ≤ 100, the first n lines of output give the elements of the solution vector x from index 0 through index n−1. Each line consists of the index; a space character; and the element value. If the matrix dimension n > 100, the first 50 lines of output give the elements of the solution vector x from index 0 through index 49, and the next 50 lines of output give the elements of x from index n−50 through index n−1. Each line consists of the index; a space character; and the element value. The final line of output consists of the program's running time in milliseconds, followed by the string " msec". The output must be printed with the following code (or equivalent code that produces the identical output): // int n = Matrix dimension // double[] x = Array containing solution vector // long t = Running time in milliseconds if (n <= 100) for (int i = 0; i < n; ++ i) System.out.printf ("%d %g%n", i, x[i]); else { for (int i = 0; i <= 49; ++ i) System.out.printf ("%d %g%n", i, x[i]); for (int i = n - 50; i < n; ++ i) System.out.printf ("%d %g%n", i, x[i]); } System.out.printf ("%d msec%n", t); Requirements Sequential Program The sequential program must implement a sequential version of the Jacobi iteration algorithm described above, in Java. The main program class must be named JacobiSeq, and this class must not be in a package. The program must be run using this command: java -Xmx2000m JacobiSeq <n> <seed> where the command line arguments are specified under Input Parameters above. (The -Xmx2000m flag sets the maximum size of the Java heap to 2000 megabytes, overriding the default of 64 megabytes.) 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. The wording of the error message is up to you. Any required command line argument is missing. There are extra command line arguments. Any command line argument is invalid. The program must measure its own running time from beginning to end, including reading the command line arguments, initializing the data, computing the solution, and printing the output. The program must print its results on the standard output as specified under Output Printout above. The program must not print anything else on the standard output. Parallel Program The requirements for the parallel program are the same as for the sequential program, except as specified below. The parallel program must implement a parallel version of the Jacobi iteration algorithm described above, for an SMP parallel computer, in Java, using the Parallel Java Library. The main program class must be named JacobiSmp, and this class must not be in a package. The program must be run using this command: java -Xmx2000m -Dpj.nt=<NT> JacobiSmp <n> <seed> where <NT> is the number of parallel threads and the other command line arguments are specified under Input Parameters above. (The -Xmx2000m flag sets the maximum size of the Java heap to 2000 megabytes, overriding the default of 64 megabytes.) When the parallel program is given the same arguments as the sequential program, the parallel program's output must be identical to the sequential program's output (except for the running time), no matter how many parallel threads are specified. 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. Describe how your parallel program is designed. As part of your description, address these points: Which parallel design patterns did you use? What data structures did you use? How did you partition the computation among the parallel threads? Did you need to synchronize the threads, and if so, how did you do it? Did you need to do load balancing, and if so, how did you do it? Run your program with the first input data set posted below. Measure your program's running time on the parasite.cs.rit.edu SMP computer. Use the Parallel Java job queue running on the paragon.cs.rit.edu computer to do your timing measurements. To run in the job queue, your sequential program and your parallel program must include the statement Comm.init(args);. For further information, see "Parallel Java on the RIT CS Parallel Computers." Measure your sequential program's running time by doing three program runs with the same input data. Measure your parallel program's running time for <NT> = 1, 2, 3, 4, and 8 parallel threads. For each value of <NT>, do three program runs with the same input data. Provide a table of your sequential and parallel program measurements with the following columns: number of threads; running time for first program run; running time for second program run; running time for third program run; smallest running time; measured speedup based on smallest running time; measured efficiency based on smallest running time; measured EDSF based on smallest running time. Repeat Question 2 with the second input data set posted below. Repeat Question 2 with the third input data set posted below. Summarize your measurements from Questions 2-4. As part of your summary, address these points: How close to the ideal speedup and efficiency did your parallel program achieve as the number of parallel threads increased? What is causing the discrepancy if any between the ideal and the measured speedup and efficiency in your parallel program? Is this problem a good candidate for an SMP parallel program? Why or why not? Write a paragraph telling me what you learned from this project. Input Data Set 1 Command lines: $ java -Xmx2000m JacobiSeq 4500 285714 $ java -Xmx2000m -Dpj.nt=1 JacobiSmp 4500 285714 $ java -Xmx2000m -Dpj.nt=2 JacobiSmp 4500 285714 $ java -Xmx2000m -Dpj.nt=3 JacobiSmp 4500 285714 $ java -Xmx2000m -Dpj.nt=4 JacobiSmp 4500 285714 $ java -Xmx2000m -Dpj.nt=8 JacobiSmp 4500 285714 Input Data Set 2 Command lines: $ java -Xmx2000m JacobiSeq 6000 428571 $ java -Xmx2000m -Dpj.nt=1 JacobiSmp 6000 428571 $ java -Xmx2000m -Dpj.nt=2 JacobiSmp 6000 428571 $ java -Xmx2000m -Dpj.nt=3 JacobiSmp 6000 428571 $ java -Xmx2000m -Dpj.nt=4 JacobiSmp 6000 428571 $ java -Xmx2000m -Dpj.nt=8 JacobiSmp 6000 428571 Input Data Set 3 Command lines: $ java -Xmx2000m JacobiSeq 7500 714285 $ java -Xmx2000m -Dpj.nt=1 JacobiSmp 7500 714285 $ java -Xmx2000m -Dpj.nt=2 JacobiSmp 7500 714285 $ java -Xmx2000m -Dpj.nt=3 JacobiSmp 7500 714285 $ java -Xmx2000m -Dpj.nt=4 JacobiSmp 7500 714285 $ java -Xmx2000m -Dpj.nt=8 JacobiSmp 7500 714285 Note: I will not post the correct output for these input data sets. Instructor's Example Here are the input parameters, the correct output printout, and the running time metrics for my sequential and parallel programs on a certain input data set. Command lines: $ java -Xmx2000m JacobiSeq 5000 142857 $ java -Xmx2000m -Dpj.nt=1 JacobiSmp 5000 142857 $ java -Xmx2000m -Dpj.nt=2 JacobiSmp 5000 142857 $ java -Xmx2000m -Dpj.nt=3 JacobiSmp 5000 142857 $ java -Xmx2000m -Dpj.nt=4 JacobiSmp 5000 142857 $ java -Xmx2000m -Dpj.nt=8 JacobiSmp 5000 142857 Correct output: output.txt My program's running time metrics on the parasite.cs.rit.edu machine via the paragon.cs.rit.edu job queue: NT T1 T2 T3 T Spdup Effic EDSF --- ----- ----- ----- ----- ----- ----- ----- seq 69318 68748 67825 67825 1 56016 56527 59619 56016 1.211 1.211 2 30704 30374 30452 30374 2.233 1.116 0.084 3 21297 21006 21366 21006 3.229 1.076 0.063 4 16594 16653 16583 16583 4.090 1.023 0.061 8 9111 9230 9039 9039 7.504 0.938 0.042 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. Oracle To aid you in testing your program, I will act as an oracle. You may send me an email message containing three or fewer input parameter sets (n and seed). The data sets must all be different from Input Data Sets 1, 2, and 3 above. I will reply and tell you, for each data set, the correct output and the running time of my sequential program on the parasite.cs.rit.edu machine (one program run only). You may send me only one such oracle request during the course of the project. 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 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 program does not run using the command line in Requirement 3 or 11, so that my test script cannot run your program, the test case will receive a grade of 0. If your program's standard output does not conform to the format specified in the Output Printout section above, so that my test script cannot read your 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 data and for performance. For correct output data, each test case will be graded as follows: 5 =  100% of the solution vector elements are correct. 4 =  90% or more of the solution vector elements are correct. 3 =  80% or more of the solution vector elements are correct. 2 =  70% or more of the solution vector elements are correct. 1 =  60% or more of the solution vector elements are correct. 0 =  Otherwise. To be considered correct, the solution vector element values must be correct to six significant figures as printed by the System.out.printf statements specified under Output Printout above. However, if your program does not obey Requirements 7 and 12, the test case will get 0 points for correct output data. Any deviation from the requirements will result in loss of points. This includes errors in the output formatting (such as misspellings, incorrect number of spaces or tabs, incorrect capitalization, or incorrect punctuation), missing output, extra blank lines, and extraneous output not called for in the requirements. The requirements state exactly what the output is supposed to be, and there is no excuse for outputting anything different. If any requirement is unclear, please ask for clarification. For performance, each test case will be graded as follows: 5 =  Smallest running time ≤ 110% of my program for all values of <NT>. 4 =  Smallest running time ≤ 120% of my program for all values of <NT>. 3 =  Smallest running time ≤ 150% of my program for all values of <NT>. 2 =  Smallest running time ≤ 200% of my program for all values of <NT>. 1 =  Smallest running time ≤ 300% of my program for all values of <NT>. 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. Resubmission If you so choose, you may submit a revised version of your project after you have received the grade for the original version. You are allowed to make one and only one resubmission of the project. However, if the original project was not successfully submitted by the (possibly extended) deadline or was not entirely your own work (i.e., plagiarized), you are not allowed to submit a revised version. Submit the revised version via email in the same way as the original version. I will accept a resubmission up until 11:59pm Wednesday 17-Apr-2013. I will grade the revised version using the same criteria as the original version, then I will subtract 7 points as a resubmission penalty. The revised grade will replace the original grade, even if the revised grade is less than the original grade. 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 © 2013 Alan Kaminsky. All rights reserved. Last updated 10-Apr-2013. Please send comments to ark­@­cs.rit.edu.