Field-Programmable Gate Array Logic Synthesis Using Boolean Satisfiability

Abstract

Field-Programmable gate arrays (FPGAs) are reprogrammable logic chips that can be configured to implement various digital circuits. FPGAs are fast replacing custom ASICs in many areas due to their flexibility and fast turn around times for product development. However, these benefits come at a heavy cost of area, speed, and power.

The FPGA architecture and technology mapping phase are fundamental in determining the performance of the FPGA. This thesis presents novel tools using Boolean satisfiability (SAT) to aid in both these areas. First, an architecture efficiency evaluation tool is developed. The tool works by reading in a description of the FPGA architecture and rates how flexible that architecture can be in implementing various circuits. Next, a novel technology mapping approach is developed and compared to current methods. This work contrasts with current approaches since it can be applied to almost any FPGA architecture. Finally, a resynthesis algorithm is described which rates the utility of current FPGA technology mappers where it can also be used to discover optimal configurations of common subcircuits to digital design.

Copyright © 2005 by Andrew C. Ling

Full Thesis PDF here.

Thesis Presentation ppt.

Last updated Jan 2006