CSC/ECE 506 Spring 2012/12a mt

Interconnection Network Topologies

Introduction

In a multiprocessor environment, the terms interconnection network usually refers to the links between multiple independent processors. There are several different network topologies that are selected based upon the unique characteristics for which a system requires. For example, in a shared memory multiprocessor, messages generally are: short, frequent, and make it hard for processors to hide the message communication delay; therefore, shared memory multiprocessors prefer interconnection networks that have low latency and high bandwidth. While latency and bandwidth are two very important factors an interconnection network, there are plenty of other factors to consider: coherence protocol, memory consistency, communication protocols, etc. In order to better understand the unique aspects and characteristics that are considered for an interconnection network, we will discuss certain examples of interconnection topologies that were researched then abandoned, as well as recent developments in networks for large scale multiprocessor systems.

Recent Studies

Balanced Variental Hypercube<ref>Tripathy, C. R., and N. Adhikari. "On A New Multicomputer Interconnection Topology For Massively Parallel Systems." International Journal of Distributed and Parallel Systems. 2.4 (2011): 162-178. Print. http://arxiv.org/ftp/arxiv/papers/1108/1108.1462.pdf</ref>

Background

Among the recent developments of various multicomputing networks, the Hypercube (HC) has enjoyed the highest popularity due to many of its attractive properties: regularity, symmetry, small diameter, strong connectivity, recursive construction, partitionability and relatively small link complexity. Additionally, there have been several variations of the Hypercube, including (but not limited to) the Varietal Hypercube (VH) and Balanced Hypercube (BH). The VH has a lower degree, average distance, and cost when compared to several other versions of Hypercube like the Folded Hypercube, Twisted Hypercube, Crossed Hypercube, etc. On the other hand, the BH has proven to be better in terms of fault tolerance (which improves system reliability as the number of processors increase) compared to the regular Hypercube.

• In interconnection network design, some of the most important performance parameters to consider are: communication efficiency, reliability, fault tolerance, and cost effectiveness. Thus, in order to meet the demands for such a network with a large number of processors, a new design that combined the basic structures of the VH and BH was designed known simply as the Balanced Varietal Hypercube (BVH). It "has got a reduced diameter, optimal average distance with less cost", and the inherited merits of fault tolerance from the BH. The following exhibits the BVH's topological properties for an n-dimensional BVH:

Parameters

Based on tests and comparisons to other hypercube networks, the BVH has certainly proven to be a compromise between the two extremes of BH and VH. For instance, in terms of topological parameters like diameter and cost, VH has the least, BH has the most, and BVH patterns out between the two. Furthermore, in terms of reliability and cost effectiveness, BVH is far more efficient than BH.

• Degree = 2n.
  1. of Nodes = 2^2n
  2. of Edges = n*2^2n
• Diameter: if n=1, 2; if n>1, n + n/2

(considered to be the most important part of any network)

• Average distance: (1/(2^2n))*sum of all distances

(conveys actual performance better in practice)

• cost = degree * diameter = [2n * (n + n/2)]

(less cost usually treated as the best)

References

<references></references>