Files in this item



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


Title:Logic and layout optimizaton for sequential circuits
Author(s):Pan, Peichen
Doctoral Committee Chair(s):Liu, C.L.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Operations Research
Computer Science
Abstract:Computer-aided design of VLSI circuits is usually carried out in three synthesis steps: high-level synthesis, logic synthesis and layout synthesis. Each synthesis step is further broken into a few optimization problems. In this thesis we study several such problems in logic and layout synthesis.
We study how the technique of retiming can be introduced to enhance the solution of three problems in logic synthesis. Specifically, we consider a partial scan approach to the problem of design-for-testability in which a set of scan signals (instead of scan flip-flops) is pre-selected. We propose an algorithm that uses retiming to position flip-flops on the pre-selected scan signals so that these signals can be scanned. Next, we combine resynthesis with retiming to reduce the cycle time of a sequential circuit. We also integrate retiming into the technology mapping step for look-up table based field programmable gate arrays (FPGAs). We present an optimal cycle time technology mapping algorithm for sequential circuits.
In layout synthesis, we study the area minimization problem in floorplanning (also known as the floorplan sizing problem). We propose two area minimization algorithms for general floorplans. Both algorithms can be viewed as generalizations of the classical area minimization algorithm by Otten and Stockmeyer. A fast pseudo-polynomial area minimization algorithm for an important class of hierarchical floorplans is also proposed. We settle an open problem on the complexity of the area minimization problem for hierarchical floorplans by showing it to be NP-complete. Finally, we study a graph constraint reduction problem in symbolic layout compaction. We present a polynomial algorithm that achieves optimal reduction.
Issue Date:1995
Rights Information:Copyright 1995 Pan, Peichen
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9624456
OCLC Identifier:(UMI)AAI9624456

This item appears in the following Collection(s)

Item Statistics