應用於查找表式場域可程式化閘陣列之壓縮樹延遲最佳化合成演算法

Delay Optimal Compressor Tree Synthesis for LUT-Based FPGAs

呂智宏(Jhih-Hong Lu)

指導教授 ： 周景揚 ； 黃俊達

國立交通大學/電機學院/電子工程系所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00430

摘要

在以查找表(Lookup table)為基礎的可程式邏輯陣列(FPGA)架構下，我們提出一個壓縮樹合成演算法(DOCT)。此演算法的主要目的是為了達到延遲最佳化。首先，在給定查找表的輸入限制之下，此演算法會先產生一組相對應的元素樣本集合，再藉著這些元素樣本，用整數線性規劃法(ILP)去合成出延遲最佳化的壓縮樹。並且在不失去延遲最佳化的特性下，更進一步用一套後製程序去降低壓縮數所需要的面積。在實驗部分，我們把結果跟另一個演算法(GPC)做比較。結果顯示，在現今的製程技術下，我們的延遲平均降低32%，而面積平均降低21%

關鍵字

壓縮樹 ； 延遲最佳化 ； 合成 ； 查找表式場域可程式化閘陣列 ； 整數線性規劃法

並列摘要

In this thesis, we present a compressor tree synthesis algorithm, named DOCT, which guarantees the delay optimal implementation in lookup-table (LUT) based FPGAs. Given a targeted K-input LUT architecture, DOCT firstly derives a finite set of prime patterns as essential building blocks. Then, it shows that a delay optimal compressor tree can always be constructed by those derived prime patterns via integer linear programming (ILP). Without loss of delay optimality, a post-processing procedure is invoked to reduce the number of demanded LUTs for the generated compressor tree design. DOCT has been evaluated over a broad set of benchmark circuits. Compared to the previous heuristic approach, the experimental results show that DOCT reduces the depth of the compressor tree by 32%, and the number of LUTs by 21% on average based on the modern 6-input LUT-based FPGA architecture.

並列關鍵字

compressor tree ； delay optimal ； synthesis ； LUT-based FPGA ； integer linear programming

參考文獻

[7] S. Mirzaei, A. Hosangadi, and R. Kastner, “FPGA implementation of high speed FIR filters using add and shift method,” International Conference on Computer Design, October 2006, pp. 308–313.

[9] C.-Y. Chen, S.-Y. Chien, Y.-W. Huang, T.-C. Chen, T.-C. Wang, and L.-G. Chen, “Analysis and architecture design of variable block-size motion estimation for H.264/AVC,” IEEE Transaction on Circuits and Systems, vol. 53, no 2, pp. 578-583, February 2006.

[11] C. S. Wallace, “A suggestion for a fast multiplier,” IEEE Transaction on Electronic computers, vol. 13, no. 1, pp. 14–17, February 1964.

[12] V. G. Oklobdzija, D. Villeger, and S. S. Liu, “A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach,” IEEE Transaction on Computers, vol. 45, no. 3, pp. 294–306, March 1996.

[15] H. Parandeh-Afshar, P. Brisk, and P. Ienne, “Improving synthesis of compressor trees on FPGAs via integer linear programming,” Design Automation and Test in Europe, March 2008, pp. 1256–1261.