臺灣博碩士論文加值系統

本篇論文提出一個環型交換方塊（Ring Switch Box; RSB）架構，以應用在FPGA之多點連線（multipoint interconnection）繞線網路架構上。一個FPGA中的交換方塊(Switch Box; SB)若能實現所有可能的多點連線繞線需求，則稱此SB具有超通用(hyper-universal)。我們提出一個新的超通用(hyper-universal)環型交換方塊架構，該架構為四邊型方塊及每一邊上有w個端點建構而成。我們的架構與Fan’s的交換盒架構皆具有超通用性質，但我們將證明RSB架構在w>23時，我們比Fan的架構有較少的開關個數。本論文也將以benchmark電路來進行實驗，與Xilinx XC4000 Type SB、Wilton’s SB、通用型(universal)SB、Fan’s SB，及我們的超通用RSB比較。我們也提出另一種非對稱活塞型架構，是改良環型交換盒架構的，減少部分的開關數，但仍達到超通用的性質。此外，我們的RSB架構設計是具有高度擴展性(Scalable)及規則性(Regular)，因此很適合實現於FPGA上。

This paper explores theories on design multipoint interconnection networks, and proposes a ring switch box (RSB) design scheme which can be directly applied to field programmable gate arrays (FPGAs) and communication switching network designs. A switch box on an FPGA is said to be hyper-universal if it is routable for all possible surrounding multi-pin net topologies satisfying the routing resource constraints. We present new hyper-universal RSBs with four sides and w terminals on each side, which is routable for every multi-pin net-routing requirement. Our RSBs and Fan’s SB are hype-universal, but our RSBs with w >23 terminals on each side have better switch-efficiency than Fan’s switch boxes. We also give a formal analysis and extensive benchmark experiments on routability comparisons between today’s most well-known FPGA switch boxes like disjoint switch blocks (Xilinx XC4000 Type), Wilton’s switch blocks, Universal switch blocks, Fan’s switch boxes and our hyper-universal RSBs. We also present an asymmetric switch box that reduce a few switches and it is still hyper-universal. Besides, due to our hyper-universal RSBs designs are highly scalable and regular, thus it is very suitable for FPGA implementation.

中文摘要 I
Abstract II
致謝 III
目次 V
圖次 VII
表次 XI
第1章、 緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 研究方法 2
1.4 論文架構概述 4
第2章、 相關文獻 5
2.1 超通用交換盒 5
2.1.1 FPGA架構連線、定義連接區塊CB以及交換盒SB 5
2.1.2 2-pin尺寸限制和通用型交換盒 6
2.1.3 Multi-pin尺寸限制和超通用型交換盒 8
2.2 最小全域繞線 10
2.3 GR分解定理 11
2.4 Fan所提出的HUSB架構 15
第3章、 新的超通用交換盒架構-環狀和活塞型 20
3.1 環型交換盒架構 20
3.2 GR分類法 21
3.3 環狀交換盒架構繞線 26
3.4 超可重排交換網路 32
3.5 非對稱超通用交換盒架構 36
3.6 繞線能力比較 37
3.7 開關個數比較 38
第4章、 實驗數據 40
第5章、 結論 50
第6章、 未來工作 51
附件A 52
參考文獻 69

[1] J. Rose and S. Brown, “Flexibility of interconnection structures for field-programmable gate arrays,” Solid-State Circuits, IEEE Journal of, vol. 26, pp. 277-282, 1991.
[2] Y. W. Chang, D. F. Wong, and C. K. Wong, “Universal Switch-Module Design for Symmetric-Array-Based FPGAs,” Field-Programmable Gate Arrays, 1996. FPGA '96. Proceedings of the 1996 ACM Fourth International Symposium on, 1996, pp. 80-86.
[3] M. H. Yen, C. Yu, H. Y. Shin, and S. J. Chen, “A three-sided rearrangeable switching network for a binary fat tree,” International Journal of Electronics, vol. 98, pp. 713-734, 2011/06/01 2011.
[4] M. H. Yen, S. J. Chen, and S. H. Lan, “A three-stage one-sided rearrangeable polygonal switching network,” Computers, IEEE Transactions on, vol. 50, pp. 1291-1294, 2001.
[5] C. Mitchell and P. Wild, “One-stage one-sided rearrangeable switching networks,” Communications, IEEE Transactions on, vol. 37, pp. 52-56, 1989.
[6] M. H. Yen, M. C. Shie, and S. H. Lan, “Polygonal routing network for FPGA/FPIC,” VLSI Technology, Systems, and Applications, 1999. International Symposium on, 1999, pp. 104-107.
[7] H. Fan, J. Liu, Y. L. Wu, and C. C. Cheung, “On optimal hyperuniversal and rearrangeable switch box designs,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 22, pp. 1637-1649, 2003.
[8] H. Fan, J. Liu, and Y. L. Wu, “General models for optimum arbitrary-dimension FPGA switch box designs,” Computer Aided Design, 2000. ICCAD-2000. IEEE/ACM International Conference on, 2000, pp. 93-98.
[9] H. Fan, J. Liu, and Y. L. Wu, “General models and a reduction design technique for FPGA switch box designs,” Computers, IEEE Transactions on, vol. 52, pp. 21-30, 2003.
[10] H. Fan, J. Liu, Y. L. Wu, and C. K. Wong, “Reduction design for generic universal switch blocks,” ACM Trans. Des. Autom. Electron. Syst., vol. 7, pp. 526-546, 2002.
[11] H. Fan, Y. L. Wu, and C. L. Zhou, “Augmented disjoint switch boxes for FPGAs,” Proceedings of the 4th international symposium on Information and communication technologies, Cape Town, South Africa, 2005, pp. 129-134.
[12] H. Fan and Y. L. Wu, “Crossbar based design schemes for switch boxes and programmable interconnection networks,” Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific, 2005, pp. 910-915.
[13] H. Fan, J. Liu, Y. L. Wu, and C. C. Cheung, “On optimum switch box designs for 2-D FPGAs,” Design Automation Conference, 2001. Proceedings, 2001, pp. 203-208.
[14] M. Shyu, Y. L. Wu, Y. D. Chang, and Y. W. Chang, “Generic universal switch blocks,” Computers, IEEE Transactions on, vol. 49, pp. 348-359, 2000.
[15] V. Betz and J. Rose, “VPR: A new packing, placement and routing tool for FPGA research,” Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, 1997, pp. 213-222.
[16] K. Zhu, Y. W. Chang, and D. F. Wong, “Timing-driven routing for symmetrical-array-based FPGAs,” Computer Design: VLSI in Computers and Processors, 1998. ICCD '98. Proceedings. International Conference on, 1998, pp. 628-633.
[17] S. Yang, “Logic Synthesis and Optimization Benchmarks, Versions,” Microelectronics Centre of North Carolina, 1991.