A systematic framework for evaluating standard cell middle-of-line (MOL) robustness for multiple patterning

Xiaoqing Xu, Brian Cline, Greg Yeric, Bei Yu, David Z. PanProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2015 · DOI

TL;DR

This paper introduces a systematic framework to evaluate the robustness of standard cell designs for advanced lithography techniques like triple and quadruple patterning, specifically focusing on Middle-Of-Line (MOL) layers. By developing efficient N-wise checks and a novel cell sequence reduction method, they enable more tractable analysis of complex inter-cell interactions, crucial for ensuring design manufacturability at the 10nm node and beyond.

What Problem Does This Paper Address?

As semiconductor manufacturing pushes to smaller technology nodes (like 10nm and below), traditional lithography techniques struggle to resolve the fine features required. Multiple Patterning (MP) techniques, such as triple patterning (TP) and quadruple patterning (QP), are employed to overcome these limitations. However, MP introduces complex design rules that extend beyond individual cells, creating interactions across cell boundaries. This is particularly challenging for Middle-Of-Line (MOL) layers, which are critical for intra-cell routing. Existing methods for checking design rule violations (DRCs) are often limited to pairwise checks and struggle with the N-wise interactions (interactions involving more than two cells) that MP necessitates. This makes it difficult for standard cell (SC) designers to ensure their library cells are robust and compatible with MP constraints, especially when the exact placement of cells is unknown during library design. The paper aims to bridge this gap by providing a systematic framework to evaluate library-level robustness against MP constraints.

Methods

The authors propose a multi-stage framework:

  1. Cell Sequence Construction and Size Reduction: To manage the combinatorial explosion of N-wise checks, they first define a "cell sequence" as a set of abutting cells. They then introduce a "redundancy graph" to identify and eliminate redundant cell sequences. This is crucial because if a larger cell sequence is compatible with MP rules, any subset of it will also be compatible. A divide-and-conquer approach is used to make this process computationally feasible for large libraries.
  2. Multi-Row Cell Compatibility Checking: This stage involves building and checking combinations of cells across multiple rows. They focus on "two-row cells" (combinations of independent cell sequences from adjacent rows) and then "multi-row cells" (randomly generated benchmarks spanning multiple rows).
  3. Elementary k-Patterning Checker: A checker is developed to determine the k-colorability of the conflict graph derived from the layout. This checker performs iterative vertex removal, clique detection, and backtrack coloring to identify MP DRC violations.
  4. Cell Shifting Histogram: To evaluate the placement-level effort required to reduce QP to TP, they generate random multi-row benchmarks and simulate cell shifting. This histogram quantifies how many placement pitches a cell needs to be shifted to resolve local conflicts (specifically, 4-cliques in the context of TP).

Datasets

The framework was evaluated on two benchmark datasets:

  • An ARM representative 10nm standard cell library (116 logic cells).
  • The NanGate 15nm open cell library (76 logic cells), modified to combine MOL layers.

The paper also describes the generation of random multi-row benchmarks for full chip interaction analysis.

Key Insights and Ideas

  • N-wise Checks are Essential: The paper strongly emphasizes that traditional pairwise checks are insufficient for MP, and N-wise interactions (especially 3-cell and beyond) are the source of many violations.
  • Redundancy is Key to Tractability: The concept of cell sequence redundancy is a critical insight. By identifying that larger, compatible sequences imply compatibility for their subsets, the authors significantly reduce the number of checks needed.
  • Local Conflicts Drive QP Needs: For the CA layer in the studied technologies, the need for QP (instead of TP) is primarily driven by local conflicts (specifically, 4-cliques) arising from row-to-row interactions.
  • Cell Shifting as a Placement Strategy: The cell shifting histogram provides a valuable metric for placement tools, indicating the effort required to achieve TP-friendly layouts by resolving local conflicts. This directly relates to reducing QP to TP, which can save a mask.
  • Special Constructs Matter: The presence of "special constructs" in standard cells can lead to non-local conflicts, making TP DRCs intractable. Removing these constructs can simplify the problem and make TP feasible.

Key Results

  • The proposed framework significantly reduces the number of cell sequences to check, enabling efficient evaluation of library robustness. For example, the number of 3-cell sequences was reduced from billions to millions.
  • The framework successfully identified that QP is often required due to local conflicts on the CA layer, while TP is feasible when special constructs are absent.
  • For the NanGate library (without special constructs), all multi-row cells passed QP DRCs, and TP DRCs were also manageable.
  • For the ARM library (with special constructs), TP DRCs for larger multi-row cells became intractable due to large graph sizes, highlighting the impact of these constructs.
  • The cell shifting histogram demonstrated that for libraries without special constructs, a significant percentage of cells could be placed within a preferred region (requiring minimal shifting) to resolve local 4-cliques, suggesting that reducing QP to TP is achievable with reasonable placement effort.

Limitations and Future Work

  • Computational Complexity: While the framework significantly reduces complexity, the N-wise checks can still be computationally intensive for very large N or complex layouts. The paper mentions using a graph node size bound and iteration bound as approximations.
  • Specific Technology Focus: The work focuses on the CA layer of 10nm/15nm technologies. While the framework is adaptable, specific findings might vary for other MOL layers or technologies.
  • Future Work: The authors suggest that further work could explore optimizing the cell shifting histogram to improve placement efficiency and reduce area penalty. They also imply that extending the framework to other MP layers beyond MOL would be valuable. The paper also hints at the need for designers to increase utilization rate and the percentage of cells in the preferred region at the standard cell library level to improve overall robustness.

Summary updated

Abstract

Multiple patterning (triple and quadruple patterning) is being considered for use on the Middle-Of-Line (MOL) layers at the 10<i>nm</i> technology node and beyond.<sup>1</sup> For robust standard cell design, designers need to improve the inter-cell compatibility for all combinations of cells and cell placements. Multiple patterning colorability checks break the locality of traditional rule checking and N-wise checks are strongly needed to verify the multiple patterning colorability for layout interaction across cell boundaries. In this work, a systematic framework is proposed to evaluate the library-level robustness over multiple patterning from two perpectives, including illegal cell combinations and full chip interactions. With efficient N-wise checks, the vertical and horizontal boundary checks are explored to predict illegal cell combinations. For full chip interactions, random benchmarks are generated by cell shifting and tested to evaluate the placement-level efforts needed to reduce the quadruple patterning to triple patterning for the MOL layer.
BibTeX
@inproceedings{xu2015systematic,
  author = {Xiaoqing Xu and Brian Cline and Greg Yeric and Bei Yu and David Z. Pan},
  title = {{A systematic framework for evaluating standard cell middle-of-line (MOL) robustness for multiple patterning}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2015},
  doi = {10.1117/12.2085918},
}

Loading related content...

Figure