In this paper, we propose a global routing method for 2-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment of each net. Our global routing method starts from an initial monotonic via assignment and incrementally improves the via assignment to optimize the total wire length and the wire congestion. Experimental results show that our proposed method generates a better global routing efficiently.

One of the difficulties in routing problem is in wirability which is to guarantee a physical connection of a given topological route. Wirability often fails since the width of a wire is relatively large compared with the size of modules. As a possible solution, this paper proposes an incremental wiring algorithm which generates wires net-by-net without overlapping other pre-placed circuit elements. The idea is to divide a wire into a series of rectangles and handles them as modules with additional constraints to keep the shape of the wire. The algorithm was implemented and experimented on a small instance to show its promising performance.