跳到主要內容

臺灣博碩士論文加值系統

(100.28.0.143) 您好!臺灣時間:2024/07/14 21:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:江凱宇
研究生(外文):Kai Yu Chiang
論文名稱:在三維晶片內網路系統上適用於主動式路由演算法之動態控制緩衝配置
論文名稱(外文):Dynamic Control of Buffer Allocation on Proactive Routing Algorithm for 3D Network-on-Chip Systems
指導教授:陳坤志陳坤志引用關係
指導教授(外文):Kun Chih Chen
口試委員:陳冠宏林書彥
口試日期:2016-07-21
學位類別:碩士
校院名稱:逢甲大學
系所名稱:電子工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:68
中文關鍵詞:三維晶片內網路主動式路由演算法動態控制緩衝配置
外文關鍵詞:3D NoCProactive Routing AlgorithmDynamic Control
相關次數:
  • 被引用被引用:0
  • 點閱點閱:153
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
在系統晶片日新月異的發展下,晶片的複雜程度隨著莫爾定律不斷的提升,因為材料的限制使得傳統製程逐漸走到盡頭,因此近年來三維晶片就被廣為討論。為了解決複雜導線所造成的延遲,因此提出網路晶片的技術來解決傳輸上延遲的問題。
傳統上我們認為由於封包的壅塞而造成溫度的提升,但其實溫度與路由器的切換呈現正相關,也就是穩定且大量的封包傳輸是造成區域過熱的主因。本篇論文參考在三維晶片內網路系統上適用於主動式路由演算法之熱感知動態緩衝配置的技術,並加以改進來提升整個網路的吞吐量,並且控制在有限的溫度之下。
我們發現,緩衝配置的啟動時間會直接影響整個系統的吞吐量,所以我們提出一個機制來有效的控管緩衝器的配置,使得其配置機制不會造成誤判並有效的提升網路的吞吐量。
因此我們發現了排隊理論中的定理與路由器和封包的傳輸之間有很相似的關聯性,所以我們結合了排隊理論和賽局理論中的投票定理,並透過排隊理論中的Little Formula來衍生出一個新的參考值,並採用投票定理中的絕對多數決,來讓相鄰路由器的緩衝器來做一個比較,再透過表決的結果來決定是否啟用動態緩衝配置的技術。
本論文基於三維晶片內網路系統上適用於主動式路由演算法之熱感知動態緩衝配置上去做優化,並提出一種動態控制的方法來,來控管動態緩衝配置的次數,來達到拓樸上的平衡,並提升整體的吞吐量。經由動態控制後,在有限溫度的限制下與先前的技術相比,確實在網路的吞吐量可以提升22.69%~32.26%。而在硬體方面我們計算各機制的面積效率與電源效率與先前技術相比,也提升了1.2%~1.226%
As the complexity of system-on-chip (SoC) grows with Moore’s law, the considerations of interconnection complexity and wire delay become more crucial for chip multiprocessor systems. The network-on-chip (NoC) has been proposed as a novel and feasible solution for efficient interconnections. A dynamic control algorithm on proactive traffic migration algorithm is proposed to resolve performance degradation problems that occur due to traffic and thermal balance on 3D Network-on-Chip. It is conventionally believed that overheated areas result from packet congestion, but in fact, temperature is correlated with the amounts of packets switched by the router. Hence, a steady stream of many packets being transmitted is the main reason that causes overheated areas. We have discovered the trigger timing of buffer allocation will affect performance, and therefore, an efficacious technique is proposed here to control buffer allocation, regardless of whether it is enabled.
In order to resolve the aforementioned problems, some correlations between the Queueing theory and the situation of packet transmit in a router. Therefore, the Queueing theory and the Game theory are combined in applying a dynamic control technique, and the Little Formula is adopted from the Queueing theory to model a new index for compare and adopt an absolute majority for a mechanism. The results will determine whether this approach will enable the buffer allocation technique.
After applying the dynamic control, under the certain thermal limit, we have improved network throughput by about 22.69% to 32.26%. In hardware architecture, we compared the area and power efficiency, with previous work also increase 1.2x and 1.226x.
中文摘要 ................................................................................................. ii
ABSTRACT ............................................................................................ iii
CONTENTS ............................................................................................iv
LIST OF FIGURES ………………………………………………....v
LIST OF TABLES .................................................................................vi
Introduction ............................................................................................ 1
1.1 Background of the 3D Network-on-Chip (3D NoC)……….............. 1
1.2 Thermal Issues of the 3D NoC .......................................................... 4
1.3 Problem description ........................................................................... 6
1.4 Goals and Contributions ..................................................................... 9
1.5 Thesis organization ........................................................................... 11
Chapter 2 Related Works………………….…………………………12
2.1 Proactive Routing for Thermal Management……………………12
2.2 Traffic-aware Adaptive Routing for Thermal Management…...........14
2.2.1 Topology-aware Adaptive Routing……………………………..…14
2.2.2 Traffic and Theraml-aware Adaptive Beltway Routing……….......16
2.3 Thermal-aware Adaptive Routing for Thermal Management…….…18
2.3.1 Dynamic Thermal-balance Routing……………………………..18
2.3.2 Thermal Budget Based Beltway………………………………..18
2.3.3 Thermal-aware Dynamic Buffer Allocation for Proactive Algorithm on 3D NoC system…………………………………………………..21
Chapter 3 Proposed Dynamic Control Buffer Allocation on Proactive Routing Algorithm for 3D NoC systems………………………….…27
3.1 Status Index represent for Routers……………………………….29
3.2 Dynamic Control Buffer Allocation on Proactive Routing Algorithm………………………………………………………………..35
3.2.1 Performance Analysis of Router by Queueing Theory…................35
3.2.2 Design Status Index following Little Formula in Queueing Theory………………………………………………………………..37
3.2.3 Design a System Rule by Game Theory………………………......39
3.3 Flow Chart…………………………………………………..........…41
Chapter 4 Performance Evaluation………………………………….43
4.1 Simulation Setup…………………………………………………..43
4.2 Thermal-Balance Comparison in Different Mesh of 3D NoC……....47
4.3 Thermal-limit Performance Evaluation in Irregular Mesh of 3D NoC system………………………………………………………………...…49
Chapter 5 Architecture Design…………………....................................53
5.1 Hardware Architecture and Dataflow………………………………53
5.2 Router Architecture Design………………………………………....55
5.3 Implement Result and Comparison…………………………………57
5.4 Summary…………………………………………………………….59
Chapter 6 Conclusion and Future Work………………………………60
6.1 Conclusion………………………………………………………..…60
6.2 Future Work……………………………………………………….61
Refernces……………………………………………………………....63
[1] R. Ho, K.W. Mai, and M.A. Horowitz, “The future of wires,” Proc. IEEE, vol. 89, no. 4, pp. 490-504, April. 2001.
[2] R. Marculescu, Umit Y. Ogras, Li-Shiuan Peh, Natalie Enright Jerger, and Yatin Hoskote, “Outstanding Research Problems in NoC Design: System, Microarchitecture, and Circuit Perspectives,” IEEE Trans. Computer-Aided Design of Integrated Circuits
and Systems, , vol. 28, pp. 3-21, 2009.
[3] Natalie Enright Jerger and Li-Shiuan Peh, “On-Chip Networks,” Synthesis Lectures on Computer Architecture, vol. 4, no. 1 , pp. 1-141, 2009
[4] V.F. Pavlidis, and E.G. Friedman, “3D topologies for Networks-on-Chip,” IEEE Trans. Very Large Scale Integration System, vol. 15, no. 10 pp. 1081-1090, 2007.
[5] I. Loi, S. Mitra, T. H. Lee, S. Fujita, and L. Benini, “A low-overhead fault tolerance scheme for TSV-based 3D Network on Chip links,” Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 598-602, 2008.
[6] R.S. Patti, “Three-dimensional integrated circuits and the future of system-on-chip designs,” Proc. IEEE, pp. 1214–1224, 2006
[7] A. W. Topol, D.C. La Tulipe, L. Shi, et al. “Three-dimensional integrated circuits,” IBM J. Res. Develop., vol. 50, no. 4/5, pp. 491-506, 2006.
[8] B. Black, M. Annavaram, N. Brekelbaum, et al., “Die stacking (3D) microarchitecture,” Proc. International Symposium on Microarchitecture, pp. 469-479, Dec. 2006.
[9] B.S. Feero, and P.P. Pande, “Networks-on-chip in a three-dimensional environment: a performance evaluation,” IEEE Trans. Computers, pp. 32–45, 2009
[10] J. Joyner, P. Zarkesh-Ha, and J.D. Meindl, “A stochastic global net-length distribution for a three-dimensional System-on-Chip (3D-SoC),” Proc. IEEE International ASIC/SOC Conference, pp. 147-151, Sept. 2001.
[11] P. Dongkook, S. Eachempati, R. Das, A. K. Mishra, Xie Yuan, N. Vijaykrishnan, and C. R. Das, “MIRA: A multi-layered on-chip interconnect router architecture,” Proc. IEEE International Symposium on Computer Architecture, pp. 251-261, 2008.
[12] S. Li., Li-Shiuan Peh, A. Kumar, and N. K. Jha, “Thermal Modeling, Characterization and Management of On-Chip Networks,” Proc. Microarchitecture
Symposium, pp. 67-78, 2004.

[13] T. Ebi, D Kramer, W. Karl, and J. Henkel, “Economic learning for thermal-aware powerbudgeting in many-core architectures,” Proc. the 9th International Conference on Hardware/Software Codesign and System Synthesis, pp. 189-196, 2011
[14] Kun-Chih Chen, Shu-Yen Lin, Hui-Shun Hung, and An-Yeu (Andy) Wu, “Topology-Aware Adaptive Routing for Non-Stationary Irregular Mesh in Throttled 3D NoC Systems,” IEEE Trans. Parallel and Distributed Systems, vol.24, no.10, pp. 2109-2120, Oct. 2013.
[15] Kun-Chih Chen, Che-Chuan Kuo, Hui-Shun Hung, An-Yeu Wu, “Traffic- and
Thermal-aware Adaptive Beltway Routing for three dimensional Network-on-Chip
Systems,” Proc. IEEE International Symposium on Circuits and Systems, pp. 1660-
1663, May 2013.
[16] F. Liu, H. Gu, Y. Yang, “DTBR: A dynamic thermal balance routing algorithm for Network-on-Chip,” Journal of Computers and Electrical Engineering, vol. 38, pp. 270-281, 2012
[17] Y.-S. Lee, H.-K. Hsin, K.-C. Chen, E.-J. Chang, A.-Y. Wu, “Thermal-aware Dynamic Buffer Allocation for Proactive Routing Algorithm on 3D Network-on-Chip Systems,” IEEE Int. Symp. VLSI Design, Automation, and Test (VLSI-DAT’14), pp.191-194, April 2014
[18] Inchoon. Yeo, Chih Chun Liu, Eun Jung Kim, “Predictive Dynamic Thermal
Management for Multicore Systems,” Proc. Design Automation Conference (DAC), pp.734-739, Jun. 2008
[19] K.-C. Chen, E.-J. Chang, H.-T. Li, and A.-Y. Wu, “RC-based Temperature Prediction Scheme for Proactive Dynamic Thermal Management on Throttle-based 3D NoCs,” IEEE Transactions on Parallel and Distributed Systems (TPDS), vol.26, no.1, pp.206-218, Jan. 2015.
[20] K.-C. Chen, S.-Y. Lin, and A.-Y. Wu, “Design of thermal management
unit with vertical throttling scheme for proactive thermal-aware 3D NoC systems,”
Proc. IEEE International. Symposium on VLSI Design, Automation, and Test,
pp.118-121, Apr. 2013
[21] K.-C. Chen, S.-Y. Lin, H.-S. Hung, A.-Y. Wu, “Topology-Aware
Adaptive Routing for Non-Stationary Irregular Mesh in Throttled 3D NoC Systems,” IEEE Trans. Parallel and Distributed Systems, vol.24, no.10, pp. 2109-2120, Oct.
2013.

[22] K.-C. Chen, C.-C. Kuo, H.-S. Hung, A.-Y. Wu, “Traffic- and
Thermal-aware Adaptive Beltway Routing for three dimensional Network-on-Chip
Systems,” Proc. IEEE International Symposium on Circuits and Systems, pp. 1660-
1663, May 2013.
[23] F. Liu, H. Gu, Y. Yang, “DTBR: A dynamic thermal balance routing algorithm for Network-on-Chip,” Journal of Computers and Electrical Engineering, vol. 38, pp. 270-281, 2012
[24] Che-Chuan Kuo, Kun-Chih Chen, En-Jui Chang, and An-Yeu Wu, “Proactive
Thermal-Budget-Based Beltway Routing Algorithm for Thermal-Aware 3D NoC Systems,” Proc. IEEE international Symposium on Network-on-Chip, pp, 20-24, Oct.
2013
[25] G. Ascia, V. Gatania, M. Palesi, and D. Patti, “Neighbors-on-Path: A New Selection Strategy for On-Chip Networks,” Proc. 2006 IEEE/ACM/IFIP Workshop on
Embedded Systems for Real Time Multimedia, pp. 79-84, 2006.
[26] C.-H. Chao, K.-C. Chen, A.-Y. Wu, “Routing-Based Traffic Migration and Buffer Allocation Schemes for Three-Dimensional Network-on-Chip Systems with Thermal Limit,” IEEE Trans. Very Large Scale Integration Systems, vol.21, no.11, pp. 2118-2131, Nov. 2013.
[27] Sundarapandian, V. “7. Queueing Theory".Probability, Statistics and Queueing Theory”. PHI Learning.ISBN 8120338448. 2009.
[28] Myerson, Roger B. “Game Theory: Analysis of Conflict”, Harvard University Press, p. 1. Chapter-preview links, pp. vii–xi. 1991.
[29] E.-J. Chang, H.-K. Hsin, S.-Y. Lin, A.-Y. Wu, “Path-Congestion-Aware Adaptive Routing with a Contention Prediction Scheme for Network-on-Chip Systems,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 1, pp 113-126, Sept. 2013.
[30] H.-K. Hsin, E.-J. Chang, C.-A. Lin, and A.-Y. (Andy) Wu, “Ant Colony Optimization-Based Fault-Aware Routing in Mesh-based Network-on-Chip Systems,” in IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 33, issue 11, pp. 1693-1705, Nov. 2014.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top