A flow based approach to the pin redistribution problem for multi-chip modules
Authors:
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 114-119
Abstract
Investigates the pin redistribution problem (PRP) for multi-chip modules. A novel transformation to the max-flow problem is introduced. This approach provides an efficient algorithm for finding a 2-layer solution, whenever one exists. A greedy heuristic to find a k-layer solution is described. The approach can find a minimum layer solution for two variants of the PRP; when each net can be routed on more than one layer, and when source and target terminals are drilled through all layers. Except for the heuristic procedure which takes O(km/sup 4/ log/sup 2/ m) time, the algorithms take O(/spl verbar/S/spl verbar/km/sup 2/) 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. One can show that generalizations of the k-layer PRP are NP-complete problems.Keywords
This publication has 5 references indexed in Scilit:
- Multilayer routing algorithm for high performance MCMs2003
- Algorithms for VLSI Physical Design Automation1993
- Electronic packaging in the 1990s-a perspective from AmericaIEEE Transactions on Components, Hybrids, and Manufacturing Technology, 1991
- Thermal Conduction Module: A High-Performance Multilayer Ceramic PackageIBM Journal of Research and Development, 1982
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975