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

半正定値計画緩和に基づくMPLレイアウト分割のための補正項

Title(English)

A correction term for positive semidefinite relaxation of MPL layout
decomposition

著者(和文)

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

Authors(English)

Shouhei Handa, Atsushi Takahashi, Kazuhide Nakata, Tomomi Matsui

出典(和文)

電子情報通信学会 2016年総合大会 講演論文集 (A-6-12), Vol. A, No. ,p. 86

Citation(English)

Proc. the 2016 IEICE General Conference (A-6-12), Vol. A, No. , p. 86

発行日 / Pub. date

2016, 3URL

http://www.ieice.org/jpn/books/t̲g.html

権利情報 / Copyright

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

Powered by T2R2 (Tokyo Institute Research Repository)

A-6-122016 年

電子情報通信学会総合大会

半正定値計画緩和に基づく MPL レイアウト分割のための補正項
A correction term for positive semidefinite relaxation of MPL layout decomposition
半田昌平 1
Shohei Handa

高橋篤司 1
Atsushi Takahashi

中田和秀 2
Kazuhide Nakata

松井知己 2
Tomomi Matsui

東京工業大学 大学院 理工学研究科 1 社会理工学研究科 2Graduate School of Science and Engineering1 , Decision Science and Engnieering2 , Tokyo Institute of Technology

まえがき
マルチパターニングリソグラフィ(MPL) では，1 回の露光でウエハ上に実現できる限界未満のレイアウト密度を，複数回の露光により達成する．このとき，ポリゴンの集合は各露光で実現される距離が小さく同時に実現できないポリゴン対（違反）を含んではならないが，レイアウト設計段階では，指定分割数で，違反がより少ない分割を得ることが求められる．
先行研究では，半正定値計画 (SDP) 緩和によりポリゴンを超球面上へ配置し，超球面を確率的丸め法 (RR)で分割することで, この分割を得る [1]．しかし, 一般的な SDP ソルバでは，違反を持たない対は超球面上で離れて配置され，違反が十分少ない分割が，RR で得られない傾向があった．
本稿では，RR により得られる分割で違反を減少させるために，違反を持たない対の超球面上での距離を減少させる補正項を, SDP 緩和の目的関数に加える方法を提案する．以下では，3 分割を例に説明する

1

先行研究
3 分割における違反数最小化は，ポリゴン集合を V ，違反集合を CE (⊆ V × V ) としたとき，ベクトル計画法を用いて次式で定式化される．
P→→
min: (i,j)∈CE 23 (−vi · −vj + 12 )n√√ o−→s.t.
vi ∈ (1, 0), (− 1 , 3 ), (− 1 , − 3 ) , ∀i ∈ V

22222

半径 1 の超球面上の配置に対応するポリゴンのベクト
ルは，SDP 緩和問題の解として得られる半正定値行列を，コレスキー分解することにより得られる．RR では，無作為に生成した 2 ベクトルにより超球面を 4 分割し，それを 3 つに縮退し 3 分割を得る．この RR を繰り返し，得られた最良解を解とする [1]．
提案手法
ポリゴンを点，違反を辺とした違反グラフの超球面への埋め込みで, ある辺が RR で分割される確率は，両端点の超球面上での大円距離に比例する．また，2 辺の最大距離が小さければ，同時に分割される可能性が高くなり最小値を減少させる可能性がある．主双対内点法に基づく SDP ソルバでは，隣接しない点対は超球面上で離2016/3/15 〜 18

福岡市

2

なお CT は違反グラフ上で距離が 2 である点対の集合である.

実験結果
実験には ISCAS-85 ベンチマークの回路を使用した.
補正項の重みは ε = 0.04, RR の回数は 10 回とし, SDPソルバは SDPA[2] を使用した.
表 1 より提案手法では違反数が平均 85.6%に減少した
ことがわかる. 一方, 計算時間は平均 21.6%増加した.

4

表1
Circuit 違反数
c432
c499
c880
c1355
c1908

2−vi の値は半径 1 の超球面上の 3 点のいベクトル変数 →
ずれかに対応し, ポリゴン集合は，ベクトル値に応じて3 分割される．上記は，以下のように SDP 緩和される．
P→→
min: (i,j)∈CE 23 (−vi · −vj + 12 )−→→→−vi = 1, ∀i ∈ V, −vi · −vj ≥ − 1 , ∀(i, j) ∈ CEs.t.
vi · →

3

れて配置され，2 辺の超球面上での最大距離は大きくなる傾向にある. 2 辺の超球面上での最大距離を減少させれば，その 2 辺に関する評価の最小値が減少する可能性があるが，他辺に関する評価を悪化する可能性もあり，最大距離を減少させる 2 辺を適切に選択する必要がある．
本稿では, 違反グラフ上である点に接続する 2 辺の最大距離を減少させるために，違反グラフ上での距離が 2である点対間の超球面上での大円距離を減少させる補正項を，目的関数に加える．
PP→→→→
min: (i,j)∈CE 23 (−vi · −vj + 12 )+ε (i,j)∈CT 23 (1− −vi · −vj )1−→−→−→−→s.t.
vi · vi = 1, ∀i ∈ V, vi · vj ≥ − , ∀(i, j) ∈ CT

1222
2817
2686
3326
5597

実験結果

残存違反数time(秒)
既存
提案
既存
提案
252 179(71.0%)
81.1
94.7
583 562(96.4%) 329.8 403.3
577 521(90.3%) 382.9 499.2
746 615(82.4%) 860.6 1026.7
1225 1074(80.7%) 2843.7 3393.5

むすび
本稿では目的関数に補正項を加えることで違反数を減らす手法を提案した. 違反数を更に減らすための逐次改善手法の考案などが課題である.

5

謝辞

本研究は JSPS 科学研究費補助金基盤研究 (B)25280013 の助成を受けたものである.
参考文献[1] T. Matsui et al., “Positive semidefinite relaxation andapproximation algorithm for triple patterning lithography,” in Proc. ISAAC, LNCS 8889, pp. 365-375, 2014.

[2] M. Yamashita et al., “A high-performance software
package for semidefinite programs: SDPA 7,” Research
Report B-460 Dept. of Mathematical and Computing
Science, Tokyo Institute of Technology, 2010.

86（ 基礎・ 境界講演論文集）

Copyright © 2016 IEICE