{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22435"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22435","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Logic and layout optimizaton for sequential circuits","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Pan, Peichen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, C.L."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:39:45Z","date_published":"2011-05-07T13:39:45Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Engineering, Electronics and Electrical","Operations Research","Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Pan, Peichen"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624456","(UMI)AAI9624456"],"render_values":[{"text":"AAI9624456","href":null,"code":true},{"text":"(UMI)AAI9624456","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22435","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, C.L."]},{"key":"dc:creator","label":"Author","values":["Pan, Peichen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:39:45Z","10000-01-01","1995"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Operations Research","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Pan, Peichen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624456","(UMI)AAI9624456","http://hdl.handle.net/2142/22435"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:title","label":"Title","values":["Logic and layout optimizaton for sequential circuits"]}]}],"canonical_facts":{"dc:contributor":["Liu, C.L."],"dc:creator":["Pan, Peichen"],"dc:date":["2011-05-07T13:39:45Z","10000-01-01","1995"],"dc:description":["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"],"dc:identifier":["AAI9624456","(UMI)AAI9624456","http://hdl.handle.net/2142/22435"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Pan, Peichen"],"dc:subject":["Engineering, Electronics and Electrical","Operations Research","Computer Science"],"dc:title":["Logic and layout optimizaton for sequential circuits"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}