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.

Unpopular Topologies

Today, many in the parallel computer programming world have come to realize that depending on the type of task needed to be accomplished, certain interconnection networks are more useful than others. Furthermore, the networks that are most in favor today: use hundreds (if not thousands) of nodes, utilize crossbar switches and sub-switch buffers, adapting routing that avoids deadlocks, etc. However, from the 1980s to the early 1990s, the mindset and the views on interconnection networks of programmers were different.

Introduction to Interconnection Network Architecture

In order to better understand the reason behind the different viewpoints and change of opinions in the 1990s it is better to understand a bit about interconnection architecture.

Brief History

Ever since inter-processor interconnection technologies were first introduced in the 1960s, many interconnection topologies fads have come and gone.

Recent Studies

Balanced Varietal 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

• Degree = 2n
• Number of Nodes = 2^2n
• Number of Edges = n*2^2n
• Diameter: if (n=1), 2; if (n>1), n + n/2
• Average distance: (1/(2^2n))* sum of all distances
• Cost = degree * diameter = [2n * (n + n/2)]

Performance

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.

Omega Network

A crucial design attribute of a large network system is its reliability. When the system size grows, the probability of having all system nodes fault free during a given operation period falls quickly and could reach an unacceptable low point. It is, thus, necessary to incorporate redundancy into the system design to guarantee proper continuous operation even after the failure of some nodes.<ref>Bataineh, Sameer, and Ghassan E. Quanzu'a. "Reliable Omega Interconnected Network for Large-Scale Multiprocessor Systems." The Computer Journal. 46.5 (2003): 467-475. Print. http://comjnl.oxfordjournals.org/content/46/5/467.abstract</ref>

Background

In real-time applications, fault tolerance and reliability are said to be two of the most important factors to consider. As a result, the main focus of the Omega Network's design was to be able to maintain its network structure despite any faults that may occur.

Description

In order to maintain the network's structure, there are additional, redundant nodes and links added to the structure to act as back-ups for the primary nodes. For instance, in the proposed design, a control switch is added between nodes and four additional switches are added to each node. In a fault-free state, everything works as it should and the nodes are considered to be in the "X" state. However, in the event of a node malfunction, the node switches to the "V" state and the four switches are used to redirect traffic flow away from the node toward its replacement. Its replacement is quite probably one of the extra nodes. Due to the presence of the extra links and control switches, this particular network is known as the FTΩ (fault-tolerance omega).

Each node has four links attached to them: two for heading forward away from the node, and two coming from behind into the node. Furthermore, the FTΩ design only has one extra node per primary node. As a result, a data path for this network can tolerate one fault, but no more than that. To be specific, when a node malfunction occurs, a node replaces it via an extra link to transfer the traffic; however, extra links are limited, and when one is in use, this makes it impossible for certain adjacent (or nearby) nodes to be used in case of any subsequent faults; these unusable nodes are called critical nodes. In order to improve the current design, it would have to incorporate another set of extra nodes.

References

<references></references>

Pop Quiz

1) If a Balanced Varietal Hypercube has 4 dimensions (n = 4), than how many nodes and edges will the network have, respectively?

a) 8, 512

b) 8, 1024

c) 256, 512

d) 256, 1024

2) What is a more simplified way to calculate the cost of a BVH?

a) 3n

b) 3n^2

c) 2n^2 + n

d) 2n^2 + 2n

3) True or False: The current FTΩ can tolerate more than one node malfunction at a time.

Answer Key

1) d; 2) b;