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:
We would like to thank Eugene Ding and Jason Cong for suggesting ways to simplify the presentation of the proofs in this paper and for observing that the simultaneous area and delay minimum mapping solution for K-exact networks is, in fact, unique. 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. We thank these agencies for the support.

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

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

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

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

M3 - Article

AN - SCOPUS:0030192760

VL - 20

SP - 287

EP - 302

JO - Integration, the VLSI Journal

JF - Integration, the VLSI Journal

SN - 0167-9260

IS - 3

ER -