Final White Paper Instructions

CPT S 483: Final White Paper (instructions and guidelines)

When to submit?                     Noon PDT, December 15, 2016 (Thursday of Finals week)
Where to submit?                    OSBLE dropbox AND email ananth@eecs.wsu.edu (do both before deadline)
Will there be any extension?    No
Assignment type:                    Individual
Submission file type:                Each submission will be accepted only as a single PDF

This course has a white paper required for all students instead of a final exam. The paper is due at or before Noon of December 15, 2016 (Thursday of the Finals week). This is an individual assignment (i..e., not team-based).

How it works?

Step 1) Problem Identification (Due date: November 10, 2016)

The problem for the white paper is to design and implement parallel counting sort.

Input: An array A of n numbers, where each number's value is bounded in a fixed interval of [min, max].
Output: An array B, which is the sorted array for A.

We already discussed in detail how to do counting sort in serial and also discussed ways to implement counting sort algorithm in parallel for distributed memory platforms (MPI).

Based on these discussions, you are expected to develop three implementations for parallel counting sort:
a) serial implementation;
b) OpenMP multitthreaded implementation;
c) MPI distributed memory parallel implementation.

Once you implement, you need to design experiments to answer and report on the following questions:

1) How do the implementations scale as a function of the number of processors/threads, and as a function of the input size?
2) Report on the speedups and efficiencies as observed through your experiments, using the serial implementation as your baseline.
3) How do the implementations compare against themselves (i.e., OpenMP vs. MPI vs. serial)? For MPi code you might want to split your total runtime into computation time vs. communication time.

Step 2) Work on the problem (Recommended completion date: November 30, 2016)

In this phase you are supposed to work on the design and programming part of the problem.

Step 3) Review White Paper (Recommended timeframe: Dead week)

During the dead week you will have the opportunity to go over your programming projects and/or the written report (partial or complete) with me for comments and feedback. I can suggest ways to improve it. This doesn't need to happen during the class time. We can set up individual times (please email to schedule).

Step 4) Write and submit white paper (Hard submission deadline: Noon PDT, December 15, 2016)

The white paper should be NOT EXCEED 5 pages including any required references. It should be written like a short scientific paper. The document should use 1.5 line spacing, 11pt Times New Roman font (or comparable font). The final submission should be uploaded as one single PDF.

The white paper should be organized as follows:
Section 1) Introduction
        - provide problem background,

Section 2) Problem Statement
        - problem definition (what is the input? what is the output?), use a formal definition to the extent possible. We used formal ways to define a problem in the class. Look at parallel prefix sum or other problems for example. Please use those as examples.

Section 3) Key Challenges in Parallelization
        - State briefly why parallelization poses challenges for this problem

Section 4) Proposed Approach(es)
        - Propose your key ideas and approach elements here. It is encouraged that you describe your algorithm precisely in the form of a pseudocode. Use figures to help illustrate and articulate the main ideas clearly. This section should also do a complexity analysis of your algorithm - space and run-time complexity.

Section 5) Experimental Results and Discussion
         - Please report your experimental results and your evaluation of those results in this section. Also add your discussion in an objective manner.

Section 6) References
        - This section should consist of citations to any literature that you have cited in the main text (any of the above sections). The bibliography format should be that of IEEE format (other similar ones okay), which means that each reference will be numbered and the numbered entries would appear like this:

[1] [author1_initial}. author1_Lastname, [author2_initial}. author2_Lastname. "Paper title", {Conference or Journal name}, {page and volume numbers}, {Year of publication}.

If you look up papers on Google Scholar there will be a CITE link next to each paper. If you click that it will show you different formats. You can use one of them.

Confirmed List of White Paper Topics (Presentation schedule will be posted in November):
Please check and report any discrepancies!

Name	Topic	Problem statement?	Quad chart Template