Realizing expression graphs using table-lookup FPGAs

The authors consider the problem of mapping an expression graph (which represents a combinational network) to a minimal number of programmable functional elements connected by a configurable network (e.g., Xilinx elements). Since each element can realize any function of a fixed arity, they look only at the topological aspect of the mapping, i.e., no algebraic (or other) simplifications are considered (this could have been done at the earlier stage which produced the expression itself). Two analytic results are presented: (1) trees (of arbitrary degree) can be mapped optimally in linear time to elements of four inputs and one output each; and (2) the problem becomes NP-complete for DAGs even if they have only one root and the maximal in-degree of nodes is three. The first result can be easily generalized to elements with any other fixed number of inputs (that is known a priori) and which are used uniformly in the circuit. In light of the second result, the authors present three heuristics for mapping DAGs to networks and discuss their performance both on the ISCAS benchmark and on randomly generated graphs