臺灣博碩士論文加值系統

在多資源的限制下，每個電路元件可以由多種不同的資源來實踐，而每項資源亦可實踐多種的電路元件，所以很難以直覺式或亂數的方法隨意產生一組合理的初始解，以獲得較佳的結果。本論文提出以最大配對法作多資源限制電路分割，則能成功的解決這個問題。此外，在本論文中將擴展問題至解決多資源限制下的成本最小化電路分割。我們所提之新演算法先以解整數線性規劃求出FPGAs的型態及數目再以最大配對結合節點排序法對電路加以分割。
我們先將各資源之限制以整數線性規劃模組來表示，並且用解整數線性規劃之套裝軟體LINGO來幫助我們解得分割電路時所需成本最低之FPGA晶片型態及數目，接著再以結合節點排序之最大配對法將電路元件分割至所求得的晶片中。最大配對法結合節點排序法的目的，是為了使得分割時能減少晶片間的連線數目，進而降低輸入/出埠的使用及提高晶片內部邏輯資源的使用率。
在我們的實驗結果中顯示若依照解整數線性規劃模組所求得的晶片對電路做分割，將較一般使用單一固定晶片的成本花費得到近20%的改善；而結合節點排序之最大配對法在使用單一固定晶片做電路分割時，將比無節點排序的成本花費有19%以上的改善。此外在我們的實驗結果中亦證明了在不同的晶片價格分佈曲線下，應該採用不同的方式來選擇整數線性規劃模組解得的晶片，並非像過去的研究中所提之只要一律選擇最大的晶片。所以本論文所提之方法不僅解決了多資源限制的初始分割問題，也在成本最小化的分割問題上得到很好的經驗及實驗結果。

In FPGAs with complex resources, each circuit element can be implemented by variant resources and each resource can implement one ore more circuit elements. Usually it is difficult to randomly generate a feasible initial solution. In this thesis, we have solved this by maximum-matching method. A new cost minimization partitioning problem with complex resource constraints in FPGAs is formulated and solved.
We first write the complex resources constraints in ILP model and use the ILP solver, LINGO, to find the types and numbers of FPGA chips needed to minimize the total cost. Once the FPGA chips are found, we then use the techniques of vertex ordering and maximum-matching to partition the given circuit according to the FPGA resources we found in ILP solver. The purpose of using maximum-matching and vertex ordering methods is trying to find a feasible partition with a smaller cut-size.
Experimental results on the MCNC LGSynth91 benchmark shows that circuit according to the FPGA resources we found in ILP solver having 20% lower cost on average then the circuits using only one type FPGA. The proposed vertex ordering technique reduces the cost by 19% compared with the method without vertex ordering.

中文摘要
Abstract
序言
第一章前言1
第二章分割問題5
2-1.分割問題5
2-2.分割問題的最佳化目標6
2-2.1連線數目最小化6
2-2.2延遲時間最小化7
2-2.3成本花費最小化8
2-3.分割問題的類型8
2-3.1Two-way 分割8
2-3.2K-way 分割9
2-3.3FPGA 分割9
2-4.常見的分割問題演算法11
2-4.1以移動為基礎之方法(Move-Based Approaches)11
2-4.2幾何表示處理法(Geometric Representations)11
2-4.3組合公式化法(Combinatorial Formulations)12
2-4.4叢集處理法(Clustering Representations)12
第三章相關重要演算法13
3-1多資源限制電路分割演算法13
3-2.成本最小化電路分割演算法16
第四章成本最小化之多資源限制電路分割演算法20
4-1.問題描述20
4-2.合理初始分割解21
4-3.成本最小化之多資源限制電路分割演算法CMPCR26
4-3.1效能評量電路27
4-3.2整數線性規劃之模型28
4-3.3最大配對法34
4-3.4節點排序35
4-3.5輸入/出埠資源檢查41
第五章 實驗結果44
5-1實驗平台及評量電路44
5-2實驗流程44
5-3實驗結果49
第六章結論及未來發展61
參考文獻62
作者簡介

[1] C.J. Aplert and A.B. Kahug, "A General Framework for Vertex Orderings, With Applications to netlist Clustering.", Proc. IEEE Intl. Conf. on Comjputer-Aided Design, 1994, pp.63-67.
[2] C.J. Aplert and A.B. Kahug , "Recent Directions in Netlist Partition: a Survey", the VLSI Journal, pp.181, 1995.
[3] Raghu Burra and Dinesh Bhatia "Timming Driven Multi-FPGA Board Partitioning", IEEE VLSI design 1998.
[4] P.K. Chan, Martin D.F. Schlag and Jason Y. Zien "Spectral-Based Multi-Way Ratio Cut Partitioning and Clustering", Proc. Symp. on Integrated Systems, Seattle, March 1993.
[5] P.K. Chan, Martin D.F Schlag and Jason Y.Zien, "Spectral-Based Multi-Way FPGA Partitioning", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, pp.133-139, Monterey, 1995.
[6] Vi Chi Chan, David Lewis, "Hierarchical Partitioning for Field-Programmable Systems", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1997.
[7] Gray Chartrand, Ortrud R. Oellermann, Applied and Algorithmic Graph Theory.
[8] C.K. Cheng and Y.C. Wei, "An Improved Two-Way Partitioning Algorithm with Stable Performacnce," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. V.10, N.12, 1991, pp.1502-1511.
[9] N.-C Chou, L.-T. Liu, C.-K. Cheng, W.-J. Dai, and R. Lindelof. "Circuit partitioning for huge logic emulation systems.", In Proc. ACM/IEEE Design Automation Conf., pages 244-249, 1994.
[10] J. Cong, L. Hagen and A.B. Kahng, "Random Walks for Circuit Clustering", Proc. 4th IEEE Intl. ASIC Conf., Rochester, September 1991, pp.14.2.1-14.2.4.
[11] Jason Cong, Sung Kyu Lim, "Multiway Partitioning with Pairwise Movement", In Proc. ACM/IEEE Design Automation Conf., 1998.
[12] Jason Cong, Wilburt Juan Labio, Narayanan Shivakumar, "Multiway VLSI Circuit Partitioning Based on Dual Net Representation", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 15. No. 4. April 1996.
[13] Shantanu Dutt, Halim Theny, "Partitioning Around Roadblocks: Tackling Constraints with Intermediate Relaxations", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1997.
[14] Shantanu Dutt, Wenyong Deng, "VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1997.
[15] Wen-Jong Fang, Allen C.-H. Wu, "Multi-Way FPGA Partitioning by Fully Exploiting Design Hierarchy", ACM/IEEE Design Automation Conf., 1997.
[16] C.M. Fiduccia and R.M. Mattheyses, "A lineartime Heuristic for improving network partitions", Proc. ACM/IEEE Design Automation Conf., 1982, pp. 175-181.
[17] T.B.C. Heigham and C. Jones and T. Leighton , " Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms", Proc. ACM/IEEE Design Automation Conf., 1989, pp.775-778.
[18] D.J.-H. Huang and A.B. Kahug "Multi-Way System Partitioning into a Signal Type or Multiple Types of FPGAs", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, 1995.
[19] D.J.-H. Huang and A.B. Kahug. "When clusters meet partitioning into single or multiple type fpgas.", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, pages 140-145, 1995.
[20] L.James Hwang and Abbas El Gamal, "Min-Cut Replication in Partitioned Networks", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 14. No. 1.January 1995.
[21] B.W. Kermighan and S.Lin, "An Efficient Heuristic Procedure for Partition Graphs", Bell system Tech. Journal, vol. 49, Feb. 1970, pp. 291-307.
[22] R. Kuznar, F. Brglez, and B. Zajc. "Multi-way netlist partitioning into heterogenous fpgas and minimization of total device cost and interconnect.", In Proc. ACM/IEEE Design Automation Conf., pages 238-243, 1994.
[23] R. Kuznar, F. Brglez, and K. Kozminski. "Cost minimization of partitions into multiple devices.", In Proc. ACM/IEEE Design Automation Conf., pages 315-320, 1993.
[24] R. Kuznar, F. Brglez, and K. Kozminski. "Partitioning Digital Circuits for Implementation in Multiple FPGA ICs.", Technical Report TR93-03, MCNC, Research Triangle Park, NC March 1993.
[25] Huique Liu, Zhu and D.F. Wong "Circuit Partitioning with Complex Resource Constraints in FPGAs", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, 1998.
[26] Huique Liu and D.F. Wong "Network-Flow-Based Multiway Partitioning with Area and Pin Constraints", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. VOL. 17 January 1998.
[27] Huiqun Liu, D.F. Wong, "Network Flow Based Circuit Partitioning for Time-multiplexed FPGAs", In Proc. ACM/IEEE Design Automation Conf., 1998.
[28] Frank M. Johannes, "Partitioning of VLSI Circuits and Systems", ACM/IEEE Design Automation Conf. 1997.
[29] Bernhard M. Riess, Heiko A. Giselbrecht, Bernd Wurth, "A New K-Way Partitioning Approach for Multiple Types of FPGAs", Asia-South Pacific Design Automation Conference Proceedings, 1995.
[30] Wai-Kei Mark, D.F. Wong, "Minimum Replication Min-Cut Partitioning", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1997.
[31] Kalapi Roy-Neogi, Carl Sechen, "Multiple FPGA Partitioning with Performance Optimization", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, 1995.
[32] Sadiq M. Sait and Habib Youssef, VLSI PHYSICAL DESIGN AUTOMATION.
[33] L.A. Sanchis. "Multiple-way network partitioning.", IEEE Trans. On Computers, 38(1):62-81, January 1989.
[34] Prashant Sawkar, Donald Thomas, "Multi-way Partitioning For Minimum Delay For Look-Up Table Based FPGAs", ACM/IEEE Design Automation Conf., 1995.
[35] C. Sechen, "VLSI Placement and Global Routing Using Simulated Annealing.", Kluwer, B.V., Deventer, the Netherlands.
[36] W. Sun and C. Sechen, "Efficient and Effective Placements for Very Large Circuits", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1993, pp.170-177.
[37] Gregory Tumbush and Dinesh Bhatia "Partitioning Under Timing and Area Constraints", IEEE Intl. Conf. on Computer Design, 1997.
[38] J. Varghese, M.Butts, and J. Batcheller, "An Efficient Logic Emulation System," IEEE Trans. on VLSI, V.1, N.2, Jun. 1993, pp.171-174.
[39] Nam-Sung Woo and Jaeseok Kim "An Efficient Method of Partitioning Circuits for Multiple-FPGA Implementation ", ACM/IEEE Design Automation Conf., 1993.
[40] Honghua Yabng and D.F. Wong, "Efficient Network Flow Based Min-Cut Balanced Partitioning", Proc. IEEE Intl. Conf. on Computer-Aided Design, 1994, pp.50-55.
[41] Honghua Yang, D.F. Wong, "Area/Pin-Constrainted Circuit Clustering for Delay Minimization", In Proc. ACM/SIGDA International Workshop on Field-Programmable Gate Arrays, 1994.
[42] C.W. Yeh and C.K. Cheng. "A general purpose multiple way partitioning algorithm.", ACM/IEEE Design Automation Conf., pages 421-426, 1991.
[43] JasonY. Zien, Martine D. F. Schlag, Pak K. Chan, "Multi-level Spectral Hypergraph Partitioning with Arbitrary Vertex Sizes", Proc. IEEE Intl. Conf. on Computer-Aided Design, Santa Clara, Nov. 1997.
[44] Xilinx, Inc., The programmable Gate Array Data Book, Xilinx, San Jose 1992
[45] Xilinx FPGA price quotation, Sept 1992.
[46] The Programmable Gate Array Data Book. Xilinx, Inc., 2100j Logic Drive, San Jose, California, 1991.