Detailed Routing Algorithms for Advanced Technology Nodes

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2015-04, Vol.34 (4), p.563-576
• Main Authors: Ahrens, Markus, Gester, Michael, Klewinghaus, Niko, Muller, Dirk, Peyer, Sven, Schulte, Christian, Tellez, Gustavo
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; algorithms; Color; Detailed routing; Heuristic algorithms; multiple patterning; Pins; Routing; Shape; VLSI; Wires
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2014.2385755

We present algorithms for routing in advanced technology nodes, used by BonnRoute (BR) to obtain efficient and almost design rule clean wire packings and pin access solutions. Designs with dense standard cell libraries in presence of complex industrial design rules, with a special focus on multiple patterning lithography are considered. The key components of this approach are a multilabel interval-based shortest path algorithm for long on-track connections, and a dynamic program for computing packings of pin access paths and short connections between closely spaced pins. The multilabel path search implementation is very general and is driven with different labeling rules, allowing to trade-off runtime against accuracy in terms of obeyed design rules. We combine BR with an industrial router for cleaning up the remaining design rule violations, and demonstrate superior results over that industrial router in our experiments in terms of wire length, number of vias, design rule violations, and runtime.