Hierarchical timing-driven partitioning and placement for symmetrical FPGAs
Karnik, Tanay
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/18976
Description
Title
Hierarchical timing-driven partitioning and placement for symmetrical FPGAs
Author(s)
Karnik, Tanay
Issue Date
1995
Doctoral Committee Chair(s)
Kang, Sung Mo
Department of Study
Electrical and Computer Engineering
Discipline
Electrical 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
Field-programmable gate arrays (FPGAs) allow circuit designers to perform quick prototyping and development. In this thesis we attempt to partition and place a hierarchically described system on multiple FPGA chips so as to minimize the maximum delay through the system. We exploit the given hierarchy to achieve computational speedup. Delay estimation is done using an accurate empirical model. The major contributions of this thesis include multichip partitioning, accurate routing delay estimation and hierarchical timing-driven placement to avoid timing problems in FPGAs.
First, we present a hierarchical partitioning algorithm that transforms the input hierarchical system into a structural hierarchy with minimum connectivity and equal FPGA chip area requirements among partitions at each hierarchical level. We address timing problems in the method by estimating path delays. Our delay model far outperforms conventional methods. The delay is assumed to be a function of path length, circuit size, fanout and congestion in the channels. An empirical model is developed by extensive simulations of various FPGA circuits. The structural hierarchy and delay estimation are then used to guide the hierarchical FPGA placement. This placement algorithm is a deterministic one. It consists of bottom-up clustering and a novel AND-OR tree-based hierarchical constraint satisfaction algorithm. It provides better results than flat-level iterative improvement algorithm based on simulated annealing with very high computational speedup. We show that it can place a large path-intensive circuit that cannot be placed at the flat level due to the combinatorial explosion.
Finally, we integrate all algorithms to form a hierarchical timing-driven partitioning and placement system for symmetrical FPGAs. The structural hierarchy generated by hierarchical partitioning is refined by a child-stealing algorithm to reduce the ill effect of initial decisions on the partitions. The timing-driven placement algorithm is extended to multichip operation. The placement is passed through a compaction step to reduce the unoccupied areas on the chips. As a final stage, we developed a flat-level iterative improvement algorithm to perform concurrent timing-driven partitioning and placement. This tool is an optional operation in our system to refine the solution. Being an iterative tool, it incurs a high computational overhead. Hence, it is judicially used when the maximum delay through the circuit is not acceptable. Our system is applicable to large industrial benchmark circuits. The results show that our system provides better results than iterative improvement based on constrained simulated annealing with a very high computational speedup.
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.
