臺灣博碩士論文加值系統

　　藉由可規劃邏輯陣列技術在電路設計自動化技術的盛行，其相關演算法的研究和設計工具的發展已經成為在晶片設計技術上一個重要的課題。查表式可規劃邏輯陣列是可規劃邏輯陣列中最廣泛被應用的架構，其基本的邏輯元素是利用一個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 Introduction 1
　　1.1 Field Programmable Gate Array (FPGA) 2
　　1.2 Lookup Table Based FPGAs 2
　　1.3 The CAD System for LUT-Based FPGAs 4
　　1.4 Technology Mapping Algorithms 8
　　1.5 Organization of Dissertation 11

2 Terminology and Problem Formulation 15
　　2.1 Terminology 15
　　2.2 Problem Formulation 18

3 A Technology Mapping Algorithm for Finding the
Minimal Area 21
　　3.1 Outline of the Mapping Algorithm 21
　　3.2 Partitioning the Given DAG into Primary Blocks 23
　　3.3 The Mapping Solution for a Primary Block 28

4 Routability Driven Technology Mapping Algorithms 40
　　4.1 Partitioning Network 41
　　　　4.1.1 Partitioning Algorithm 41
　　　　4.1.2 Evaluation Method for Selecting Vertices 45
　　4.2 Selecting Pairs 49

5 A Technology Mapping Algorithm for Heterogeneous FPGAs 55
　　5.1 Formulating Technology Mapping Problem as a Flow Network Problem 56
　　5.2 An Algorithm for Finding the Min-cost Max-flow as a Mapping Solution 59
　　5.3 An Algorithm to Enumerate All Feasible Cones 62
　　5.4 The Optimization Objectives 65
　　　　5.4.1 Finding the Mapping with Minimum Number of LUTs 65
　　　　5.4.2 Finding the Mapping with Minimum Area 66

6 Experimental Results 69
　　6.1 Decomposition Step 69
　　6.2 Mapping for Minimal Area 74
　　6.3 Mapping for Optimizing Routability 77
　　6.4 Mapping for Heterogeneous FPGAs 83

7 Conclusions 89

References 91


List of Tables
1.1 A truth table for f = A¢BC+AB¢C¢ 4
6.1 Performance of the proposed algorithm 75
6.2 Comparison of the numbers of LUTs with Chortle-crf and MIS-pga 76
6.3 Comparison of the numbers of interconnections and tracks required with
Chortle-crf, Flow-map, and the proposed system 80
6.4 Comparison of the number of CLBs and depth with Chortle-crf,
Flow-map, and the proposed system 81
6.5 Comparison of pins-per-CLB (P/C) 82
6.6 Comparison of the numbers of CLBs 84
6.7 Comparison of Area and CPU Time on XC4000 series FPGAs 86
6.8 Comparison of Area on a Given Heterogeneous FPGA 87


List of Figures

1.1 A conceptual diagram of a typical FPGA 3
1.2 A Typical CAD System for LUT-Based FPGAs 7
1.3 Three mappings of a given circuit with various FPGAs 13
1.4 Combinational Models of Various LUT-Based FPGA CLBs 14
2.1 a) A combinational circuit;
b) The DAG corresponding to the circuit in (a) 16
2.2 Two different mappings of a given DAG
a) A given DAG
b) A mapping of the DAG in (a)
c) A mapping with minimal interconnection of the DAG in (a) 20
3.1 Four cases in which a SO cone is not totally included in a primary block 25
3.2 The result of labeling vertices of the given graph 27
3.3 a) A given DAG ; b) The new DAG after selecting a critical
floor cone Cv as a cone in the optimal mapping solution (k =5) 30
3.4 Transformation of an optimal mapping solution such that every feasible
floor cone is covered with a cone in this solution 31
3.5 The case in which every floor cone tipped at a vertex in Ui is feasible 32
3.6 Transformation of an optimal mapping solution such that the prime cone
whose fan-out vertex is a critical leading vertex in this solution 34
3.7 An example of finding an optimal mapping solution by the greedy
method (k =5) 35
3.8 An example of selecting the prime cone as a cone in the solution (k =5) 36
4.1 Cell gains 42
4.2 Bucket list structure 43
4.3 Critical nets 43
4.4 Determining a cut for gi2 46
4.5 Determining a cut for gi3 47
4.6 A partition tree 50
4.7 Selecting pairs 54
5.1 a) A given DAG; b) The flow network constructed from (a) 58
5.2 A min-cost max-flow 60
5.3 The logic block model 67
5.4 A model for estimating the routing area 68
6.1 MISII script 70
6.2 Decomposition of a multi-input gate 73
6.3 A circuit routing succeeded by the VPR tool 77
6.4 Flowchart of experimental procedure 78
6.5 The impact of the routing area 88

[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.