Redundant-via-aware ECO routing

Redundant via insertion (RVI) has become an inevitable means adopted in the routing or post-routing stage to enhance chip reliability and yield as feature size shrinks down to nanometer scale. The remaining routing resources, however, could become so limited after RVI, and make engineering change order (ECO) routing during a pre-mask stage or even a post-mask stage difficult to complete. In this paper, we study an ECO routing problem where redundant vias are present in the given layout but can be considered for replacement or removal to increase the routability and improve the routing quality. To find an ECO routing path, we construct only the necessary part of the routing graph on-the-fly, and develop an A* search based algorithm for achieving efficient path finding. We also take redundant via replacement, removal, and insertion into account when formulating the routing cost, and apply a state-of-the-art method to perform redundant via replacement and insertion. Experiments show that our algorithm not only successfully routes all test cases but also efficiently produces high-quality solutions.