Technology mapping for field-programmable gate arrays.

Field-programmable gate arrays (FPGAs) are integrated circuits (ICs) used for rapid prototyping and low-cost manufacture of digital systems. Technology mapping is the process of transforming a given logic circuit C to a form that can be embedded (mapped) into an FPGA. Most FPGAs contain a large number of logic blocks, each of which can be programmed to implement any logic function of a few variables; the connections between the logic blocks are also programmable. The goal of technology mapping is to map C to minimize either the number of logic blocks (area) or the worst-case signal propagation delay (performance). Prior methods use heuristics that can only handle a few types of FPGAs and produce results that can be far from optimal. This thesis addresses the technology-mapping problem using an exact optimization technique, mixed-integer linear programming (MILP), and targets a very wide class of FPGA types and design goals. The logic blocks of most commercial FPGAs are composed of a few interconnected lookup tables (LUTs), where a LUT is a memory device that can map any function of a predefined number of inputs (usually 3 to 6). We introduce the notion of virtual switch to model the connection among the LUTs of a logic block. The virtual switches are used to represent the block's possible mapping configurations, which are called multiple-LUT blocks (MLBs). We show that a logic block can be accurately modeled by a small set of its MLBs, called an MLB-basis, and derive the MLB-bases of the most popular FPGA types. The MLB-basis of a logic block is fundamental to our exact technology mapping technique. We first develop an MILP formulation of the technology mapping problem for a single-LUT logic block with the objective of minimizing FPGA area. Two key properties of circuit structure that complicate technology mapping, reconvergence and non-monotonicity of signals, are characterized. We also develop efficient MILP models for multiple-LUT logic blocks using a compact matrix representation of their MLB-bases, which can be solved using off-the-shelf MILP solver programs. We perform extensive experiments that use our theory to map large benchmark circuits to commercial FPGAs. Area improvements of up to 50% over prior heuristic-based methods are obtained in the case of single-LUT logic blocks. We also successfully apply our approach to commercial FPGAs that contain multiple-LUT logic blocks, which existing methods are unable to handle directly, thus demonstrating the generality of our approach. Finally, the MILP methodology is extended to performance optimization where a fixed delay is assigned to every logic block in the mapped circuit. We again performed experiments with benchmark circuits and commercial FPGAs to generate solutions that cover a wide range of area and performance values, thus for the first time permitting precise area-performance trade-offs to be made. Our experiments demonstrate that circuits with up to 500 gates can be exactly mapped to multiple-LUT logic blocks in a few hours. For larger circuits, approximations based on partitioning the circuit or simplifying the MLB-basis of the logic block are presented that yield provably near-optimal solutions in minutes.Ph.D.Applied SciencesComputer scienceElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130448/2/9732057.pd