MCMCF-Router: Multi-capacity Ordered Escape Routing Algorithms for Grid/Staggered Pin Array

Ordered escape routing (OER), which means that the pins need to be routed to the boundary of a pin array in a given order, is an important research topic in PCB design. Although OER has been widely investigated, most works assume that the routing capacity between two adjacent pins is just 1 and the structure of the pin array is a grid pin array. In this article, we focus on multi-capacity ordered escape routing (MC-OER) both in grid pin arrays and staggered pin arrays, which means that multiple wires are allowed to pass through between two adjacent pins. We first propose a multi-capacity multi-commodity flow (MC-MCF) model for the MC-OER problem. To accelerate the routing process, MCMCF-Router is proposed. In MCMCF-Router, a wiring resources driven partition strategy is proposed to reduce the problem size, followed by the approach based on routing conflicts. These approaches largely accelerate the MC-MCF model based method and increase the routability with minimal sacrifice on wire length. Experiments on various cases (with up to 525 pins) show that the proposed method achieves 100% routability within reasonable time (<810 seconds). Compared to the state-of-the-art works for single-capacity OER problems, MCMCF-Router performs similarly well or better.