OPTIMAL REALIZATION OF SETS OF INTERCONNECTION FUNCTIONS ON SYNCHRONOUS MULTIPLE BUS SYSTEMS

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.