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

K. K. Lee, D. F. Wong

Research output: Contribution to conferencePaper

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·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.

Original languageEnglish (US)
Pages216-221
Number of pages6
StatePublished - Dec 1 1999
Externally publishedYes
EventInternational Conference on Computer Design (ICCD'99) - Austin, TX, USA
Duration: Oct 10 1999Oct 13 1999

Other

OtherInternational Conference on Computer Design (ICCD'99)
CityAustin, TX, USA
Period10/10/9910/13/99

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs'. Together they form a unique fingerprint.

  • Cite this

    Lee, K. K., & Wong, D. F. (1999). Exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs. 216-221. Paper presented at International Conference on Computer Design (ICCD'99), Austin, TX, USA, .