Virtual-Channel Flow Control and Buffering - Microarchitecture of Network-on-Chip Routers - page 97

deq deq

A1 A0 A2 A1

B1 B0

A2 A1 A3 A2

B1 B0

t=0 t=1 t=2 t=3

en q enq enq

B1 B0 B1 B0

C0 B2 A4

A3

deq

B2 A4

A2 A3 B2 A3

C0

Fig. 6.8 An example of the interaction between the shared buffer (3 slots) and the private buffers
(2 slots) per VC. Every time a flit is drained from the private VC buffer, the shared buffer is checked
for another flit that belongs to the same VC. A VC uses the shared buffer only when it runs out of
private buffer space

interaction between the shared buffer and the private buffer space per VC through
a simple example. In this configuration, each VC owns a private buffer of 2 slots
and all VCs share three extra buffer slots. In cycle 0, VC A owns 2 shared slots
and dequeues a flit from its private buffer that was previously full. The empty slot
in the private buffer of VC A should be refilled by a flit from the shared buffer.
Therefore, VC A accesses the shared buffer to find the flits that match VC A and
locate the oldest (the one that came first). The refill of the private buffer of VC A is
completed in cycle 1. Then, in cycle 2, the same procedure is followed, effectively
loading the private buffer of VC A with a new flit. The private buffer of a VC does
not necessarily get new data from the shared buffer, but it can be loaded directly
from the input, as done for VC C in cycle 0.

6.3.1 The Organization and Operation of a Generic

Shared Buffer

Maintaining the flits' order of arrival among VCs is the main concern when
designing a shared buffer. It should be as flexible as possible, without imposing
any restrictions on the expected traffic patterns. The way this is achieved leads
to different implementations. For example, the self-compacting shared buffers (Ni
et al. 1998 ;Parketal. 1994 ) require the flits of a single VC to be stored in
contiguous buffer positions. To enable this continuity in the storage of flits of each
VC, every time a flit enters or leaves the queue of a certain VC the data of all
queues should be shifter either to make room for the incoming flit or to close the
gap left by the outgoing flit. To avoid shifting that may lead to increased power
consumption, the shared buffer can employ pointers that allow locating flits by
reference, although they may be stored in practically random addresses (Tamir and
Frazier 1992 ; Katevenis et al. 1998 ).
An example of such an approach is presented in Fig. 6.9 . Apart from the
main buffer space used to store flits (Buffer Memory), the shared buffer uses a
list of single-bit elements which tells whether an address actually contains data
(Availability List) and a Linked List, used to track flits' order of arrival. If a flit
for VC k is stored in address a of the buffer memory, then the next flit for VC k
is stored in the address pointed by element a of the Linked List (a NULL pointer