An Algorithmic Study of Exact Route Matching for Integrated Circuits

As system-on-chip designs are getting more popular, the importance of design automation for analog and mixed-signal integrated circuits 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 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 and heuristic search algorithms to solve the min-cost route matching problem. We also discuss various practical considerations related to this problem. Our experimental results show the effectiveness of our algorithms.