Parallel Computer Architecture

806 CHAPTER 10 Interconnection Network Design

expected number of output ports covered by k random inputs to an n-port switch,

then

E(n,k

+

l)=E(n,k)

+

n

-

E

^

k)

n

Computing this recurrence up to k = n for various switch sizes reveals that the

expected output channel utilization for a single cycle of a fully loaded switch

quickly drops to about

65%.

Queuing theory analysis shows that the expected utili-

zation in steady state with input queuing is 59% (Karol, Hluchyj, and Morgan 1987).

The impact of head-of-line blocking can be more significant than this simple

probabilistic analysis indicates. Within a switch, there may be bursts of traffic for