Simultaneous Escape Routing (SER) with application to PCB

Abstract

With the advancement in technology, the use of compact ball grid array (BGA) components is being increased in printed circuit boards (PCB). The problem of routing pins from under the body of BGA, towards component boundary is known as escape routing. It is often desirable to perform simultaneous escape routing (SER) to produce elegant PCB design. The task of SER is non-trivial, given the small size of components and hundreds of pins arranged in random order in each component that need ordered connectivity. This thesis proposes the use of optimization models with multiple routing constraints that simultaneously solves the net ordering and net escape problem. It is hypothesized that optimization model along with all necessary constraints can route more number of nets, instead of solving constraints one by one. In the first part of thesis, flow models are proposed for different types of pin arrays for multiple capacities and the routing problem is mapped to planar bipartite graph problem. In the second part, integer linear programming (ILP) based opiii iv timization model is proposed for single component ordered escape routing to see the effect of planar routing, net ordering and system constraints. In the third part, ILP optimization model for SER problem is proposed and finally an algorithm is proposed to find the valid net order to reduce the complexity of SER problem. Both optimization models prove that they can route maximum possible nets in their respective scenarios, by considering the design rules. Comparative analysis shows that the proposed optimization models perform better than the existing routing algorithms in terms of number of nets routed. Also the use of net ordering algorithm reduces the complexity and converts the SER problem to simple ordered escape routing problem.