Exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs

We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n^2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n⁵) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n³) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.