臺灣博碩士論文加值系統

在網路晶片架構（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.

ABSTRACT...........................................................I
LIST OF FIGURES....................................................V
LIST OF TABLES....................................................IX
CHAPTER 1 INTRODUCTION.............................................1
1.1 Networks-on-Chip Architecture..................................2
1.2 Deadlocks on Interconnection Networks..........................3
1.3 Motivation and Contribution of the Thesis......................4
1.4 Thesis Organization............................................5
CHAPTER 2 BACKGROUND KNOWLEDGE.....................................7
2.1 Bidirectional NoC Architecture.................................7
2.1.1 Inter-router Transmission Scheme.............................7
2.1.2 Bidirectional Channel Routing Direction Control..............9
2.2 Deadlock Handling.............................................10
2.2.1 Deadlock Avoidance..........................................11
2.2.2 Deadlock Detection..........................................12
2.2.2.1 Timeout-based Mechanism...................................14
2.2.2.2 Cycle-based Mechanism.....................................14
2.2.2.3 Turn-based Mechanism......................................15
2.2.3 Deadlock Resolution.........................................17
CHAPTER 3 PROPOSED DEADLOCK DETECTION MECHANISM...................19
3.1 Motivation....................................................19
3.2 Our Proposed Deadlock Detection Mechanism.....................24
3.2.1 Channel Wait-for Graphs.....................................24
3.2.2 Backward Deadlock Detection Mechanism.......................26
3.3 Router Implementation.........................................40
3.3.1 Implementation of Proposed Deadlock Detection Mechanism.....40
3.3.2 Implementation of Deadlock Resolution Mechanism.............44
CHAPTER 4 EXPERIMENTAL RESULTS AND DISCUSSION.....................45
4.1 Experimental Platform and Setting.............................45
4.2 Synthetic Traffic Analysis....................................47
4.2.1 Experiments on Conventional NoC.............................48
4.2.2 Experiments on FA-BiNoC.....................................60
4.3 Estimation on Implementation Overhead.........................71
CHAPTER 5 CONCLUSION..............................................75
REFERENCE.........................................................77

[1]A. Jantsch, H. Tenhunen, and I. Ebrary, Networks on chip, Kluwer Academic Publishers, 2003.
[2]W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers, 2004.
[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.
[5]Y.-C. Lan, H.-A. Lin, S.-H. Lo, Y. H. Hu, and S.-J. Chen, "A Bidirectional NoC (BiNoC) Architecture With Dynamic Self-Reconfigurable Channel," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 3, pp. 427-440, Mar. 2011.
[6]S.-H. Lo, Y.-C. Lan, H.-H. Yeh, W.-C. Tsai, Y.-H. Hu, and S.-J. Chen, "QoS aware BiNoC architecture," in Proceedings of IEEE International Symposium on Parallel & Distributed Processing, pp. 1-10, Apr. 2010.
[7]Intel, "A Touchstone DELTA System Description," in Intel Advanced Information, Intel, Portland, Oregon, Intel Corporation, 1991.
[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.
[9]K. V. Anjan and T. M. Pinkston, "DISHA: a Deadlock Recovery Scheme for Fully Adaptive Routing," in Proceedings of 9th International Symposium on Parallel Processing, pp. 537-543, Apr. 1995.
[10]J. H. Kim, L. Ziqiang, and A. A. Chien, "Compressionless Routing: a Framework for Adaptive and Fault-Tolerant routing," in Proceedings of the 21st Annual International Symposium on Computer Architecture, pp. 289-300, Apr. 1994.
[11]J.-M. M. Rubio, P. Lopez, and J. Duato, "A Cost-Effective Approach to Deadlock Handling in Wormhole Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 7, pp. 716-729, Jul. 2001.
[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.
[13]D. Park, C. Nicopoulos, J. Kim, N. Vijaykrishnan, and C. R. Das, "Exploring Fault-Tolerant Network-on-Chip Architectures," in Proceedings of International Conference on Dependable Systems and Networks, pp. 93-104, Jun. 2006.
[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.
[15]S. Lee, "A Deadlock Detection Mechanism for True Fully Adaptive Routing in Regular Wormhole Networks," Computer Communications, vol. 30, no. 8, pp. 1826-1840, Feb. 2007.
[16]J.-M. M. Rubio, P. Lopez, J. Duato, and T. M. Pinkston, "Software-based Deadlock Recovery Technique for True Fully Adaptive Routing in Wormhole Networks," in Proceedings of the International Conference on Parallel Processing, pp. 182-189, Aug. 1997.
[17]S. Wamakulasuriya and T. M. Pinkston, "A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 3, pp. 212-229, Mar. 2000.
[18]"IEEE Standard Verilog Hardware Description Language," in IEEE Std 1364-2001, IEEE Press, 2001.
[19]U. M. Corporation, UMC 90 Nanometer CMOS Technology, United Microelectronics Corporation (UMC), 2003.
[20]D. C. Gazis, Traffic Science, John Wiley & Sons, 1974.
[21]S. Inc, Design Compiler, Synopsys Inc, 1999.