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.
