Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21326
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Deza, Antoine | - |
dc.contributor.author | Dickson, Chris | - |
dc.date.accessioned | 2017-05-02T14:06:23Z | - |
dc.date.available | 2017-05-02T14:06:23Z | - |
dc.date.issued | 2007-05 | - |
dc.identifier.uri | http://hdl.handle.net/11375/21326 | - |
dc.description.abstract | <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> | en_US |
dc.language.iso | en_US | en_US |
dc.subject | global routing, VLSI, Algorithms, Theory, Computation, design, optimization | en_US |
dc.title | Global Routing in VLSI: Algorithms, Theory, and Computation | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Master of Science (MSc) | en_US |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dickson_Chris_2007May_Masters..pdf | 2.47 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.