Homework #1
Due Thursday 4/8/2004 in class
[10 points]

1. PRAM algorithms.
1. Give a CRCW PRAM algorithm to sum a list of N numbers.
2. What are the speedup and efficiency as a function of N? As a basis for a serial algorithm, use a Random Access Machine, which is the special case of a PRAM restricted to 1 processor.
3. Now, give an efficient Concurrent Read Exclusive Write (CREW) algorithm to sum N numbers, that runs in time O(log₂(N))
4. What are the speedup and efficiency as a function of N?
2. Speedup.
1. You are given some time on a new parallel computer which has 8 processors. You run a program which parallelizes perfectly during certain phases, but which must run serially during the others. If the best serial algorithm runs in 64 seconds on one processors, and your parallel algorithm runs in 22 seconds on 8 processors (T₈), what fraction of the serial running time T₁ is spent in the serial section?
2. What is the parallel speedup?
3. You have another program that has three distinct phases. The first phase runs optimally on 5 processors; this is, performance remains constant on 6 or more processors. The second phase runs optimally on 10 processors, and the third on 15. The phases consume 20%, 20%, and 60% of the serial running time, respectively. If the running time of the best serial algorithm is 100 seconds, what is the running time of the parallel algorithm on 15 processors?