臺灣博碩士論文加值系統

在於可程式化邏輯陣列的設計流程中技術映射是相當關鍵的一個步驟，他不僅影響效能和功率的消耗也影響繞線的難易度。而現今由Altera所生產的可程式化邏輯陣列使用了適性邏輯模組(ALM)的結構來提升整體的效能[1]。適性邏輯模組可用來實作單一的布林涵式或是可以拆解成兩個比較小的查著表(LUT)。在這篇論文中，我們一開始先提出一個證明來證明在適性邏輯模組式可程式化邏輯陣列上作面積最佳化的技術映射是一個NP-Hard的問題，接著我們提出一個演算法來解決這樣的問題同時必須符合深度的條件限制。我們也修改了傳統以分割為基礎的反覆式技術映射流程，我們將傳統流程中的切割選擇、映成和面積流修正等步驟有效的合成單一步驟稱作「於深度限制下動態修正面積流的映成過程」。除此之外我們提出了一個全新的流程來產生切割集合並使用面積流和邊流來有效的減少我們最後的適性邏輯模組的數量。實驗結果顯示出我們的演算法跟classical mapper[2]和WireMap[3]比較起來我們所使用到的適性邏輯模組數量分別減少了28.3%和14.1%。而我們所提出的「於深度限制下動態修正面積流的映成過程」這個步驟對於傳統查著表式的可程式化邏輯陣列也相當有效，實驗結果顯示出當我們使用6輸入查著表來做技術映射時，比起WireMap我們的演算法可以減少5.5%的查著表使用量。

Technology mapping is a critical step in the FPGA design flow that aects performance, power consumption, and routability. Moderm FPGAs like Altera’s Stratix series has adopted the adaptive logic module (ALM) structure due to its potential performance and area advantages[1]. An ALM can implement a single logic function or fractured into two smaller LUTs. In this work, we first prove that technology mapping for ALM minimization is a NP-Hard problem. Then we propose an ALM mapping algorithm, ALMmap, for area minimization with bounded depth. We revamp the traditional iterative cut-based mapping flow and introduce a procedure for bounded depth mapping generation with dynamic area recovery that eectively combines cut selection, mapping and area recovery together. In addition, we introduce a new procedure for cut set determination for ALM minimization under depth constraint. The notion of area flow which has been used successfully for cut selection to reduce LUT count is revised for cut selection to reduce ALM count. ALMmap obtains depth optimal solutions that are 28.3% and 14.1%smaller on average than those produced by a classical mapper[2] and WireMap[3], respectively. The new procedure for bounded depth mapping generation with dynamic area recovery is also effective for traditional LUT mapping and led to 5.5% LUT reduction in traditional 6-LUT mapping compared to WireMap.

Acknowledgement i
Abstract ii
1 Introduction 1
2 Terminologies and Problem Formulation. . . . . . . . . 4
2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 5
3 NP-Hardness of ALM Minimization Mapping. . . . . . . . . 6
4 Algorithm 11
4.1 Review of Typical Iterative Cut-Based Mapping . . . . 12
4.1.1 Cut Enumeration . . . . . . . . . . . . . . . . . . . . . . . 12
4.1.2 Compute Area Flow . . . . . . . . . . . . . . . . . 12
4.1.3 Reverse Topological Order Mapping . . . . . . . . . 13
4.1.4 Area Recovery . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Revamped Flow for Bounded Depth K-LUT Minimization Mapping . . . . . . . . . . . . . . . . . . . . . .. . . .15
4.2.1 Compute Depth . . . . . . . . . . . . . . . . . . . 16
4.2.2 Select Initial Best Cuts . . . . . . . . . . . . . 16
4.2.3 Bounded Depth Mapping Generation with Dynamic Area Recovery . . . . . . . . . . . . . . . . . . . . . . . . .17
4.3 ALMmap . . . . . . . . . . . . . . . . . . . . . . . . . .19
4.3.1 Cut Set Determination for ALM Minimization with Depth Constraint . . . . . . . . . . . . . . . . . . . . . . . .20
5 Experimental Results . . . . . . . . . . . . . . . . . .23
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . 29
Reference . . . . . . . . . . . . . . . . . . . . . . . .30

[1] M. Hutton, J. Schleicher, D. Lewis, B. Pedersen, R. Yuan, S. Kaptanoglu, G. Baeckler, B. Ratchev, K. Padalia, M. Bourgeault, A. Lee, H. Kim and R. Saini1, “Improving
FPGA Performance and Area Using an Adaptive Logic Module,” In International Conference on Field Programmable Logic and Applications, pp. 135-144, 2004
[2] A. Mishchenko, S. Chatterjee, and R. Brayton, “Improvements to technology mapping for LUT-based FPGAs,” In Proceedings of International Symposium on Field Programmable Gate Arrays, pp. 41-49, 2006
[3] S. Jang, B. Chan, K. Chung, and A. Mishchenko, “WireMap: FPGA technology mapping for improved routability and enhanced LUT merging,” ACM Transactions on Reconfigurable Technology and Systems (TRETS), Article 14, Vol. 2(2), June 2009.
[4] J. Cong, C. Wu, and Y. Ding, “Cut ranking and pruning: Enabling a general and efficient FPGA mapping solution,” In Proceedings of International Symposium on Field Programmable Gate Arrays, pp. 25-39, 1999
[5] A. H. Farrahi and M. Sarrafzadeh, “Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping,” IEEE Transactions on Computer-Aided Design of Iintegrated Circuits and Systems, Vol. 13, No. 11, 1994.
[6] J. Cong, and 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 Systems, Vol. 13, No. 1, 1994.
[7] Y. Kukimoto, R. K. Brayton, and P. Sawkar, “Delay-optimal technology mapping by DAG covering,” In Proceedings of Design Automation Conference, pp. 348351, 1998.
[8] Altera, “Stratix III Device Family Architecture,”http://www.altera.com/products/devices/stratix-fpgas/stratixiii/overview/architecture/performance/st3-alm-structure.html
[9] H. Yang and D. F. Wong, “Edge-map:Optimal Performance Driven Technology Mapping for Iterative LUT based FPGA Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 150-155, 1994
[10] J. Cong and Y. Ding, “On Area/Depth Trade-o in LUT-Based FPGA Technology Mapping,” IEEE Transactions on Very Large Scale Integration Systems, vol. 2, pp. 137-148, 1994
[11] J. Cong and Y. Hwang, “Simultaneous Depth and Area Minimization in LUT-Based FPGA Mapping,” In Proceedings of International Symposium on Field Programmable Gate Array, pp. 68-74, 1995
[12] C. Legl. B.Wurth. and K. Eckl, “A Boolean Approach to Performance-Directed Technology Mapping for LUT-Based FPGA Designs,” In Proceedings of Design Automation Conference, vol. 2, pp. 730-733, 1996
[13] D. Chen and J. Cong, “DAOmap: A depth-optimal area optimization mapping algorithm for FPGA designs,” in Proceedings of International Conference on Computer-Aided Design, pp. 752-757,2004
[14] V. Manohararajah, S. D. Brown, and Z. G. Vranesic, “Heuristics for area minimization in LUT-based FPGA technology mapping,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 11, 2006
[15] Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification,”http://www.eecs.berkeley.edu/ alanmi/abc/
[16] A. Mishchenko, S. Cho, S. Chatterjee, and R. Brayton, “Combinational and sequential mapping with priority cuts,” in Proceedings of International Conference on Computer-Aided Design, pp.354-361, 2007
[17] E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli, “SIS: A System for Sequential Circuit Synthesis,” Memorandum No. UCB/ERL M92/41, Department of EECS. UC Berkeley, 1992