Timing-constrained layout algorithms for symmetrical field-programmable gate arrays

In this thesis, we address timing-constrained placement and routing in symmetrical field-programmable gate arrays (FPGAs).First, we present a timing-driven placement algorithm for symmetrical FPGAs. The algorithm combines the computational simplicity of a net-based algorithm with the net length flexibility permitted by a path-based algorithm. The algorithm has three phases. First, we determine the relative placement of logic blocks in accordance with timing requirements, using the classical force-directed placement technique modified to reflect the goal of satisfying timing constraints. Second, we assign logic blocks to 2D grid positions on the array using an algorithm whose cost function incorporates timing considerations. The net weights depend on the net delays obtained from a timing analysis of the circuit. Third, the timing requirements that are not satisfied are remedied by adaptively reassigning the net weights. The first two phases are repeated with the set of new net weights to generate a solution that meets the timing constraints. Experiments indicate that the algorithm is effective in meeting all the timing constraints and in increasing the speed of the resulting circuit. The routability is not seriously degraded and the CPU time required by our algorithm is much smaller than that required by a simulated annealing based placement algorithm.Second, we present a timing-driven routing algorithm for symmetrical FPGAs. Our algorithm exploits the architectural features of symmetrical FPGAs while providing timing-accurate routing solutions. The salient features of our algorithm are as follows. (1) Uses a one-step routing approach that combines global and detailed routing. (2) Assigns nets to routing resources dictated by the characteristics of the resource. (3) Calculates delays of sinks using the Elmore delay models. (4) Routes on a sink-by-sink, as opposed to a net-by-net basis, (referred to as incremental routing tree construction). (5) Incorporates incremental feedback of timing delays of currently routed sinks to guide the routing process.Experimental results indicate that the algorithm is successful in meeting the timing requirements imposed on the circuit, utilizes the routing resources judiciously, completely routes all the nets, and incurs a low CPU time.U of I OnlyETDs are only available to UIUC Users without author permissio