Parallel Computation - Models of Computation: Exploring the Power of Computing - page 321

7.24 Design an algorithm to perform a prefix computation on an √ n

× √ n mesh in 3 √ n
steps. Show that no other algorithm for this problem on this mesh has substantially
better performance.

ROUTING IN NETWORKS

7.25 Give a complete description of a procedure to set up the switches in a Beneˇsnetwork.
7.26 Show how to perform an arbitrary permutation on a linear array.

THE PRAM MODEL

7.27 a) Design an O ( 1 ) -step CRCW PRAM algorithm to find the maximum element in a
list.
b) Design an O (log log n ) -step CRCW PRAM algorithm to find the maximum ele-
ment in a list that uses O ( n ) processors.
Hint: Construct a tree in which the root and every other vertex has a number of
immediate descendants that is about equal to the square root of the number of leaves
that are its descendants.
7.28 The goal of the list-ranking problem is to assign a rank to each record in a linked
list; the rank of a record is its position relative to the last element in the list where the
last element has rank zero. Each record has two fields, one for its rank and another for
the address of its successor record. The address field of the last record contains its own
address.
Describe an efficient p -processor EREW PRAM algorithm to solve the list-ranking
problem for a list of p items stored one per location in the common memory.
Hint: Use pointer doubling in which each address is replaced by the address of its
current successor.
7.29 Consider an n -vertex directed graph in which each vertex knows the address of its
parent and the roots have themselves as parents. Under the assumption that each vertex
is placed in a unique cell in a common PRAM memory, show that the roots can be
found in O (log n ) steps.
7.30 Design an efficient PRAM algorithm to find the item in a list that occurs most often.
7.31 Figure 7.23 shows two trees containing one and three copies of a computational ele-
ment, respectively. This element accepts three inputs and produces three outputs using

, an associative operator. Tree (a) accepts a , b ,and c as input and produces a , a b ,

and b c as output. Tree (b) accepts a , b , c , d ,and e as input and produces a , a b ,

a b c , a b c d ,and b c d e as output. If the input and output at the root

of the trees are combined with , the output of each tree is the prefix computation on

its inputs.
Generalize the constructions of Fig. 7.23 to produce a circuit for the prefix function on
n inputs, n arbitrary. Give a convincing argument that your construction is correct and
derive good upper bounds on the size and depth of your circuit. Show that to within
multiplicative factors your construction has minimal size and depth.