EMBEDDING BINARY X-TREES AND PYRAMIDS IN PROCESSOR ARRAYS WITH SPANNING BUSES

We study the problem of network embeddings in 2-1) array architectures in which each row and column of processors are interconnected by a bu s. These architectures are especially attractive if optical buses are used that allow simultaneous access by multiple processors through eit her wavelength division multiplexing or message pipelining, thus overc oming the bottlenecks caused by the exclusive access of buses. In part icular, we define X-trees to include both binary X-trees and pyramids, and present two embeddings of X-trees into 2-D processor arrays with spanning buses. The first embedding has the property that all neighbor ing nodes in X-trees are mapped to the same bus in the target array, t hus allowing any two neighbors in the embedded V-trees to communicate with each other in one routing step. The disadvantage of this embeddin g is its relatively high expansion cost. In contrast, the second embed ding has an expansion cost approaching unity, but does not map all nei ghboring nodes in X-trees to the same bus. These embeddings allow all algorithms designed for binary trees, pyramids, as well as X-trees to be executed on the target arrays.