Interconnection Network Design - Parallel Computer Architecture

What is an Interconnection network in parallel computer architecture?

The information is passed from any of the desired source node by using minimal possible latency, to any of the required destination node by using the interconnection network. Huge volumes of information are passed by this method several numbers of times. The cost of the transfer of information is considered to be low.

Different links and switches are being used by the interconnection network for transforming the information between the source and the destination nodes. The flow control mechanism, its switching strategy, routine algorithm and the topology determines the interconnection network.

What is the Organizational Structure of Interconnection Network?

The organizational structure of the interconnection network comprises of three components. They are -

  • Links – Links are used for passing of the information. From one end to other an analog signal is transmitted, which enables the other end to receive the original information. A combination of more than one electric wires or optical fibres are combined into a cable and at each of the ends, a connector is fixed such that the cable is attached to the switch.
  • Switches – Switches constitute a combination of the ports both input and output, which are connected using a cross-bar, an internal buffering and an control logic. Switches usually have equal number of input and output ports.
  • Network Interfaces – Special links are used for connecting the network interface. The routing and the control information is being transformed by network interface. Network interface has both input and output buffering. The flow control and identification of the errors is done by network interface. The complexity associated with its processing, the storage capacity and the number of ports used determines dost of the network interface.

What is an Interconnection Network?

By adopting the concept of topology, the switches are connected to some of the elements such as other switches, processors and memories through an interconnection network. In parallel computer systems, the information is communicated among the processors by interconnection network.

The interconnection networks are of two types -

  • Direct connection networks – The nodes that are adjacent to each other are connected, which is known as direct connection networks. The connection between the two points is fixed and hence direct connection networks are considered to be static. Examples of direct networks are rings, meshes and cubes.
  • Indirect connection networks – The connections between the nodes is not fixed and not all the adjacent nodes are connected. Depending on the demands of the application, the nodes are connected to each other by using the concept of topology. There are three different types of Indirect connection networks -
  1. Bus networks – In these networks, the resources are assigned to each of the bit lines. The lines are also used for data and address lines. Bus networks require an arbiter, when more number of buses is used by the bus network.
  2. Multistage networks – Different multiple stages of switch constitute multistage networks. An interstage connection pattern (ISC), is used for connecting ‘axb’ switches. Most of the multistage networks use 2x2 switch elements. Different types of multistage networks can be developed by suing different patterns of interstage connections.
  3. Crossbar switches – The connection can be either created or can be stopped by using crossbar switches. The switch is used either to create a connection or stop the connection. Without any blocking information can be communicated using the crossbar switches.

How to evaluate Design Trade-offs in Network Topology?

For any of the network topology design the main concern or issue is the routing distance. One of such methods is the store-and-forward method of routing. Under this method, it is assumed that the dimensions can be minimized and a mesh can be built by considering the degree of the switches and the number of links as the main cost.

The other method is traffic pattern. Under this method, all the paths are kept short, by adopting dimensional networks. The networks where communication is supposed to be passed onto to the adjacent nodes, the low dimensional networks best suits the situation.

What is Routing?

The path taken up for information from passing though source to destination is considered as a route and is identified and defined by the routing algorithm. The paths between the source and the destination are restricted to only one possible path by dimension order routing. According to this concept, the distance which is travelled by high-order dimension is considered and the ideal and the first route, the distance travelled by the next level order dimension is considered as the next best route.

Routing Mechanisms

In the header of the packet, the different channels of output are identified by using high-speed switches known as routing mechanisms. Routing mechanisms can be determined by three types – arithmetic, source-based port and table look-up. The routers of LAN and WAN follow some of the traditional routing mechanisms but which seems to be more complex then the above mentioned three routing mechanisms. The routing mechanisms are simplified and made efficient by parallel networks by deciding on the routes in each of the cycles.

Deterministic Routing

When the source and destination alone can identify the route and when the network traffic is not allowed to identify and determine the route, then the routing algorithm is considered to be deterministic. The minimal deterministic routing is the shortest path of the routing algorithm from the source to the destination.

Deadlock Freedom

There are many cases which lead to deadlocks. When a resource of a network is used by multiple messages at the same time, this situation may lead to deadlock. When data is sent by two different nodes to each other at the same time prior to their receiving of the data, this situation lead to deadlock.

The occurrences of the deadlock can be eliminated by concentrating and maintaining in such a manner that traffic patterns does not exist, which may cause deadlock. The traffic patterns can be eradicated by not allowing forming any cycles in the dependency graph of the overall channel. This can be achieved by clearing the occurrences of the dependencies as the message pass through the networks.

To simplify, the occurrence of the dependency cycles can be reduced by numbering the channel resources which enables all the routes to follow the specified sequence, avoiding queues.

What is a Switch Design?

The pattern in which the structure of the switch and the wiring of the switch determines the network design. The specific routing that needs to be adopted and the topology that best suites is determined and identified by the degree of the switch, internal routing mechanisms of the switch, internal buffering etc. Data path, control and storage together constitute a network switch.

What are Ports?

The number of input and output ports when multiplied with the width of the channel, the resultant is the number of pins. The switches are restricted by certain number of pins as the perimeter of the chip grows.

Internal Datapath

Each of the input port when connected to each of the output port, such a connection is referred to as datapath. When each of the input port is connected to a distint output port it is considered as a non-blocking cross-bar datapath.

Channel Buffers

The performance of a particular switch depends on its buffer storage. The buffering is external to the switch for some of the conventional routers and switches. The buffering is internal to the switch for VLSI switches. The increase in the chip size results in increase in the buffering facilitating more options for the designers.

How the Flow is controlled?

There are some instances, where the shared network resources are used by various multiple data flows at the same specified time, these flows leads to confusion and becomes out of control. Some of the measures to be taken to control such data flow. To avoid losing of the data, allow some of the flows to process and block some of the flows.

The problem of flow data flows in parallel computers is different from that of local networks. In parallel computers, the time span provided is very short and existence of the parallel flows is in huge volumes and the data need to be delivered accurately.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd Protection Status

Parallel Computer Architecture Topics