Simultaneous area and delay minimum K-LUT mapping for K-exact networks

Shashidhar Thakur, D. F. Wong

Research output: Contribution to conferencePaper

Abstract

We address the technology mapping problem for lookup table FPGAs. The area minimization problem for mapping K-bounded networks, consisting of nodes with at most K inputs using K-input lookup tables is known to be NP-complete for K ≥ 5. The complexity was unknown for K = 2, 3, and 4. The corresponding delay minimization problem (under the constant delay model) was solved in polynomial time by the flow-map algorithm, for arbitrary values of K. We study the class of K-bounded networks, where all nodes have exactly K inputs. We call such networks K-exact. We give a characterization of mapping solutions for such networks. This leads to a polynomial time algorithm for computing the simultaneous area and delay minimum mapping for such networks using K-input lookup tables. We also show that the flow-map algorithm minimizes the area of the mapped network as well, for K-exact networks. We then show that for K = 2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be solved in polynomial time, resolving an open problem.

Original languageEnglish (US)
Pages402-408
Number of pages7
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE International Conference on Computer Design: VLSI in Computers & Processors - Austin, TX, USA
Duration: Oct 2 1995Oct 4 1995

Other

OtherProceedings of the 1995 IEEE International Conference on Computer Design: VLSI in Computers & Processors
CityAustin, TX, USA
Period10/2/9510/4/95

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Simultaneous area and delay minimum K-LUT mapping for K-exact networks'. Together they form a unique fingerprint.

  • Cite this

    Thakur, S., & Wong, D. F. (1995). Simultaneous area and delay minimum K-LUT mapping for K-exact networks. 402-408. Paper presented at Proceedings of the 1995 IEEE International Conference on Computer Design: VLSI in Computers & Processors, Austin, TX, USA, .