Homework 6 (Mini-Project) - CIS534 Spring 2010

Instructor: Prof. Milo Martin

Step #1: Mid-Project Report -- Due at start of class on Wednesday, April 14th

Step #2: Project Talks -- In class on Wednesday, April 26th

Step #3: Final Project Report -- Due 5pm on Friday, April 30th

(This project proposal document based on David Wood's project description: http://pages.cs.wisc.edu/~david/courses/cs758/Fall2009/includes/project.html)

Mini-Project Overview

For the last three weeks of the course, you'll be working on a mini-project in teams of three. The project is reasonably open-ended, but should involve writing, tuning, and experimentally analysing parallel code. If appropriate, you should also use one of the frameworks we've talked about this semester: OpenMP, TBB, and/or OpenCL/CUDA (your choice), Java Fork/Join, Cilk, etc.

Option #1: Parallelize a Non-Trivial Computation

Select some computationally intensive computation or program and parallelize some of all of it. Iteratively refine and tune the code to increase the parallel performance. You can use any of the frameworks we've talked about (or more than one, to compare), and you may wish to consider vectoring the code, too. Evaluate the speedup of the parallel implementation and discuss what the remaining bottlenecks might be. The writeup should clearly explain the problem, the various approaches and tuning performed, describe the results, and include any insight and conclusions drawn.

Ideal the application/computation you explore would not just be a synthetic algorithm, but part of an actual application.

Some benchmark suites to give you some ideas. These benchmarks provide descriptions of established computations and provide data input sets. They are already parallel, but you could start with the sequential version and write a new parallel version.

Some application domains to consider:

The simpler the application, the higher the expectation I'll have for tuning and analysis. However, ensure that most of the time is spent on writing the parallel version of the code. Thus, pick a problem with an available non-parallel implementation (perhaps open-source) or one that is easy to write. Again, the focus is on the parallel aspect of the code.

Option #2: Evaluate some Research Idea

Implement and evaluate some parallel runtime, framework, or language improvement. You could experimentally compare two models, including models we only talked about (Cilk, Java Fork/Join). You could explore more advanced implementations of locks (reader-writer locks, adaptive queue-based locks, hierarchical spin locks). You could explore some enhancements to a work-stealing scheduler or implement and evaluate a tricky lock-free data structure. Replicating some of the results of a research paper would be good; trying out your own ideas is even better.

Some ideas:

Relationship to GPU Course

If you're taking or have taken the GPU programming class, your mini-project for this course should be non-GPU related. You might consider comparing a GPU versus CPU implementation, but the core of the mini-project should CPU-based parallelism.

If nobody in your group has taken the GPU programming course, feel free to experiment with CUDA/OpenCL, but I don't have any hardware for you to test it out on (you'll need to have your own).


Step #1: Mid-Project Report

Due at start of class on Wednesday, April 14th

Mid-way through the project, I'd like you to turn in a one or two page document listing the group members, describing the proposed project, and the initial progress. The idea is to be as informative as possible such that I can determine if you're on the right track and so that can give you guidance if needed.

Step #2: Project Talks

In class on Wednesday, April 26th

On the last day of class, groups will present a 12-minute talk using up to seven slides. All group members should present and be ready to answer questions. An example talk outline:

  • Title slide (1 slide)
  • Problem the project addresses & why it is important (1 slide)
  • Methods & how approached the problem (1-2 slides)
  • Preliminary results (1-2 slides)
  • Next steps / future plans (1 slide)

Please bring a hardcopy printout of the slides to me the day of the presentation.

Step #3: Final Project Report

Due 5pm on Friday, April 30th

The reports should consist of an abstract, body and optional appendices, much like many of the paper's we've read (but shorter). The paper should be 5 to 8 pages formatted with two-column with 10 pt font, not counting appendices. The abstract should summarize the contributions of the report in one or two paragraphs. Additional supporting material of any length can be put in appendices. I will read the abstract and body and only skim appendices.

Hints and Tips

You will be graded on how well you define your problem, design and conduct experiments, and present your results. The goal to shoot for a conference paper, like the ones in your reader (only shorter).

Because time is limited, however, the above goal is hard to reach, and I will reward those that aim high even if they do not completely succeed. The key is insuring that some aspects of your work are completely done; it is very hard to grade a project where nothing really works.