Interchangeable pin routing with application to package layout

Many practical routing problems such as BGA, PGA, pin redistribution and test fixture routing involve routing with interchangeable pins. These routing problems, especially package layout, are becoming more difficult to do manually due to increasing speed and I/O. Currently, no commercial or university router is available for this task. In this paper, we unify these different problems as instances of the interchangeable pin routing (IPR) problem, which is NP-complete. By representing the solution space with flows in a triangulated routing network instead of grids, we developed a min-cost max-flow heuristic considering only the most important cuts in the design. The heuristic handles multiple layers, prerouted nets, and all-angle, octilinear or rectilinear wiring styles. Experiments show that the heuristic is very effective on most practical examples. It had been used to route industry designs with thousands of interchangeable pins.