簡易檢索 / 詳目顯示

研究生: 莊淯凱
Yu-Kai Chuang
論文名稱: 於光網路晶片下考慮最小化線交叉的同時繞線與配置
PlanarONoC: Concurrent Placement and Routing Considering Crossing Minimization for Optical Network-on-Chip
指導教授: 方劭云
Shao-Yun Fang
口試委員: 李毅郎
Yih-Lang Li
呂學坤
Shyue-Kung Lu
劉一宇
Yi-Yu Liu
郭鴻飛
Hung-Fei Kuo
學位類別: 碩士
Master
系所名稱: 電資學院 - 電機工程系
Department of Electrical Engineering
論文出版年: 2018
畢業學年度: 106
語文別: 中文
論文頁數: 59
中文關鍵詞: 光網路晶片光繞線器光敏開關的擺置與繞線
外文關鍵詞: Optical network-on-chip, optical router, PSE placement and routing
相關次數: 點閱:186下載:1
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 光網路晶片已成為一個未來的趨勢,相較於傳統的晶片,在晶片上的溝通以及多核的系統中,它提供了更佳的頻寬、更有效率的功耗,和更短的延遲。
    作為一個光網路晶片的重要元件,光繞線器由波導和光敏開關 (Photonic switching element) 所構成,並於兩個樞紐或一個樞紐及一個記憶體控制器間做繞線。許多先前的研究都著重於發展一個有效率的架構,然而在物理的實作上卻有可能導致一個好的架構效率低落,但這卻鮮少有人研究。
    現存的自動擺置與繞線工具面臨了雷射能量損失的問題,而這些能耗主要來自於光敏開關外波導的交叉。藉由觀察這些架構,我們發現了其實大部分的架構都是平面的,我們使用這個特性發展了一個同時擺置與繞線的系統名為PlanarONoC,其可以保證波導交叉的最小化。
    實驗結果顯示我們的方法相較於現有最新的技術可以更有效率,並平均降低能耗達百分之三十七,且保證沒有任何光敏開關外的波導交叉。


    Optical networks-on-chips (ONoCs) have become a promising solution for the
    on-chip communication of multi-and many-core systems to provide superior communication bandwidths, efficiency in power consumption, and latency performance
    compared to electronic NoCs. Serving as the critical part of ONoCs, an optical
    router composed of waveguides and photonic switching elements (PSEs) routes signals between two hubs or between a hub and a memory controller. Many studies focus on developing efficient architectures of optical routers, while their physical implementation that can seriously deteriorate the quality of the architectures is rarely addressed. The existing automatic place-and-route tools suff er from considerable insertion loss due to many waveguide crossings outside of PSEs, which leads to huge power consumption of laser sources. By observing that the logic schemes of most optical routers are actually planar, we develop a concurrent PSE placement and waveguide routing flow, called PlanarONoC, that guarantees optimal solutions in terms of crossings for planar logic schemes. Experimental results show that the proposed flow reduces the maximum insertion loss by 37% on average, guarantees no waveguide crossing outside of PSEs, and performs much more efficient compared to the state-of-the-art work.

    Abstract vii List of Tables xi List of Figures xii Chapter 1. Introduction 1 1.1 Optical Network-on-Chip . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 Chapter 2. Preliminaries 13 2.1 Insertion Loss in Wavelength-Routed Optical Router . . . . . . . . . . . . 13 2.2 Planar Embedding at Fixed Vertex Locations . . . . . . . . . . . . . . . . 15 Chapter 3. Concurrent Placement and Routing for Crossing Minimization 18 3.1 Algorithm Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Orientation-aware Planar Embedding . . . . . . . . . . . . . . . . . . . . . 20 3.3 Order-constrained Hamiltonian Cycle Finding . . . . . . . . . . . . . . . . 21 3.3.1 Cycle Initialization for Fixed Vertices . . . . . . . . . . . . . . . . . 22 3.3.2 PSE Chaining and Insertion . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.3 Restricted PSE Chaining Considering Thermal Effect . . . . . . . . . . . 25 3.4 Planarity-preserving PSE Placement and Routing . . . . . . . . . . . . . . 27 Chapter 4. Experimental Results 30 4.1 Environment Setting . . . . . . . . . . . . . . . .. . . . . . . . . . . . 30 4.2 Comparison Between Our Method and The Other Works . . . . . . . . . . . . . 30 Chapter 5. Conclusions 40 Bibliography 41 Publication List 45

    [1] A. v. Beuningen, L. Ramini, D. Bertozzi, and U. Schlichtmann, \PROTON+:
    a placement and routing tool for 3d optical networks-on-chip with a single
    optical layer," ACM Journal on Emerging Technologies in Computing Systems
    (JETC), vol. 12, no. 4, article 44, 2015.
    [2] A. v. Beuningen and U. Schlichtmann, \PLATON: a force-directed placement
    algorithm for 3D optical networks-on-chip," Proc. ACM International Sympo-
    sium on Physical Design, 2016.
    [3] A. Boos, L. Ramini, U. Schlichtmann, and D. Bertozzi, \PROTON: an au-
    tomatic place-and-route tool for optical networks-on-chip," Proc. IEEE/ACM
    International Conference on Computer-Aided Design, 2013.
    [4] M. Briere, E. Drouard, F. Mieyeville, D. Navarro, I. O'Connor, and F. Gaot,
    \Heterogeneous modelling of an optical network-on-chip with SystemC," Proc.
    IEEE International Workshop on Rapid System Prototyping, 2005.
    [5] T. M. Chan, H.-F. Ho mann, S. Kiazyk, and A. Lubiw, \Minimum length
    embedding of planar graphs at xed vertex location," Graph Drawing (GD13),
    vol. 8242 of LNCS, pp. 376{387, 2013.
    [6] M. Chrobak and T. Payne, \A linear-time algorithm for drawing a planar graph
    on the grid," Information Processing Letters, vol. 54, no. 4, pp. 241{246, 1995.
    [7] M.-R. Garey, D.-S. Johnson, and L. Stockmeyer, \Some simpli ed NP-complete
    problem," Proc. ACM Symposium on Theory of Computing, 1974.
    [8] H. Gu, J. Hu, and W. Zhang, \A low-power fat tree-based optical network-on-
    chip multiporcessor system-on-chip," Proc. Design, Automation and Test in
    Europe, 2009.
    [9] J. Pach and R. Wenger, \Embedding planar graphs at xed vertex locations,"
    Graphs and Combinatorics, vol. 17, no. 4, pp. 717{728, 2001.
    [10] A. Scandurra and I. O.Connor, \Scalable CMOS-compatible photonic routing
    topologies for versatile networks on chip," Network on Chip Architecture, 2008.
    [11] X. Tan, M. Yang, L. Zhang, Y. Jiang, and J. Yang, \On a scalable, non-blocking
    optical router for photonic networks-on-chip designs," Proc. Symposium on
    Photonics and Optoelectronics, 2011.
    [12] X. Tan, M. Yang, L. Zhang, Y. Jiang, and J. Yang, \A generic optical router de-
    sign for photonic network-on-chips," Journal of Lightwave Technology, vol. 30,
    no. 3, pp. 368{376, 2012.
    [13] M. Tala, M. Castellari, M. Balboni, and D. Bertozzi, \Populating and Explor-
    ing the Design Space of Wavelength-Routed Optical Network-on-Chip Topolo-
    gies by Leveraging the Add-Drop Filtering Primitive," Proc. IEEE/ACM In-
    ternational Symposium on Networks-on-Chip, 2016.
    [14] M. C. Meyer, A. B. Ahmed, and Y. Okuyama, \FTTDOR: Microring
    Fault-resilient Optical Router for Reliable Optical Network-on-Chip Systems,"
    Proc. IEEE 9th International Symposium on Embedded Multicore/Many-core
    Systems-on-Chip, 2015.
    [15] M. Tinati, S. Koohi, and S. Hessabi, \Impact of On-chip Power Distribution
    on Temperature-Induced Faults in Optical NoCs," Proc. IEEE International
    Symposium on Embedded Multicore/Many-core Systems-on-Chip, 2016.
    [16] S. Feng, T. Lei, H. Chen, H. Cai, X. Luo, and A.W. Poon, \Silicon photonics:
    from a microresonator perspective," Laser Photonics Rev. 6, no. 2, pp. 145{177,
    2012.
    [17] C. J. Nitta, M. K. Farrens, and V. Akella, \Resilient Microring Resonator
    Based Photonic Networks," IEEE/ACM International Symposium on Microar-
    chitecture, 2011.
    [18] A. B. Ahmed, and A. B. Abdallah, \An Energy-Ecient High-Throughput
    Mesh-Based Photonic On-Chip Interconnect for Many-Core Systems," Journal
    of Photonics, vol. 3, no. 2, 2016.
    [19] T. Barwicz, M. A. Popovic, P. T. Rakichand, M. R. Watts etal:, \Microring-
    resonator-based add-drop lters in sin: fabrication and analysis," Opt. Express,
    vol. 12, no. 7, pp. 1437-pp.1442, Apr 2004.
    [20] K. Bergman, L. P. Carloni, A. Biberman, J. Chan, and G. Hendry, \Photonic
    Network-on-Chip Design," Springer-Verlag New York, 2014, iSBN: 978-1-4419-
    9334-2.
    [21] W. Bogaerts, P. Dumon, D. V. Thourhout, and R. Baets, \Low-loss, lowcross-
    talk crossings for silicon-on-insulator nanophotonic waveguides," Optics letters,
    vol. 32, no. 19, pp. 2801{2803, 2007.
    [22] M. McLaren, N. L. Binkert, A. L. Davis, and M. Florentino, \Energy-ecient
    and fault-tolerant resonator-based modulation and wavelength division multiplexing systems," 22 2014, U.S. Patent 8705972.
    [23] T. Baba, S. Akiyama, M. Imai, N. Hirayama etal:, \50-gb/s ring-resonator-
    based silicon modulator," Opt. Express, vol. 21, no. 10, pp. 11869{11876, May
    2013.
    [24] D. Chen, H. R. Fetterman, A. Chen, W. H. Steier, L. R. Dalton, W. Wang, and
    Y. Shi, \Demonstration of 110 ghz electro-optic polymer modulators," Applied
    Physics Letters, vol. 70, no. 25, pp. 3335{3337, 1997.
    [25] S. Xiao, M. H. Khan, H. Shen, and M. Qi, \Compact silicon microring res-
    onators with ultra-low propagation loss in the C band," Opt. Express, vol. 15,
    no. 22, pp. 14467{14475, Oct 2007.
    [26] S. S. Y. Liu, R. G. Luo, S. Aroonsantidecha, C. Y. Chin, and H. M. Chen,
    \Fast thermal aware placement with accurate thermal analysis based on green
    function," IEEE TVLSI, vol. 22, no. 6, pp. 1404{1415, 2014.
    [27] The LEDA package. http://www.algorithmic-solutions.com/leda
    [28] The tool to draw heat maps. https://plot.ly

    無法下載圖示 全文公開日期 2019/07/30 (校內網路)
    全文公開日期 本全文未授權公開 (校外網路)
    全文公開日期 本全文未授權公開 (國家圖書館:臺灣博碩士論文系統)
    QR CODE