About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Integration, the VLSI Journal
Paper
Maximizing pin alignment in semi-custom chip circuit layout
Abstract
We consider the problem of logically permuting pins of a semi-custom chip circuit layout in order to maximize the number of connections that can be realized in the polysilicon layer. As the problem is NP-hard, we present an infinite hierarchy of heuristics, including an algorithm which produces an optimal solution. The heuristics can be tuned to yield approximate solutions of varying degree, as well as an optimal solution. The tradeoff lies in the length of runtime. We have implemented the procedures and demonstrate their behavior with one real and various randomly generated examples. © 1988.