User:Vidyanandgouda/sandbox

Virtual Channel in Multiprocessors

Introduction

Virtual channels were introduced to solve the deadlock problem in router buffers. When the buffers in the routers become full, at that time the senders will not send new flits till the time the buffers become free. To deal with this situation we need to implement spare channels. Implementing spare channels is expensive as we need to include new links as well as buffers. To restrict the cost, we can use virtual channels. The problem that needs to be dealt is with the buffers becoming full even though links are present. Virtual channels are channels which include their own buffers but share single links. Hence, by using a virtual channel we cut down the cost of implementing spare channels with links. Virtual channels can be used for various purposes like allocating bandwidth to virtual circuits.

Deadlock and need for an optimal solution

cyclic deadlock in pushing packets

Deadlocks can occur in different components of a multiprocessor, one such place is interconnection networks. Deadlocks in interconnection networks halt forwarding the packets. Each transmission channel has an input buffer and an output buffer to push the packets. Deadlock is a situation where in these buffers have formed a cyclic channel structure and are unable to push the packets because each buffer sees its next buffer being filled with a packet.

Avoiding deadlocks:

There are many algorithms/techniques to detect, avoid/remove deadlocks.

• Dropping a packet: It is one of the methods to remove deadlock. It removes deadlock instantly but has costly effort to detect the dropped packet and re transmit. Most cases it introduces intolerable delays. In a shared memory multiprocessor such a delay degrades performance (speed being the primary victim).
• Turn restriction routings: It is one of the methods to avoid deadlock. The basis for these algorithms is on the observation that in order for a deadlock to occur, all four anti-clockwise turns or all four clockwise turns must occur. Solution to resolve this is by restricting the direction of turns in a way that same path is not traversed. This improves path diversity, at the same time allows non-minimum length paths between two nodes.
• Redundant channels: Suppose that between a pair of nodes an additional channel is added but it will be used only in the situation of deadlocks. Key drawback of this method is it resolves deadlock in a expensive way. Doubling the channels and buffers at the channel's ends are significant costs.

However there is a way to reduce the cost of channels. A deadlock situation means buffers in routers are full and are unable to receive more packets. But the links are unused in a deadlock.

Using virtual channels to resolve deadlock

One of the optimal solutions:

Instead of adding extra links, these spare channels can include buffers at the routers. Two or more channels have their own buffers but can share a single link. Such channels are referred to as Virtual channels. Hence to the network protocols, it is as if there are multiple separate channels while in fact physically they have common links.

Referring to the picture - The network has 2 virtual channels, VC1 and VC2. VC1 is used for regular routing and VC2 used as an escape channel, when congestion results in a packet being blocked or being blocked for more than a threshold amount of time, it is moved to the escape channel, allowing it to move in its path. Note, however, that the design must ensure that deadlocks are not possible in the escape channel (This can be taken care by employing one of the deadlock avoid techniques, ex: turn restriction routing).

Router Architecture with virtual channels

Architecture of the router is shown in the figure. Here we are using Virtual channels to prevent the deadlock which was mentioned above. We can see that on either side of crossbar switch there are boxes named Box A, Box B. These boxes are a simple representation of presence of routing logic between a cross bar and an input/output physical channel.

Input Channel/Box A

1. Can be a simple FIFO queue to buffer the flits or data packets that come from respective channels. Because it is a FIFO queue all the packets move in order starting from header flit and if any of the packet/flit is blocked then the trailing packets are stalled as well even if they want to go to different physical channel. This is undesirable and can be avoided by serving the flits out of order by the use of virtual channels.
2. It can be an arrangement of large and small buffers with multiple virtual channels. VC1, VC2 as shown in the Box A are one such example involving two virtual channels. Here multiple queues can be formed. Packet's header flit contains information on which channel the packet should be transmitted in. Based on that information the flit goes through one of the virtual channels (VC1 or VC2 in the given picture).
3. Virtual cut through routing and Wormhole routing - These are routing strategies and the primary difference between them is in their approach towards pushing a data packet. In Wormhole routing the flits of data packet are immediately pushed to next node as and when they arrive. While in cut-through routing entire package of data packets is collected at every node and then again forwarded flit by flit. That is the reason buffer sizes are big in Cut-through routing and small in Wormhole routing. It is important to note that Cut-through routing has packet size granularity and Wormhole routing has flit size granularity.

Output Channel/Box B

1. Assuming that virtual channel strategy is employed at the input, output channel either uses Wormhole type(Box B top diagram) or Cut-through type (Box B bottom diagram) of routing.

Route Compute, VC allocate, Switch Allocator are the logics to determine the routing path, deciding Virtual Channel to be selected and Switch to be used respectively. Header flit goes through all these logics because it has the information on source and destination.

Virtual channels share the load of physical channel. Instead of having one physical channel, and facing storage problems, multiple virtual channels can be implemented to divide the storage buffers of all the physical channels. Virtual channels provide multiple buffers for one single physical channel. It is possible to send multiple flits at one time. So from allocation of channels they decouple to provide allocation of buffers and the routing mechanism on the whole can also be implemented parallelly. If one flit is in crossbar switch stage then it is possible for the other flit to be in the step of buffering. In this way parallelism can be exploited.

A Cross bar switch is expensive when number of ports is high. In order to connect "n" input ports to "n" output ports, complexity of cross bar is of order n². If "n" is big it means that the complexity of cross bar switch implementation, complexity of control logic and the arbitration policy would increase along with the complexity of virtual channel implementation.

Advantages and Disadvantages of using virtual channels

Advantages: The deadlock in routing channel can be solved. Using virtual channels allows to pass blocked packets which otherwise would have not been passed. Cost can be minimized as virtual channels will decouple both physical channel and buffers.

Disadvantages of virtual channels - Cost of implementing additional control logic which decides which virtual channels needs to be connected to the input and the output ports.

Further Reading

1. http://www.csl.cornell.edu/~martinez/doc/ics99.pdf
2. https://books.google.com/books?id=L4QzxzaNDFIC&pg=PA57&lpg=PA57&dq=virtual+channels+in+multiprocessors&source=bl&ots=Aeg7qVIBzr&sig=5dqUv1-rM7xBT5FcIu5V_7riLBc&hl=en&sa=X&ved=0ahUKEwipo4akjNXQAhVHNiYKHXjAC3EQ6AEIXTAI#v=onepage&q=virtual%20channels%20in%20multiprocessors&f=false
3. https://www.google.com/patents/US6101181
4. Case study: Alpha 21364 Network Architecture

References