new graph bipartizations for double-exposure, bright field alternating phase-shift mask layout
We describe new graph bipartization algorithms for lay-out modification and phase assignment of bright-field alternating phase-shifting masks (AltPSM) [25]. The problem of layout modification for phase-assignability reduces to the problem of making a certain layout-derived graph bipartite (i.e., 2-colorable). Previous work [3] solves bipartization optimally for the dark field alternating PSMregime. Only one degree of freedom is allowed (and relevant) for such a bipartization: edge deletion, which corresponds to increasing the spacing between features in order to remove phase conflict. Unfortunately, dark-field PSM is used only for contact layers, due to limitations of negative photoresists. Poly and metal layers are actually created using positive photoresists and bright-field masks. In this paper, we define a new graph bipartization formulation that pertains to the more technologically relevant bright-field regime. Previous work [3] does not apply to this regime. This formulation allows two degrees of freedom for layout perturbation: (i) increasing the spacing between features, and (ii) increasing the width of critical features. Each of these corresponds to node deletion in a new layout-derived graph that we define, called the feature graph. Graph bipartization by node deletion asks for a minimum weight node set A such that deletion of A makes the graph bipartite. Unlike bipartization by edge deletion, this problem is NP-hard. We investigate several practical heuristics for the node deletion bipartization of planar graphs, including one that has 9/4 approximation ratio. Computational experience with industrial VLSI layout benchmarks shows promising results.
graph layout algorithm assignment relevance feature order conflict layer posit paper critic practical heuristics planar graph approximation computation experience industrial benchmark