Summary of 20th Feb class

Static networks VS Dynamic Networks

 

Static Networks:-

·         In a static network, the connection between input and output nodes is fixed and cannot be changed.

·         Static interconnection network cannot be reconfigured.

·         The examples of this type of network are linear array, ring, chordal ring, tree, star, fat tree, mesh, tours, systolic arrays, and hypercube.

·         This type of interconnection networks are more suitable for building computers where the communication pattern is more or less fixed, and can be implemented with static connections.

Dynamic Networks:-

·         In dynamic network the interconnection, pattern between inputs and outputs can be changed.

·         The interconnection pattern can be reconfigured according to the program demands.

·         Here, instead of fixed connections, the switches or arbiters are used.

·         Examples of such networks are buses, crossbar switches, and multistage networks.

·         The dynamic networks are normally used in shared memory(SM) multiprocessors.

 

Wormhole Routing:-

A property of a message passing system in which each part of a message is transmitted independently and one part can be forwarded to the next node before the whole message has been received.

 All parts of a single message follow the same route. The independent parts are normally small and this reduces latency and the storage  requirements on each node when compared with message switching where a node receives the whole message before it starts to forward it to the next node.

It is more complex than message switching because each node must keep track of the messages currently following through it.

Wormhole routing is applied to packets in packet switching system so that forwarding of a packet starts as soon as its destination is known, before the whole packet had arrived.

• A message is broken into multiple packets (each packet has header information that allows the receiver to re-construct the original message)

• A packet may itself be broken into flits – flits do not contain additional headers.

• Two packets can follow different paths to the destination. Flits are always ordered and follow the same path

• Such an architecture allows the use of a large packet size (low header overhead) and yet allows fine-grained resource allocation on a per-flit basis.

The characteristics of wormhole switching system include:

• Large network packets are divided into small flits
• Every router is assigned small buffers of one to a few flits.
• The header flit defines the network path for all the other flits in the network pipeline.
• The buffer sequence and links that are already occupied by a given packet of flits constitutes the wormhole system. Typically, the length of the network path is measured in accordance to the number of flits in a single packet.

Let the size of a Flit be F and the size of message be L. N are the no. of processors.

No. of flits = L/F

So, at each stage of a linear network,there would be transfer delay of F/W where W is the Bandwidth.(Propagation delay is neglected)

Total Time = F*N/W + (L-F)*1/W

                = F*(N-1)/W + L/W

This time is much less than the transfer time(N*L/W) obtained when L bits of data was passed through the n/w.

 

• If the output channel is busy, the entire flits chain - including the header – can become stuck blocking communication via the transmission path.

The key advantages of wormhole switching include:

• Working with small, cheap, simple and comparatively fast routers.
• Suitable for long messages.
• Employing only input buffering.
• Throughput is snowballing because it does not buffer the entire network packet to move toward the next node.
• Bandwidth and channel allocation are generally decoupled.

Disadvantages of wormhole switching include:

• Blocks resources in cases of stuck network pipelines
• Prone to deadlock.
• Inability to support backtracking.

 

Why shared memory is faster than message passing:

In message passing suppose we have thousands or so instructions then steps taken to pass it to the another processors are

--First we need to prepare the message

--Then it need to be passed to the IO ,that is call to the OS

--Another processor will receive it in its IO, hence another call to the OS

And as we know that IO are handle through OS and drivers through some program or instructions. So in need to pass only a single message we saw many other instructions are also need to be execute. This is the case for only one instructions if this number increases, we can imagine how much time would increase but in case of shred memory every processor can access memory of any of the other processor no need to involve OS and device drivers or execute these kind of extra instructions

That is why message passing is slower than shared memory.

But yes there are problems with shared memory too

1).Inconsistency

2).Synchronization

However dynamic networks which we discussed before for shared memory can be use for message passing by using memory/buffer as channels to pass the message. Here two processors will communicate through these buffers. One processor sent the message to other processor through this intermediate buffer. But there should be control over which one is accessing to avoid situations like one is reading and another is writing simultaneously then some errors can occur.

To avoid this situation let us suppose we’ve 3 processors and 2 buffers. First processor will send message a message to its buffer , second buffer will act like a network will transfer this message to the buffer of another processor.

Similarly we can implement shared memory through message passing. But one can imagine the time taken as we know that if a processor need to communicate with the memory or another processor then it will be required to invoke OS calls and involve device drivers etc. hence it is not good idea to implement a shared memory over message passing.

 

Distributed shared memory :-

Distributed Shared Memory (DSM) is a form of memory architecture where the (physically separate) memories can be addressed as one (logically shared) address space.  Here, the term shared does not mean that there is a single centralized memory but shared essentially means that the address space is shared (same physical address on two processors refers to the same location in memory). Distributed Global Address Space (DGAS), is a similar term for a wide class of software and hardware implementations, in which each node of a cluster has access to shared memory in addition to each node's non-shared private memory.

 

Scalability:-

scalability is the ability of a system, network, or process to handle a growing amount of work in a capable manner or its ability to be enlarged to accommodate that growth. For example, it can refer to the capability of a system to increase its total output under an increased load when resources (typically hardware) are added. 

 

Scalability  = Speed up on PRAM model/Speed up on realistic machine

 

Submitted by:-

Uzma and Sweety Yadav