Scalable, high-quality, SAT-based multi-layer escape routing

• Main Authors: Bayless, Sam, Hoos, Holger H., Hu, Alan J.
• Format: Conference Proceeding
• Language: English
• Subjects: Electronics packaging; Encoding; Pins; Printed circuits; Routing; Scalability; Wires
• ISSN: 1558-2434
• DOI: 10.1145/2966986.2967072

Escape routing for Printed Circuit Boards (PCBs) is an important problem arising from modern packaging with large numbers of densely spaced pins, such as BGAs. Single-layer escape routing has been well-studied, but large, dense BGAs often require multiple PCB layers to be fully escaped. Unfortunately, multi-layer escape routing is much more challenging than single-layer escape routing, and currently lacks scalable, high-quality, automatic solutions. As a result, multilayer escape routing for high-end BGAs typically requires extensive human intervention in practice. This paper introduces a novel approach to multi-layer escape routing. Our approach builds on recent advances in SAT (Boolean satisfiability) solving, in particular, the solver MonoSAT, which efficiently supports network-flow constraints within a general constraint-solving framework. We formulate multi-layer escape routing in this framework and demonstrate scalability to the largest BGAs presently in common use, with more than 2000 pins. Our approach supports 45and 90-degree routing, simultaneously places traces and vias, and supports all commonly used via technologies, including through-hole, blind, buried, and any-layer micro-vias. In addition, because our approach is based on constraint-solving, it can flexibly interoperate with partial solutions from other routing techniques. We demonstrate the utility of our technique by finding escape routings for a diverse set of large, commercial BGAs. Compared to a typical layer-by-layer approach, our approach produces better routings, often saving one or more PCB layers for larger BGAs, and in some cases, proving that no solution is possible with fewer layers. Finally, we describe how our technique can be extended to handle common additional constraints, such as differential-pair constraints.