Timing-driven optimization problems in VLSI CAD

We study several optimization problems that arise in the design of VLSI circuits, with the satisfaction of timing constraints as the primary objective. We focus on problems where the underlying architecture is regular. Field Programmable Gate Arrays (FPGAs), identical standard cell based architectures and WSI arrays of blocks having a regular structure are the major architectures that are regular. The regularity of these architectures allows us to use powerful graph theoretic techniques that would not be possible otherwise.In this thesis we study problems at several different steps in the FPGA design flow. We address the problems of timing driven technology mapping and placement. We also study the problem of reconfiguring the placement of a circuit on an FPGA in order to tolerate faults in the logic blocks of the FPGA without significant degradation in the circuit delay. This problem is referred to as the timing driven reconfiguration problem. Timing driven reconfiguration can be used for off-line reconfiguration for yield enhancement and for on-line reconfiguration for fault tolerance. In a typical design flow, the design may be altered several times after the initial design cycle according to minor changes in the design specification either as a result of design debugging or as a result of changes in engineering requirements. In order to speed up the entire design process it is important to efficiently handle these engineering changes. We study the problem of incorporating engineering changes into a design in the presence of timing constraints. We propose a unified approach to solving the timing driven placement, reconfiguration and re-engineering problems using the concept of slack neighborhood graph.U of I OnlyETDs are only available to UIUC Users without author permissio