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)?
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|