INPUT-DRIVEN PARTITIONING METHODS AND APPLICATION TO SYNTHESIS ON TABLE-LOOKUP-BASED FPGAS

This paper proposes a synthesis approach for a set of Boolean functions on table-lookup-based field programmable gate arrays (Xilinx series 3000 and 4000). Synthesis is considered as a global problem and, therefore, includes suitable factorization techniques as well as decomposition methods relying on the factored form. The factorization step looks for lexicographical expressions of Boolean functions. This approach defines and respects an input order during factorization and aims to prepare structured, layered logic cones that enter inputs in the same order for all the functions. The expected benefits are threefold: a limitation of the number of levels in the factored form, thus preparing a good critical path optimization phase; a decreased wiring complexity, as this is an important point for the target devices; and a good clustering capability of the subfunctions into the physical cells. The basic features of such an approach are stated in the second section. As these devices imply a decomposition of the functions into subfunctions of,no more than k variables, the ordered input set is partitioned into substrings, or slices of k variables, and an ''input-driven partitioning,'' explained in Section III, isolates the logic portions depending on a given slice. Some trade-offs between a strict input-driven decomposition and a maximal cell filling strategy are presented in the same section. Section IV applies this approach to practical targets, the Xilinx XC3000 and XC4000 series. Decomposition techniques both for area and speed optimization are detailed and compared to all available results.