論文 / 著書情報
Article / Book Information
論題(和文)

半正定値計画緩和に基づく擬似スティッチを用いたTPLのためのレイアウト分割手法

Title(English)

Layout Decomposition Method by Positive Semidefinite Relaxationwith
Pseudo Stitch Edge for TPL

著者(和文)

半田昌平, 高橋篤司, 中田和秀, 松井知己

Authors(English)

Shouhei Handa, Atsushi Takahashi, Kazuhide Nakata, Tomomi Matsui

出典(和文)

第29回 回路とシステムワークショップ 論文集, , , pp. 214-219

Citation(English)

Proc. the 29th Workshop on Circuits and Systems, , , pp. 214-219

発行日 / Pub. date

2016, 5URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2016 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Tokyo Institute Research Repository)

第29回 回路とシステムワークショップ
The 29th Workshop on Circuits and Systems
in Kitakyushu, May 12-13, 2016

半正定値計画緩和に基づく擬似スティッチを用いた TPL のためのレイアウト分割手法

Layout Decomposition Method by Positive Semideﬁnite
Relaxation with Pseudo Stitch Edge for TPL
半田昌平 †
高橋篤司 ‡中田和秀 ††松井知己 †††東京工業大学 大学院 理工学研究科 通信情報工学専攻‡
東京工業大学 工学院 情報通信系††
東京工業大学 工学院 経営工学系

Shohei Handa†
Atsushi Takahashi‡
Kazuhide Nakata††
Tomomi Matsui†††
Department of Communications and Computer Engineering, Tokyo Institute of Technology‡
Department of Information and Communications Engineering, Tokyo Institute of Technology††
Department of Industrial Engineering and Economics, Tokyo Institute of Technology
1

はじめに今日まで集積回路の微細化はムーアの法則に沿って進んできた．今後，超微細な集積回路製造において
Extreme Ultra-Violet Lithography (EUVL) [1] やElectric Beam Lithography (EBL) [2] などの次世代リソグラフィー技術が期待されているが，これらには未だ課題が残っており，量産で用いるには至っていない．そのため現在の光リソグラフィー技術で集積回路の微細化を実現させるために，回路のレイアウトパターンを複数回に分けてウエハ上に形成するマルチパターニング技術が注目されている．

1 つである露光工程を 3 回繰り返しレイアウトパターンを形成するトリプルパターニングリソグラフィー(Triple Patterning Lithography (TPL)) に着目する．
TPL には，最後の露光工程をパターンの除去に用いる LELECUT [8, 9, 10] と呼ばれる方法もあるが，本稿では，パターンを逐次的に形成する，より一般的な Litho-Etch Litho-Etch Litho-Etch (LELELE) を対象とする．

本稿では，ウエハ上に形成したいレイアウトパターンがポリゴン集合として与えられたとき，各露光工程で形成するレイアウトに対応するように，ポリゴマルチパターニング技術の中で，側壁プロセスを利 ン集合を 3 分割するレイアウト分割問題を考える．本用する Self-Aligned Double-Patterning (SADP) や 稿で扱うレイアウト分割では，レイアウト分割によっ
Self-Aligned Quadruple-Patterning (SAQP) などは， て解決した違反数と不採用のスティッチ数の重み付き露光工程を用いてウエハ上に形成した芯材を加工して 和を分割の品質を表す目的関数とし，その最大化をレイアウトパターンを形成する．効率よく SADP や 目指す．この分割問題は一般に NP 困難である [11]．
SAQP で製造可能なレイアウトパターンを生成する
このレイアウト分割問題を，Yu らはベクトル計画手法は提案されているが，SADP や SAQP で任意の 2 法で定式化し，その半正定値計画 (SDP) 緩和により次元パターンを実現できるわけではない [3, 4, 5, 6, 7]． 得られるポリゴンの超球面上へ配置からレイアウト一方，複数回の露光工程でレイアウトパターンを逐次的にウエハ上に形成する Litho-Etch Litho-Etch(LELE) などは，微細化の実現のために各露光工程で形成するパターン間の位置合わせの精度を向上させる必要があるものの，より複雑な 2 次元パターンを実現可能である．本稿では，14 nm/10 nm ノードのプロセス作成において最も有力視されている技術の分割を得る発見的手法を提案した [11]．松井らは，超球面を確率的丸め法 (Randomized Rounding (RR))
で分割することでポリゴンの超球面上へ配置からレイアウト分割を得る近似比 7/9 の近似手法を提案した [12]．しかし, 一般的な SDP ソルバでは，違反を持たないポリゴン対は超球面上で離れて配置され，違反が十分少ない分割が，確率的丸め法 (RR) で得ら－ 214 －れない傾向があった．
そこで，我々は，違反を持たない対の超球面上での距離を減少させる補正項を，擬似的なスティッチとして SDP 緩和の目的関数に加える方法を提案した[13]．しかし，擬似的なスティッチを用いた緩和問題に確率的丸め法 (RR) を適用したのちに残る未解決の違反やスティッチの数は依然として多い．
そこで，本稿では，初期分割を擬似的なスティッチを用いた緩和問題に確率的丸め法 (RR) を適用して得たのち，初期分割に含まれる未解決の違反や採用されているスティッチを減少させるために，FM アルゴリズム [14] をベースとした逐次改善手法を追加したレイアウト分割手法を提案する．
本稿の構成は以下のとおりである．まず 2 節で準備として必要な語句や記号を定義する．3 節で半正定値計画緩和による問題の定式化と確率的丸め法 (RR) について説明する．4 節で緩和問題に擬似スティッチを加える手法について説明し，続く 5 節で疑似スティッチ辺を用いた場合の効果を示す．6 節では得られた分割の緩和問題最適解との乖離度を定義する．7 節で評価値改善のための提案手法について説明し，続く 8 節で計算機実験の結果を示す．最後に 9 節でまとめる．

2

準備

ウエハ上に形成したいレイアウトパターンがポリゴン集合として与えられ，各露光工程で形成するレイアウトに対応するようにポリゴン集合を分割するとき，近接するポリゴン対が同一分割に割り当てられると，その分割は 1 回の露光工程で形成できない可能性がある．そのため，ポリゴン分割は，1 回の露光工程では形成できない近接するポリゴン対を含んではならない．
以下では，1 回の露光工程では形成できないポリゴン対を違反と呼び，ポリゴンが異なる分割に割り当てられたとき，違反を含まない，解決した，という．また，あるポリゴンをスティッチで分割し複数回に分けて形成することもできる．ただし，スティッチによるポリゴン分割は，露光工程間の合わせズレの影響による歩留り低下の大きな要因となるため，違反を解決するために用いることはできるが，できるかぎり用いないほうが好ましい．以下では，スティッチ候補で分割されているポリゴンを考え，レイアウ
ト上でスティッチ候補で接するポリゴン対をスティッチと呼び，ポリゴンが同じ分割に割り当てられたとき，スティッチ含まない，不採用という．

レイアウト設計段階では，すべての違反が解決可能なレイアウトパターンが与えられるとは限らない．
違反を含まないレイアウト分割や質の良いレイアウ
ト分割が得られなかった場合には，レイアウト修正を行うことになる．レイアウト修正を最小限に抑えるために，できる限り違反とスティッチが少ない分割を得ることが求められる．
本稿では，ポリゴン集合を 3 分割するレイアウト分割問題を考える．レイアウトパターンを構成するポリゴンの集合を V = {v1 , v2 , . . . , vn }，違反の集合
を C(⊆ V × V ) スティッチの集合を S(⊆ V × V ) とする．ポリゴン集合 V の 3 分割は，c : V → {1, 2, 3}で表す．分割を彩色で表すこととすると，3 分割 c において，ポリゴン v の色が i のとき，c(v) = i となる．
3 分割 c において，ポリゴン u ∈ V とポリゴンv ∈ V は，{u, v} ∈ C かつ c(u) = c(v) とのきかつそのときに限り違反するといい，u と v が異なる分割に割り当てられたとき，違反 {u, v} を含まない，解決した，という．同様に，{u, v} ∈ S かつ c(u) = c(v)とのきかつそのときに限りスティッチ {u, v} は採用されているといい，u と v が同じ分割に割り当てられたとき，スティッチ {u, v} を含まない，不採用，という．
ポリゴン集合 V を点集合，違反集合 C を辺集合とするグラフ G = (V, C) を違反グラフと呼ぶ．

3半正定値計画緩和による問題定式化

3 分割 c で解決した違反と不採用のスティッチは，それぞれ
def

CE(c) = {{u, v} ∈ C | c(u) = c(v)},defSE(c) = {{u, v} ∈ S | c(u) = c(v)}となる．レイアウト分割問題は，α を定数としたとき，解決した違反と不採用のスティッチの最大化問題として，以下のように問題 P1 と定式化できる．

P1 : maximize |CE(c)| + α|SE(c)|subject toc(v) ∈ {0, 1, 2}(∀v ∈ V )．
また，3 分割 c に対し，ベクトル x をdef⎧⎪(1, 0)
⎪⎪√ ⎨ − 12 , 23x(v) =⎪√ ⎪⎪⎩ −1, − 3 22(c(v) = 0),(c(v) = 1),(c(v) = 2)とすると，任意の u, v ∈ V に対して，－ 215 －1c(u) = c(v) ↔ x(u) x(v) = − ,2c(u) = c(v) ↔ x(u) x(v) = 1となる．したがって，レイアウト分割問題は，以下のようにベクトル計画法で問題 P2 と定式化できる．

P2: max .

回繰り返し，得られた最良解を出力した．このとき，得られる解の評価の期待値は最適解の 7/9 以上となる [12]．

−2x(u) x(v)+ 23{u,v}∈C3
+α {u,v}∈S 2x(u)3 x(v) + 13
√  √ (1, 0) , − 21 , 23 , − 12 , − 234擬似スティッチ辺による超球面配置の改善

松井らの手法では，問題 SDP の最適解に対して，確． 率的丸め法 (RR) を適用したときの解の評価の期待値は，最適解の 7/9 以上となる [12]．しかし，確率行列 X は，(u, v) 要素 Xuv が x(u) x(v) であると的丸め法 (RR) を適用したとき期待値が大きい超球
き半正定値行列となることを利用して，上記の問題
面上の配置と，最大値が大きい超球面上の配置は異P2 は半正定値計画問題として定式化できる．この半なる可能性があり，期待値を増大させることは，最正定値計画問題において x の値域を緩和することで，大値の増大につながらないかもしれない．
レイアウト分割問題は以下のように半正定値計画緩主双対内点法に基づく一般的な SDP ソルバは，最和問題 SDP と定式化できる．
[15]．違適解集合の解析的中心を解として出力する−2Xuv2+3SDP: max .
反を持たないポリゴン対の超球面上での大円距離は，{u,v}∈C
32Xuv
1SDP 緩和の目的関数に直接は影響しない．したがっ+α {u,v}∈S
3 + 3て最適解集合の解析的中心では超球面上で，違反をs.t. Xuv ≥ − 12 (∀ (u, v) ∈ V 2 ),持たないポリゴン対は一般には離れている．
Xvv = 1(∀v ∈ V ),s.t. x(v) →n．
X ∈ S+n は，すべての対称半正定値 n × n 行列のただし，S+集合である．レイアウト分割問題は，NP 困難である
が，その半正定値計画緩和問題 SDP は，多項式時間で解くことができる [11, 12]．
問題 SDP の最適解として得られる半正定値行列∗X を (M ∗ ) M ∗ とコレスキー分解し，行列 M ∗ の各列成分をポリゴン v と対応したベクトル x∗ (v) とする．ベクトル x∗ (v) は単位 d 次元超球面上に分布するが，問題 P2 の制約条件を必ずしも満たさないため，ベクトル x をそのまま 3 分割とすることはできない．ベクトル x から，Yu ら [11] は発見的手法を用いて，松井ら [12] は確率的丸め法 (RR) を用いて，それぞれ 3 分割を得た．
確率的丸め法 (RR) では，単位ベクトルをランダムに生成し，生成したベクトルと直行する超平面で超球を分割することで，超球の表面に分布するベクトルを分割する．単位ベクトルの生成，および，生成した単位ベクトルによる超球面分割は，問題 SDP の解を得るための時間に比べ短い．確率的丸め法 (RR)
では，一般に超球面分割を繰り返し，得られた最良解を出力する．
松井らは，2 つの超平面を利用して，超球面を 4 分割したのち，2 つの分割を縮退することでことで 3 分割を得た．縮退の方法は 4 通りあるが，その中で評価が最大の縮退を選んだ．また，超球面分割を複数そのため，ある 2 辺 {u, w}, {y, z} ∈ C を考えたとき，u = y で {u, y} ∈ C であるならば，u と y の超球面上での大円距離は大きくなる傾向にある．すな
わち 2 辺 {u, w}, {y, z} の超球面上での最大大円距離は大きくなる傾向にある．このとき，u と y は確率的丸め法 (RR) で異なる分割に属す可能性が高くな
り，2 辺 {u, w}, {y, z} が同時に解決される可能性は低くなる．他の点対，例えば，w と z についても同様の議論ができる．

2 辺の超球面上での最大距離を減少させれば，その 2 辺に対応する違反が同時に解決され，分割の評価の最大値を増加させる可能性がある．しかし，2 辺を接近させる操作が，他の辺に関する評価を悪化させる可能性もあるので，大域的に良い評価を得るた
めには，最大距離を減少させる 2 辺を適切に選ぶ必要がある．
そこで，我々は，違反グラフ上で距離が 2 である点対間に重みの小さい擬似的なスティッチ辺を，目的関数の補正項として加える手法を提案した [13]．すなわち，{u, w}, {u, z} ∈ C ，{w, z} ∈ C の関係にある異なる 3 点 u, w, z に着目し，隣接しない 2 点 w, zの大円距離を減少させることで，2 辺 {u, w}，{u, z}が，確率的丸め法 (RR) で同時に解決される確率を増大させる．
レイアウト分割問題は提案の擬似スティッチ辺を用いた半正定値計画緩和問題 SDP-m は以下のよう－ 216 －

分割の緩和問題最適解からの乖離度6
表 1: 星形グラフによる評価

グラフ

|C|

内積SDP SDP-mS50
S100
S200
S3004999199299

0.254
0.269
0.264
0.257

1111|CE|SDP SDP-m
7013
0250390に定式化される．

s.t.





−2Xuv
+ 233+α {u,v}∈S 2X3uv + 13+ε {u,v}∈P 2X3uv + 31Xuv ≥ − 12 (∀(u, v) ∈ V 2 ),SDP-m: max .

Xvv = 1n.
X ∈ S+{u,v}∈C⎧⎪⎨⎩(∀v ∈ V ),擬似スティッチ辺の効果

1cXuv
=−0.5
⎪

0

if {u, v} ∈ C and c(u) = c(v),if {u, v} ∈ C and c(u) = c(v),if {u, v} ∈ C.

次に，行列 X c と緩和問題の最適解 X ∗ の差行列 Dcを以下のように定義する．

ただし，P は違反グラフ上で距離が 2 である点対の集合を表し，ε は，擬似スティッチの重みを表す．αと ε は，ともに違反の解決を阻害しないよう十分小さな値とする．

5

擬似的なスティッチを用いた定式化 SDP-m に確率的丸め法 (RR) を適用することで，既存定式化 SDPによる手法よりも良いレイアウト分割を得ることができる．しかし，未解決の違反やスティッチの数は依然として多い．そのため，よりよい 3 分割を得るために，緩和問題の最適解をもとに，解を探索することを考える．このとき緩和問題の最適解の性質を受け継いだ解を中心に探索することで，よりよいレイアウト分割を得られる可能性が高くなると考えるのは自然であろう．そこで，3 分割 c の緩和問題の最適解 X ∗ からの乖離度を定義し，解の探索に利用する．
まず，3 分割 c により定義される行列 X c を以下のように定義する．

cDuv=∗ − X c | if {u, v} ∈ C,|Xuvuv
0if {u, v} ∈ C.

3 分割 c の緩和問題の最適解 X ∗ からの乖離度を
c とする．
D(c) = V ×V Duv
SDP の最適解 X ∗ は必ずしも一意に定まらないが，本稿では SDP ソルバとして SDPA[16] を用いて求められた解を X ∗ としている．

中心点 v1 と葉からなる n 点の木，すなわち，点集合{v1 , v2 , . . . , vn }，辺集合 {{v1 , vj } | 2 ≤ j ≤ n} から 7 提案手法なるグラフを星形グラフ Sn と呼ぶ．違反グラフが，擬似的なスティッチを用いた緩和問題に確率的丸め星形グラフの場合には，中心点と他の点に分割にす
法 (RR) を適用したのちに残る未解決の違反や採用れば，すべての違反は解決できる．
されているスティッチ数を減少させるために，FM アスティッチ集合 S = ∅ で違反グラフが星形グラフ
ルゴリズム [14] をベースとした逐次改善手法を提案の場合に，既存の定式化 SDP および，提案の定式する．
化 SDP-m によりポリゴンを超球面上に配置したと提案手法 SDP-m-FM では，擬似的なスティッチ
き，任意の 2 辺のなす内積はそれぞれすべて一致しを用いた緩和問題 SDP-m により，超球面上にポリた．表 1 に超球上で違反グラフの 2 辺のなす内積，おゴンを配置し，確率的丸め法 (RR) で得られるポリよび，確率的丸め法 (RR) で 10 回分割した場合の未ゴン分割の中から，乖離度 D(c) が最小の 3 分割 c を解決の違反数を示す．SDP-m では，擬似スティッチ初期解とし，乖離度を考慮しながら FM アルゴリズの重みは ε = 0.04 とした．
ムをベースとした逐次改善を施す．提案手法を図??
従来の定式化 SDP では，10 回の分割では最適分 に示す．
割が得られないのに対し，提案の定式化 SDP-m では，すべての葉が超球面上の同一点に配置され，2 辺 8 実験結果の内積が 1，すなわち，最大距離が 0 となり，確率的 本節では，計算機実験を通して提案手法の評価を行丸め法 (RR) で最適な分割が得られた．
う．プログラムは C++で記述し SDP ソルバは SDPA

－ 217 －

Algorithm 1 SDP-m-FM
1: SDP-m を解き，X ∗ を求める．
2: 確率的丸め法 (RR) を適用し，評価値と関係なく乖離度 D(c) が最小の分割を解 c とする．
3: 解 c を「現在までの最良解」として記録する．
4: while 「現在までの最良解」が更新される do
5:
Dc の行と列に対応する点がともに固定されている成分を除く最大の成分を Duv とする．
6:
u と v の一方の点が固定されていたら，他方の点を k とする．両方とも固定されていなければ，対応する D の列の L1 ノルムが他方に比べ小さくない点を k とする．
7:c(k) を c(k) + 1 mod 3 もしくは，c(k) + 2 mod3 に変更し，D を更新する．ただし，評価が他方に比べ低くならない変更を選択する．
8:k を固定する．
9:「現在までの最良解」よりも良い解が得られたら「現在までの最良解」を更新する．
10: end while
11: 「現在までの最良解」を出力する．

図 1: 初期解 c の乖離度 D と逐次改善の効果の関係

D(c) と逐次改善後の評価の関係を調べた．図 1 に，その関係を示す．図の横軸は確率的丸め法 (RR) で得た 3 分割の乖離度，縦軸は逐次改善後の評価値である．乖離度が小さいとき，よりよい 3 分割が逐次改善により得られる傾向にあることがわかる．乖離度
D(c) が小さい分割を初期解としたとき，よりよい 3分割が逐次改善により得られる可能性が増大することを実験的に示している．

9 まとめ[16] を用いた．計算機は 2.40 GHz の CPU×2，メモ
リ容量 16 GB の Linux マシンを用いた．実験データ 本稿では，既存の半正定値計画緩和を用いたレイア
は，ISCAS85 ベンチマークをもとに作成されたレイ ウト分割手法に対し，擬似的なスティッチ辺を加えるアウトパターンに対応する違反グラフを用いた．ス ことで確率的丸め法 (RR) で得るレイアウトの初期ティッチ候補は定義されていないため，評価には不採 分割を改善し，緩和問題の最適解からの乖離度を考用のスティッチ数は含まない．確率的丸め法 (RR) に 慮して初期分割を逐次改善する手法を提案した．今よるレイアウト分割は各手法ですべて 10 回とした． 後の課題としては，スティッチ候補を含むレイアウ
SDP-m では，擬似スティッチの重みは ε = 0.04 と トパターンを用いた実験と評価とともに，大きなレした．実験結果を表 2 に示す．
イアウトパターンに対して，効率的にレイアウト分
SDP，SDP-m，SDP-m-FM はそれぞれ，既存 割を得る手法の考案があげられる．の定式化 SDP 確率的丸め法 (RR) を適用した手法，謝辞
提案の定式化 SDP-m に確率的丸め法 (RR) を適用した手法，提案の定式化 SDP-m に確率的丸め法 (RR) 本研究は JSPS 科学研究費補助金基盤研究 (B)25280013を適用しさらに逐次改善を行った手法を示す．|C| と の助成を受けたものである.
|CE| はそれぞれ違反数と未解決の違反数を示す．表 参考文献
2 より，SDP に比べ，SDP-m は未解決の違反数が[1] Y. Du, H. Zhang, M.D.F. Wong, and R.O.
平均 85.6%に減少し，逐次改善まで行った SDP-mTopaloglu, “EUV mask preparation considering
FM は平均 0.01%以下に減少していることが分かる．
blank defects mitigation,” Proc. SPIE, Photomask
実行時間は，SDP に比べ，SDP-m は平均 21.6%のTechnology 2011, 2011.
増加し，逐次改善まで行った SDP-m-FM は平均[2] Y. Du, H. Zhang, M.D.F. Wong, and K.Y. Chao,204%ほど増加している．
次に，確率的丸め法 (RR) で得た初期分割 c の選択に乖離度 D(c) を用いることの効果を確認するために，ISCAS-85 ベンチマークの c432 を用いて乖離度－ 218 －

“Hybrid lithography optimization with E-beam andimmersion processes for 16nm 1D gridded design,”
Proc. Asia and South Paciﬁc Design Automation
Conference (ASP-DAC), pp.707–712, 2012.

表 2: 実験結果
グラフ

c432
c499
c880
c1355
c1908

|C|
12222817
2686
3326
5597

SDP2525835777461225|CE|
SDP-m SDP-m-FM
179
4562
0521
7615
510743[3] C. Kodama, H. Ichikawa, K. Nakayama, T. Kotani,
S. Nojima, S. Mimotogi, S. Miyamoto, and A. Takahashi, “Self-aligned double and quadruple patterning aware grid routing with hotspots control,” Proc.
Asia and South Paciﬁc Design Automation Conference (ASP-DAC), pp.267–272, 2013.
[4] C. Kodama, H. Ichikawa, K. Nakayama, F. Nakajima, S. Nojima, T. Kotani, T. Ihara, and A. Takahashi, “Self-aligned double and quadruple patterning aware grid routing method,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol.34, no.5, pp.753–765, 2015.
[5] T. Ihara, A. Takahashi, and C. Kodama, “Rip-upand reroute based routing algorithm for self-aligneddouble patterning,” Proc. the 19th Workshop onSynthesis And System Integration of Mixed Information technologies (SASIMI), pp.83–88, 2015.
[6] T. Ihara, A. Takahashi, and C. Kodama, “Eﬀectivetwo-dimensional pattern generation for self-aligned
double patterning,” Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp.2141–2144, 2015.
[7] T. Ihara, T. Hongo, A. Takahashi, and C. Kodama, “Grid-based self-aligned quadruple patterning aware two dimensional routing pattern,” Proc.
Design, Automation and Test in Europe (DATE),
pp.241–244, 2016.
[8] Y. Kohira, T. Matsui, Y. Yokoyama, C. Kodama,A. Takahashi, S. Nojima, and S. Tanaka, “Fastmask assignment using positive semideﬁnite relaxation in LELECUT triple patterning lithography,”Proc. Asia and South Paciﬁc Design Automation
Conference (ASP-DAC), pp.665–670, 2015.
[9] Y. Kohira, C. Kodama, T. Matsui, A. Takahashi,
S. Nojima, and S. Tanaka, “Yield-aware mask assignment using positive semidenite relaxation inSDP
81.1
329.8
382.9
860.6
2843.7

実行時間 (秒)SDP-m SDP-m-FM

94.7
403.3
499.2
1026.73393.5121.6
646.5
1153.65101.310598.3

LELECUT triple patterning,” Proc. SPIE, DesignProcess-Technology Co-optimization for Manufacturability IX, pp.1–9, 2015.
[10] Y. Kohira, C. Kodama, T. Matsui, A. Takahashi,
S. Nojima, and S. Tanaka, “Yield-aware mask
assignment by positive semideﬁnite relaxation intriple patterning using cut process,” Journal of Micro/Nanolithography, MEMS, and MOEMS (JM3),
vol.15, no.2, 021207, 2016.
[11] B. Yu, K. Yuan, B. Zhang, D. Ding, and D.Z. Pan,
“Layout decomposition for triple patterning lithography,” Proc. IEEE/ACM International Conference
on Computer Aided Design (ICCAD), pp.1–8, 2011.
[12] T. Matsui, Y. Kohira, C. Kodama, and A. Takahashi, “Positive semideﬁnite relaxation and approximation algorithm for triple patterning lithography,” Proc. the 25th International Symposium
on Algorithms and Computation (ISAAC), LNCS
8889, pp.365–375, 2014.
[13] 半田昌平, 高橋篤司, 中田和秀, 松井知己, “半正定値計画緩和に基づく MPL レイアウト分割のための補正項,” 電子情報通信学会 総合大会 講演論文集 (A6-12), p.86, 2016.
[14] C.M. Fiduccia and R.M. Mattheyses, “A lineartime heuristic for improving network partitions,”
Proc. Design Automation Conference (DAC),
pp.175–181, 1982.
[15] 寒野善博, 大崎純, 室田一雄, 加藤直樹, “半正定値計画法に対する主双対内点法の群対称性,” 数理解析研究所講究録, pp.214–222, 2001.
[16] M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata,M. Fukuda, K. Kobayashi, and K. Goto, “A highperformance software package for semideﬁnite programs: SDPA 7,” Department of Mathematical andComputing Sciences, Tokyo Institute of Technology,
SERIES B: Operations Research, 2010.

－ 219 －