Upper and lower bounds for recurrent and recursively decomposable parallel processor‐networks

A “recursively decomposable network” can be partitioned into a finite number of subnetworks that are smaller “versions of itself,” where the subnetworks are themselves recursively decomposable. Several interesting notions of such networks emerge depending on the collections of parameters chosen to model the relative behavioral characteristics that make a subnetwork a version of another. Examples of such parameters are permutation time, bandwidth, latency, topology, wires, degree, and size. This paper introduces and studies the class of networks that are recursively decomposable relative to bandwidth limitations, and the subclass of “recurrent networks” that are recursively decomposable relative to topology limitations. We show that an N ‐node recursively decomposable into halves network with bandwidth‐inefficiency function β( x ) must be at least \documentclass{article}\pagestyle{empty}\begin{document}$\frac{N}{2}\sum\nolimits_{i = l}^{\lg N}{\frac{1}{{\beta(2^i)}}}$\end{document} wires. This implies that the linear array, hypercube, and completely connected networks are all exactly optimal. The above lower bound is generalized to networks that are recursively decomposable, but not necessarily into halves. We show that the bound is tight up to a constant factor by exhibiting recurrent networks matching the above lower bounds. Our lower bound results both tighten and generalize a result of Meertens: no recurrent, fixed degree network can permute in O (log N ) time. © 1996 John Wiley & Sons, Inc. ©1996 John Wiley & Sons, Inc.