Abstract
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^{2b1}) 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^{5}) 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 nontrivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n^{3}) algorithm. The mapping results are comparable to the best NPhard 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.
Original language  English 

Title of host publication  Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999 
Publisher  IEEE 
Pages  216221 
Number of pages  6 
ISBN (Print)  076950406X 
DOIs  
Publication status  Published  10 Oct 1999 
Event  17th IEEE International Conference on Computer Design, ICCD 1999  Austin, United States Duration: 10 Oct 1999 → 13 Oct 1999 https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings) 
Publication series
Name  Proceedings  IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors 

ISSN (Print)  10636404 
ISSN (Electronic)  25766996 
Conference
Conference  17th IEEE International Conference on Computer Design, ICCD 1999 

Country/Territory  United States 
City  Austin 
Period  10/10/99 → 13/10/99 
Internet address 

Scopus Subject Areas
 Hardware and Architecture
 Electrical and Electronic Engineering