MESSAGE PASSING MECHANISMS

Message passing in any multicomputer computer network requires hardware and software support. There are  both deterministic and adaptive routing algorithms for achieving deadlock-free message routing.

Message Formats:

Message is a logical unit for internode communication. It is assembled from an arbitrary number of fixed length packets.

Packet: It is the basic unit containing the destination address for routing purposes. A sequence number is needed in each packet  as they may arrive asynchronously to allow message to be reassembled properly. A packet can further divided into a number of fixed-length flits(flow control digits). Routing information  and sequence number occupy the header flits. The remaining flits length is often affected by the network size.

                                       WORMHOLE ROUTING

 

• The packets are split to flits which are snaked along the route exactly in the same pipeline way as in conflict-free VCT switching. Hence, also here transmission of different packets cannot be interleaved or multiplexed freely over one physical channel without additional architectural support.
• Routers do not have buffers for the whole packets. Every router has small buffers for one or a few flits.
• The header flit again builds a path in the network, which the other flits follow in pipeline. The sequence of buffers and links occupied by flits of a given packet forms the wormhole. However, the length of the path here is proportional to the number of flits in the packet. Typically, it spans the whole path between the source and destination.
• If the header cannot proceed due to busy output channels, the whole chain of flits gets stalled, occupying flit buffers in routers on the path constructed so far and blocking other possible communications.

 

 

 

source:http://pages.cs.wisc.edu/~tvrdik/7/html/Section7.html                  

              Wormhole switching of a packet

(a)   The header is copied in the output buffer after having done routing decision. (b) The header flit is transfered to the second router and other flits are following it. (c) The header flit arrived into a router with busy output channel and the whole chain of flits along the path got stalled, blocking all its channels. (d) Pipeline of flits in case of conflict-free routing, establishing the wormhole across routers.

 

 

• Wormhole routing allows simple, small, cheap, and fast routers. Therefore, it is the most common switching technique used nowadays in commercial machines.
• Wormhole routers use often only input buffering.
• Blocking resources in case of stalled pipelines is the main drawback of this technique.
• Since blocking chains of buffers can easily cause snow ball effect, WH switching is very deadlock-prone. Deadlock handling requires special care.
• This issue is related to the concept of virtual channels. We cannot mix flits of different packets into one buffer (= one physical channel), since flits carry no identity flags. However, with adding some control logic, we can split one physical channel into several virtual channels. They will have their own buffers, but will share (time-multiplex) one single physical channel medium (similarly to processes with own contexts sharing one physical processor).

Sources:: Advanced computer architecture by Kai hwang 

http://pages.cs.wisc.edu/~tvrdik/7/html/Section7.html

 By- Tarun Kumar