{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69570"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69570","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)","abstract":"The thesis addresses the algorithmic design aspect of VLSI circuit layout. We study several optimization problems that arise from various stages of circuit layout. In particular, we consider problems chosen from the area of floorplan design, module synthesis, and routing.","abstract_html":"The thesis addresses the algorithmic design aspect of VLSI circuit layout. We study several optimization problems that arise from various stages of circuit layout. In particular, we consider problems chosen from the area of floorplan design, module synthesis, and routing.","abstract_has_math":false,"creators":["Wong, Martin Ding Fat"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:25:52Z","date_published":"2014-12-15T19:25:52Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8711904"],"render_values":[{"text":"(UMI)AAI8711904","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69570","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Wong, Martin Ding Fat"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:25:52Z","10000-01-01","1987"]},{"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":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69570","(UMI)AAI8711904"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis addresses the algorithmic design aspect of VLSI circuit layout. We study several optimization problems that arise from various stages of circuit layout. In particular, we consider problems chosen from the area of floorplan design, module synthesis, and routing.","In chapter 2, we present an algorithm to construct slicing floorplans for rectangular modules. Our major contributions are: (1) a new representation of floorplans which enables us to carry out neighborhood search effectively, and (2) a simultaneous minimization of area and interconnections in the final solution.","In chapter 3, we present an unified approach to generate: (1) floorplans for rectangular and L-shape modules, (2) non-slicing floorplans for rectangular modules, and (3) slicing floorplans for rectangular modules.","In chapter 4, we present an algorithm for folding Programmable Logic Arrays. Our algorithm can perform multiple folding as well as simple folding. We also show how our algorithm can be extended to handle constrained folding.","In chapter 5, we present an algorithm that solves a general array optimization problem. Our algorithm can be used for compacting Gate Matrix layouts, SLAs, Weinberger Arrays, and for multiple folding of PLAs.","In chapter 6, we study the channel routing problem in which via size on the total routing area is considered. We introduce a track permutation technique to produce routing solutions that contain no horizontally adjacent vias and a close to minimum number of vertically and diagonally adjacent vias. Such solutions lead to compaction that will reduce total routing area.","All of our algorithms except those in chapter 7 for channel routing employ the technique of simulated annealing. Our research not only produced good algorithms for a number of important problems in the area of VLSI circuit layout, but also illustrated that the technique of simulated annealing is an effective and valuable algorithmic design methodology.","Made available in DSpace on 2014-12-15T19:25:52Z (GMT). No. of bitstreams: 1 8711904.pdf: 4824221 bytes, checksum: 3e07385be001e816add9c7f1cd97be9e (MD5) Previous issue date: 1987","Embargo set by: Seth Robbins for item 69736 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","162 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987."]},{"key":"dc:title","label":"Title","values":["Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)"]}]}],"canonical_facts":{"dc:creator":["Wong, Martin Ding Fat"],"dc:date":["2014-12-15T19:25:52Z","10000-01-01","1987"],"dc:description":["The thesis addresses the algorithmic design aspect of VLSI circuit layout. We study several optimization problems that arise from various stages of circuit layout. In particular, we consider problems chosen from the area of floorplan design, module synthesis, and routing.","In chapter 2, we present an algorithm to construct slicing floorplans for rectangular modules. Our major contributions are: (1) a new representation of floorplans which enables us to carry out neighborhood search effectively, and (2) a simultaneous minimization of area and interconnections in the final solution.","In chapter 3, we present an unified approach to generate: (1) floorplans for rectangular and L-shape modules, (2) non-slicing floorplans for rectangular modules, and (3) slicing floorplans for rectangular modules.","In chapter 4, we present an algorithm for folding Programmable Logic Arrays. Our algorithm can perform multiple folding as well as simple folding. We also show how our algorithm can be extended to handle constrained folding.","In chapter 5, we present an algorithm that solves a general array optimization problem. Our algorithm can be used for compacting Gate Matrix layouts, SLAs, Weinberger Arrays, and for multiple folding of PLAs.","In chapter 6, we study the channel routing problem in which via size on the total routing area is considered. We introduce a track permutation technique to produce routing solutions that contain no horizontally adjacent vias and a close to minimum number of vertically and diagonally adjacent vias. Such solutions lead to compaction that will reduce total routing area.","All of our algorithms except those in chapter 7 for channel routing employ the technique of simulated annealing. Our research not only produced good algorithms for a number of important problems in the area of VLSI circuit layout, but also illustrated that the technique of simulated annealing is an effective and valuable algorithmic design methodology.","Made available in DSpace on 2014-12-15T19:25:52Z (GMT). No. of bitstreams: 1 8711904.pdf: 4824221 bytes, checksum: 3e07385be001e816add9c7f1cd97be9e (MD5) Previous issue date: 1987","Embargo set by: Seth Robbins for item 69736 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","162 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987."],"dc:identifier":["http://hdl.handle.net/2142/69570","(UMI)AAI8711904"],"dc:subject":["Computer Science"],"dc:title":["Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)"],"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:26:01Z"}