NJIT
Investigation of reduced hypercube (RH) networks : embedding and routing capabilities
Abstract
dc:description.abstractThe choice of a topology for the interconnection of resources in a distributed-memory parallel computing system is a major design decision. The direct binary hypercube has been widely used for this purpose due to its low diameter and its ability to efficiently emulate other important structures. The aforementioned strong properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per node with an increase in the total number of nodes. The reduced hypercube (RH) topology, which is obtained by a uniform reduction in the number of links for each hypercube node, yields lower complexity interconnection networks compared to hypercubes with the same number of nodes, thus permitting the construction of larger parallel systems. Furthermore, it has been shown that the RH at a lower cost achieves performance comparable to that of a regular hypercube with the same number of nodes. A very important issue for the viability of the RH is to investigate the efficiency of embedding frequently used topologies into it. This thesis proposes embedding algorithms for three very important topologies, namely the ring, the torus and the binary tree. The performance of the proposed algorithms is analyzed and compared to that of equivalent embedding algorithms for the regular hypercube. It is shown that these topologies are emulated efficiently on the RH. Additionally, two already proposed routing algorithms for the RH are evaluated through simulation results.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Electrical Engineering - (M.S.)
- Discipline thesis:degree_discipline
- Electrical and Computer Engineering
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sideras, Michalis A.
- Contributors dc:contributor
-
- Sotirios Ziavras
- Denis L. Blackmore
- John D. Carpinelli
Subjects
dc:subject × 4Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.njit.edu/theses/1697