Timing-constrained layout algorithms for symmetrical field-programmable gate arrays
Raman, Srilata
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22655
Description
Title
Timing-constrained layout algorithms for symmetrical field-programmable gate arrays
Author(s)
Raman, Srilata
Issue Date
1994
Doctoral Committee Chair(s)
Liu, C.L.
Department of Study
Electrical and Computer Engineering
Discipline
Electrical and Computer Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Language
eng
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
