Homework #1
Due Tuesday 10/3/2006 in class
[10 points]

1. PRAM algorithms.
1. Give a CRCW PRAM algorithm to find the max of an array 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 compute the maximum N numbers, that runs in time O(log₂(N))
4. What are the speedup and efficiency as a function of N?
2. Speedup.
You are given some time on a new parallel computer.
1. Your favorite program runs in 64 seconds on 1 processor. This is the so-called "best serial algorithm." You then parallelize the program so that it runs in 11.5 seconds on 16 processors (T₁₆), What is the parallel speedup?
2. The program doesn't parallelize perfectly. If it did, what would T₁₆ be?
3. Your parallel program contains two parts. One part parallelizes perfectly. The other part must run as a serial section, as you didn't have time to parallelize it. What fraction of the serial running time T₁ is spent in the serial section?
3. Data parallelism. Revised 10/3/06
   You are given an N × N 2D array, X[ N , N ], and an N element vector y[N]
   1. Using a doubly nested forall loop, make a copy of y[ ] in each row i of X[ ] (X[i,:]), such that the copying over the entire array completes in 1 time unit.
   2. We are given an arbitrary vector p[ ], which we use to rearrange the elements of y[ ]:

          forall i = 0 to N do
              y[p[i]] = y[i]
          end do
      

      After running the code, we discover that some elements are incorrect. What restriction on p[ ] is required in order to ensure correctness?

4. Sorting.
   The following bubble sort algorithm will sort its N element input using at most O(N²) comparisons.

       for i = N-1 to 1 by -1 do
           for j = 0 to i-1 do
   	      Compare-exchange(a[j] , a[j+1])
            end do
       end do
   

   where Compare-exchange(x,y) will swap the contents of x and y if x > y, and the by -1 construct steps backwards through the array.

   To parallelize this sort algorithm, we are tempted to introduce a forall into the inner loop nest.

        forall j = 0 to i-1 do
   	  Compare-exchange(a[j] , a[j+1])
        end do
   

   1. This strategy fails to produce the correct result. Why is this the case?
   2. Extra credit (2 points). Restructure the program so that it will parallelize. Hint: use the by keyword, this time with a positive step size 2, to step through every other element of the array. You may have to introduce new loop nests

          forall j = 0 to i-1 by 2 do