Optimization of micro-coaxial wire routing in complex microelectronic systems

In this thesis, we explore wire routing strategies for new paradigms in chip design. Where current chip design techniques involve multi-layered techniques to prevent wire crossings and electrical interference, we work with new technology that utilizes coaxial wires, allowing the construction of single-layered chips. Though the single layer lends itself well to optimization techniques, this approach generates novel challenges of its own. We design and implement multiple global routing algorithms appropriate for the new technology, and we discuss how these algorithms address technical constraints introduced by dierent variations of the routing problem. We cover three approaches using dierent techniques; these include simulated annealing, local heuristics, and global mixed-integer optimization. We demonstrate the performance of these algorithms on physical chip designs and existing layouts, including metrics of total wire length, overall routability, and running time. We also discuss our process of algorithm design, specically in context of satisfying engineering requirements decided by an external technical team. Finally, we describe our ideas for future areas of research, tailored towards improvement of our approaches and addressing technical problems that will be introduced as the new technology develops.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Herrling, Austin Donald, First Lieutenant

Advisor dc:contributor.advisor

• Michael J. Ricard and Juan Pablo Vielma.

• Operations Research Center.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/119285

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/119285