Optimal Embeddings of Multiple Graphs into a Mesh of Buses

A mesh of buses (MOB), a versatile parallel architecture, is obtained from a 2-dimensional mesh by replacing each linear connection with a bus. We optimally embed multiple graphs into a MOB by a labeling strategy. This optimal embedding provides an optimal expansion, dilation and congestion at the same time. First, we label on an N-node graph G, possibly disconnected, such that this labeling makes it possible to optimally embed multiple copies of G into an N 0 \Theta N 0 MOB when N 0 is divisible by N . Second, we show that many important classes of graphs have this labeling: for example, tree, cycle, mesh of trees and product graphs including mesh, torus, and hypercube. Third, we generalize these results to optimally embed multiple graphs into a multidimensional and possibly non-square MOB. This labeling strategy is applicable to the embeddings of other classes of graphs into a MOB. Index terms - Graph embedding, mesh of buses, dilation, congestion, expansion 1 Introduction Mes..