P. Kulasinghe et A. Elamawy, OPTIMAL REALIZATION OF SETS OF INTERCONNECTION FUNCTIONS ON SYNCHRONOUS MULTIPLE BUS SYSTEMS, I.E.E.E. transactions on computers, 45(8), 1996, pp. 964-969
We develop a formal and systematic methodology for designing an optima
l multiple bus system (MBS) realizing a set of interconnection functio
ns whose graphical representation (denoted as IFG) is symmetric. The p
roblem of constructing an optimal MBS for a given IFG is NP-Hard. In t
his paper, we show that polynomial time solutions exist when the IFG i
s vertex symmetric. This is the case of interest for the vast majority
of important interconnection function sets. We present a particular p
artition (which can be found in polynomial time) on the edge set of a
vertex symmetric IFG, that produces a symmetric MABS with minimum numb
er of buses as well as minimum number of interfaces. We demonstrate se
veral advantages of such an MBS over a direct-link architecture realiz
ing the same IFG, in terms of the number of ports per processor, numbe
r of neighbors per processors, and the diameter.