Parallel computing					13.12.2010

Exercise 7

Last lecture at Wed 15.12.
Course exam at Thu 16.12. 08:00 - 10:00 at T2/D106 / MT3

The following X4 exercise replaces standard exercises 31 and 32.

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 Sunday 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_X4_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_X4_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.

X4) Parallelize the longest common subsequence (task 21) using MPI. Use
    the same skeleton (lcss_seq.c) from www-page.

33) Parallelize the counting of primes (X3) using pthreads, Java
    threads, or CUDA.

At www-page you can find a "game" where all processes generate a random
number 0..9, compare the numbers, and the one with the largest number is
the winner. After someone has 5 wins, all quit. Here, if there are
several processes with the same number, no process wins and all
processes just go the next round. The program is implemented in MPI and
Fortran 90. MPI version uses processes and collective
communication/computation. F90 version does not actually use processes,
but just vector operations. F90 compiler at cs: /opt/SUNWspro/bin/f90. A
brief introduction to Fortran 90:at lecture handouts. Longer version at
http://web.am.qub.ac.uk/users/d.dundas/msci_workshop/fortran/notes/fortran90.pdf.
F90 compiler for Linux/Win/Mac/etc.: http://www.gfortran.org/ or
http://www.g95.org/.

34) Modify the MPI version of the game to solving draws by new numbers.
    Only those processes that had the largest number will generate new
    numbers, and only if there was a sole winner, it wins. If even the
    new numbers generated a draw, the procedure is repeated among
    remaining processing with the largest value on each round until the
    winner of the round if found. Hint: create new communication groups.

35) Modify the f90 version of the game to have rematches among winners
    as in exercise 34. Try to use as much vector operations as possible.