2026-09-20T18:31:27Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/22435 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Liu, C.L. Pan, Peichen 2011-05-07T13:39:45Z 2011-05-07T13:39:45Z 10000-01-01 1995 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. Made available in DSpace on 2011-05-07T13:39:45Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624456.pdf: 5629112 bytes, checksum: 1aba02f8b457cc43a6fb9632a81a3ec4 (MD5) Previous issue date: 1995 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:57:36Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:27:01-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9624456 (UMI)AAI9624456 http://hdl.handle.net/2142/22435 eng Copyright 1995 Pan, Peichen Engineering, Electronics and Electrical Operations Research Computer Science Logic and layout optimizaton for sequential circuits text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.