DELAY OPTIMAL COMPRESSOR TREE SYNTHESIS FOR LUT-BASED FPGAS

Abstract

A compressor tree synthesis algorithm, named DOCT, which guarantees the delay optimal implementation in 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. The DOCT reduces the depth of the compressor tree and the number of LUTs based on the modern 8-input LUT-based FPGA architecture.