Parallel computing					29.11.2010

Exercise 5

No X-exercises this week.

The following tasks are OpenMP implementations of parallel algorithms.
Now remember that number of processors is very low. Thus there is no
need to try to parallelize to more than few processors. We'll cover
OpenMP in more detail at Wed lecture.

21) Write a parallel implementation of the longest common subsequence
    -task using OpenMP and C (or Fortran). Take the sequential
    implementation from www-page, parallelize it using OpenMP, test it
    using a multiprocessor/core system, and record the speedup you got.

22) Parallelize the prefix-sum -algorithm using OpenMP. Take the
    sequential implementation from www-page and use the same techique
    that we showed in the blocking prefix sum algorithm and radix sort.
    I.e., do local prefix sums, prefix sum the sums (sequentially), and
    adjust the final result. Now the simple "parallel for" -construc is
    not enough, but you need to use OpenMP threads and make of function
    that uses those.

23) Analyse the time complexity of blocking prefix algorithm of exercise
    14 (example at www-page) if each shared memory reference (to the
    shared arrays) takes L time units. Further, analyse the algorithm if
    you can retrieve k elements from shared memory in L+k*G time (G is
    word gap as in LogGP). How to change the algorithm to work most
    efficiently if L is fairly large (e.g., 10x) compared to G?

Now we'll forget shared memory and start using message passing between
processes/processors. All processes execute the same code. Use PID
(process-id) to distinguish the processes.

24) Convert the prefix-sum algorithm (handouts page 94) to a message
    passing algorithm. In the beginning, each processor has a single
    value.  In the end, the each processor has the correspondig value of
    the prefix sum. Express your algorithm so that all processors can
    execute the same algorithm, i.e., use PID (process-id) in giving
    roles to processors. Use message passing primitives send(in
    destination, in data) and receive(in source, out data), where
    destination and source are process-id's and data is the value to be
    send / variable to which message is received.

25) This task is moved to week 6.