SIMULTANEOUS AREA AND DELAY MINIMUM K-LUT MAPPING FOR K-EXACT NETWORKS

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 greater than or equal to 5. The complexity was unknown for K = 2, 3, and 4. The corresponding delay minimization pro blem (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 solution s for such networks. This leads to a polynomial time algorithm for com puting the simultaneous area and delay minimum mapping for such networ ks using K-input lookup tables. We also show that the flow-map algorit hm computes the same mapping solution as our algorithm. We then show t hat for K = 2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that o f a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be s olved in polynomial time, resolving an open problem.