{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/21770"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/21770","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"VLSI routing on the hexagonal grid","abstract":"The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes +30$\\sp\\circ$ and $-$30$\\sp\\circ$, respectively. The goal of this thesis research has been to investigate the potential of the hexagonal grid for VLSI detailed routing. We have studied the layout geometry of the hexagonal grid and shown it to be compatible with standard VLSI implementation. This distinguishes the hexagonal routing models developed in this work as the first consistent environments on which to base comparative study of diagonal and traditional rectilinear routing.","abstract_html":"The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes +30$\\sp\\circ$ and $-$30$\\sp\\circ$, respectively. The goal of this thesis research has been to investigate the potential of the hexagonal grid for VLSI detailed routing. We have studied the layout geometry of the hexagonal grid and shown it to be compatible with standard VLSI implementation. This distinguishes the hexagonal routing models developed in this work as the first consistent environments on which to base comparative study of diagonal and traditional rectilinear routing.","abstract_has_math":true,"creators":["Powers, Kris Dee"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Brown, Donna J."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:18:37Z","date_published":"2011-05-07T13:18:37Z","updated_at":"2026-07-22T22:25:18Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1993 Powers, Kris Dee"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411752","(UMI)AAI9411752"],"render_values":[{"text":"AAI9411752","href":null,"code":true},{"text":"(UMI)AAI9411752","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/21770","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Brown, Donna J."]},{"key":"dc:creator","label":"Author","values":["Powers, Kris Dee"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:18:37Z","10000-01-01","1993"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1993 Powers, Kris Dee"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9411752","(UMI)AAI9411752","http://hdl.handle.net/2142/21770"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes +30$\\sp\\circ$ and $-$30$\\sp\\circ$, respectively. The goal of this thesis research has been to investigate the potential of the hexagonal grid for VLSI detailed routing. We have studied the layout geometry of the hexagonal grid and shown it to be compatible with standard VLSI implementation. This distinguishes the hexagonal routing models developed in this work as the first consistent environments on which to base comparative study of diagonal and traditional rectilinear routing.","A major portion of this work has been devoted to assessing the potential of hexagonal routing in terms of the specific problem of channel routing. We have considered algorithms for arbitrary channel routing problems (CRP's), as well as algorithms specifically designed for those problems most appropriate to diagonal interconnection. More specifically, for a CRP with density d, the availability of the diagonal tracks leads to a lower bound of ${d\\over\\sqrt{3}}$ for routing without overlap. We present three algorithms for routing CRP's on the hexagonal grid in widths which approach or achieve this lower bound. Our algorithms route in three, four, and five layers, respectively, and as is the case on the square grid, the less restrictive models better approximate the lower bound. The CRP's best suited to diagonal interconnection are those in which the maximum net span is small, relative to channel density. In particular, for a CRP having maximum net span $s\\sp*$, the maximum possible density is 2$s\\sp*$. We give an algorithm which routes every (2-terminal or multiterminal) 2-sided net CRP in width ${2\\over\\sqrt{3}}s\\sp*$ + O(1) in three layers. For problems having density d near the 2$s\\sp*$ upper bound, a routing of width $s\\sp*$ is essentially optimal on the hexagonal grid. Further, for a CRP having $s\\sp* < {\\sqrt{3}\\over 2}d$, a hexagonal routing of width $s\\sp*$ hu is less than the square grid lower bound for routing without overlap.","We have also investigated hexagonal routing in more general frameworks. Specifically, we have examined relations between traditional rectilinear and hexagonal layouts, and in doing so, provide a comparative basis which is independent of any particular class of routing problems. Finally, we have considered the effect of the geometry of the hexagonal grid on the requisite conditions for layout of more general instances of the detailed routing problem.","Made available in DSpace on 2011-05-07T13:18:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411752.pdf: 8538494 bytes, checksum: 9f0eb6eae4a8aa3abe67283ae18a033b (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:53:05Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:24:30-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":["VLSI routing on the hexagonal grid"]}]}],"canonical_facts":{"dc:contributor":["Brown, Donna J."],"dc:creator":["Powers, Kris Dee"],"dc:date":["2011-05-07T13:18:37Z","10000-01-01","1993"],"dc:description":["The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes +30$\\sp\\circ$ and $-$30$\\sp\\circ$, respectively. The goal of this thesis research has been to investigate the potential of the hexagonal grid for VLSI detailed routing. We have studied the layout geometry of the hexagonal grid and shown it to be compatible with standard VLSI implementation. This distinguishes the hexagonal routing models developed in this work as the first consistent environments on which to base comparative study of diagonal and traditional rectilinear routing.","A major portion of this work has been devoted to assessing the potential of hexagonal routing in terms of the specific problem of channel routing. We have considered algorithms for arbitrary channel routing problems (CRP's), as well as algorithms specifically designed for those problems most appropriate to diagonal interconnection. More specifically, for a CRP with density d, the availability of the diagonal tracks leads to a lower bound of ${d\\over\\sqrt{3}}$ for routing without overlap. We present three algorithms for routing CRP's on the hexagonal grid in widths which approach or achieve this lower bound. Our algorithms route in three, four, and five layers, respectively, and as is the case on the square grid, the less restrictive models better approximate the lower bound. The CRP's best suited to diagonal interconnection are those in which the maximum net span is small, relative to channel density. In particular, for a CRP having maximum net span $s\\sp*$, the maximum possible density is 2$s\\sp*$. We give an algorithm which routes every (2-terminal or multiterminal) 2-sided net CRP in width ${2\\over\\sqrt{3}}s\\sp*$ + O(1) in three layers. For problems having density d near the 2$s\\sp*$ upper bound, a routing of width $s\\sp*$ is essentially optimal on the hexagonal grid. Further, for a CRP having $s\\sp* < {\\sqrt{3}\\over 2}d$, a hexagonal routing of width $s\\sp*$ hu is less than the square grid lower bound for routing without overlap.","We have also investigated hexagonal routing in more general frameworks. Specifically, we have examined relations between traditional rectilinear and hexagonal layouts, and in doing so, provide a comparative basis which is independent of any particular class of routing problems. Finally, we have considered the effect of the geometry of the hexagonal grid on the requisite conditions for layout of more general instances of the detailed routing problem.","Made available in DSpace on 2011-05-07T13:18:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411752.pdf: 8538494 bytes, checksum: 9f0eb6eae4a8aa3abe67283ae18a033b (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:53:05Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:24:30-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":["AAI9411752","(UMI)AAI9411752","http://hdl.handle.net/2142/21770"],"dc:language":["eng"],"dc:rights":["Copyright 1993 Powers, Kris Dee"],"dc:subject":["Computer Science"],"dc:title":["VLSI routing on the hexagonal grid"],"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:18Z"}