Old Dominion University
Single Row Routing: Theoretical and Experimental Performance Evaluation, and New Heuristic Development
Abstract
dc:description.abstractThe Single Row Routing Problem (SRRP) is an abstraction arising from real-world multilayer routing concerns. While NP-Complete, development of efficient SRRP routing heuristics are of vital concern to VLSI design. Previously, researchers have introduced various heuristics for SRRP; however, a comprehensive examination of SRRP behavior has been lacking. We are particularly concerned with the street-congestion minimization constraint, which is agreed to be the constraint of greatest interest to industry. Several theorems stating lower bounds on street congestion are known. We show that these bounds are not tight in general, and argue they may be in error by at least 50% for some problem instances. On an experimental level, we examine upper and lower bound behavior through generation and processing of large data sets of randomly distributed problem instances. Using this data as input to implementations of previously published heuristics, we establish a minimal performance baseline for evaluation of routing algorithms. We also present a new algorithmic framework, and discuss its use for development of heuristics of varying "optimality" and time performance characteristics. We fully implement one such algorithm, and experimentally show its superiority to previous routing heuristics.
Degree
thesis:*- Name thesis:degree_name
- Master of Science (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hysom, David A.
- Contributors dc:contributor
-
- Stephen Olariu
- David E. Keyes
- Shunichi Toida
- Stewart Shen
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.odu.edu/computerscience_etds/168