由於現場可規劃邏輯陣列具有可讓使用者自行規劃設計、快速的製程及較低的生產成本的優點，現場可規劃邏輯陣列已經成為最受歡迎的超大型積體電路設計技術。
本論文主要是探討當以現場可規劃邏輯陣列實現組合邏輯電路時如何提高技術應對的可繞度。為了降低接腳與邏輯區塊的比例，我們首先減少接腳的總數。然後，在不增加接腳數目的情況下，進一步去減少所需使用邏輯區塊數。
我們的演算法可分成四個步驟，包括使用角錐結構分割電路，找出所有可實現的邏輯區塊，使用覆蓋節點的技巧將所有的節點指定到適合的區塊之中，及減少使用的邏輯區塊。實驗的結果驗證了我們所使用的演算法是相當有效的。

Because Field Programmable Gate Array (FPGA) has the features of user programmable, short turn-around time and low manufacturing cost, it is most popular technique for VLSI design.
The thesis focuses on increasing routability of technology mapping for Lookup-Table based FPGA to implement a combinational logic circuit. To reduce the of pins-of-cell-- ratio, we first minimize the total number of pins among LUTs. Next, the number of LUTs is further reduced when the number of pins does not increase.
Our algorithm is divided four steps: 1) using cone structure to partition the DAG, 2) using polynomial time algorithm to generate all feasible cones with input number no more than K, 3) using vertex cover based techniques to assign all gates to the feasible cones, and 4) reducing the numbers of LUTs. Experimental results for the benchmark circuits demonstrate the effectiveness of our algorithm.

CHAPTER 1 INTRODUCTION
CHAPTER 2 Preliminaries and Problem Formulation
CHAPTER 3 Technology Mapping
CHAPTER 4 Experimental RESULTS
CHAPTER 5 CONCLUSIONS
APPENDIX

[1] H. Hsieh, et. al “A 9000-Gate User-Programmable Gate
Arrays,” Proc. 1988 CICC, May 1988, pp. 15.3.1-
15.3.7.
[2] H. Hsieh, “Third-generation architecture boosts speed and
density of field-programmable gate array,” Proc. 1990
CICC, pp. 31.2.1-31.2.7, May 1990.
[3] J. Rose, R. J. Francis, P. Chow, and D. Lewis, “The Effect
of Logic Block Complexity on Area of Programmable Gate
Arrays”, Proc. 1989 CICC, pp. 5.3.1-5.3.5, May 1989.
[4] J. Rose, R. J. Francis, D. Lewis, and P. Chow,
“Architecture of Field-Programmable Gate Array: The effect
of Logic Block Functionality of Area Efficiency,” IEEE
Journal of Solid-State Circuits, Vol. 25, No. 5, Oct. 1990,
pp. 1217-1225.
[5] J. Rose and S. Brown, “Flexibility of interconnection
structures for field-programmable gate array,” ISSC, Vol.
26, pp. 277-282, Mar. 1991.
[6] S. Singh, J. Rose, P. Chow, D. Lewis, “The Effect of Logic
Block Architecture on FPGA Performance,” IEEE Journal of
Soild-State Circuits, Vol. 27 No. 3, March 1992, pp.281-287.
[7] P. T. Wang, Y. T, Lai, and K. N. Chen, “A high performance
FPGA with hierarchical interconnection structure,”
ISCAS’94, pp. 4.239-4.242.
[8] The programmable gate array. Xilinx Co., 1992.
[9] 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.
[10] R. M. Karp and J. P. Roth, “Minimization over Boolean
graphs,” in IBM J. Res. and Development, Apr. 1962.
[11] 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.
[12] 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.
[13] D. Filo, J. C. Yang, F. Mailhot, and G. De Micheli,
“Technology Mapping for a Two-output RAM-based field
Programmable Gate Array,” Proc. EDAC, pp 534-538, Feb.
1991.
[14] N. Woo, “A Heuristic Method for FPGA Technology Mapping
Based on Edge Visibility,” 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. 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.
[17] 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.
[18] 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.
[19] 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.
[20] J. Cong. And Y. Ding, “On area/depth trade-off in LUT-
Based FPGA technology mapping,” in Proc. ACM/IEEE Design
Automation Conf.1993, pp. 213-218.
[21] 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.
[22] S. Trimberger, and M. R. Chene, “Placement-based
partitioning for lookup-table-based FPGAs”, Proc. ICCD,
pp. 86-90, Oct. 1992.
[23] Martine Schlag, Jackson Kong, and Pak K. Chan,
“Routability-Driven Technology Mapping for Lookup Table-
Based FPGA’s”, IEEE Transactions on Computer-Aided
Design of Integrated Circuits and System pp.13-26 Vol.13
No. 1, January 1994.
[24] N. Togawa, M. Sato and T. Ohtsuki, “Maple: A Simultaneous
Technology Mapping Placement, and Global Routing Algorithm
for Field-Programmable Gate Arrays,” Proc. ICCAD-94, pp.
156-163, 1994.
[25] W. Carter, K. Duong, R. H. Freeman, H. Hsieh, J. Y. Ja, J.
E. Mahoney, L. T. Ngo, and S. L. Sze, “A User
Programmable Reconfigurable Gate Array”, in Proceedings
1986 Custom Integrated Circuits Conference, May 1987, pp.
515-521.
[26] A. El Gamal, “Two-Dimensional Stochastic Model for
Interconnections in Master Slice Integrated Circuits”,
IEEE Transactions on Circuits and System, pp.127-138 Vol.
28 No. 2, February1981.
[27] J. R. Ford and D. R. Fulkerson, Flows in Networks.
Princeton, NJ: Princeton University, 1962.
[28] 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.