CSC/ECE 506 Spring 2010/12 EC

Interconnection Network Architecture

Introduction

In a multi-processor system, processors need to communicate with each other and access each other's resources. In order to route data and messages between processors, an interconnection architecture is needed.

Typically, in a multiprocessor system, message passed between processors are frequent and short ¹. Therefore, the interconnection network architecture must handle messages quickly by having low latency, and must handle several messages at a time and have high bandwidth.

In a network, a processor along with its cache and memory is considered a node. The physical wires that connect between them is called a link. The device that routes messages between nodes is called a router. The shape of the network, such as the number of links and routers, is called the network topology.

Types of Network Topologies

Linear Array

<pic top_linear> The nodes are connected linearly as in an array. This type of topology is simple, however, it does not scale well. The longest distance between two nodes, or the diameter, is equivalent to the number of nodes.

Ring

<pic top_ring> Similar structure as the linear array, except, the ending nodes connect to each other, establishing a circular structure. The longest distance between two nodes is cut in half.

2-D Mesh

<pic top_2Dmesh> The 2-D mesh can be thought of as several linear arrays put together to form a 2-dimensional structure. Nodes that are not on the edge have 4 input or output links, or a degree of 4.

2-D Torus

<pic top_2Dtorus> The 2-D torus takes the structure of the 2-D mesh and connects the nodes on the edges. This decreases the diameter, but the number of links is higher.

Cube

<pic top_cube> The cube can be thought of as a three-dimensional mesh.

Hypercube

<pic top_hypercube> The hypercube is essentially multiple cubes put together.

Tree

<pic top_tree> The tree is a hierarchical structure nodes on the bottom and switching nodes at the upper levels. The tree experiences high traffic at the upper levels.

Fat Tree

<pic top_fat_tree> The fat tree alleviates the traffic at upper levels by "fattening" up the links at the upper levels.

Butterfly

<pic top_butterfly> The butterfly structure is similar to the tree structure, but it replicates the switching node structure of the tree topology and connects them together so that there are equal links and routers at all levels.