Proceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No.99CB37040)
Download PDF

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 can be mapped in O(C?n2b-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(n5) 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(n3) 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.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!