Question

Give an O(lg n)-time EREW algorithm that determines for each object in an n-object list whether it is the middle (n/2

th) object.

Answer 1

The following EREW algorithm starts with a value x[i] in each object i in a list L. If object i is the kth object from the beginning of the list, then x[i] = xk is the kth element of the input sequence. Thus, the parallel prefix computation produces y[i] = yk = [1, k].

LIST-PREFIX(L)

1 for each processor i, in parallel

2 do y[i] x[i]

3 while there exists an object i such that next[i] NIL

4 do for each processor i, in parallel

5 do if next[i] NIL

6 then y[next[i]] y[i] y[next[i]]

7 next[i] next[next[i]]
The pseudocode and Figure 30.3 indicate the similarity between this algorithm and List-Rank. The only differences are the initialization and the updating of d or y values. In List-Rank, processor i updates d[i]--its own d value--whereas in LIST-PREFIX, processor i updates y[next[i]]--another processor's y value. Note that LIST-PREFIX is EREW for the same reason as List-Rank: pointer jumping maintains the invariant that for distinct objects i and j, either next[i] next[j] or next[i] = next[j] = NIL.

Figure 30.3 shows the state of the list before each iteration of the while loop. The procedure maintains the invariant that at the end of the tth execution of the while loop, the kth processor stores [max(1, k - 2t + 1), k], for k = 1, 2, . . . , n. In the first iteration, the kth list object points initially to the (k + 1)st object, except that the last object has a NIL pointer. Line 6 causes the kth object, for k = 1, 2, . . . , n - 1, to fetch the value [k + 1, k + 1] from its successor. It then performs the operation [k, k] [k + 1, k + 1], yielding [k, k + 1], which it stores back into its successor. The next pointers are then jumped as in LIST-RANK, and the result of the first iteration appears in Figure 30.3(b). We can view the second iteration similarly. For k = 1, 2, . . . , n - 2, the kth object fetches the value [k + 1, k + 2] from its successor (as defined by the new value in its field next), and then it stores [k - 1, k] [k + 1, k + 2] = [k - 1, k + 2] into its successor. The result is shown in Figure 30.3(c). In the third and final iteration, only the first two list objects have non-NIL pointers, and they fetch values from their successors in their respective lists. The final result appears in Figure 30.3(d). The key observation that makes LIST-PREFIX work is that at each step, if we perform a prefix computation on each of the several existing lists, each object obtains its correct value.

the parallel prefix algorithm LIST-PREFIX on a linked list. (a) The initial y value of the kth object in the list is [k, k]. The next pointer of the kth object points to the (k + 1)st object, or NIL for the last object. (b)-(d) The y and next values before each test in line 3. The final answer is in part (d), in which the y value for the kth object is [1, k] for all k.

Comment Down if Any Query

Pleause Thumbs up if you satisfy with Answer