Abstract
We address the technology mapping problem for lookup table FPGAs. The area minimization problem for mapping Kbounded networks, consisting of nodes with at most K inputs using Kinput lookup tables is known to be NPcomplete 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 flowmap algorithm, for arbitrary values of K. We study the class of Kbounded networks, where all nodes have exactly K inputs. We call such networks Kexact. 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 Kinput lookup tables. We also show that the flowmap algorithm minimizes the area of the mapped network as well, for Kexact networks. We then show that for K = 2 the mapping solution for a 2bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2input lookup tables can be solved in polynomial time, resolving an open problem.
Original language  English 

Title of host publication  1995 IEEE International Conference on Computer Design, ICCD 1995: VLSI in Computers and Processors 
Publisher  IEEE 
Pages  402408 
Number of pages  7 
ISBN (Print)  0818671653 
DOIs  
Publication status  Published  Oct 1995 
Event  1995 IEEE International Conference on Computer Design, ICCD 1995: VLSI in Computers and Processors  Austin, United States Duration: 2 Oct 1995 → 4 Oct 1995 https://ieeexplore.ieee.org/xpl/conhome/4053/proceeding (Link to conference proceedings) 
Publication series
Name  Proceedings of 1995 IEEE International Conference on Computer Design, ICCD 1995: VLSI in Computers and Processors 

Conference
Conference  1995 IEEE International Conference on Computer Design, ICCD 1995: VLSI in Computers and Processors 

Country/Territory  United States 
City  Austin 
Period  2/10/95 → 4/10/95 
Internet address 

Scopus Subject Areas
 Hardware and Architecture
 Electrical and Electronic Engineering