| When implementing digital circuits with FPGAs, designers are always concerned with limited and inflexible resources. Additionally, fulfillment of timing constraints is always an issue. This thesis describes a series of algorithms developed to assist a designer fitting a circuit into an FPGA chip.; In the traditional circuit design flow, the logic design step is completely separated from physical design step. There are many arbitrary decisions made during logic design which create difficulties in the physical design. This is particularly acute in FPGA design where the routing resources are limited. It is very important to explore the freedom between the interaction of the logic and physical design steps. The first part of this thesis presents a concept of connectivity restructuring in the logic domain.; An incremental logic synthesis technique is proposed to control wiring topology. In particular, we will discuss how to add or remove one or more wires and gates, how to identify places where the transformation should be applied and how to efficiently manipulate incremental changes. We will also present new and very efficient methods of computing local don't cares and of using external don't cares in circuit optimization.; Finally, we describe algorithms to minimize the number of FPGA cells. An approach is proposed to reduce the depth of a mapped circuit by restructuring it in the logic domain. |
