Files in this item



application/pdf9624381.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Hierarchical timing-driven partitioning and placement for symmetrical FPGAs
Author(s):Karnik, Tanay
Doctoral Committee Chair(s):Kang, Sung Mo
Department / Program:Electrical and Computer Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
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.
Issue Date:1995
Rights Information:Copyright 1995 Karnik, Tanay
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9624381
OCLC Identifier:(UMI)AAI9624381

This item appears in the following Collection(s)

Item Statistics