Parallel computing					15.11.2010

Exercise 3

No X-exercises this week.

We switch from human parallel algorithms to PRAM parallel algorithms.
The algorithms must be presented in programming language -like algorithm
notation (and par-do statements). The syntax may be like C, Pascal,
Modula-2, etc. If you need to, you can specify local and shared
variables separately in each block.

You can write algorithms either by hand (and copy to white/black board
at exercise class) or preferably to a file at your own account
(cs/UEFAD) or USB drive, tec. Then we can examine it using data
projector. Pictures at white board are still needed (draw a picture of
each exercise).

11) What are the time complexity, used number of processors, and work of
    the following parallel procedure (as a function of N)? Which PRAM
    variant is required? You can assume that all processor execute in
    strict synchrony. A + i*N/2 means a subarray A[i*N/2..] of array A.
    I.e., refering to the same array, but with different startpoint.

    procedure doit(A : array; N : integer);
	if N > 1 then begin
		for i := 0 to N/2-1 pardo
			A[i] := A[i+N/2];
		for i := 0 to 1 pardo
			doit(A + i*N/2, N/2);		
		for j:= 1 to log(N) do
			for i := 0 to N-j pardo
				A[i] := A[i] + A[i+j];
	end

12) Refine the matrix multiplication algorithm (N*N matrix, N^2
    processors, O(N) time) to work on EREW PRAM (see handouts page 69).

13) Refine the matrix multiplication algorithm to work in O(logN) time
    with N^3/logN processors. Now you may use CREW. You may assume N to be
    of form 2^n. Sketch how the algorithm could be modified to EREW.

14) Refine the prefix-sum algorithm to a work optimal one by using
    blocking (see handouts page 94) .

15) Write a PRAM algorithm that compares two strings similarly as
    strcmp() or String.compareTo(), i.e., return 0, -1, 1 depending on
    alphabetical order. You may assume that the lengths of both strings
    are equal and of convenient size (e.g., a power of two). You may use
    PRIORITY CRCW. Time complexity? Number of needed processors? Hint:
    raw power.