Algorithms for Maze Routing With Exact Matching Constraints

Exact route matching is an important constraint for analog and mixed signal designs with nonuniform metal stacks. In this paper, we propose a constrained-path-based maze routing algorithm that can handle exact matching constraints for multiple nets. We also propose a scalable framework that utilizes the proposed maze routing algorithm for realistic problem sizes. Compared to the pattern routing algorithms proposed recently , our algorithms allow a more thorough exploration of the solution space by allowing bends to be inserted to avoid congested regions. Furthermore, we propose an ILP-based model to explore the impact of the initial routing topologies on the final solutions. Our experimental study demonstrates that the proposed algorithm leads to significant reductions in congestion costs compared to the previous algorithm.