Increasing the Size of a Network by a Constant Factor can Increase Performance by More Than a Constant Factor
Richard Koch · SIAM Journal on Computing · 1992
The performance of unbuffered routing algorithms for parallel computer architectures is analyzed. Unbuffered algorithms are an alternative to the use of queues. When the capacity of a switch or communications link is exceeded, the extra messages are discarded, and another attempt to transmit the message will be made at a later time. The analysis presented here is relevant for routing on the BBN Butterfly and Agarwal and Knight’s Alewife architecture, both of which have interconnection networks based on the butterfly graph. Suppose that each of the N inputs of the butterfly independently decides to send a message with probability p, and that the message is sent to a random output, with each output having an equal probability of being chosen. If more than q messages attempt to traverse an edge, the extra messages over q are discarded. q is called the dilation of the network. The bandwidth is the number of messages that reach their destinations. It is shown that if $p = \Omega ((\log N)^{ - 1/q} )$, the expected bandwidth is $\Theta (N(\log N)^{ - 1/q})$, and if $p = o((\log N)^{ - 1/q} )$, the expected bandwidth is $N(p + o(p))$. This result also holds for dilated networks based on the d-ary butterfly and for graphs constructed by taking r copies of butterflies and identifying corresponding inputs and also identifying corresponding outputs. An expression is also derived for the asymptotic constants and it is shown that the probability distribution is tightly concentrated about its mean. Interesting techniques are developed for finding asymptotics of nonlinear systems of recurrences. The result may also have implications for design trade-offs since, for sufficiently large networks, having a fixed amount of hardware increasing the value of q will increase bandwidth more than increasing the values of d or r.