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

Figure 7.22 A four-by-four mesh-of-trees network.

7.2 Sketch a data-parallel program that operates on a sorted list of keys and finds the largest
number of times that a key is repeated.
7.3 Sketch a data-parallel program to find the last record in a linked list where initially each
record contains the address of the next item in the list (except for the last item, whose
next address is null ).
Hint: Assign one processor to each list item and assume that accesses to two or more
distinct addresses can be done simultaneously.
7.4 The n

n mesh by replac-
ing each linear connection forming a row or column by a balanced binary tree. (See
Fig. 7.22 .) Let the entries of two n

× n mesh-of-trees network, n = 2 r ,isformedfroma n ×

n matrices be uniformly distributed on the vertices
of original mesh. Give an efficient matrix multiplication algorithm on this network and
determine its running time.
7.5 Identify problems that arise in a crossbar network when more than one source wishes
to connect to the same destination. Describe how to insure that only one source is
connected to one destination at the same time.

×

THE PERFORMANCE OF PARALLEL ALGORITHMS

7.6 Describe how you might apply Amdahl's Law to a data-parallel program to estimate its
running time.
7.7 Consider the evaluation of the polynomial p ( x )= a n x n + x n− 1 x n− 1 + + a 1 x + a 0

on a p -processor shared-memory machine. Sketch an algorithm whose running time is
O ( p +log n ) for this problem.

···