DocumentCode :
2496242
Title :
Design and analysis of product networks
Author :
Youssef, Abdou
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., George Washington Univ., Washington, DC, USA
fYear :
1995
fDate :
6-9 Feb 1995
Firstpage :
521
Lastpage :
528
Abstract :
In this paper a unified theory of Cartesian product networks is developed. Product networks (PN) include meshes, tori, and hypercubes among others. This paper studies the fundamental issues of topological properties, cost-performance ratio optimization, scalability, routing, embedding, and fault tolerance properties of PNs. In particular, the degree, diameter, average distance, connectivity, and node-symmetry of PNs are related to those of their constituent factor networks. Cost/performance analysis and comparison between different PNs, especially n-dimensional meshes/tori and n-dimensional r-ary hypercubes, are conducted, and the optimal trade-off between the number of dimensions and the size along each dimension are identified. Fast generic algorithms for point-to-point routing, broadcasting and permuting on PNs are designed, making use of the corresponding algorithms of the factor networks. Finally, efficient embeddings on PNs are constructed for linear arrays, rings, meshes, tori and trees
Keywords :
multiprocessor interconnection networks; optimisation; Cartesian product networks; average distance; broadcasting; connectivity; cost-performance ratio optimization; embedding; fault tolerance properties; generic algorithms; hypercubes; meshes; node-symmetry; point-to-point routing; product networks; routing; scalability; topological properties; tore; unified theory; Algorithm design and analysis; Broadcasting; Costs; Fault tolerance; Hypercubes; Multidimensional systems; Partitioning algorithms; Performance analysis; Polynomials; Routing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the
Conference_Location :
McLean, VA
Print_ISBN :
0-8186-6965-9
Type :
conf
DOI :
10.1109/FMPC.1995.380472
Filename :
380472
Link To Document :
بازگشت