Concurrent Programming Project / Rinnakkaisohjelmointi projekti (20 p + bonus points)

Project is done in study circles, preferably in 2-4 person teams, but also 1 person team is allowed.

Project turn-in deadline is 9.5.2011 at 12:00 (this will not be moved later any more - no sad stories please). Deadline is for email copy, paper copy should be in by Tuesday morning 10.5.2011. Late penalty is 5 p per day. Make your project early and try to return it in April, or at least before the last weekend. However, please do not turn in your project before April 20, because report requirements might still be fine tuned before that date.

Each team implements one of chosen concurrent programming projects from the text book. Study circles and their project are shown in page Study Circles and Projects. 

Implementation is in Java, unless agreed otherwise with the instructor.

Project includes performance measurements on how well concurrency is utilized and how well the solution scales up to 2, 4, 8, or 16. Programs are supposed to run in one node (2 cpus with 4-cores, each core with 2 hyperthreads) of the departmental cluster Ukko.  Ukko nodes 145-149 (e.g., ukko147.hpc.cs.helsinki.fi) will be reserved for our use in Period IV.

Report, paper copy and emailed deliverables

Project is turned in as paper copy to Teemu Kerola (personally in D220 or via internal mail, e.g. leave it in an envelope marked to Teemu Kerola to the lobby attendants in Exactum) and it includes a (some 10 page) report (in English or in Finnish), that has at least the following components:

1. Student names, student id's, and approximate estimation of participation (total 100%)
2. Extra points given to some team member(s) by the study circle (see grading below)
3. Introduction and problem
4. Solution method, communication and synchronization problems and their solutions. Especially explain any possible speedup optimization you may have used.
5. User instructions, which make it easy to rerun the program for all test runs cases.
6. Evaluation of given solution (correctness, performance, scalability).
   
   1. You do not need to prove the correctness with propositional calculus or temporal logic.
   2. For theorethical problems, some simple proofs (functional correctness properties, deadlock, starvation?) with invariants is expected.
   3. For performance problems, you should verify algorithmically solution correctness once program completes (e.g., are the sorted values really in ascending order?). Verification time should not be counted for solution time. Sometimes correct answer must obtained by time consuming serial computation.
   4. Performance is important. Try to show theoretically that your solution scales up (e.g., to 128 cores?). Make practical experiments with Ukko to show it.
7. Performance test run data sets and run results (especially including the run results with given performance competition data set)
8. Summary
9. Attachments: program codes, inputs and outputs (reasonable print output, no huge full data set)

Project is also turned in electronically (to teemu.kerola (at) cs.helsinki.fi), with the report, program codes, inputs and outputs as email attachements.

The program must be easily usable in Ukko. This achieved by following these guidelines:

• Java program must be turned in as a zip attachement, which will unzip to similar file structure as given in project-example. Your turned-in program zip-file should be such that (a) it can be saved to a new directory, (b) unzipped there, (c) compiled in Ukko with script compile, and (d) finally executed in Ukko with script start. You need to modify scripts compile and start to suit your application. The scripts compile and start must be included in your zip attachement in proper place. Let me know if the explanations in project-example are not clear for you.
• C program must be also turned in as a zip attachement, which can be (a) copied to any directory, (b) unzipped there, and (c) compiled and run in Ukko with one single make command in that directory. You need to build an appropriate makefile that compiles and runs your application in Ukko. The makefile must be included in your zip attachement in proper place. Let me know if the these explanations are not clear for you.
• C++ program must be also turned in as a zip attachement, which can be (a) copied to any directory, (b) unzipped there, and (c) compiled and run in Ukko with one single make command in that directory. You need to build an appropriate makefile that compiles and runs your application in Ukko. The makefile must be included in your zip attachement in proper place. Use library boost for concurrency control. Let me know if the these explanations are not clear for you.

You do not need to prove the correctness with propositional calculus or temporal logic.

For theorethical problems, some simple proofs (functional correctness properties, deadlock, starvation?) with invariants is expected.

For performance problems, you should verify algorithmically solution correctness once program completes (e.g., are the sorted values really in ascending order?). Verification time should not be counted for solution time. Sometimes correct answer must obtained by time consuming serial computation.

Performance is important. Try to show theoretically that your solution scales up (e.g., to 128 cores?). Make practical experiments with Ukko to show it. 

Projects (see Appendix C in text book)

• 8 Binomial coefficient   -- not selected in 2011
  • Performance competition data set (parameters n, k) will be given here later on.
• 10 Roller coaster  
  • More theorethical problem. What corretness properties in your solution can you prove?
• 11 Santa Claus
  • More theorethical problem. What corretness properties in your solution can you prove?
  • Check the original complete problem definition (Trono).
• 14i Sorting integers(to ascending order)
  • Performance competition data set is /fs-1/2/kerola/uint64-keys.bin  (64 bit  little-endian unsigned integers, 58M values, file size 0.47 GB; read from file server, do not make extra copies and waste space...)
    • Best time was 1,72 s (out of 5 projects in Java)
  • Java does not support well 64 bit unsigned integers. You may interpret the data set as signed integers instead.
• 14s Sorting strings(to ascending order)
  • Performance competition data set is /fs-1/2/kerola/utf-8-keys.txt  (8 bit utf, 58M lines, file size 0.74 GB; read from file server, do not make extra copies and waste space...)
    • Best time was 98 s (out of 3 projects in Java)
• 16 Matrix multiplication
  • Performance competition data set consists of text file matrixes 
    • /fs-1/2/kerola/matr1_7500.txt 
    • /fs-1/2/kerola/matr2_7500.txt 
    • Best time was 66,6 s (out of 5 projects in Java)
  • Data set is given as two text files, each holding one matrix. Both files start with decimal integer N denoting the array size and followed by NxN array in row wise order (single accuracy floating points), values separated with white space. E.g.,
    • file 1:   3    1.23 3.45 6.78    2.23 1.45 5.78   5.23 5.45 5.78       
    • file 2:   3    1.33 3.35 6.38    2.33 1.35 5.38   5.33 5.35 5.38 
  • Tommi Tuura made 2 practice matrixes for testing purposes. These files are only to aid the development of your program, they are not substitutes for the larger matrices in any way:
    • http://www.cs.helsinki.fi/u/ttuura/matr1_1000.txt
    • http://www.cs.helsinki.fi/u/ttuura/matr2_1000.txt
• 19 Game of life
  • Performance competition data set (grid size NxN, nr of steps P, starting state) is /fs-1/2/kerola/life_800_10000.txt (800x800 matrix, 10000 steps).
    • Best time was 17,5 s (out of 6 projects in Java)
  • Data set is given as a text file with integers N, P, NxN grid in row wise order (1 = alive, 0 = dead), values separated with white space
    • E.g., 4 20    0 0 0 0   0 1 0 0    0 0 1 0      0 0 0 0
    • You can give suggestions  (web address for data set file) for competition data set via email to the instructor. Give your solution time in the email.
    • Currently a 800x800 grid for 10000 steps can be solved in 10-20 seconds (code in C).
• 23 Image processing for ppm images
  • Performance competition data set is /fs-1/2/kerola/7976x4480.ppm with operations {smoothen, smoothen, smoothen, sharpen, sharpen, sharpen}.
    • Best time was 2,1 s (out of 2 projects in Java)
• 25 Stable marriage  -- not selected in 2011
  • Performance competition data set (n, preference arrays) will be given here later on.
  • You can give suggestions  for competition data set via email to the instructor.
    
• 26 n-Queens (find all solutions)
  • Performance competition data set (problem size n) is 17.
    • Best time was 144 s (out of 6 projects in Java)
  • Currently at least one group can solve size 17 problem in under 10 minutes.

Evaluation

Accepted project is given grade 1-20, which is counted as is towards your course grade.

• Minimally passing grade (4/20) is given, if the program works, is easily testable, computes correctly, and utilizes concurrency significantly. Code is readable.
• Normal grade (12/20) is given, if (in addition to those above) user instructions are clear, solution is workable, solution evaluation is sensible, with proper measurements and well reported (or some correctness properties have been show to apply for theorethical problems) .
• Excellent grade (20/20) is given, if (in addition to those above) user guide is excellent, solution is especially good in utilizing concurrency (or many correctness properties have been shown to apply for theorethical problems), code is properly commented, and/or solution (correctness/performance) evaluation is planned, executed and reported especially well.

For performance oriented solutions, the team with fastest solution (or best correctness proofs, problems 10 and 11) for given problem case will get n-1 (max 5) bonus points, when n teams have tried to solve the same problem using the same programming language. The data sets used for performance bonus competition are in instructor fs-home page and they are supposed to be read directly from there. There should be no need for everyone to copy these data set files onto their own directories.

Performance competition will be decided by the results supplied by teams. To ensure honesty in reporting, the projects with best results will be ran and checked against reported results. Also, other projects might be randomly checked as well in this manner.

If it's shown with strong basis that a serially executing algorithm provides a solution quicker for given task and task size than the obvious or well-known best parallel algorithm, a project using such approach can reach excellent grade given that the arguments are presented in documentation and all the other requirements for excellent grade are fulfilled. Referencing relevant existing scientific knowledge in your documentation is strongly advised should you want to take this route.

For study circles of 3 or more students, the team may assign 2 extra points total to one or two students that may have done more work than the others. E.g., "student X will get 2 extra points", or "students X and Y will each get one extra point". The other students must be real participants in the project and in this lecture course, and not just names on the cover sheet.

Assistance and Advice

Most of period IV practice sessions are reserved for project consulting. You can also questions concerning the project during normal practice sessions. Also, you can ask Advice Hut ("neuvontapaja") in Period III Mondays 14-16 (CK110) and Thursdays 13-15 (CK110) any questions on any programming problems. The word is that Thursdays might be better for Java Thread class problems. In Period IV the Advice Hut is only on Thursdays 13-15 (CK110).