MORE-Router+: Multilayer Multi-capacity ORdered Escape Routing via Bus-oriented Layer Assignment

Zhenyi Gao, Sheqin Dong, Zifei Cheng, Wenjian Yu
Tsinghua University


Abstract

Escape routing is one of the fundamental problems in advanced packaging and PCB design. In this work, the multilayer multi-capacity ordered escape routing on grid pin array (GPA) is considered with a bus-oriented layer assignment. The nets are grouped as a set of buses and the problem objective is minimizing the number of routing layers while satisfying the layer-adjacency, capacity and projection ordering constraints. We propose a router for multilayer multi-capacity ordered escape routing (named MORE-Router+), which is based on integer linear programming (ILP) and consists of bus planning, layer assignment and detailed routing. In the bus planning stage we assign one feasible escape direction for each bus. The layer assignment algorithm determines the layer location so that the number of used layers is minimized and the layer-adjacency constraint is satisfied. For the detailed routing, we extend the multi-capacity min-cost multi-commodity flow (MC-MCF) graph [1] to multilayer MC-MCF graph and formulate the problem as an ILP problem. Furthermore, a net sequence division technique is proposed to accelerate the detailed routing. The proposed method is tested on 9 cases with up to 54 buses and 1602 nets in 50*50 GPA. The results show that the net sequence division technique brings 4.06X through over 156X speedup, and MORE-Router+ costs no more than 266 seconds to complete the multilayer multi-capacity ordered escape routing.