藉由可規劃邏輯陣列技術在電路設計自動化技術的盛行，其相關演算法的研究和設計工具的發展已經成為在晶片設計技術上一個重要的課題。查表式可規劃邏輯陣列是可規劃邏輯陣列中最廣泛被應用的架構，其基本的邏輯元素是利用一個k-輸入的表以實現k-變數所有可能的布林代數，因為查表式可規劃邏輯陣列這種特性，使得查表式可規劃邏輯陣列設計中的映射方法成為重要的課題。這篇論文是用來探討查表式可規劃邏輯陣列之映射技術的問題。

　　我們先針對各種最佳化的目標，如面積和繞線度等，將映射技術的問題公式化，接著再針對各種不同的目標提出有效的演算法。對於不同可規劃邏輯陣列的架構及目標，所有被提出的映射技術演算法可以被區分成三類：1)同質性可規劃邏輯陣列面積的最小化，2)同質性可規劃邏輯陣列繞線度的最大化，以及3)異質性可規劃邏輯陣列面積的最佳化。

　　面積最小化是查表式可規劃邏輯陣列的一個重要目標，但這個問題已被證明是一個非多項式完全的問題；在這篇論文中，我們提出一個多項式的演算法來解決這個問題，它的時間複雜度是和電路閘數的三次方成正比，這個演算法先分割代表電路的圖形為數個子圖形，使得合併所有子圖形的解即可得到該圖形的解，我們再利用貪婪法來發現每一個子圖形的解；我們能顯示除了少數特殊的圖形外，利用貪婪法均可得到每一個子圖形的最佳解。這個演算法已利用測試電路加以驗證，實驗的結果也證實了這個演算法的有效性。

　　因為一個可規劃邏輯陣列內部所有的繞線資源是有限的，繞線度的最佳化就成為映射技術演算法中最重要的目標之一；為了最佳化繞線度，我們提出了一個內部連接總數最小化的映射技術演算法。首先，利用最小切割演算法切割代表布林網路的圖形成數個叢集，並使所有叢集間的內部連接總數最小化，配對的技術接著被用來合併數個叢集成一個大叢集，以更進一步減少所需的內部連接總數。根據測試電路的實驗，這個演算法比其他已發表的查表式可規劃邏輯陣列的映射技術具有更好的繞線度。

　　一個異質性的可規劃邏輯陣列可以是一個不同大小的同質性查表陣列，也可以是一個實體的異質查表陣列，明顯的，對於各種不同的目標，異質性的可規劃邏輯陣列將比同質性的可規劃邏輯陣列對設計者而言，具有更大的設計空間，因此，在這篇論文中，我們針對異質性的可規劃邏輯陣列的架構提出一個映射技術的演算法；首先，針對各種不同的目標，映射技術的問題被轉換成網路流量的問題，然後，我們提出以最小成本，最大流量演算法為基礎，選擇一組適當的查表的演算法來求解這個網路流量的問題；除此之外，查表數及包含查表和繞線面積最小化的兩個最佳化目標也被提出來討論。依據各種不同異質性的可規劃邏輯陣列架構的實驗結果，這個演算法產生令人滿意的成果。

　　The increasing popularity of the field programmable gate array (FPGA) technology has generated a great deal of interest in the algorithmic study and tool development for FPGA specific design automation problems. The most widely used FPGAs are LUT based FPGAs, in which the basic logic element is a k-input lookup table (LUT) that can implement any Boolean function of up to k variables. This unique feature of the LUT has brought new challenges to technology mapping. This dissertation studies the technology mapping problem for LUT-based FPGAs.

　　We first present problem formulations for various optimization objectives such as area and routability. And then efficient algorithms that focus on the given objectives are presented. The technology mapping algorithms in this dissertation is divided into three categories: 1) Minimizing area for homogeneous FPGAs, 2) Maximizing routability for homogeneous FPGAs, and 3) Optimizing area for heterogeneous FPGAs

　　Minimum area is one of the important objectives in technology mapping for lookup table-based FPGAs. It has been proven that the problem is NP-complete. This dissertation presents a polynomial time algorithm which can run in O(n3) time to generate a solution where n is the total number of gates in the circuit. The proposed algorithm partitions the graph representing the given circuit into subgraphs such that the solution can be obtained by merging the subgraph solutions. The greedy technique is then used to find the solution for each subgraph. It is shown that except for some cases the greedy method can find an optimal solution of a given problem. We have tested our algorithm on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.

　　Since interconnections in an FPGA must be accomplished with limited routing resources, routability is the most important objective in a technology mapping algorithm. To optimize routability, the goal of the presented algorithm is the production of a design with a minimum interconnection. The Min-cut algorithm is first used to partition a graph representing a Boolean network into clusters so that the total number of interconnections between clusters is minimum. To decrease further the number of interconnections needed, clusters are then merged into larger clusters by a pairing technique. This algorithm has been tested on the MCNC benchmark circuits. Compared with other LUT-based FPGA mapping algorithms, the algorithm produces better routability characteristics.

　　A heterogeneous FPGA provides an array of homogeneous LUTs of different sizes or an array of physically heterogeneous LUTs. It has been shown that the heterogeneous FPGA leads to the attainment of various objectives. In this dissertation, a technology mapping algorithm is proposed for heterogeneous FPGAs. The technology mapping problem is formulated first as a flow network problem. An algorithm based on the min-cost max-flow algorithm is then presented to select a proper set of feasible LUTs for various objectives. Finally, two objectives, the minimum number of LUTs and the total area composed of the LUTs and routing area, are discussed. This algorithm has been tested on the MCNC benchmark circuits. According to the experimental results, the proposed algorithm generates favorable results for various FPGA architectures.

[1] Xilinx, “The Programmable Logic Data Book,” Xilinx Inc., San Jose, CA, 1997.

[2] Lucent Technologies, “ORCA OR2C-A/OR2T-A Series FPGAs Data Sheet,” Lucent Technologies Inc., Allentown, PA, 1996.

[3] R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Improved Logic Synthesis Algorithms for Table Look Up Architectures,” Proc. IEEE International Conf. Computer-aided Design, pp. 564-567, Nov.1991.

[4] Y. T. Lai, M. Pedram, and S. B. K. Vrudhula, “BDD Based Decomposition of Logic Functions with Application to FPGA Synthesis,” Proc.30th Design Automation Conf., pp. 642-~647, June 1993.

[5] T, T. Hwang, R. M. Owens, and M. J. Irwin, “Logic Synthesis for Field-programmable Gate Arrays,” IEEE Trans. Computer-Aided Design, Vol. 13, pp. 1280-1287, Oct. 1994.

[6] B. Wurth, K. Eckl, and K. Antreich, “Functional Multiple-output Decomposition: Theory and an Implicit Algorithm,” Proc. 32nd Design Automation Conf., pp. 54-59, June 1995.

[7] H. Sawada, T. Suyama, and A. Nagoya, “Logic Synthesis for Look-up Table Based FPGA's Using Functional Decomposition and Support Minimization,” Proc. Int. Conf. Computer-Aided Design, pp. 353-358, Nov. 1995.

[8] W. Z. Shen, J. D. Huang, and S. M. Chao, “Lambda Set Selection in Roth-Karp Decomposition for LUT-based FPGA Technology Mapping,” Proc. 32nd Design Automation Conf., pp. 65-69, June 1995.

[9] J. D. Huang, J. Y. Jou, and W. Z. Shen, “Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture,” Proc. Int. Conf. Computer-Aided Design, pp. 359-363, Nov. 1995.

[10] R. M. Karp and J. P. Roth, “Minimization over Boolean Graph,” IBM J. Res. And Development, April 1962.

[11] Amir H. Farrahi and Majid Sarrafzadeh, “Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp.1319-1332 Vol.13 No. 11, November 1994.

[12] Shujian Zhang, D. Michael Miller, and Jon C. Muzio, “Notes on Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp.1588-1590 Vol.15 No. 12, December 1996.

[13] J. Francis, J. Rose, and K. Chungm “Chortle: A Technology Mapping Program for Lookup Table-Based Field Programmable Gate Arrays,” Proc, 27th ACM/IEEE Design Automation Conference, pp. 613-619, June 1990.

[14] J. Francis, J. Rose, and Z. Vranesic, “Chortle-crf: Fast Technology Mapping for Lookup Table-Based FPGAs,” Proc, 28th ACM/IEEE Design Automation Conference, pp. 248-251, June 1991.

[15] R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Performance Directed Synthesis for Table Look Up Programmable Gate Arrays,” Proc. IEEE International Conf. Computer Aided Design, PP. 572-575, Nov. 1991.

[16] R. J. Francis, J. Rose, and Z. Vranesic, “Technology Mapping for Lookup Table-Based FPGAs for Performance,” Proc. IEEE International Conf. Computer Aided Design, PP. 568-571, Nov. 1991.

[17] J. Cong, Y. Ding, A. Kahug, and P. Trajmar, “An Improved Graph-Based FPGA Technology Mapping Algorithm for Delay Optimization,” Proc. ICCD, pp. 154-158, Oct.1992.

[18] J. Cong, Y. Ding, “FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-table Based FPGA Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp. 1-11 Vol.13 No. 1, January 1994.

[19] J. Cong. And Y. Ding, “On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping,” IEEE Transactions on VLSI Systems, pp. 137-148 Vol.2 No. 2, June 1994.

[20] N. B. Bhat, and D. D. Hill, “Routable Technology Mapping for LUT FPGAs,” Proc. ICCD, pp. 95-98, Oct. 1992.

[21] Martine Schlag, Jackson Kong, and Pak K. Chan, “Routability-Driven Technology Mapping for Lookup Table-Based FPGAs”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp.13-26 Vol.13 No. 1, January 1994.

[22] Chau-Shen Chen, Yu-Wen Tsay, TingTing Hwang, Allen C. H. Wu and Youn-Long Lin, “Combining Technology Mapping and Placement for Delay-Minimization in FPGA Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp. 1076-1084 Vol.14 No. 9, September 1995.

[23] N. B. Bhat, and D. D. Hill, “Routable Technology Mapping for LUT FPGAs,” Proc. ICCD, pp. 95-98, Oct. 1992.

[24] Aiguo Lu, Erik Dagless, and Jonathan Saul, “DART: Delay and Routability Driven Technology Mapping for LUT Based FPGAs”, Proc. ICCD, pp. 409-414, Oct. 1995.

[25] J. Cong and Y. Ding, “Combinational Logic Synthesis for LUT Based Field Programmable Gate Arrays,” ACM Trans. Design Automation Electron. Syst., vol. 1, pp. 145-204, Apr. 1996.

[26] J. He and J. Rose, “Technology Mapping for Heterogeneous FPGAs,” Proc. ACM Int. Workshop on Field Programmable Gate Arrays, Feb. 1994.

[27] J. Cong and S. Xu, “Delay-Optimal Technology Mapping for FPGAs with Heterogeneous LUTs,” Proc. 35th ACM/IEEE Design Automation Conf., pp. 704-707 June 1998.

[28] M. R. Korupolu, K. K. Lee, D. F. Wong, “Exact Tree-based FPGA Technology Mapping for Logic Blocks with Independent LUTs,” Proc. 35th ACM/IEEE Design Automation Conf., pp. 708-711 June 1998.

[29] Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin, “Network Flows Theory, Algorithms, and Applications,” Prentice-Hall International Editions, 1993.

[30] James R. Evans and Edward Minieka, “Optimization Algorithms for Networks and Graphs,” Marcel Dekker, INC., 1992.

[31] Michael R. Garey and David S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” New York, W. H. Freeman, 1979.

[32] M. Fiducciz and R. M. Matheyses, “A Linear Time Heuristic for Improving Network partitions,” Proc. 19th Design Automation Conference, 1982, pp. 175-181.

[33] B. Krishnamurthy “An Improved Min-Cut Algorithm for Partitioning VLSI Networks”, IEEE Transactions on Computer, vol. C-33 pp.438-446, May 1984.

[34] B. M. Kerninghan and S. Lin, “A Efficient Heuristic Procedure for Partitioning Graph,” Bell Syst. Tech. J., vol. 49, no. 2, pp. 297-307, Feb. 1970.

[35] V. Betz and J. Rose, “VPR: A New Packing, Placement and Routing Tool for FPGA Research,” 7th International Workshop on Field-Programmable Logic, Londan, August 1997, pp. 213-222.

[36] Rose, J. S., Francis, R. J., Lewis, D., and Chow, P., “Architecture of Programmable Gate Array: The Effect of Logic Block Functionality on Area Efficiency,” IEEE Journal of Solid State Circuits, Vol. 25, No 5, Oct. 1990, pp. 1217-1225.

[37] Sedgewick R., “Algorithm,” Addison Wesley Publishing Company, Inc. 1988.

[38] Deo N., “Graph Theory with Applications to Engineering and Computer Science,” Prentice-Hall International Editions, Inc. 1974.

[39] Evans, J. R., and Minieka, E., “Optimization Algorithms for Networks and Graphs,” Marcel Dekker, Inc., 1992.