適性邏輯模組式可程式化邏輯陣列之映成技術

ALMmap: Technology mapping for FPGAs with Adaptive Logic Modules

梁有毅(Yu-Yi Liang)

指導教授 ： 麥偉基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00487

摘要

在於可程式化邏輯陣列的設計流程中技術映射是相當關鍵的一個步驟，他不僅影響效能和功率的消耗也影響繞線的難易度。而現今由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.

並列關鍵字

FPGA ； Adaptive Logic Modules ； Technology Mapping

參考文獻

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

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