EasyMRC論文を読んで、MRCツールをC++で実装する話
最近、香港中文大学とTsinghua大学の研究者たちが発表した論文「EasyMRC: Efficient Mask Rule Checking via Representative Edge Sampling」を見かけて、なんか面白そうだな...と思ったんです。
正直なところ、マスクルールチェックについてはあんまり知らないんですけど、このアルゴリズムの考え方が面白そうだったので、背景から勉強し直してみることにしました。理解するのも込みで、論文を読んで学んだことをまとめてみます。
参考論文
- タイトル: EasyMRC: Efficient Mask Rule Checking via Representative Edge Sampling
- 著者: Jiahao Xu, Zhuolun He, Shuo Yin, Yuan Pu, Wenjian Yu, Bei Yu
- 出版: ACM Trans. Des. Autom. Electron. Syst., Vol. 30, No. 3, Article 47 (April 2025)
- DOI: https://doi.org/10.1145/3723044
- ライセンス: Creative Commons Attribution 4.0 International License
まず、背景を説明します
フォトリソグラフィとOPC
半導体チップを製造する過程で、フォトマスク（光学マスク）が使われます。設計データから実際のマスクを作る際に、光学的な回折や収差の影響を補正する必要があります。これを Optical Proximity Correction（OPC） と呼びます。
OPC を施されたマスクは、当初の矩形的な形状ではなく、複雑で不規則な曲線形状を持つようになります。
なぜマスクルールチェック（MRC）が必要か
OPC 後のマスクが実際に製造できるか確認するため、マスクルールチェック（MRC） という検査が必要です。これは：
- パターン間の最小間隔が基準を満たしているか
- パターンの最小幅が基準を満たしているか
- その他の製造規則に違反していないか
...を確認する処理です。
DRC（Design Rule Check）と似ていますが、重要な違いがあります。
DRC と MRC の違いを理解する
論文を読んでて、まず理解する必要があったのが、DRC と MRC の違いです。
DRC（Design Rule Check）とは
従来の設計ルールチェック。半導体設計データが、製造可能かを確認する処理です。
- パターンが矩形的
- 辺が水平・垂直方向のみ
- チェックが比較的単純
MRC（Mask Rule Check）とは
OPC が施された後のマスクパターンをチェックする処理。ここが複雑なんです。
- OPC により不規則な曲線形状になる
- 辺が任意の角度で存在
- ジグザグ形の複雑な輪郭が大量に存在
- 全方向で距離チェックが必要
つまり、従来の DRC ツールをそのまま MRC に使うと、計算量が膨大になってしまうんですね。
EasyMRC の革新：Representative Edge Sampling
この論文の新規性は、Representative Edge Sampling（代表的なエッジサンプリング） という手法です。
基本的な考え方
ジグザグ形の複雑な輪郭から、本当に重要なポイントとエッジだけを抽出する。そうすることで：
- 図形の輪郭は依然として正確に把握できる
- チェック対象のエッジが大幅に削減される
- 全違反を見落とさない
具体的な仕組み
- サンプリング半径 r の定義 → 平均エッジ長 l の 4 倍 (r = 4l) が推奨
- 代表点の選択 → 各ポリゴンの頂点をスキャン、r 以上離れた次の点を代表点として選択
- シールド領域 → 代表点から r 以内のポイント・エッジは、その代表点に「シールド」される
- 拡張ルール → R' = R + 2r として、シールド領域内の違反を見落とさない
数学的に正確性を保証する
論文では Theorem 1, 2 で、サンプリング後でも全ての違反が検出されることを証明しています。具体的には、違反は 2 つのカテゴリに分かれます：
- (a) 型違反 → 2つの代表点間の距離違反
- (b) 型違反 → 代表点と代表エッジ間の距離違反
カスタマイズされた Sweepline アルゴリズムが、この両方を確実に検出します。
Sweepline アルゴリズムによる実装
EasyMRC では、古典的な Sweepline アルゴリズム を MRC 用にカスタマイズしています。
処理フロー
- フォーマット変換 → OPC後の画像をGDSIIフォーマットに変換
- 候補ペア生成 → スペースチェックの場合、候補ペアを事前抽出
- サンプリング → 代表点・代表エッジを抽出
- Sweepline実行 → 型(a)と型(b)の違反を検出
- 結果報告 → 違反位置をレポート
計算量
- フォーマット変換: O(m) (m: ピクセル数)
- サンプリング: O(N) (N: 頂点総数)
- Sweepline: O(n log n) (最適ケース)
実際には、R/l と r/l が小さい定数と見なせるため、従来の DRC に比べて大幅に高速化されます。
実験結果：驚異的な高速化
論文のベンチマーク結果を見てください。
スペースチェック
- 小規模マスク (Mask1～10): 平均 106 倍高速化
- 大規模マスク (Active, Metal, Poly, Via): 平均 442 倍高速化
- フルチップサイズ (CPU0, CPU1): 平均 404 倍高速化
従来ツール (KLayout) との比較で、こんなに違うんです。
ウィジェットチェック
- 小規模: 平均 46 倍
- 大規模: 平均 96 倍
- フルチップ: 平均 177.2 倍
僕が C++ で実装してみてる進捗
この論文の内容を理解するために、実装してみることにしました。「論文を読む」だけじゃなくて、「実装してみる」と、ぐっと理解が深まると思うんです。
現在の状況
実装済み：
- GDSII フォーマット変換の基本（画像 → ポリゴン）
- ポリゴン・エッジ・頂点の基本データ構造
- サンプリングアルゴリズムの基本実装
開発中：
- Sweepline アルゴリズムの詳細実装
- 型(a)違反、型(b)違反の検出処理
- エラーハンドリングと検証
実装で気づいたこと
- 論文と実装のギャップ → 理論的には「こういうアルゴリズムだ」と書いてあっても、実装では細かい判定が必要で難しい
- 幾何学的な精度 → 浮動小数点演算の誤差が意外と大事
- データ構造の工夫 → メモリ効率と計算速度のバランス
課題
正直なところ、Sweepline の詳細な実装が複雑です。特に、型(a)と型(b)の違反を正確に分ける部分。
でも、そこがちょうどいい学習になっていて、「論文にはこう書いてあるけど、どうやって実装するんだ？」って考えながら、コードを書く。その過程が面白いんですよね。まだまだ公開するには時間がかかりそうですが、進捗報告していきます。
次のステップ
- Sweepline 実装の完成 → 今月中に型(a), (b) 両方完成させたい
- テストベンチマーク → 論文の実験データを使って検証
- GitHub で公開 → 実装コードとドキュメントを整備して共有
- 進捗報告（定期更新予定） → Zenn でも随時更新します
最後に
この論文を読んで、実装してみて思うのは、面白い課題をちゃんと追求するってことの大事さですね。
最初は「何これ？」って感じだったんですけど、背景から理解して、アルゴリズムの考え方を読んで、実装してみると、段々と「あ、こういう考え方があるのか」って納得できる。
その過程で、計算幾何だとか、アルゴリズム設計だとか、C++ での実装だとか...いろんなスキルが必要になってくることに気づきます。
半導体業界で働いてると、こういう「面白い論文」に出会う機会があります。そういう時、ちゃんと「勉強してみるか」って動く人間になりたいな、って思ってます。
GitHub で進捗を公開していく予定なので、興味あれば見てもらえたら嬉しいです。
参考資料
- 論文: https://doi.org/10.1145/3723044
- 関連トピック: マスクデータ準備、OPC、GDSII、計算幾何学
次回は、実装の詳細について書きたいと思います。では！
Discussion