這篇論文在探討多邊形現場可程式邏輯陣列(Polygonal Field Programmable Gate Array) 內部的交換模組(Switching Module) 所使用新奇的繞線演算法(Routing Algorithm). 在先前整局繞線演算法(Global Routing) 常被探討使用在現場可程式邏輯陣列(Field Programmable Gate Array) , 但是此法的複雜度比較高 . 所以我們發展比較簡易的繞線演算法 , 來解決這個問題 . 這個新奇的繞線演算法稱為“圖形組對開關繞線演算法”(Mapping Pair Switch Routing Algorithm).

任一個圖形組對開關是一個開關且存在於普遍性交換模組(Universal Switch Module) . 所有的 兩端點網狀物(2-pin net) 都能被尋找到它相對映的圖形組對開關經由圖形組對開關繞線演算法 . 這個圖形組對開關繞線演算法會呼叫兩個子演算法來完成整體功能 . 第一個子演算法是“尋找相鄰的圖形組對開關演算法”(Searching Neighbor Mapping Pair Algorithm) , 另一個子演算法是“尋找平行圖形組對開關演算法”(Searching Parallel Mapping Pair Algorithm) . 主演算法在運作過程中會呼叫這兩個子演算法當它認為有需要時 .

整個圖形組對開關繞線演算法在處理全部的兩端點網狀物, 在全部的兩端點網狀物都處理完畢後 , 整個流程結束 . 所需要的答案就是多邊形交換網路模組(Polygonal Switching Network Module) 內部被設為 “開”(on) 的圖形組對開關 . 實驗上的結果在說明用此法於對稱可程式多晶片模組(Symmetric Programmable Multi-Chip Module) , 可減少使用開關的數目 . 圖形組對開關繞線演算法對多邊形的結構非常好用 .

This thesis proposes a novel routing algorithm for solving switch modules of polygonal Field Programmable Gate Array (FPGA). The dominating set method for Global Routing in symmetrical FPGA has high computational complexity. Consequently, we present a novel low complexity routing algorithm, namely, the Mapping Pair (MP) routing algorithm, for solving the problem. An MP is a programmable switch in universal switch modules. All two-pin nets can be searched for their relative MP of switch module through two sub-algorithms of the proposed routing algorithm. The first one is “Searching Neighbor MP Algorithm” and the other is “Searching PMP (Parallel Mapping Pair) Algorithm”. The routing is repeated again and again until all 2-pin nets have been fully processed. The experimental results show that the proposed algorithm for polygonal switching architecture can reduce the number of programmable switches in the routing module. As a result, the MP routing algorithm is very useful for any polygonal architecture.

[1] M. H. Yen, S. J. Chen, and S. H. Lan, “Symmetric and programmable multi-chip module for rapid prototyping system,” Proc. 1999 IEEE Workshop on SiGNAL PROCESSING SYSTEMS Design and Implementation, pp. 301-310, 1999.
[2] Jason Meyer and Fatih Kocan, “Sharing of SRAM Tables Among NPN-Equivalent LUTs in SRAM-Based FPGAs”, IEEE Transaction on VLSI Systems, vol. 15, Issue 2, pp. 182-195, Feb. 2007.
[3] Francisco-Javier Veredas, Michael Scheppler, Bumei Zhai and Hans-Joerg Pfleiderer, “Regular Routing Architecture for a LUT-based MPGA”, 2006 IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architecture, vol. 00, 2-3. Pages: 6 pp., March 2006.
[4] Parivallal Kannan and Dinesh Bhatia, “Interconnect Estimation for FPGAs”, IEEE Transactions on Computer-Aidad Design if Integrated Circuits and Systems,vol. 25, no. 8, pp. 1523-1534, August 2006.
[5] Wing On Fung, Tughrul Arslan and Sami Khawam, “Genetic Algorithm based Engine for Domain-Specific Reconfigurable Arrays”, Proc. of the First NASA/ESA Conference on Adaptive Hardware and Systems, pp. 200-206, June 2006.
[6] M. Butts, “Future directions of dynamically reprogrammable systems,” Proc. IEEE 1995 Custom Integrated Circuits Conference, pp. 487-494, May 1995.
[7] David M. Lewis, Marcus van Ierssel, and Paul Chow, “The Transmogrifier-2: A 1 Million Gate Rapid-Prototyping System”, IEEE Transactions on VLSI Systems, vol. 6, no. 2, pp. 188-198, June 1998.
[8] Eduardo I. Boemo, and Juan M. Meneses, “Some Experiments About Wave Pipelining on FPGA’s”, IEEE Transactions on VLSI Systems, vol. 6, no. 2, pp. 232-237, June 1998.
[9] Lan S., “Architecture and CAD tools for a field programmable multi-chip module,” Ph.D. Thesis, Standford University, August 1995.
[10] S. Burman and Naveed A. Sherwani, “Programmable multichip module,” IEEE Micro, pp. 28-35, April 1993.
[11] A. Dobbelare, El Gamal, D. How, and B. Kleveland, “Field programmable MCM system-design of an interconnection frame,” Proceeding of the IEEE 1992 Custom Integrated Circuits Conference, pp. 15.1/1-6.
[12] S. Walters, “Computer-aided prototyping for ASIC-based systems,”, IEEE Design and Test of Computers, pp. 4-10, June 1991.
[13] Pritha Banerjee and Susmita Sur-Lolay, “Faster Placer for Island-Style FPGAs”, International Conference on Computing: Theory and Applications, 2007, ICCTA, pp. 117-121, March 2007.
[14] Luca Sterpone and Massimo Violante, “A New Reliability-Oriented Place and Route Algorithm for SRAM-Based FPGAs”, IEEE Transactions on Computers, vol. 55, no. 6, pp.732-744, June 2006.
[15] Brian Von Herzen, “Signal Processing at 250 MHz Using High-Performance FPGA’s”, IEEE Transactions on VLSI Systems, vol. 6, no. 2, pp. 238-246, June 1998.
[16] Yao-Wen Chang, S. Thakur, Kai Zhu and D.F. Wong, “A new global routing algorithm for FPGA” IEEE/ACM International Conference on ComputerAided Design, pp. 356-361, 1994.
[17] S. Thakur, Yao-Wen Chang, D. F. Wong, S. Muthukrishnan, “Algorithm for an FPGA switch module routing problem with application to global routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, vol. 16, no. 1, pp. 32-46, January 1997.
[18] Deepak Rautela, Rajendra Katti, “Design and implementation of FPGA router for efficient utilization of heterogeneous routing resources,” Proceedings of the IEEE Computer Society Annual Symposium on VLSI, New Frontiers in VLSI Design, 2005 IEEE
[19] Yao-Wen Chang, “Routing Architectures and Algorithms for Field-Programmable Gate Arrays”, Ph.D. Thesis, The University of Texas at Austin, August 1996.
[20] Mao-Hsu Yen, Mon-Chau Shie, and Sanko H. Lan, “Polygonal routing network for FPGA/FPIC,” 1999 International Symposium on VLSI Technology, System, and Applications, pp. 104-107, 1999 VLSI-TSA
[21] Aptix, Inc., “Aptix field programmable interconnect data book,” 1993
[22] R. Guo, H. Nguyen, A. Srinivasan, H. Verheyen, H. Cai, S. Law, and A. Mohsen, “A 1024 pin universal interconnection array with routing architecture,” Proc. IEEE 1992 Custom Integrated Circuits Conference, pp. 4.5.1-4.5.4, May 1992.
[23] I-Cube, Inc., I-Cube FPID family data book, Nov. 1993.
[24] Mao-Hsu Yen, “Polygonal switching network for symmetric programmable multi-chip module,” Ph.D. Thesis, National Taiwan University of Science and Technology, November 2000.
[25] S.D. Brown and J. Rose, “FPGA and CPLD architectures: a tutorial”, IEEE Design and Test of Comput., pp. 42-57, Summer 1996.
[26] Actel Corp., “FPGA data book and design guide,”, 1996.
[27] E. Syam Sunder Reddy, M. Saahikanth and V. Kamakoti, “Detecting SEU-caused Routing Errors in SRAM-based FPGAs”, International Conference on VLSI Design, pp. 736-741, January 2005.
[28] Fei He, William N. N. Hung, and Jianguang Sun, “Segmented Channel Routing with Pin Rearrangements via Satisfiability”, IEEE International Symposium on Circuits and Systems, vol. 6, pp. 6248-6251, May 2005.
[29] Zied Marrakchi, Hayder Mrabet and Habib Mehrez, “Hierarchical FPGA clustering to improve routability”, International Conference on Reconfigurable Computing and FPGAs, Pages 4, September 2005.
[30] J. Varghese, M. Butts, and J. Batcheller, “An efficient logic emulation system,” IEEE Transactions on VLSI Systems, vol. 1 no. 1 pp. 171-174, June 1993.
[31] J. Hwang and A. El Gamal, “Min-Cut Replication in Partitioned Networks,” IEEE Trans. On CAD of ICs and System, pp. 96-106, January 1995.
[32] Kostas Siozios and Dimitrios Soudris, “A Novel Methodology for Temperature-Awarw Placement and Routing of FPGAs”, IEEE Computer Society Annual Symposium on VLSI, pp. 55-60, March 2007.
[33] Fei He, Xiaoyu Song, Ming Gu, and Jiaguang Sun, “Probabilistic Optimization for FPGA Board level Routing Problems”, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 53, no. 4, pp. 264-268, April 2006.
[34] Cristinel Ababei, Hushrav Mogal and Kia Bazargan, “Three-Dimensional Place and Route for FPGAs”, IEEE Transactions on Computer-Aidad Design if Integrated Circuits and Systems, vol. 25, no. 6, pp. 1132-1140, June 2006.
[35] J. Babb et al., “Virtual Wires: Overcomeing Pin Limitation in FPGA-based Logic Emulators,” Proc. IEEE Workshop on FPGAs for Custom Computing Machine, pp. 142-151, April 1993.
[36] Pongstorn Maidee, Cristinel Ababei and Lia Bazargan, “Timing-Driven Partitioning-Based Placement for Island Style FPGAs”, IEEE Transaction on Computer-Aided Design of Integrated Circuits and System, vol. 24, no. 3, pp. 395-406, March 2005.
[37] I. Dobbelaere and A. El Gamal, How and B. Kleveland, “Field programmable MCM Systems – Design of an Interconnection Frame,” Proc. IEEE 1992 Custom Integrated Circuits Conference, pp. 4.6.1-4.6.4, May 1992.
[38] Manuel Rubio del Solar, Vega Rodriguez, “Placement and Routing of Boolean Functions in constrained FPGAs using a Distributed Genetic Algorithm and Local Search”, International Parallel and Distributed Processing Symposium, Pages:7, April 2006.
[39] R. Manimegalai, E. Siva Soumya, and Kamakoti, “Placement and Routing for 3D-FPGAs using Reinforcement Learning and Support Vector Machines”, International Conference on VLSI Design, pp. 451-456, 2005.
[40] Altera Corp., “Flex 10K handbook,”, 1996.
[41] Xilinx Inc., “The programmable logic data book,”, 1996.
[42] M. H. Yen, S. J. Chen, and S. H. Lan, “A three-sided rearrangeable polygonal switching network for FPGA,” 2002 VLSI/CAD Conferences, Taiwan, pp. 207-210, 2002.
[43] J. Rose and S. Brown, “Flexibility of interconnection structures for field-programmable gate arrays,” IEEE J. Solid State Circuits, vol. 26, no. 3, pp. 277-282, March 1991
[44] Y. Sun, T. C. Wang, C. K. Wong, and C. L. Liu, “Routing for symmetric FPGAs and FPICs,” Proc. IEEE Trans. Computer Aided Design, vol. 16, no. 1, pp. 20-31, Jan. 1997.
[45] Michael Shyu, Guang-Ming Wu, Yu-Dong Chang and Yao-Wen Chang, “Generic universal switch blocks,” IEEE Transactions on Computers, vol. 49, no. 4, pp. 348-359, April 2000.
[46] Hongbing Fan, Jiping Liu and Yu-Liang Wu, “General models and a reduction design technique for FPGA switch box designs” IEEE Transactions on Computers, vol. 52, no. 1, pp. 21-30, January 2003
[47] Guang-Min Wu and Yao-Wen Chang, “Quasi-universal switch matrices for FPD design,” IEEE Transactions on Computer, vol. 48, no. 10, pp. 1107-1122, 1999
[48] Yao-Wen Chang, D. F. Wong, C. K. Wong, “Universal switch modules for FPGA design,” ACM Transactions on Design Automation of Electronic System, vol. 1, no. 1, pp. 80-101, January 1996.
[49] G.-M. Wu, M. Shyu, and Y.-W. Chang, “Universal switch blocks for three-dimensional FPGA design,” IEE Proc.-Circuits Devices Syst., vol. 151, no. 1, pp. 49-57, February 2004.
[50] Hongbing Fan, Yu-Liang Wu, Ray Chak-Chung Cheung and Jiping Liu, “Decomposition Design Theory and Methodology for Arbitrary-Shaped Switch Boxes”, IEEE Transactions on Computers, vol. 55, Issue 4, pp. 373-384, April 2006.
[51] Taraneh Taghavi, Soheil Ghiasi and majid Sarrafzadeh, “Routing Algorithms: Architecture Driven rerouting Enhancement for FPGA”, IEEE International Symposium on Circuits and Systems, pp. 21-24, May 2006.
[52] Andy Ye and Jonathan Rose, “Using Bus-Based Connections to Improve Field-Programmable Gate-Array density for implementing Datapath Circuits”, IEEE Transactions on VLSI Systems, vol. 14, no. 5, pp. 462-473, May 2006.
[53] Jun Tan, Qiushi Shen, Yuanfeng Chen, Lingli Wang and Jiarong Tong, “FPGA Routing Architecture Optimization”, 2006 8th International Conference on Solid-State and Integrated Circuit Technology, pp. 1934-1936, 2006.
[54] Catherine L. Zhou, Yu-Liang Wu and Wai-Chung Tang, “Use Augmented Connection Boxes to Improve FPGA Performance”, International Conference on Communications, Circuits and Systems proceedings, vol. 4, pp. 2469-2473, June 2006.
[55] G. G. Leminex and S. D. Brown, “A detailed routing algorithm for allocating wire segments in field-programmable gate arrays,” Proc. ACM/SIGDA Physical Design Workshop, pp. 215-216, Lake Arrowhead, CA, 1993.
[56] Wai-Kei Mak and Hao Li, “Placement for Modern FPGAs”, Emerging Information Technology Conference, Pages 4, August 2005.
[57] Lipo Wang, Lei Zhou and Wen Liu, “FPGA Segmented Channel Routing Using Genetic Algorithms”, IEEE Congress on Evolutionary Computation, vol. 3, pp. 2161-2165, September 2005.
[58] R. Glenn Wood and Rob A. Rutenbar, “FPGA Routing and Routability Estimation via Boolean Satisfiability”, IEEE Transactions on VLSI Systems, vol. 6, no. 2, pp. 222-231, June 1998.