Return to search

Global Routing in VLSI: Algorithms, Theory, and Computation

<p> Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this thesis, we present a polynomial time approximation algorithm for the global routing problem based on an integer programming formulation. The algorithm features a theoretical approximation bound, while ensuring all the routing demands are concurrently satisfied.</p> <p> We provide both a serial and a parallel implementation, as well as develop several heuristics to improve the quality of the solution and reduce running time. Our computational tests on a well-known benchmark set show that, combined with certain heuristics, our new algorithms perform very well compared with other integer programming approaches.</p> / Thesis / Master of Science (MSc)

Identiferoai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21326
Date05 1900
CreatorsDickson, Chris
ContributorsDeza, Antoine, Computing and Software
Source SetsMcMaster University
Languageen_US
Detected LanguageEnglish
TypeThesis

Page generated in 0.0019 seconds