MODULE 4

[I] Interconnection Networks

· Interconnection networks are also called networks or communication

subnets, and nodes are sometimes called end systems or hosts.
· The connection of two or more interconnection networks is called
internetworking,
· Internetworking, relies on communication standards to convert information
from one kind of network to another.
· The generic components of this community are - computer nodes, hardware
and software interfaces, links to the interconnection network, and the
interconnection network.
· A generic interconnection network is shown below:

· Depending on the number of nodes and their proximity, these

interconnections are given different names.

[A] Wide area network (WAN)

· Also called long haul network

· WAN connects computers distributed throughout the world.
· WANs include thousands of computers, and the maximum distance is
 thousands of kilometers.
· ATM is a current examplxe of a WAN.

[B] Local area network (LAN)

· This device connects hundreds of computers, and the distance is up to a few

kilometers.
· Unlike a WAN, a LAN connects computers distributed throughout a building
or on a campus.
· The most popular and enduring LAN is Ethernet

[C] Storage or System area network (SAN)

· This interconnection network is for a machine room, so the maximum

distance of a link is typically less than 100 meters.
· It can connect hundreds of nodes.
· SAN usually means Storage area network as it connects computers to
storage devices, such as disk arrays.

[II] A Simple Network

· The below figure shows a simple model with a unidirectional wire from
machine A to machine B and vice versa.

· At the end of each wire is a first-in-first-out (FIFO) queue to hold the data.
· In this example, each machine wants to read a word from the other’s
memory.
· A message is the information sent between machines over an
 interconnection network.
· For one machine to get data from the other, it must first send a request
containing the address of the data it desires from the other node.
· When a request arrives, the machine must send a reply with the data.
· Hence, each message must have at least 1 bit in addition to the data to
determine whether the message is a new request or a reply to an earlier
request.
· The payload contains the data.
· The below figure shows the format of messages in our simple network.

· The software steps to send a message are as follows:

1. The application copies data to be sent into an operating system buffer.

2. The operating system calculates the checksum, includes it in the header or

trailer of the message, and then starts the timer.

3. The operating system sends the data to the network interface hardware
and tells the hardware to send the message.

· The software steps to receive a message is in the reverse order as

follows:

3. The system copies the data from the network interface hardware into the
operating system buffer.

2. The system calculates the checksum over the data.

· If the checksum matches the sender’s checksum, the receiver sends an
acknowledgment back to the sender.
 · If not, it deletes the message, assuming that the sender will resend the
message when the associated timer expires.

1. If the data pass the test, the system copies the data to the user’s address
space and signals the application to continue.

NOTE :

· When the sender gets the acknowledgment, it releases the copy of the
message from the system buffer.

· If the sender gets the time-out instead of an acknowledgment, it resends the

data and restarts the timer.

Bandwidth (Throughput)
· It is the maximum rate at which the network can propagate information once
the message enters the network.
· Bandwidth includes the headers and trailers as well as the payload, and the
units are traditionally bits/second rather than bytes/second.

Time of flight
· The time for the first bit of the message to arrive at the receiver, including
the delays due to repeaters or other hardware in the network.
· Time of flight can be milliseconds for a WAN or nanoseconds for an SAN.

Transmission time
· The time for the message to pass through the network, not including time of
flight.
 · It is also the difference in time between when the first bit of the message
arrives at the receiver and when the last bit of the message arrives at the
receiver.

Transport latency
· The sum of time of flight and transmission time.
· It is the time between when the first bit of the message is injected into the
network and when the last bit of the message arrives at the receiver.

Sender overhead
· The time for the processor to inject the message into the network, including
both hardware and software components.

Receiver overhead
· The time for the processor to pull the message from the interconnection
network, including both hardware and software components.

[III] Connecting More Than Two Computers

(a) Shared versus Switched Media

· The simplest way to connect multiple computers is to have them share a

single interconnection medium, just as I/O devices share a single I/O bus.
· When the medium is shared, there must be a mechanism to coordinate and
arbitrate the use of the shared medium so that only one message is sent at a
time.
· If the network is small, it may be possible to have an additional central
arbiter to give permission to send a message.
· Centralized arbitration is impractical for networks with a large number of
nodes.
· When two nodes send at the same time, it is called a collision.
· Listening to avoid and detect collisions is called carrier sensing and
collision detection.
· To avoid repeated head-on collisions, each node whose message was
garbled waits (or “backs off”) a random time before resending.
· Another approach to arbitration is to pass a token between the nodes, with
the token giving the node the right to use the network.
· If the shared media is connected in a ring, then the token can rotate through
all the nodes on the ring.
· The alternative to sharing the media is to have a dedicated line to a switch
that in turn provides a dedicated line to all destinations.
· Switches allow communication directly from source to destination, without
intermediate nodes to interfere with these signals.
· Such point-to-point communication is faster than a line shared between
many nodes

· Every node of a shared line will see every message, even if it is just to check
to see whether or not the message is for that node.
· This type of communication is sometimes called broadcast to contrast it
with point-to-point.
· The shared medium makes it easy to broadcast a message to every node, and
even to broadcast to subsets of nodes, called multicasting.
· Switches allow multiple pairs of nodes to communicate simultaneously,
giving these interconnections much higher aggregate bandwidth than the
speed of a shared link to a node.
· Switches also allow the interconnection network to scale to a very large
number of nodes.
· Switches are also called data switching exchanges, multistage
 interconnection networks, or interface message processors (IMPs)

(b) Connection-Oriented versus Connectionless Communication

1. Connectioned Oriented Service

· Frequency-division multiplexing is a technique by which the total

bandwidth available in a communication medium is divided into a
series of non-overlapping frequency bands, each of which is used to
carry a separate signal.
· For eg, In telecommunication an operator set up a connection
between a caller and a callee, and once the connection is established, a
conversation can continue for hours.
· To share transmission lines over long distances, the
telecommunications industry used switches to multiplex several
conversations on the same lines.
· Circuit switching is the traditional way to offer a connection-based
service.
· A circuit is established from source to destination to carry the
conversation, reserving bandwidth until the circuit is broken.

2. Connectionless Service

· Here the packetswitched transmission is used in which divide the

information into packets, or frames.
· Each packet including the destination of the packet plus a portion of
the information.
· The packetswitched approach allows more use of the bandwidth of the
medium and is the traditional way to support connectionless
communication.
· The postal system is a good example of connectionless
communication.

(c) Routing: Delivering Messages

· Switched media use three solutions for routing - Source-based

routing,Virtual circuit and Destination-based routing.
· In source-based routing, the message specifies the path to the
destination. Since the network merely follows directions, it can be
 simpler.
· In virtual circuit, a circuit is established between source and
destination, and the message simply names the circuit to follow. eg :
ATM uses virtual circuits.
· The third approach is a destination-based routing, where the message
merely contains a destination address, and the switch must pick a path
to deliver the message.
· Destination-based routing may be deterministic and always follow the
same path, or it may be adaptive, allowing the network to pick
different routes to avoid failures or congestion.
· Closely related to adaptive routing is randomized routing, whereby
the network will randomly pick between several equally good paths to
spread the traffic throughout the network.
· Switches in WANs route messages using a store-and-forward policy;
each switch waits for the full message to arrive in the switch before it
is sent on to the next switch.
· The alternative to store-and-forward is for the switch to examine the
header, decide where to send the message, and then start transmitting
it immediately without waiting for the rest of the message. This is
called cut-through routing or wormhole routing.

(d) Congestion Control

· Packet-switched networks generally do not reserve interconnect

bandwidth in advance, so the interconnection network can become
clogged with too many packets.
· Packets take longer to arrive, and in extreme cases fewer packets per
second are delivered by the interconnect.
· Deadlock is achieved when packets in the interconnect can make no
forward progress no matter what sequence of events happens.
· The solution to congestion is to prevent new packets from entering the
network until traffic reduces.
· Congestion control refers to schemes that reduce traffic when the
collective traffic of all nodes is too large for the network to handlem,
· There are three basic schemes used for congestion control in
computer interconnection networks,
-packet discarding,
-flow control
-choke packets.
 Packet discarding.
· If a packet arrives at a switch and there is no room in the buffer, the
packet is discarded.
· Internetworking protocols such as UDP discard packets.

Flow Control
· The idea is to use feedback to tell the sender when it is allowed to
send the next packet.
· One version of feedback is via separate wires between adjacent
senders and receivers that tell the sender to stop immediately when the
receiver cannot accept another message.
· A more sophisticated variation of feedback is for the ultimate
destination to give the original sender a credit to send n packets before
getting permission to send more. These are generically called credit-
based flow control.
· A window is one version of credit-based flow control.
· The window’s size determines the minimum frequency of
communication from receiver to sender.
· The TCP protocol uses a window.
.
Choke packets
· Here the idea is to limit traffic when the network is congested.
· The idea is for each switch to see how busy it is, entering a warning
state when it passes a threshold.
· Each packet received by the switch in a warning state are sent back to
the source via a choke packet that includes the intended destination.
· The source is expected to reduce traffic to that destination by a fixed
percentage.

[IV] Practical Issues for Interconnection Networks

[a] Connectivity

· The number of machines that communicates affects the complexity of the

network and its protocols.
· The protocols must target the largest size of the network, and handle the
types of anomalous events that occur.

[b] Connecting the Network to the Computer-

 The following things have to be taken into consideation while connecting
the network -

· Whether to use the memory bus or the I/O bus, how to avoid invoking the
operating system etc.
· Whether to buy a standard network interface card or are willing to design or
buy one that only works with the memory bus on your model of computer.
· The location of the network connection significantly affects the software
interface to the network as well as the hardware.
· A related question of where to connect to the computer is how to connect to
the software.
· Do you use programmed I/O or direct memory access (DMA) to send a
message?
· In general, DMA is the best way to send large messages.
· Whether to use DMA to send small messages depends on the efficiency of
the interface to the DMA.
· The DMA interface is usually memory-mapped, and so each interaction is
typically at the speed of main memory rather than of a cache access.
· If DMA setup takes many accesses, each running at uncached memory
speeds, then the sender overhead may be so high that it is faster to simply
send the data directly to the interface.

[c] Standardization: Cross-Company Interoperability

· Standards are useful in many places in computer design, but with

interconnection networks they are often critical.
· Advantages of successful standards include low cost and stability.
· The customer has many vendors to choose from, which both keeps price
close to cost due to competition.
· One drawback of standards is the time it takes for committees to agree on
the definition of standards, which is a problem when technology is changing
quickly.
· Another problem is when to standardize: on one hand, designers would like
to have a standard before anything is built; on the other, it would be better if
something is built before standardization to avoid legislating useless features
or omitting important ones.
· LANs and WANs use standards and interoperate effectively.
· WANs involve many types of companies and must connect to many brands
of computers, so it is difficult to imagine a proprietary WAN ever being
successful.
 · The ubiquitous nature of the Ethernet shows the popularity of standards for
LANs as well as WANs, and it seems unlikely that many customers would
tie the viability of their LAN to the stability of a single company.

[V] Multiprocessors

Taxonomy of Parallel Architectures

· The idea of using multiple processors both to increase performance and to
improve availability.
· Flynn proposed a simple model of categorizing all computers into 4
categories.
· They are :-

1. Single instruction stream, single data stream (SISD) .

2. Single instruction stream, multiple data streams (SIMD)
3. Multiple instruction streams, single data stream (MISD)
4. Multiple instruction streams, multiple data streams (MIMD)

1. Single instruction stream, single data stream (SISD)

· This category is the uniprocessor.

2. Single instruction stream, multiple data streams (SIMD)

· The same instruction is executed by multiple processors using different data
streams.
· Each processor has its own data memory (hence multiple data).
· But there is a single instruction memory and control processor, which
fetches and dispatches instructions.
· The multimedia extensions are a limited form of SIMD parallelism. Vector
architectures are the largest class of processors of this type.

3. Multiple instruction streams, single data stream (MISD)

· No commercial multiprocessor of this type has been built to date.

4. Multiple instruction streams, multiple data streams (MIMD)

· Each processor fetches its own instructions and operates on its own data.

· The processors are often off-the-shelf microprocessors.

· MIMD has clearly emerged as the architecture of choice for general-purpose
multiprocessors.
· With an MIMD, each processor is executing its own instruction stream.

· In many cases, each processor executes a different process.

· A process is an segment of code that may be run independently, and that the
state of the process contains all the information necessary to execute that
program on a processor.
· In a multiprogrammed environment, where the processors may be running
independent tasks, each process is typically independent of the processes on
other processors.
· It is also useful to be able to have multiple processors executing a single
program and sharing the code and most of their address space.
· When multiple processes share code and data in this way, they are often
called threads.
· To take advantage of an MIMD multiprocessor with n processors, we must
usually have at least n threads or processes to execute.
· The independent threads are typically identified by the programmer or
created by the compiler.
· Since the parallelism in this situation is contained in the threads, it is called
thread-level parallelism.
· Existing MIMD multiprocessors fall into two classes, depending on the
number of processors involved, which in turn dictate a memory organization
and interconnect strategy.
1. Centralized shared-memory architectures
2. Distributed-memory multiprocessor

1) Centralized shared-memory architectures

· In the centralized shared-memory architectures the processors share
a single centralized memory and the processors and memory are
interconnected by a bus.
· With large caches, the bus and the single memory, possibly with
multiple banks, can satisfy the memory demands of a small number of
processors.
· By replacing a single bus with multiple buses, or even a switch, a
centralized shared memory design can be scaled to a few dozen
processors.
· Although scaling beyond that is technically conceivable, sharing a
centralized memory, even organized as multiple banks, becomes less
attractive as the number of processors sharing it increases.
· Because there is a single main memory that has a symmetric
relationship to all processors and a uniform access time from any
processor, these multiprocessors are often called symmetric (shared-
memory) multiprocessors (SMPs), and this style of architecture is
sometimes called UMA for uniform memory access.
· This type of centralized shared-memory architecture is currently by
far the most popular organization.
 2. Distributed-memory multiprocessor
· To support larger processor counts, memory must be distributed
among the processors rather than centralized.
· Otherwise the memory system would not be able to support the
bandwidth demands of a larger number of processors without
incurring excessively long access latency.
· Both direct interconnection networks (i.e., switches) and indirect
networks (typically multidimensional meshes) are used.

· Advantages of distributing the memory among the nodes are

· It is a cost-effective way to scale the memory bandwidth, if most of the

accesses are to the local memory in the node.
· It reduces the latency for accesses to the local memory.

· The key disadvantage for distributed memory architecture is that

communicating data between processors becomes somewhat more complex
and has higher latency,because the processors no longer share a single
 centralized memory.

[a] Models for Communication and Memory Architecture

· There are two alternative architectural approaches that differ in the method
used for communicating data among processors.
· In the first method, communication occurs through a shared address
space.
· That is, the physically separate memories can be addressed as one logically
shared address space, meaning that a memory reference can be made by any
processor to any memory location, assuming it has the correct access rights.
· These multiprocessors are called distributed shared-memory (DSM)
architectures.
· The term shared memory refers to the fact that the address space is shared;
that is, the same physical address on two processors refers to the same
location in memory.
· Shared memory does not mean that there is a single, centralized memory.
· In contrast to the symmetric shared-memory multiprocessors, also known as
UMAs (uniform memory access), the DSM multiprocessors are also called
NUMAs, non-uniform memory access.
· Alternatively, the address space can consist of multiple private address
spaces that are logically disjoint and cannot be addressed by a remote
processor.
· In such multiprocessors, the same physical address on two different
processors refers to two different locations in two different memories.
· Each processor-memory module is essentially a separate computer; therefore
these parallel processors have been called multicomputers.
· A multicomputer can even consist of completely separate computers
connected on a local area network, which, today, are popularly called
clusters.
· For a multiprocessor with multiple address spaces, communication of data is
done by explicitly passing messages among the processors. Therefore, these
multiprocessors are often called message passing multiprocessors.
· In message passing multiprocessors, communication occurs by sending
messages that request action or deliver data.
· For example, if one processor wants to access or operate on data in a remote
memory, it can send a message to request the data or to perform some
operation on the data.
· In such cases, the message can be thought of as a remote procedure call
 (RPC).
· When the destination processor receives the message, it performs the
operation or access on behalf of the remote processor and returns the result
with a reply message. This type of message passing is also called
synchronous.
· Here the initiating processor sends a request and waits until the reply is
returned before continuing.

[b] Performance Metrics for Communication Mechanisms

Three performance metrics are critical in any communication mechanism:
1. Communication bandwidth
· Bandwidth is the maximum rate of data transfer across a given path.

· How does the communication mechanism affect the communication

bandwidth of a node has to be considered.
· When communication occurs, resources within the nodes involved in the
communication are tied up or occupied, preventing other outgoing or
incoming communication.
· When this occupancy is incurred for each word of a message, it sets an
absolute limit on the communication bandwidth.
2. Communication latency
· Ideally the latency is as low as possible.

· Communication latency is = Sender overhead + Time of flight +

Transmission time + Receiver overhead
3. Communication latency hiding
· How well can the communication mechanism hide latency by overlapping
communication with computation or with other communication has to be
taken into account.

[VI] Synchronization and various Hardware Primitives

[a] Synchronization
· Synchronization mechanisms are typically built with user-level software
 routines that rely on hardware-supplied synchronization instructions.
Basic Hardware Primitives
· The key ability we require to implement synchronization in a multiprocessor
is a set of hardware primitives with the ability to atomically read and modify
a memory location.
· These hardware primitives are the basic building blocks that are used to
build a wide variety of user-level synchronization operations, including
things such as locks.
· One typical operation for building synchronization operations is the atomic
exchange, which interchanges a value in a register for a value in memory.
· Use this to build a basic synchronization operation, assume that we want to
build a simple lock where the value 0 is used to indicate that the lock is free
and a 1 is used to indicate that the lock is unavailable.
· A processor tries to set the lock by doing an exchange of 1, which is in a
register, with the memory address corresponding to the lock.
· The value returned from the exchange instruction is 1 if some other
processor had already claimed access and 0 otherwise.
· In the latter case, the value is also changed to be 1, preventing any
competing exchange from also retrieving a 0.
· There are a number of other atomic primitives that can be used to implement
synchronization.
· They all have the key property that they read and update a memory value in
such a manner that we can tell whether or not the two operations executed
atomically.
· One operation, present in many older multiprocessors, is test-and-set, which
tests a value and sets it if the value passes the test.
· For example, we could define an operation that tested for 0 and set the value
to 1, which can be used in a fashion similar to how we used atomic
exchange.
· Another atomic synchronization primitive is fetch-and-increment: it returns
the value of a memory location and atomically increments it.
 · By using the value 0 to indicate that the synchronization variable is
unclaimed, we can use fetch-and-increment, just as we used exchange.
· The coherence mechanisms of a multiprocessor to implement spin locks:
locks that a processor continuously tries to acquire, spinning around a loop
until it succeeds.
· Spin locks are used when a programmer expects the lock to be held for a
very short amount of time and when she wants the process of locking to be
low latency when the lock is available.
· Because spin locks tie up the processor, waiting in a loop for the lock to
become free, they are inappropriate in some circumstances.

[VII] Models of Memory Consistency

· Cache coherence ensures that multiple processors see a consistent view of
memory.
· It does'nt answer the question of how consistent the view of memory must
be.
· By 'consistent ', it means when must a processor see a value that has been
updated by another processor.
· Since processors communicate through shared variables,in what order must
the processor observe the writes of another processor is relevant.
· Since the only way to observe the writes of another processor is through
reads , it depends upon what properties must be enforced among reads and
writes to different locations by different processors.
eg :
P1: A=0; P2: B=0;
---------- ----------
A=1; B=1;
L1: if(B==0) .... L2: if(A==0).....
 · In the above eg, the processes are running on different processors and that
locations A and B are originally cached by both processors with initial value
of 0.
· If writes always take immediate effect and immediately seen by other
processors, it will be impossible for both if statements(L1 & L2) to evaluate
their conditions as true ,since reaching the if statement means that either A or
B must have been assigned the value 1.
· But suppose the write inavlidate is delayed, and the processor is allowed to
continue this delay, then it is possibe that both P1 and P2 have not seen the
invalidations for B and A respectively before they attempt to read the values.
· The point here is should the above behavior be allowed, and if yes , under
what conditions and thats the where the concept of models of memory
consistency comes into play.
· The most straightforward model for memory consistency is Sequential
consistency.

[A] SEQUENTIAL CONSISTENCY MODEL:

· This model requires that the result of any execution be the same as if the
memory accesses executed by each processor were kept in order and the
accesses among different processors were arbitrarily interleaved.
· All instructions are executed atomically without any reordering.

· The advantage here is simplicity and the disadvantage is low performance.

eg: STORE A
LOAD A
LOAD B
LOAD C
LOAD D
· Here A's initial contents is in the cache. According to sequential consistency
model, every LOAD opeartion has to wait until STORE A finishes,
eventhough A is not required in any load operation.
· This causes unnecessary waiting and reduces the performance.

[B] RELAXED CONSISTENCY MODELS- BASICS

· The key idea in relaxed consistency model is to allow reads and writes to
complete out of order, but to use synchronization operations to enforce
ordering ,so that a synchronized program behaves as if the processor were
sequentially consistent.
· The major three sets of ordering that are relaxed are :

1) W-> R ordering - Total store ordering

2) W-> W ordering - Partial store ordering
3) R->R & R-W ordering - Includes models like Alpha
consistency model, PowerPC consistency model and realease
consistency.

eg : LOAD A
LOAD B
STORE B
LOAD B
STORE C
LOAD B
STORE A
STORE B
· In the abov example, the following rules can be imposed on relaxed
consitency model.
· They are :

1) Writes are not reordered wrt. other writes.

eg : STORE B cannot exceute until STORE A finishes
 its execution.
2) Loads are not reordered wrt. other loads.
eg : LOAD B cannot execute before LOAD A finishes its
execution.
3) Writes are not reordered wrt. other reads.
eg: STORE C cannot execute before LOAD B finishes
its execution.
4) Reads may be reordered wrt writes to different
memory addresses.
->This means if a STORE operation is taking a
very long time, a subsequent read can progress
provided they dont access the same memory
location.
eg : LOAD B can be executed before STORE C
finishes its execution.( Different memory
accesses).

------------------------------------------END---------------------------------