TY - JOUR

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

AU - Thakur, Shashidhar

AU - Wong, D.F.

N1 - Funding Information:
This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by a DAC Design Automation Scholarship, a Schlumberger Graduate Fellowship, and by a grant from the AT&T Bell Laboratories.
Publisher Copyright:
© 1996 Published by Elsevier B.V.

PY - 1996/7

Y1 - 1996/7

N2 - 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 computes the same mapping solution as our algorithm. 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.

AB - 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 computes the same mapping solution as our algorithm. 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.

UR - http://www.scopus.com/inward/record.url?scp=0030192760&partnerID=8YFLogxK

U2 - 10.1016/0167-9260(96)00004-1

DO - 10.1016/0167-9260(96)00004-1

M3 - Journal article

AN - SCOPUS:0030192760

SN - 0167-9260

VL - 20

SP - 287

EP - 302

JO - Integration, the VLSI Journal

JF - Integration, the VLSI Journal

IS - 3

ER -