Exact route matching algorithms for analog and mixed signal integrated circuits

As SOC designs are getting more popular, the importance of design automation for analog and mixed-signal ICs is increasing. In this paper, we study the problem of exact route matching, which is an important physical design constraint commonly imposed on specific analog signals for the purpose of correct analog functionality. For this, we first propose a mathematical formulation that models the route matching problem exactly. Based on this formulation, we derive important theoretical conclusions, and propose dynamic-programming algorithms to solve the problem. We also discuss how to use heuristic search techniques to enable faster computations. Our experimental results show the effectiveness of our algorithms.