Abstract
When the manufacturing processes of integrated circuits shrink to deep submicron technologies, loss of yield caused by via defects becomes more significant. In order to improve via yield and reliability, redundant via insertion is highly recommend by foundries. In this thesis, we study the post-layout redundant via insertion problem while considering the resultant GDSII file size. We formulate this problem as a maximum weighted independent set (MWIS) problem, and present a heuristic to solve the MWIS problem. Moreover, since the cells described in the GDSII file format can be instantiated by reflecting and rotating, for efficiently identifying the directions where some redundant vias can be inserted simultaneously, we propose the idea of direction sequence to quickly query the relationship between the direction relative to an original single via in a structure and the direction relative to a corresponding flattened single via. Experimental results show that for almost all test cases, our algorithm can insert the maximum numbers of redundant vias while keeping the resultant GDSII file sizes to have small increases. On average the size of a resultant GDSII file generated by our algorithm is one fifth of the size of the GDSII file which is flattened.