A Method for Improving Cascode-Switch Macro Wirability

Abstract

In this paper, a problem in macro design using cascode-switch tree logic is studied. It involves selecting specific tree instantiations of Boolean functions and input variable assignments to maximize the alignment of variables between adjacent trees. An algorithm to find optimal solutions based on the principle of optimality is proposed. Although in general it is not a polynomial time algorithm, it runs sufficiently fast for our practical application. Finally we prove the problem is NP-complete, thus the existence of polynomial time algorithms is indeed unlikely. Copyright © 1985 by The Institute of Electrical and Electronics Engineers, Inc.