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

Abstract

在以查找表(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.