a In oddeven reduction the first phase is combining equation

a. In odd-even reduction, the first phase is combining equations so as to reduce the number of unknowns down to one. Show how to modify odd-even reduction as exaplained above so that any desired unknown can be found at the end of this reduction phase.

b. Show that, with enough processors, all unknowns may be solved in parallel by the technique of part (a). Show that the complexity of odd-even reduction is O(log n) using O(n) processors.

Solution

Use as many processes as N\' where N\' is a power of 2 and the smallest number larger than N. Assign a special value such as \"infinity\" to all the extra processes (some kind of a padding). Extra Ps will take part in the algorithm for the sake of regularity and simplicity, but won\'t be doing any useful work. BITONIC SORT EXAMPLE: (Arbitrary Sequence) --------------------- Unsorted sequence : C N M F H A P D (sorted in windows of 1) (bitonic sequences of size 2) D=1 C N M F A H P D (sorted in windows of 2) (bitonic sequences of size 4) D=2 C F M N P H A D C F M N P H D A (sorted in windows of 4) (bitonic sequences of size 8) D=3 C F D A P H M N C A D F M H P N A C D F H M N P (sorted in windows of 8) TIME COMPLEXITY FOR BITONIC SORT : =================================== Bito-sort on windows of size 2 Bito-sort on windows of size 4 : noninc - nondec - noninc - .... Bito-sort on windows of size 8 : noninc - nondec - noninc - .... Bito-sort on windows of size 2 1 step Bito-sort on windows of size 4 : 2 steps Bito-sort on windows of size 8 : 3 steps ........ Bito-sort on windows of size 2^k: k steps Total STEPS = 1 + 2 + 3 + 4 + .....+ k where k=logN = 1/2 * k(k+1) = 1/2 * (log N)^2 TOTAL EXECUTION TIME of Bitonic Merge Sort: O((logN)^2)