Files in this item
|(no description provided)|
|Title:||Hierarchical timing-driven partitioning and placement for symmetrical FPGAs|
|Doctoral Committee Chair(s):||Kang, Sung Mo|
|Department / Program:||Electrical and Computer Engineering|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Subject(s):||Engineering, Electronics and Electrical
|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.
|Rights Information:||Copyright 1995 Karnik, Tanay|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI9624381|
This item appears in the following Collection(s)
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering