Logic module design and technology mapping for field-programmable gate arrays
Shashidhar Thakur, Martin D. F. Wong · 1996
A Field-programmable Gate Array (FPGA) is a pre-fabricated chip, with programmable logic and routing resources. Designers can program this chip to realize arbitrary circuits, without having to go through a fabrication process. This technology is very popular for developing hardware applications, due to the short turnaround and low cost it offers. Typically, FPGAs are used for prototyping systems before doing custom fabrication. This thesis focuses on the design and utilization of the logic modules on the FPGA. The technology mapping problem for FPGAs is the problem of implementing an arbitrary circuit using the programmable logic modules on the FPGA chip. The functionality of the logic module affects the quality of mapped circuits (i.e., area, delay etc.). But the complexity of the logic module (i.e., number of transistors in the implementation) increases with functionality. In addition, technology mapping algorithms may not be able to take full advantage of the functionality. Thus, there is a mutual dependence between technology mapping algorithms and the design of the logic module. This thesis addresses problems in technology mapping as well as logic module design. Specifically, the following problems are addressed: (1) We give a polynomial time technology mapping algorithm for lookup table-based FPGAs. This algorithm simultaneously minimizes the area and delay of the mapped circuit, for a special class of circuits. This result is used to resolve the open problem of area optimal mapping for two-input lookup tables. (2) We show how the use of better decomposition techniques can improve technology mapping for multiplexer rich libraries. This work directly applies to mapping for multiplexer-based FPGAs. (3) The concept of universal logic functions has been developed in literature in the past. We show how this can be extended to the design of FPGA logic modules that can implement many different functions by specialization. (4) The tree-based technology mapper is one of the most popular mapping algorithms used in practice. We show how one can do a systematic design of logic modules that are optimized for use with this technology mapping algorithm. Thus, the mapping algorithm is taken as the starting point for logic module design.