Maximizing pin alignment in semi-custom chip circuit layout

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.