Before starting with flow control, we need to learn some terminologies. Let’s start!
Communication starts with a message. A message is a logically contiguous group of bits that are delivered from a source terminal to a destination terminal. Because messages may be arbitrarily long, resources are not directly allocated to messages. Instead, messages are divided into one or more packets that have a restricted maximum length. By restricting the length of a packet, the size and time duration of a resource allocation is also restricted, which is often important for the performance and functionality of a flow control mechanism. A packet is the basic unit of routing and sequencing. [4]. Packet usually has a header (routing and control information), payload (data) and error code. See the picture below.
A packet may be further divided into flow control digits or flits. A flit is the basic unit of bandwidth and storage allocation used by most flow control methods. Flits carry no routing and sequencing information and thus must follow the same path and remain in order. [4]
A flit is itself subdivided into one or more physical transfer digits or phits. A phit is the unit of information that is transferred across a channel in a single clock cycle. [4]
There are no hard and fast rules about sizes. However, phits are typically between 1 bit and 64 bits in size, with 8 bits being typical. Flits usually range from 16 bits (2 bytes) to 512 bits (64 bytes), with 64 bits (8 bytes) being typical. Finally, packets usually range from 128 bits (16 bytes) to 512 Kbits (64 Kbytes), with 1 Kbit (128 bytes) being typical. With these typical sizes, there are eight 8-bit phits to a 64-bit flit, and sixteen 64-bit flits to a 1-Kbit packet.
Message-Based flow control
With that out of the way, let’s start with message-based flow control, which operates at the message level, which as you can see from the above picture is the coarsest granularity. Circuit switching is a type of message-based flow control in which the full path for message to be sent is set up before starting the transmission. The path will have resources like nodes and channels and all those resources combined form a “link”. The message will take multiple hops across this link to reach the destination. No one else can use this link when it is set for transmission of a particular message. The advantage of this switching is there is no need for arbitration and no buffering is required. There are some disadvantages as well. Firstly, the setup of this link takes time. A small setup message called “probe” is sent into the network to reserve the link before sending the actual message. Another disadvantage which I have already mentioned is when a path is setup (reserved), it cannot be used by other flows. [3] [7]
Packet-Based flow control
Similarly, packet-based flow control operates in packet level. A message is broken down into packets, like it’s shown in the picture above, and then these packets are transmitted independently through the network. Store-and-forward (SAF) flow control is a type of packet-based flow control. In SAF, each node waits until an entire packet has been received before forwarding any part of the packet to the next node. As a result, long delays are incurred at each hop, which makes them unsuitable for on-chip networks that are usually delay-critical. Moreover, SAF flow control requires that there be sufficient buffering at each router to buffer the entire packet. These high buffering requirements reduce store and forward switching’s flexibility to on-chip networks. [3]
Another type of packet-based flow control is Cut-Through flow control. In this method, the packets are forwarded as soon as header is received and resources are allocated, which causes a large reduction in latency. However, bandwidth and storage are still allocated in packet-sized units. Packets still move forward only if there is enough storage at the next downstream router to hold the entire packet. On-chip networks with tight area and power constraints may find it difficult to accommodate the large buffers needed to support virtual cut-through when packet sizes are large.
Flit-Based flow control
Moving to finer granularity, packets are divided into flits, and when we transmit flits instead of packets or messages, it is a flit-based flow control. Since flits are smaller in size than packets, the buffering requirements is low in this flow control method. It helps routers meet tight area or power constraints on chip. Wormhole flow control is a type of flit-based flow control. It operates like cut-through, but with channels and buffers allocated to flits rather than packets. While wormhole flow control uses buffers effectively, it makes inefficient use of link bandwidth. Though it allocates storage and bandwidth in flit-sized units, a link is held for the duration of a packet’s lifetime in the router. As a result, when a packet is blocked, all the physical links held by that packet are left idle. This is called head-of-line blocking and is a serious issue in Wormhole flow control.
To mitigate this, virtual channel is used. Virtual channel (VC) is a very important concept in NoCs. It was first proposed as a solution for deadlock avoidance, but it has also been applied to mitigate head-of-line blocking in flow control, thus extending throughput. Head-of-line blocking can occur in any of the flow control method discussed above. The idea is to multiplex multiple channels over one physical channel. We are basically dividing the input buffer into multiple buffers sharing a single physical channel. For example, a 16-deep FIFO can be divided into 4 4-deep FIFOs as shown in the picture below.
VCs can be applied to all the above flow control techniques to alleviate head-of-line blocking. To understand how virtual channel can solve our head-of-line blocking problem, see the picture below.
So, these are the some of the flow control methods that are classified based on the transmitted data sizes. Please look at the table below which summarizes all of them.
Some more flow control mechanisms
Credit based flow control – In this, the sender maintains a buffer with an estimate number of free spaces. This estimate is known as credit. Initially, the number of credits is equal to the number of buffers in the receiving router. When sender sends a message, it reduces the credit by 1. When a message is received in the receiving router, it is stored in the buffer and when that message is read, it sends a notification back to sender that the buffer is freed and it can accept more data, so the sender increases its credit by 1. If the credit count goes to zero in the sending router, it means that there is no free buffer in receiving router and it stops sending a message.
On-Off flow control – The main disadvantage of credit-based flow control is that we need to send a message when every buffer is freed. This increases the load on the NoC, and it is also not power efficient. To increase the power efficiency, we need to send messages sparingly. One trivial approach is to send a message once for every k buffers freed (k > 1). This will decrease the number of messages; however, it will make A less responsive. On these lines, let us propose a protocol called on-off flow control, where we propose a set of rules that A can use to decide whether it can send a flit to B. Let us create two thresholds: NON (on threshold) and NOFF (off threshold). If the number of free buffers in B becomes equal to NOFF, then it sends a message to A to stop sending. Once A receives this message, it stops sending flits. On the flip side, when the number of free buffers becomes equal to NON, B sends a message to A to start sending flits. [10]
This was a brief overview of different kind of flow control methods. As an exercise, you can try finding which kind of flow control does industry standard protocol like APB, AXI, OCP etc. uses. Also, don’t forget to check the references to learn about this in more detail.
That is all for this article, I will see you in the next one!
References:
[1] Dally, William & Towles, Brian. (2001). Route packets, not wires: On-chip interconnection networks. Proceedings - Design Automation Conference. 684 - 689. 10.1109/DAC.2001.156225.
[2] Networks-on-Chip: From Implementations to Programming Paradigms by Sheng Ma, Libo Huang, Mingche Lai, Wei Shi, Zhiying Wang
[3] On-Chip Networks, Second Edition by Natalie Enright Jerger, Tushar Krishna, Li-Shiuan Peh
[4] Principles and Practices of Interconnection Networks by William James Dally, Brian Patrick Towles
[5] Wu, Chang & Li, Yubai & Peng, Qicong & Chai, Song & Yang, Zhongming. (2009). Construction of a multidimensional plane network-on-chip architecture based on the hypercube structure. Progress in Natural Science - PROG NAT SCI. 19. 635-641. 10.1016/j.pnsc.2008.10.003.
[7] Computer Architecture - Lecture 20: Interconnects (Fall 2022) by Onur Mutlu (Link)
[8] Computer Architecture - Lecture 21: On-Chip Networks & Efficient Router Design (Fall 2022) by Onur Mutlu (Link)
[9] W. J. Dally, "Virtual-channel flow control," in IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 2, pp. 194-205, March 1992, doi: 10.1109/71.127260.
[10] Next-Gen Computer Architecture: Till the End of Silicon by Smruti R. Sarangi
Comments