應用在雙向通道網路晶片的死結偵測機制

Deadlock Detection Mechanism for Bidirectional Networks-on-Chip

王姿蓉(Zi-Rong Wang)

指導教授 ： 陳少傑

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.01037

摘要

在網路晶片架構（Networks-on-Chip）上，死結（Deadlock）是一個相當重要的課題。在這篇論文中，我們提出一個偵測死結的機制，應用在採用完全動態路由演算法（Fully Adaptive Routing）的雙向通道網路晶片架構（BiNoC）上。我們提出的死結偵測機制，不僅會檢查路由器內部的資料停滯的時間，同時也利用一個偵測封包，沿著資料封包移動的反方向傳送，藉此找到資料封包彼此之間的循環相依性。
我們提出的死結偵測機制，不論是在傳統單向通道網路晶片架構或是雙向通道網路晶片架構上，都能夠有效的降低偵測到的死結資料封包數量，從而避免用於死結復原的資源飽和。同時在雙向通道網路晶片架構上，我們所提出的反方向傳送偵測封包之死結偵測機制，能夠有效的使用因為死結而閒置的通道。這些位置的通道不單單提供給偵測封包使用，同時也供給資料封包使用。這樣的作法能夠提高通道的使用效率，並藉此得到更好的系統效能。

關鍵字

死結偵測 ； 完全可適性路由演算法 ； 雙向通道 ； 網路晶片架構

並列摘要

Dealing with the deadlock problem on a networks-on-chip becomes an important issue. This Thesis proposes a back-trace deadlock detection mechanism implemented on a bidirectional-channel NoC design (BiNoC) with a fully adaptive routing environment. Not only dependent on the time-out value, our proposed method uses a backward transferred probe-packet to detect any cycle dependency existed in the network. This mechanism can effectively reduce the number of detected deadlock packets which could saturate the recovery resources on both conventional NoC and bidirectional-channel NoC. By transferring the probe-packet backward on the bidirectional-channel NoC, the unused link (caused by deadlock) can then be used to transmit the probe-packet, or even the real data. Our proposed deadlock mechanism can reserve the benefit of better channel utilization as BiNoC, thus obtain better performance.

並列關鍵字

Deadlock Detection ； Fully Adaptive Routing ； Bidirectional Channel ； NoC

參考文獻

[3] T. M. Pinkston and S. Warnakulasuriya, "Characterization of Deadlocks in k-ary n-cube Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 9, pp. 904-921, Sep. 1999.

[4] T. M. Pinkston, "Flexible and Efficient Routing based on Progressive Deadlock Recovery," IEEE Transactions on Computers, vol. 48, no. 7, pp. 649-669, Jul. 1999.

[8] C. Ge-Ming, "The Odd-Even Turn Model for Adaptive Routing," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 7, pp. 729-738, Jul. 1999.

[12] J.-M. M. Rubio, P. Lopez, and J. Duato, "FC3D: Flow Control-based Distributed Deadlock Detection Mechanism for True Fully Adaptive Routing in Wormhole Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 8, pp. 765-779, Aug. 2003.

[14] C. Nicopoulos, V. Narayanan, and C. R. Das, "Exploring Fault-Tolerant Network-on-Chip Architectures," in Network-on-Chip Architectures, vol. 45, pp. 65-92, Springer Netherlands, 2010.