臺灣博碩士論文加值系統

現場可程式化邏輯閘陣列(FPGA)正廣泛運用在數位電路和許多商業產品的實現，由於可程式化的開關具有高電阻和電容且佔大量面積，因此FPGA中的可程式化開關會影響本身的速率效能、晶元尺寸和繞線能力。在本篇論文中，我們提出了一個可重新安排階層式交換網路(HSN)運用在FPGA上。HSN的主要結構包含多邊形交換區塊(PSB)和連接閂(crossbar)。在相同面積和相同的開關個數下，我們證明了clique-based的階層式交換網路並非可重新安排的。HSN減少連線路徑的開關個數，因而提高FPGA的速率效能。

Field Programmable Gate Arrays (FPGA’s) are now widely used for the implementation of digital circuits and many commercial products. Since the programmable switches usually have high resistance and capacitance and occupy a large area, the number of programmable switches used in an FPGA affects its speed performance, die size, and routability. In this thesis, we propose a rearrangeable hierarchical switching network (HSN) for the implementation of an FPGA. The main component of this HSN consists of polygonal switch blocks and crossbars. With the same size and the same number of switches as our HSN, a clique-based hierarchical switching network is shown not rearrangeable. The HSN can reduce the number of switches along interconnecting paths, such that the speed performance of an FPGA can be improved.

摘要 I
Abstract II
誌謝 III
圖目錄 VI
第一章 緒論 9
1.1 研究動機與目的 9
1.2 論文內容簡述 13
第二章 背景與相關研究 14
2.1 交換網路 14
2.2 現場可程式邏輯陣列的架構 17
2.2.1 對稱陣列型 17
2.2.2 通用型交換區塊 19
2.2.3 交換區塊(Switch Block) 22
2.3 多邊型交換網路 25
第三章 階層式交換網路的運算 30
3.1 階層式交換網路 30
3.2 連線運算 34
3.3 階層式交換區塊 36
3.3.1 樹狀交換區塊 36
3.3.2 多邊形交換區塊 38
3.3.3 階層式交換區塊 40
3.4 階層式交換區塊相互連接運算 44
第四章 可重新安排階層式交換網路 50
4.1 二階層階層式交換區塊 50
4.2 多階層階層式交換區塊 58
4.3 可重新安排階層式交換網路 71
4.4 階層式交換網路的開關個數 73
第五章 結論與未來研究方向 74
參考文獻 75

[1] 鄭群星, “FPGA/CPLD 數位晶片設計入門-使用Xilinx ISE發展系統”, 2005
[2] Y. M. Yen and T. Y. Feng, “On a class of rearrangeable networks,” IEEE Transaction on Computers, vol. 41, no. 11, pp. 1361-1379, Nov. 1992.
[3] C. Mitchell and P. Wild, “One-stage one-sided rearrangeable switching net- works,” IEEE Transaction on Communications, vol. 37, no. 1, pp. 52-56, Jan. 1989.
[4] J. Gordon and S. Srikanthan, “Single sided switching network,” Electronics Letters, vol. 26, no. 4, pp. 248-250, Feb. 1990.
[5] H. Fan, J. Liu, Y. L. Wu “On Optimal Hyperuniversal and Rearrangeable Switch Box Designs,” IEEE Transactions On Computer-aided Design Of Integrated Circuits And Systems, Vol. 22, No. 12, December 2003
[6] C. Clos, “A study of nonblocking switching networks,” Bell Syst. Tech. J., vol. XXXII, pp. 406-424, Mar. 1953.
[7] V. E. Benes, “Mathematical Theory of Connectioning Networks and Telephone Traffic”, Academic Press, 1965.
[8] A. Jajszczyk, “Nonblocking, Repackable, and Rearrangeable Clos Networks: Fifty Years of the Theory Evolution”, IEEE Communications Magazine, October 2003, 41(10):28-33.
[9] S. Ohta, “A simple Control Algorithm for Rearrangeable Switching Networks with Time Division Multiplexed Links”, IEEE JSAC, vol. 5, no. 8, pp. 1301-08, Oct. 1987.
[10] S. D. Brown, R. J. Francis, J. Rose, and Z. G. Vranesic, “Field-Programmable Gate Arrays,” Kluwer Academic Publishers, Boston, MA, 1992.
[11] Y.-W. Chang, D.F. Wong, and C.K. Wong, “Universal Switch Modules for FPGA Design,” ACM Trans. Design Automation of Electronic Systems, vol. 1, no. 1, pp.80-101, Jan. 1996.
[12] S. D. Brown, R.J. Francis, J. Rose, and Z.G. Vranesic, "Field-Programmable Gate Arrays," Boston: Kluwer Academic, 1992.
[13] J. S. Rose and S. Brown, “Flexibility of interconnection structure for filed-programmable gate arrays,” IEEE, J. Solid-State Circuits, vol.26, no.3, pp.277-282, May, 1991.
[14] M. Shyu, Y. D. Chang, G. M. Wu, and Y. W. Chang, “Generic universal switch blocks,” IEEE Transaction on Computers, vol. 49, no. 4, pp. 348-359, Apr. 2000.
[15] H. Fan, J. Liu, and Y. L. Wu, “A Global Routing Model for Universal Switch Box Design” , IEEE, 2000.
[16] H. Fan, J. Liu, and Y. L. Wu, “Combinatorial Routing Analysis and Design of Universal Switch Blocks”, IEEE In: Proceedings of the 2001 Asia and South Pacific Conference on Design Automation, S. 641 – 644, New York, NY, USA, 2001.
[17] H. Fan, J. Liu, and Y. L. Wu, “The Exact Channel Density and Compound Design for Generic Universal Switch Blocks”, ACM Transactions on Design Automation of Electronic Systems , 2007.
[18] K. Kawana, H. Keida, M. Sakamoto, K. Shibata, and I. Moriyama, "An efficient logic block interconnect architecture for user-reprogrammable gate array," Proc. IEEE Custom Intergrated Circuits Conf., pp.313.1-31.3.4, 1990.
[19] M. J. Alexander, J. P. Cohoon, J. L. Ganley, and G. Robins, “Three-dimensional filed-programmable gate arrays.” Proc. IEEE Int. ASIC Conf., Austin, TX, September 1995, pp.253-256.
[20] A. Gayasen, V. Narayanan, M. Kandemir, and A. Rahman “Designing a 3-D FPGA: Switch Box Architecture and Thermal Issues” IEEE Transactions On Very Large Scale Integration VLSI Systems, Vol. 16, No. 7, July 2008.
[21] G.M. Wu, M. Shyu, Y.W. Chang, “Universal Switch Blocks for Three-Dimensional FPGA Design”, IEEE Proc.-Circuits Devices., Vol. 151, No. 1, February 2004.
[22] Y. T. Lai and P. T. Wang, “Hierarchical interconnection structures for field programmable gate arrays”, IEEE Trans. VLSI Systems, pp.186-196, 1997.
[23] M. H. Yen, S. J. Chen, and S. H. Lan, “A Three-Stage One-Sided Rearrangeable Switching Networks”, In IEEE Tr. Computers, pp.1-4, 2001
[24] M. H. Yen, “Polygonal Switching Network for Symmetric Programmable Multi-chip Module”, pp.20-30, 2000.
[25] Y. S. cheng, “A Rearrangeable Binary Tree Switching Network for FPGA Routing Architecture”, pp.33-39, 2009.