(3.238.186.43) 您好!臺灣時間:2021/02/28 12:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:莊馥宇
研究生(外文):Fu-Yu Chuang
論文名稱:考慮波導匹配限制之晶片上光繞線
論文名稱(外文):On-chip Optical Routing with Waveguide Matching Constraints
指導教授:張耀文張耀文引用關係
指導教授(外文):Yao-Wen Chang
口試委員:江蕙如黃婷婷方劭云
口試委員(外文):Hui-Ru JiangTing-Ting HwangShao-Yun Fang
口試日期:2019-07-10
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:62
中文關鍵詞:實體設計波導匹配光繞線
DOI:10.6342/NTU201902861
相關次數:
  • 被引用被引用:0
  • 點閱點閱:42
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在積體電路的深奈米技術節點之中,為了因應晶片對大頻寬與低功耗日趨嚴苛的要求,光學積體電路(Photonic Integrated Circuits, PICs)逐漸成為一個有前景的解決方案。在光學積體電路中,晶片上的訊號傳遞是透過光互連(optical interconnections)的形式達成。在文獻上有許多針對光學積體電路繞線問題的演算法被提出,這些文獻分別考慮不同電路設計上的問題,例如:熱可靠度(thermal reliability)、訊號傳遞損失(transmission loss)等。
然而,在許多新興的應用之中,不同的光路徑需要被匹配才能保證電路正確的功能性,匹配的條件包含路徑長度、路徑的彎曲數量、路徑彎曲的曲率半徑、路徑的交叉數量等。就我們所知,這些光繞線路徑匹配的限制在目前並沒有文獻提出方法處理。
在本篇論文中,我們提出了一套完整的繞線流程,包含預處理階段(preprocessing stage)、全局繞線階段(global routing stage)以及細部繞線階段(detailed routing stage)。在預處理階段中,我們建立基於六邊形繞線風格的最佳史坦納樹來處理多腳位信號線。接著我們使用基於整數線性規劃(Integer Linear Programming, ILP)的全局繞線演算法處理波導匹配限制,並同時最小化總訊號傳遞損失。最後,採用基於A星搜尋演算法並遵從全局繞線結果的細部繞線來決定最終的光繞線拓樸。
實驗結果顯示我們的光繞線器在所有的光電路設計上能夠達到百分之百的繞線率,且與一般基於A星搜尋演算法的匹配繞線器相比,我們的光繞線器在不違反任何波導匹配的限制之下,能夠達成較小的總訊號傳遞損失以及最大訊號傳遞損失。
In the deep nanometer VLSI technology node, photonic integrated circuits (PICs), which introduce optical interconnections for on-chip communication, have become one of the most promising solutions to the increasing requirements with large bandwidth and low-power consumption.
Routing techniques for optical interconnections have been proposed to deal with different routing issues in PICs, including thermal reliability, transmission losses, and other design considerations. In some emerging applications, however, different optical paths are required to be closely matched (in terms of the path length, the number of bends, the radius of curvature of bends, and the crossing count) to operate correctly. To the best of our knowledge, there is no previous work dealing with these matching constraints in optical routing.
In this thesis, we propose a complete algorithm flow consisting of the preprocessing stage, the global routing stage, and the detailed routing stage.
In the preprocessing stage, an optimal Steiner tree is constructed with a hexagonal routing style to handle multi-pin nets. Then, an integer-linear-programming-based global routing is adopted to deal with the matching constraints while minimizing the total transmission loss in a design. Finally, an A*-search detailed routing which honors the global routing result is adopted to generate the final routing topology.
Experimental results on the 2007 ISPD Global Routing Contest designs with proper netlist preprocessing show that our optical router can route all nets without violating any matching constraints while achieving lower total/maximum transmission loss compared to an A*-search-based match-net routing.
Acknowledgements iii
Abstract (Chinese) iv
Abstract vi
List of Tables x
List of Figures xi

Chapter 1. Introduction 1
1.1 Introduction to On-Chip Optical Routing . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Routing for Optical Networks-on-Chips (ONoCs) . . . . . . . . . 7
1.3.2 Optical Routing for On-chip Signals . . . . . . . . . . . . . . 9
1.3.3 Analog Routing . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . 13

Chapter 2. Preliminaries 14
2.1 Transmission Loss . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Crossing Loss . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Bending Loss . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.3 Splitting Loss . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.4 Path Loss . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.5 Total and Maximum Transmission Loss . . . . . . . . . . . . . 16
2.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 17

Chapter 3. Our Proposed Algorithm 18
3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Hexagonal Routing Grids Construction . . . . . . . . . . . . . 20
3.2.2 Loss-Aware Hexagonal Steiner Tree Construction . . . . . . . . 21
3.3 Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 ILP-Based Global Routing Formulation . . . . . . . . . . . . . 27
3.3.2 ILP Solving with Net Clustering and Partitioning . . . . . . . 33
3.3.3 Detailed Routing Guide Construction . . . . . . . . . . . . . 36
3.4 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1 Guided A*-Search Routing . . . . . . . . . . . . . . . . . . . 37
3.4.2 Bezier-Curve-Based Curvilinearizing . . . . . . . . . . . . . 38

Chapter 4. Experimental Results 40
4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Benchmark Preprocessing and Statistics . . . . . . . . . . . . . . . 41
4.3 Results and Comparisons . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 A*-search-based Matching Routing . . . . . . . . . . . . . . . 44
4.3.2 Comparisons to Matching Routing Methods (HMSTs) . . . . . . . 45
4.3.3 Comparisons to Matching Routing Methods (LHSTs) . . . . . . . 48
4.3.4 Effectiveness of LHST Construction . . . . . . . . . . . . . . 51

Chapter 5. Conclusions and Future Work 54
5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Bibliography 58
[1] W. Bogaerts and L. Chrostowski, "Silicon photonics circuit design: methods, tools and challenges," Laser & Photonics Reviews, vol. 12, no. 4, p. 1700237, 2018.
[2] W. Bogaerts, P. Dumon, D. Van 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.
[3] A. Boos, L. Ramini, U. Schlichtmann, and D. Bertozzi, "Proton: An automatic place-and-route tool for optical networks-on-chip," in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 38--145, San Jose, CA, November 2013.
[4] M.-C. F. Chang, V. P. Roychowdhury, L. Zhang, H. Shin, and Y. Qian, "RF/wireless interconnect for inter-and intra-chip communications," Proceedings of the IEEE, vol. 89, no. 4, pp. 456--466, 2001.
[5] M.-C. F. Chang, E. Socher, S.-W. Tam, J. Cong, and G. Reinman, "RF interconnects for communications on-chip," in Proceedings of ACM International Symposium on Physical Design, pp. 78--83, Portland, OR, April 2008.
[6] N. Charles, N. Jovanovic, S. Gross, P. Stewart, B. Norris, J. O''Byrne, J. S. Lawrence, M. J. Withford, and P. G. Tuthill, "Design of optically path-length-matched, three-dimensional photonic circuits comprising uniquely routed waveguides," Applied Optics, vol. 51, no. 27, pp. 6489--6497, 2012.
[7] Y.-K. Chuang, K.-J. Chen, K.-L. Lin, S.-Y. Fang, B. Li, and U. Schlichtmann, "PlanarONoC: Concurrent placement and routing considering crossing minimization for optical networks-on-chip," in Proceedings of ACM/IEEE Design Automation Conference, pp. 151:1--151:6, San Francisco, CA, June 2018.
[8] D. Ding, B. Yu, and D. Z. Pan, "GLOW: A global router for low-power thermal-reliable interconnect synthesis using photonic wavelength multiplexing," in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 621--626, Sydney, Australia, February 2012.
[9] D. Ding, Y. Zhang, H. Huang, R. T. Chen, and D. Z. Pan, "O-Router: An optical routing framework for low power on-chip silicon nano-photonic integration," in Proceedings of ACM/IEEE Design Automation Conference, pp. 264--269, San Francisco, CA, July 2009.
[10] C. M. Fiduccia and R. M. Mattheyses, "A linear-time heuristic for improving network partitions," in Proceedings of ACM/IEEE Design Automation Conference, pp. 175--181, Las Vegas, NV, June 1982.
[11] IBM, "Cplex optimizer," https://www.ibm.com/analytics/cplex-optimizer.
[12] G.-H. Lin, G. Xue, and D. Zhou, "Approximating hexagonal Steiner minimal trees by fast optimal layout of minimum spanning trees," in IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp. 392--398, Austin, TX, October 1999.
[13] D. Liu, Z. Zhao, Z. Wang, Z. Ying, R. T. Chen, and D. Z. Pan, "OPERON: Optical-electrical power-e cient route synthesis for on-chip signals," in Proceedings of ACM/IEEE Design Automation Conference, pp. 75:1--75:6, San Fancisco, CA, June 2018.
[14] M. E. Mortenson, Mathematics for computer graphics applications. Industrial Press Inc., 1999, p. 264.
[15] H.-C. Ou, H.-C. C. Chien, and Y.-W. Chang, "Nonuniform multilevel analog routing with matching constraints," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 12, pp. 1942--1954, 2014.
[16] T. Samanta, P. Ghosal, H. Rahaman, and P. Dasgupta, "A heuristic method for constructing hexagonal steiner minimal trees for routing in VLSI," in IEEE International Symposium on Circuits and Systems, pp. 1788--1791, Island of Kos, Greece, May 2006.
[17] P. Sanchis, J. V. Galan, A. Griol, J. Marti, M. A. Piqueras, and J. M. Perdigues, "Low-crosstalk in silicon-on-insulator waveguide crossings with optimizedangle," IEEE Photonics Technology Letters, vol. 19, no. 20, pp. 1583--1585, 2007.
[18] S. K. Selvaraja, E. Sleeckx, M. Schaekers, W. Bogaerts, D. V. Thourhout, P. Dumon, and R. Baets, "Low-loss amorphous silicon-on-insulator technology for photonic integrated circuitry," Optics Communications, vol. 282, no. 9, pp. 1767--1770, 2009.
[19] N. Sherwani, Algorithms for VLSI physical design automation, 2nd ed. Kluwer Academic Publisher, Dordrecht, The Netherlands and Toppan Company (S) Pte Ltd, 1996.
[20] P. Spindler, "E cient quadratic placement of VLSI circuits," Ph.D. dissertation, Technische Universitat Munchen, 2008.
[21] P. Spindler and F. M. Johannes, "Fast and accurate routing demand estimation for e cient routability-driven placement," in Proceedings of ACM/IEEE Design, Automation and Test in Europe, pp. 1226--1231, Nice Acropolis, France, April 2007.
[22] N. Srivastava and K. Banerjee, "Performance analysis of carbon nanotube interconnects for VLSI applications," in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 383--390, San Jose, CA, November 2005.
[23] M. Torabi and L. Zhang, "Effi cient ILP-based variant-grid analog router," in IEEE International Symposium on Circuits and Systems, pp. 1266--1269, Montreal, Canada, May 2016.
[24] ----, "Electromigration-and parasitic-aware ILP-based analog router," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 99, pp. 1--14, 2018.
[25] A. Truppel, T.-M. Tseng, D. Bertozzi, J. C. Alves, and U. Schlichtmann, "PSION: Combining logical topology and physical layout optimization for wavelength-routed ONoCs," in Proceedings of ACM International Symposium on Physical Design, pp. 49--56, San Francisco, CA, April 2019.
[26] Y. Vlasov, "Silicon photonics for next generation computing systems," in European Conference on Optical Communications, pp. 1--2, Brussels, Belgium, September 2008.
[27] A. von Beuningen and U. Schlichtmann, "PLATON: A force-directed placement algorithm for 3D optical networks-on-chip," in Proceedings of ACM International Symposium on Physical Design, pp. 27--34, Santa Rosa, CA, April 2016.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔