Next: Week 6
Up: Week 5
Previous: Class 1: Performance
Announcement: Please see the newsgroup for some new announcements (including the announcement of
html versions of this semester's projects).
In today's class, we will discuss the effect that interconnection
networks have on communication costs, and how you might have to
change the communication cost model to take this factor into account.
This discussion will be based on Section 3.7 of the text.
Thus far, the communication model that we developed for the time required
to send a message was independent of which two PEs where communicating.
For this to be true in real life, each pair of PEs would need to have
a direct link of the same length, leading to 
links, and a very
expensive network!
Instead, real interconnection networks use a limited number of links, and
some method to route messages from one PE to another-sometimes, the PEs
along the way do the routing, and other times, there are special switches
dedicated to routing messages. We define the distance between two PEs
as the minimum number of hops that a message has to traverse to get from one PE
to the other. The diameter of the IN is then the maximum distance
between any two PEs in the network.
An important pair of (often related) questions one needs to ask is:
- how difficult/expensive is it to build the IN?
- what kind of communication speed does it provide?
To answer these questions, there are a set of factors that need to
be considered:
- Diameter of the network.
- The degree of the network. The degree of a node in the network
is the number of links incident on the node. The degree of the overall
network is the maximum node degree in the network.
- Bisection Bandwidth: this is the minimum number of channels
that cross the cut when the network is divided into two equal halves.
- Is the network a static network (fixed links between nodes) or
dynamic (switches reconfigure connections)?
- Competition for bandwidth: If S PEs attempt to use
a link at the same time, the bandwidth is reduced by S.
In this case, we need to modify the communication cost model, and
we get Equation 3.10 in the text. The value of S
depends on the underlying IN.
Static INs:
We will discuss a number of examples of static interconnection networks, and
for each of them, we will evaluate the network based on the factors
defined above.
- Fully Connected network.
- bus-based networks.
- ethernet.
- linear array.
- ring.
- 2-D mesh.
- 2-D mesh with wrap arounds (Illiac IV type network).
- 2-D mesh with toroidal connections.
- 3-D meshes with the above variations.
- Hypercube.
- Trees and Fat Trees.
The above list covers the most popular static INs used in commercial
machines. However, there are many other INs with nice properties that
have been proposed, and used in experimental machines. Examples
are Pyramids, Mesh of Meshes (MOM), Reduced Mesh of Trees (RMOT),
Cube Connected Cycles, etc.
Dynamic INs:
Unlike the above networks, where PEs route messages to
get them to the right place, dynamic networks have separate switches that
can setup different connections on demand. Examples include:
- Crossbar switch.
- Reconfigurable meshes.
- Multistage Interconnection Networks (MINs).
We will discuss each class, and evaluate their performance.
The message of today's discussion is that the underlying interconnection
network can affect the cost of sending and receiving messages, and you
might need to factor this cost into your communication cost model when
you analyze your algorithm.
Next: Week 6
Up: Week 5
Previous: Class 1: Performance