Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., George Washington Univ., Washington, DC, USA
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;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the