Parallel computing		7.12.2010

Exercise 6

Notice: these exercises exceptionally Tuesday 7.12. Joensuu 12-14 at
T/B181 and Kuopio 12-14 at MT4.

The following X3 exercise replaces standard exercises 26 and 27.

The answers to X-exercises have to be unique for every student. No
copies of the same answer are allowed. The answer has to be sent via
email by Monday 4:00 pm (the previous day). You will receive an
acknowledgment upon successful processing. Answers will be graded. The
answer must also contain a short self-evaluation in which you describe
whether the algorithm works, nearly works, or does not probably work;
how efficient it is, etc. A correct and proper self-evaluation is worth
one point (in case of a proper answer). As the answer is a C program,
the self evaluation must be included in the comments of the program. 

Send your answer (the compileable C source file) to simo.juvaste@uef.fi
(i.e., sjuva@cs.joensuu.fi) with a subject  PAR_X3_email@add.re.ss
(with underscores), and the answer (with self-evaluation) as the body of
the message (no MIME attachments, no HTML). At simplest, using program
mail at cs.uef.fi:

    /usr/ucb/mail -s PAR_X3_email@add.re.ss sjuva < answer.c 

where email@add.re.ss is the email address you have in WebOodi (or given
to this course), and answer.c is the C-program containing your answer.
The exercise handler will compile your answer and respond with compiler
report. Notice, that some email clients (as web-mail) will split long
lines, thus resulting problems in comments, strings, etc. Be careful not
to send HTML or MIME attachements.

X3) Parallelize the prime counting program found from course www-page
    using OpenMP. The key function counts how many primes there are on
    given integer interval. For max 4 points, it is sufficient to
    parallelize the countPrimes() function. For full 6 points, you need
    to parallelize also the helping function smallPrimes() (even if the
    smallPrimes() is quite fast for small n). Take the skeleton from
    course www-page.

28) (This is the leftover from last week (task #25)). Implement the
    prefix-sum algorithm of previous exercise 24 in MPI. Do not use
    collective communication primitives. The algorithm must have
    sublinear time complexity.

29-30) Parallelize the prime counting of X3 using MPI. Test speedup
    using csclust0.