Avoiding Message-Dependent Deadlock in Network-Based Systems on Chip

Networks on chip (NoCs) are an essential componentof systems on chip (SoCs) and much research is devotedto deadlock avoidance in NoCs. Prior work focuses on the routernetwork while protocol interactions between NoC and intellectualproperty (IP) modules are not considered. These interactionsintroduce message dependencies that affect deadlock propertiesof the SoC as a whole. Even when NoC and IP dependencygraphs are cycle-free in isolation, put together they may stillcreate cycles. Traditionally, SoCs rely solely on request-response protocols.However, emerging SoCs adopt higher-level protocols for cachecoherency, slave locking, and peer-to-peer streaming, therebyincreasing the complexity in the interaction between the NoCand the IPs. In this paper, we analyze message-dependent deadlock, arisingdue to protocol interactions between the NoC and the IPmodules. We compare the possible solutions and show thatdeadlock avoidance, in the presence of higher-level protocols,poses a serious challenge for many current NoC architectures.We evaluate the solutions qualitatively, and for a number ofdesigns we quantify the area cost for the two most economicalsolutions, strict ordering and end-to-end flow control. We showthat the latter, which avoids deadlock for all protocols, adds anarea and power cost of 4% and 6%, respectively, of a typical Æthereal NoC instance