| Short turnaround time has become critical in the design of electronic systems. Software-programmable components such as microprocessors and digital signal processors have been used extensively in these systems. However, the inherent performance limitations of software-programmable systems makes them inadequate for high-performance designs. As a result, designers have turned to a mask-programmable hardware solution, namely gate arrays. Recently, user-programmable gate arrays, called field-programmable gate arrays (FPGAs), have emerged and are changing the way electronic systems are designed and implemented. The most popular FPGA architectures use either a look-up table (LUT) or a multiplexor-configuration as the basic building block.; With the growing complexity of the logic circuits that can be packed on an FPGA chip, it becomes important to have automatic synthesis tools that implement logic functions on these architectures. Conventional synthesis approaches fail to produce satisfactory solutions for FPGAs, since the constraints imposed by FPGA architectures are quite different. In this thesis, we explore the problem of logic synthesis for both LUT- and multiplexor-based architectures.; In the first part, we propose algorithms to synthesize combinational logic with a minimum number of m-input LUTs, where each m-input LUT can realize any Boolean function of up to m inputs. We use the widely-accepted two-phase paradigm for logic synthesis consisting of technology-independent optimization followed by technology mapping. Technology-independent optimization derives a minimal representation (with respect to a cost function), which is then implemented by the mapping phase on the target technology, in our case LUTs. We present LUT-specific mapping techniques for implementing a function that has more than m inputs and for combining functions with less than m inputs into the fewest possible LUTs. We use the proposed algorithms for mapping sequential logic on to a commercial LUT-based architecture containing sequential elements. We also investigate issues in logic optimization for LUTs. In particular, we establish the inadequacy of the standard cost function and propose a new one.; In the first part we also address the theoretical complexity issues regarding the minimum number of LUTs needed for a function. We derive complexity upper bounds and demonstrate that they can be used to quickly and quite accurately predict the LUT-count without doing any mapping. Finally, algorithms for performance optimization are presented. Because of the constraints imposed by the architecture and programming methodology, the wiring delays can be a significant fraction of the total path delay. Lacking placement information, the logic-level delay models cannot handle wiring delays. Our contribution is to solve the problem by coupling logic-level optimization with timing-driven placement of the LUTs.; In the second part, our main contribution is to demonstrate that for obtaining high quality solutions on multiplexor-based architectures, the mapping algorithm should use a multiplexor-based representation for the functions instead of the conventional NAND-based one. Efficient architecture-specific algorithms to construct and map the representation are given.; In both parts of the thesis, theoretical results regarding the optimality of various algorithms are presented. These algorithms have been implemented in a system called mis-fpga, and are compared with those developed by other researchers. On average, 10-30% improvement in the solution quality is obtained, establishing the effectiveness of our techniques. (Abstract shortened by UMI.)... |
