{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29764"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29764","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Single-layer bus routing for high-speed boards","abstract":"As the clock frequencies used in industry increase, the timing requirements on high-speed boards become very tight. Since wire length is directly proportional to wire delay of the buses that connect each chip on high-speed boards, each wire in the bus has to be tightly bounded by the maximum and minimum lengths during routing. These rigid requirements cause challenges for automatic routing. Therefore, more aggressive routing algorithms are required for current industrial circuits. This thesis intends to improve Ozdal and Wong's previous work, which is an algorithmic study of single-layer bus routing on high-speed boards. Their routing algorithm assumes that there are no boundaries in the grid during routing, and the maximum-length bound for each net is always met. This thesis modifies their code so that it does not make those assumptions. As a result, the program can now handle boundaries with wire snaking to meet the minimum-length bound and use diagonal wires if the Manhattan distance between the two terminal pins cannot satisfy the maximum-length bound.","abstract_html":"As the clock frequencies used in industry increase, the timing requirements on high-speed boards become very tight. Since wire length is directly proportional to wire delay of the buses that connect each chip on high-speed boards, each wire in the bus has to be tightly bounded by the maximum and minimum lengths during routing. These rigid requirements cause challenges for automatic routing. Therefore, more aggressive routing algorithms are required for current industrial circuits. This thesis intends to improve Ozdal and Wong's previous work, which is an algorithmic study of single-layer bus routing on high-speed boards. Their routing algorithm assumes that there are no boundaries in the grid during routing, and the maximum-length bound for each net is always met. This thesis modifies their code so that it does not make those assumptions. As a result, the program can now handle boundaries with wire snaking to meet the minimum-length bound and use diagonal wires if the Manhattan distance between the two terminal pins cannot satisfy the maximum-length bound.","abstract_has_math":false,"creators":["Chang, Yun Wei"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-02-06T20:15:05Z","date_published":"2012-02-06T20:15:05Z","updated_at":"2026-07-22T22:25:29Z","subjects":["Single Layer Bus","High-Speed Printed Circuit Board"],"languages":["en"],"rights":["Copyright 2011 Yun Wei Chang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29764","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Chang, Yun Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-02-06T20:15:05Z","2011-12"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["Single Layer Bus","High-Speed Printed Circuit Board"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Yun Wei Chang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29764"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["As the clock frequencies used in industry increase, the timing requirements on high-speed boards become very tight. Since wire length is directly proportional to wire delay of the buses that connect each chip on high-speed boards, each wire in the bus has to be tightly bounded by the maximum and minimum lengths during routing. These rigid requirements cause challenges for automatic routing. Therefore, more aggressive routing algorithms are required for current industrial circuits. This thesis intends to improve Ozdal and Wong's previous work, which is an algorithmic study of single-layer bus routing on high-speed boards. Their routing algorithm assumes that there are no boundaries in the grid during routing, and the maximum-length bound for each net is always met. This thesis modifies their code so that it does not make those assumptions. As a result, the program can now handle boundaries with wire snaking to meet the minimum-length bound and use diagonal wires if the Manhattan distance between the two terminal pins cannot satisfy the maximum-length bound.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-11-22T21:14:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Chang_Yun Wei.pdf: 5083811 bytes, checksum: a4b4c85c8216171d83850e2d09b18ebf (MD5)","Made available in DSpace on 2012-02-06T20:15:05Z (GMT). No. of bitstreams: 2 Chang _YunWei.pdf: 5083210 bytes, checksum: e31bf9cff86b2f7540d47c89f8a47861 (MD5) license.txt: 4058 bytes, checksum: 2ba5c3c8b547dd5026e58517c2ce832b (MD5)"]},{"key":"dc:title","label":"Title","values":["Single-layer bus routing for high-speed boards"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F."],"dc:creator":["Chang, Yun Wei"],"dc:date":["2012-02-06T20:15:05Z","2011-12"],"dc:description":["As the clock frequencies used in industry increase, the timing requirements on high-speed boards become very tight. Since wire length is directly proportional to wire delay of the buses that connect each chip on high-speed boards, each wire in the bus has to be tightly bounded by the maximum and minimum lengths during routing. These rigid requirements cause challenges for automatic routing. Therefore, more aggressive routing algorithms are required for current industrial circuits. This thesis intends to improve Ozdal and Wong's previous work, which is an algorithmic study of single-layer bus routing on high-speed boards. Their routing algorithm assumes that there are no boundaries in the grid during routing, and the maximum-length bound for each net is always met. This thesis modifies their code so that it does not make those assumptions. As a result, the program can now handle boundaries with wire snaking to meet the minimum-length bound and use diagonal wires if the Manhattan distance between the two terminal pins cannot satisfy the maximum-length bound.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-11-22T21:14:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Chang_Yun Wei.pdf: 5083811 bytes, checksum: a4b4c85c8216171d83850e2d09b18ebf (MD5)","Made available in DSpace on 2012-02-06T20:15:05Z (GMT). No. of bitstreams: 2 Chang _YunWei.pdf: 5083210 bytes, checksum: e31bf9cff86b2f7540d47c89f8a47861 (MD5) license.txt: 4058 bytes, checksum: 2ba5c3c8b547dd5026e58517c2ce832b (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/29764"],"dc:language":["en"],"dc:rights":["Copyright 2011 Yun Wei Chang"],"dc:subject":["Single Layer Bus","High-Speed Printed Circuit Board"],"dc:title":["Single-layer bus routing for high-speed boards"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}