04/01/1996 09:00 AM
Computer Engineering
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, is 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 Interchangeable Pin Routing (IPR) problem. We show that this problem is NP-complete. We formulate the problem as flows in a routing network on a triangulation instead of grids and developed a min-cost max- flow heuristic considering only the most important cuts in the design. The heuristic is extended to multiple layers and handles prerouted nets. It can accommodate all-angle, octilinear or rectilinear metric. Experiments showed that the heuristic is very effective on most practical examples. It successfully routed an industry design with 4000 interchangeable pins without manual intervention.
