page 2  (183 pages)
to previous section1
3to next section

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 K-input 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 library-based 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 K-input 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.