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

combines two values, one that it owns and one owned by one of its neighbors. Thus, if
t steps are executed to compute a value, that value cannot depend on more than 2 t other
values. Since each entry in an n

× n product matrix is a function of 2 n other values, t must

be at least log 2 ( 2 n ) .

The lower bound stated above applies only to normal algorithms. If a non-normal algo-
rithm is used, each processor can combine up to d values. Thus, after k steps, up to d k values
can be combined. If 2 n values must be combined, as in n

× n matrix multiplication, then

k log d ( 2 n )=(log 2 2 n ) / log 2 d .Ifan n 3 -processor hypercube is used for this problem,

d = 3 log 2 n and k =Ω(log n/ log log n ) .
The normal matrix multiplication algorithm described above can be translated to linear
arrays and 2D meshes using the mappings ba sed on the shuffle and unshuffle operations. The

≥

2D mesh version has a running time O ( √ n log n ) , which is inferior to the running time of
thealgorithmgiveninSection 7.5.3 .

7.8 Routing in Networks
A topic of major concern in the design of distributed memory machines is routing ,thetaskof
transmitting messages among processors via nodes of a network. Routing becomes challenging
when many messages must travel simultaneously through a network because they can produce
congestion at nodes and cause delays in the receipt of messages.
Some routing networks are designed primarily for the permutation-routing problem ,the
problem of establishing a one-to-one correspondence between n senders and n receivers. ( A
processor can be both a sender and receiver.) Each sender sends one message to a unique
receiver and each receiver receives one message from a unique sender. (We examine in Sec-
tion 7.9.3 routing methods when the numbers of senders and receivers differ and more than
one message can be received by one processor.) If many messages are targeted at one receiver,
a long delay will be experienced at this receiver. It should be noted that network congestion
can occur at a node even when messages are uniformly distributed throughout the network,
because many messages may have to pass through this node to reach their destinations.

7.8.1 Local Routing Networks
In a local routing network each message is accompanied by its destination address. At each
network node ( switch ) the routing algorithm, using only these addresses and not knowing the
global state of the network, finds a path for messages.
A sorting network, suitably modified to transmit messages, is a local permutation-routing
network. Batcher's bitonic sorting network described in Section 6.8.1 will serve as such a
network. As mentioned in Section 7.7 , this network can be realized as a normal algorithm on
a hypercube, with running time on an n -vertex hyper cu be O (log 2 n ) . (See Problem 6.28 .)
On the two-dimensional mesh its running time is O ( √ n ) (see Problem 7.21 ), whereas on the
linear array it is O ( n ) (see Problem 7.20 ).
Batcher's bitonic sorting network is data-oblivious ; that is, it performs the same set of op-
erations for all values of the input data. The outcomes of these operations are data-dependent,
but the operations themselves are data-independent. Non-oblivious sorting algorithms per-
form operations that depend on the values of the input data. An example of a local non-