Title :
An optimal multiple bus network for fan-in algorithms
Author :
Dharmasena, Hettihe P. ; Vaidyanathan, Ramachandran
Author_Institution :
Dept. of Electr. & Comput. Eng., Louisiana State Univ., Baton Rouge, LA, USA
Abstract :
We consider a class of algorithms called fan-in algorithms, with numerous applications in problems involving semigroup operations. We present a multiple bus network (MBN) that runs any fan-in algorithm in optimal number of steps. The degree and loading of this MBN are each 3. We prove that the product of the degree and loading of any MBN that runs a fan-in algorithm in optimal time is at least 9. This establishes the proposed MBN to be optimal
Keywords :
multiprocessor interconnection networks; parallel algorithms; fan-in algorithms; multiple bus network; optimal multiple bus network; semigroup operations; Application software; Contracts; Costs; Hypercubes; Multiprocessor interconnection networks; Network topology; Parallel algorithms; Polynomials;
Conference_Titel :
Parallel Processing, 1997., Proceedings of the 1997 International Conference on
Conference_Location :
Bloomington, IL
Print_ISBN :
0-8186-8108-X
DOI :
10.1109/ICPP.1997.622566
