NI
NI

Request
Request

s 1
m 1
m 2
s 2
R
R
b 1
b 2
Response
Response
Request
Response
Request
Response
NI
NI
42
Network-on-Chip
Figure 2.22
Request–response message-dependent deadlock.
are created when reception of a request on the slave side is coupled to the
generation of a request on the master side. This occurs when IP modules process a certain input that is sent to them by the preceding module and then write
their output to the succeeding module. In such protocols, an initial request
passes through a number of intermediate IPs, generating new requests until
the final destination is reached. Potentially, a response is travelling in the
other direction, creating response–response dependencies on the way back.
Two prominent examples of request–request and response–response protocols are cache coherency protocols and collective communication protocols.
Hansson et al. (2007) proposed four solutions to avoid message-dependent
deadlock—increased buffer sizing, end-to-end flow control, strict ordering, and use of virtual circuit. Buffer sizing solves the deadlock problem by
ensuring enough space by oversizing the buffers. This can be implemented
by designing the NIs such that NI buffers are guaranteed to consume all messages sent to them. While extensively used in parallel computers, this method
is prohibitively expensive in NoCs and is not used in any known architecture.
Instead of adapting the buffer size to the maximum requirements, end-to-end
flow control does the other way around: it assures that no more is ever injected
than what can be consumed. This approach, end-to-end flow control, is used
in the Æthereal (Radulescu et al. 2005) NoC. As illustrated in Figure 2.23, it
removes a dependency edge from the network to the NI.
In strict ordering, deadlock avoidance is performed by introducing logically independent networks, physical or virtual, for each message type.
A major drawback of the strict ordering is that buffers cannot be shared
between the different message classes, increasing the amount of buffering required. The partitioning into logical networks leads to inefficient utilization of network resources and increased congestion due to unbalance.