Algorithms and Parallel Computing

5.1 INTRODUCTION

We saw in Chapter 3 that parallel computers require an interconnection network to allow exchange of data between the processors and between the processors and common shared or distributed memories. Interconnection networks connect processors in a parallel computer system. The main factors that affect the interconnection network performance are

1. network links, which could be wires, wireless, or even optic channels or media;

2. switches that connect the links together;

3. the protocol software/firmware that is used to route the packets or messages between the processors through the switches and links; and

4. the network topology, which is the way the switches are connected together.

The capabilities and characteristics of the interconnection network have a direct influence on the resulting performance of the multiprocessor system. The following sections discuss the different types of networks used in multiprocessor systems. We should mention here that multicore processors have all the cores and their interconnection network on the same chip. Thus, the network is called network-on-chip (NoC). We discuss in this chapter interconnection networks based on their topology. Topology defines how the processor or nodes are connected. The topology impacts system performance parameters such as data throughput, delay, and network power consumption.

We define the interconnection network diameter as the longest distance between two nodes in the graph. The diameter represents ...