
Abstract
Field Programmable Gate Arrays (FPGAs) provide a new approach to Application
Specific Integrated Circuit (ASIC) implementation that features both large scale
integration and user programmability. The logic capacity of these devices is large
enough to make automated synthesis essential for the efficient design of FPGA circuits.
This thesis focuses on the class of FPGAs that use lookup tables (LUTs) to
implement combinational logic. A Kinput lookup table is a digital memory that can
implement any Boolean function of K variables. Lookup table circuits present new
challenges for logic synthesis, particularly technology mapping, which is the phase of
logic synthesis directly concerned with the selection of the circuit elements to implement
the final circuit. Conventional librarybased technology mapping has difficulty
with lookup table circuits because each lookup table can implement a large number
of different functions.
This thesis presents two new technology mapping algorithms that construct circuits of Kinput lookup tables from networks of ANDs, ORs and NOTs. The first algorithm, referred to as the area algorithm, minimizes the number of LUTs in the final circuit, and the second algorithm, referred to as the delay algorithm, minimizes the number of levels of LUTs. The key feature of both algorithms is the application of bin packing to the decomposition of nodes in the original network. The original network is first partitioned into a forest of trees, each of which is mapped separately. For each tree, the circuit constructed by the area algorithm is shown to be an optimal tree of LUTs for values of K <= 5 and the circuit constructed by the delay algorithm is an optimal tree of LUTs for values of K <= 6. Both algorithms also include optimizations that exploit reconvergent paths, and the replication of logic at fanout nodes to further optimize the final circuit. The algorithms described in this thesis are implemented in a software program called Chortle and experimental results for a set of benchmark networks demonstrate the effectiveness of the algorithms.
i