User:Mdcotter

New Interconnection Topologies

Introduction

Parallel processing has assumed a crucial role in the field of supercomputing. It has overcome the various technological barriers and achieved high levels of performance. The most efficient way to achieve parallelism is to employ multicomputer system. The success of the multicomputer system completely relies on the underlying interconnection network which provides a communication medium among the various processors. It also determines the overall performance of the system in terms of speed of execution and efficiency. The suitability of a network is judged in terms of cost, bandwidth, reliability, routing ,broadcasting, throughput and ease of implementation. Among the recent developments of various multicomputing networks, the Hypercube (HC) has enjoyed the highest popularity due to many of its attractive properties. These properties include regularity, symmetry, small diameter, strong connectivity, recursive construction, partitionability and relatively small link complexity.

Metrics Interconnection Networks

Network Connectivity

Network nodes and communication links sometimes fail and must be removed from service for repair. When components do fail the network should continue to function with reduced capacity. Network connectivity measures the resiliency of a network and its ability to continue operation despite disabled components i.e. connectivity is the minimum number of nodes or links that must fail to partition the network into two or more disjoint networks The larger the connectivity for a network the better the network is able to cope with failures.

Network Diameter

The diameter of a network is the maximum internode distance i.e. it is the maximum number of links that must be traversed to send a message to any node along a shortest path. The lower the diameter of a network the shorter the time to send a message from one node to the node farthest away from it.

Narrowness

This is a measure of congestion in a network and is calculated as follows: Partition the network into two groups of processors A and B where the number of processors in each group is Na and Nb and assume Nb < = Na. Now count the number of interconnections between A and B call this I. Find the maximum value of Nb / I for all partitionings of the network. This is the narrowness of the network. The idea is that if the narrowness is high ( Nb > I) then if the group B processors want to send messages to group A congestion in the network will be high ( since there are fewer links than processors )

Network Expansion Increments

A network should be expandable i.e. it should be possible to create larger and more powerful multicomputer systems by simply adding more nodes to the network. For reasons of cost it is better to have the option of small increments since this allows you to upgrade your network to the size you require ( i.e. flexibility ) within a particular budget. E.g. an 8 node linear array can be expanded in increments of 1 node but a 3 dimensional hypercube can be expanded only by adding another 3D hypercube. (i.e. 8 nodes)

Hypercube

Hypercube networks consist of N = 2^k nodes arranged in a k dimensional hypercube. The nodes are numbered 0 , 1, ....2^k -1 and two nodes are connected if their binary labels differ by exactly one bit.

Referecences

<references />