The Grid-Pyramid: A Generalized Pyramid Network |
| |
Authors: | M R HoseinyFarahabady H Sarbazi-Azad |
| |
Affiliation: | (1) IPM School of Computer Science, Tehran, Iran;(2) Sharif University of Technology, Tehran, Iran |
| |
Abstract: | The Pyramid network is a desirable network topology used as both software data-structure and hardware architecture. In this
paper, we propose a general definition for a class of pyramid networks that are based on grid connections between the nodes
in each level. Contrary to the conventional pyramid network in which the nodes in each level form a mesh, the connections
between these nodes may also be according to other grid-based topologies such as the torus, hypermesh or WK-recursive. Such
pyramid networks form a wide class of interconnection networks that possess rich topological properties. We study a number
of important properties of these topologies for general-purpose parallel processing applications. In particular, we prove
that such pyramids are Hamiltonian-connected, i.e. for any arbitrary pair of nodes in the network there exists at least one
Hamiltonian path between the two given nodes, and pancyclic, i.e. any cycle of length 3, 4 … and N, can be embedded in a given N-node pyramid network. It is also proven that two link-disjoint Hamiltonian cycles exist in the torus-pyramid and hypermesh-pyramid
networks. |
| |
Keywords: | Interconnection networks Pyramid Mesh Torus WK-recursive mesh Hypermesh Hamiltonian-connectivity Hamiltonian path Hamiltonian cycle Pancyclicity Link-disjoint Hamiltonian cycles |
本文献已被 SpringerLink 等数据库收录! |
|