PIN REDISTRIBUTION PROBLEM FOR MULTI-CHIP MODULES: ALGORITHMS AND COMPLEXITY

We investigate the pin redistribution problem (PRP) for multi-chip modules. We transform the PRP to the max-flow problem and obtain an efficient algorithm for finding a 2-layer solution, whenever one exists. A greedy heuristic to find a k-layer solution is described. Our approach can also construct a minimum layer solution for two variants; nets can be routed on more than one layer, and terminals (source and target) are drilled through all layers. Our algorithms take O(min{|S|, mk^1/2}m²k) time, except for the heuristic procedure which takes O(km⁴log² m) time, where S is the set of source terminals, m is the number of rows and columns in the grid, and k is the number of layers required. Several variations of the PRP when generalized to graphs can also be solved efficiently by our algorithms, whereas other variations are shown to be NP-complete.