障害物回避を考慮したスタイナー木配線法
An Obstacle Avoiding Approximate Minimum Steiner Tree Router豊永 昌彦 1） 松下 充 2) 川真田 雅則 1) Masahiko Toyonaga 1) Mitsuru Matsushita 2） Masanori Kawamata 1)
1）高知大学理学部 2)高知大学大学院理学専攻情報講座 Information Science Division, Faculty of Science, Kochi University あらまし 高性能 VLSI レイアウト設計で求められる配線長最短 化をするための障害物回避を考慮した擬似スタイナー木 による配線法を提案する．従来のスタイナー木からの配 線が障害物において配線長冗長化する問題を解決する ため，本手法は 3 ステップ，すなわち 1)準 Hanan 格子の 生成，2)準 Hanan 格子の線分のランダムな削除，3)前述 の様々な経路から最短となるスタイナー木を選択して出 力，で構成する． 提案手法を実装して評価実験をおこなったところ，端 子数 6 以内の多端子ネットで，厳密なスタイナー木を得ら れ，また端子数 10，20, 40，50 の多端子ネットでは，準 Hanan 格子線分長の 28.8%から 34.0%まで短縮した配線 構成が得られることがわかった．これは，端子数 6 までの 多端子ネットの厳密解の準 Hanan 格子線分長と同等の 短縮率である． Keyword: 迷路配線法，多端子ネット，スタイナー木, Hanan 格子 1．はじめに 高性能 VLSI のレイアウト設計では，配線最短化がそ のまま動作速度の改善につながる．そのため，配線長最 短が保障される配線手法．迷路配線法が利用されてき た． しかし，迷路配線法[1]は，そもそも端子数 2 のネットの 経路を求める手法であるため，端子数が 3 以上の多端子 ネットでは最短経路が求められない問題があった．これ は，迷路配線法が，配線領域をデザインルールで決めた 格子間隔上で始点から終点までの経路を横型探索 (Breadth First Search)で求める方法であるからである．配 線を格子上で求める理由は，VLSI 製造上の制約からで ある．迷路配線法を端子数 3 以上へ適用するためには， 多端子ネットをあらかじめ 2 端子ペアに分割するためネッ ト全体の最短化が狙えない．例えば，図１(a)に端子 A,B,C の３端子ネットの配線例では，A-C および C-B を 2 端子ペアとすると図 1(b)のように冗長な配線長をもつ配 線結果となる．この例では，図 1(c)の方がより配線長が短 いことがわかる．
×
×
×
×
×
×
×
×
×
×
×
×
A B C (a)端子数 3 のネット×
×
×
×
×
×
×
×
×
×
×
×
A B C (b)端子数 3 の配線×
×
×
×
×
×
×
×
×
×
×
×
A B C (c)端子数 3 の最短経路(スタイナー木) 図 1 端子数３のネットの配線例 そこで多端子ネットとして図 1(c)の経路を計算する方法 (スタイナー木計算[2])により多端子間の分岐点(スタイナ ー点)を含めた 2 端子分割を迷路配線法で配線すること Technical Reports on Information andComputer Science from Kochi Vol. 8 (2016), No. 11
で最短化する方法がとられた．たとえば，図 2(a)は，図 1(c)のスタイナー木の分岐点を SP とし，端子 A, B, C と SP を含めて 2 端子分割することで図 2(b)のような最短経路 が得られる． しかし，実際の配線では，スタイナー木の線分上に「障 害物」がある場合があり，その回避のため，迷路配線法で 配線が冗長になる場合がある． (a)スタイナー点 SP (b)点 SP と端子の配線 図 2 障害物のある配線例 しかし，実際の配線問題では図 3 の矩形で表したよう な障害物があるため，配線の迂回が生じる場合がある[3]． そのため，スタイナー点を利用しても最短な配線が得ら れなくなる．よって，障害物を含めた多端子ネットの最短 配線手法が求められる． 図 3 障害物による配線の迂回の例 本論文は，障害物回避を考慮したスタイナー木配線法 を提案するものである．提案手法は，3 つのステップで構 成する．まず，第 1 に準 Hanan 格子を求め，第 2 にその 準 Hanan 格子の線分を，ランダムな枝刈で端子間を結ぶ 最小木を作り，第 3 に，第 2 の方法を繰返して最短経路 を持つスタイナー木を求めるものである．Hanan 格子[4] は，各端子から水平垂直に線分を生成して作った格子で ある，図 4 に多端子 A, B, C の Hanan 格子の例(破線)を 示す． 図 4 Hanan 格子の例 本提案手法では，端子から水平垂直の線分検索にお いて，障害物か他の検索線分を見つけた場合に，そこで 線分生成をやめて得られた新たな近似的な Hanan 格子 (準 Hanan 格子)[5]を新たに定義する．多端子 A, B, C の 準 Hanan 格子の例，および障害物を含む場合の例を図 5(a)，図 5(b)にそれぞれ示す． (a) 準 Hanan 格子の例 (b) 障害を考慮した準 Hanan 格子の例 図 5 準 Hanan 格子の例
提案する配線法で最短な配線が得られるかどうかを評 価するため，様々な端子数をもつ多端子ネットのテストデ ータを生成し，評価実験をおこなったところ，端子数 3,4,5,6 のネットでは，スタイナー木と一致する配線経路が 得られることが判明した．また端子数 10, 20, 30, 40, 50 の ネットでは，準 Hanan 格子の配線長の 30％の配線長まで 短縮化した配線経路が得られることがわかった． 以下の 2 章では，本手法について詳細な説明をおこな い，3 章では，評価実験について紹介し，その効果を示 す．最後に 4 章でまとめを述べる． 2．障害物回避を考慮した擬似スタイナー木生成法 提案手法のアルゴリズムを図 1 に示す．まずステップ 1 は，多端子ネットの全端子について，準 Hanan 構成を生 成する処理である．まず，配線領域内で上下左右の 4 方 向の隣接点 P を調べ，もし点 P が配線可能であれば，P にトレースバックコード TB(検索方向情報)を設定する処 理である． 図１．障害物回避を考慮した擬似スタイナー木生成法 同点 P について，ステップ 1.1 において場合わけ処理 を行う．まず，ステップ 1.1a として，点 P の TB 方向への隣 接点 P’が配線可能なら，リストへ点 P*を追加する，あるい は，ステップ 1.1b として，点 P が障害物で別方向の隣接 点 P*が配線可能なら P*をリストへ追加する，あるいは，ス テップ 1.1c として，隣接点 P が他の端子からの TB なら Step1 を終了する．上記のステップ 1.1a とステップ 1.1b の 場合は，ステップ 1.2 として，リストの点を P として再びステ ップ 1.1 から繰り返す処理である． 次にステップ 2 において，準 Hanan 格子から枝刈を 300 回試みる．まず，ステップ 2.1 において，準 Hanan 格子の 線分をランダムに 1 本除去，ステップ 2.2 において，同線 分の除去により端子が未接続なら元に戻す処理である． (a)配線領域の格子モデル (ｂ)端子からの線分探索 B C A (ｃ)準Ｈａｎａｎ格子 B C A (ｄ)枝刈と繰返しで得られた線分 図 2．障害物回避を考慮した擬似スタイナー木生成例 次にステップ 3 において，前述のステップ 2 を 2000 回 試行し，準 Hanan 格子から様々な順番で枝刈したものか ら，配線長が最短となる配線経路を求める処理である． 3 端子ネット A, B, C のスタイナー木生成例を図 2 で説 明する．図 2 では，配線格子を線，格子点を○として配線 領域をあらわし，ラベルＡ，Ｂ，Ｃはネットの端子位置を示
すものとする． ステップ 1 における，多端子ネットの全端子について， 準 Hanan 構成を生成する処理で，配線領域内の端子の 上下左右の 4 方向の隣接点 P を調べている様子を図 2(ｂ)に示す．同図ではどの隣接点 P も配線可能であるた め，トレースバックコード TB(矢印)が設定されている． 図 2.(ｃ)は，ステップ 1.1 で生成された格子(準Ｈａｎａｎ 格子)の結果を示している． 次にステップ 2 において，図 2.(ｃ)の準 Hanan 格子から 線分をランダムに 1 本除去し，ステップ 2.2 において，同 線分の除去により端子が未接続なら元に戻す処理を 300 回試みた結果を図 2.(ｄ)に示す． 次にステップ 3 において，前述のステップ 2 を 2000 回 試行するが，本例では，ステップ 2 の結果と同じ図 2.(ｄ)と なる． 3．評価実験 提案する障害物回避を考慮した擬似スタイナー木生成 法を C 言語(MinGW/Cygwin)で実装し，Windows7 環境 で実行した．実験データは 100×100 格子の配線領域に 端子数 3,4,5,6,10,20,30,40,50 の多端子ネットの端子を配 置したものを使用する．端子位置は，乱数のシードを変 えて 5 種類ずつランダムで配置した． 端子数 3,4,5,6 の多端子ネットのデータで，本手法が求 めた線分長と，スタイナー木から求めた厳密解の線分長 と実行時間を比較する．また，端子数 10,20,30,40,50 では， 本手法が求めた線分長と準 Hanan 格子の線分長からの 改善率をと実行時間を比較する． 端子数 3,4,5,6 多端子における線分長とスタイナー木 の線分長との比較結果を，表 1.1，表 1.2，表 1.3 および表 1.4 に示す．各表において，「配線長」は，提案手法で得 られた線分長，「厳密長」は，スタイナー木の線分長，「時 間」は処理時間（秒）を表す．また，各データから提案手 法で得た準 Hanan 長を「準 H 長」，および「短縮率」は準 Hanan 長に対して得られた線分長の割合を示す．表 1.1 から表 1.4 より，いずれの端子数のパターンでも全て厳密 解と同値で，最短経路を得られているという結果が出た． さらに短縮率の平均は 34.5%であるが，これは厳密解と 準 Hanan 長の短縮率 34.5%となっている． 端子数 10,20,30,40,50 の端子数の実験では，厳密解を 見つけることが難しいため，準 Hanan の線分長からの削 減率のみを評価した．各データは，先ほどと同様にランダ ムに端子数毎に 5 種類のデータ A,B,C,D,E を作成して評 価した．表の記号は先ほどと同じである． 端子数 10 の結果を示す表 1.5 によれば，A における短 縮率は 28.6%，端子数 20 の結果を示す表 1.6 によれば， A における 29.0%，端子数 30 は，表 1.7 によれば 31.4%， 端子数 40 は，表 1.8 によれば 32.6%，端子数 50 は，表 1.9 によれば 34.0%という結果が出た．この結果から，50 端子までの数であれば，経路は準 Hanan 格子の約 30% 程度まで削減できていることがわかる． 6 端子までの実験結果でも，厳密解の配線長は準 Hanan の 30~40%程度の削減りつであったことから，本手 法で求められた配線経路は十分スタイナー木に近いもの のであるといえる． 参考までに，提案手法でえられた端子数 10 端子，20 端子，40 端子，50 端子の準 Hanan 格子と，最終の配線 結果を図 4.1(a)，図 4.1(b)，図 4.2(a)，図 4.2(b)，図 4.3(a)， 図 4.3(b)，図 4.4(a)，図 4.4(b)にそれぞれ示す．なお，40, 50 端子においてループが残される結果も見られる． 4．まとめ 高性能 VLSI の配線設計でより短い配線を得るため， 障害物回避を考慮した多端子配線の新手法を提案した． 提案手法は，準 Hanan 格子を生成し，同格子からランダ ムに線分を削除することで最短配線経路を得る． 提案法を実装した計算機実験で，端子数 6 以内では， スタイナー木の厳密解を得た．また端子数 10, 20, 30, 40, 50 の多端子ネットでは，配線長が準 Hanan 格子の線分 長の 28.8%から 34.0%にまで削減でき，6 端子までの準 Hanan 格子の線分長と厳密解との短縮率と同等であるこ とがわかった． なお，本手法では 40, 50 端子において，一部ループが 残る問題が見られる．今後，ループ除去の機能追加が望 まれる． 参考文献
[1] Lee, C. Y. (1961). An algorithm for path connections and its applications. Electronic Computers, IRE Transactions on, (3), 346-365.
[2]Hanan, Maurice. "On Steiner's problem with rectilinear distance." SIAM Journal on Applied Mathematics 14.2 (1966): 255-265.
[3] Ajwani, G., Chu, C., & Mak, W. K. (2011). FOARS: FLUTE based obstacle-avoiding rectilinear steiner tree construction. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 30(2), 194-204.
[4] Snyder, Timothy Law. "On the exact location of Steiner points in general dimension." SIAM Journal on Computing 21.1 (1992): 163-180.
[5] 川真田雅則, 豊永昌彦” 多端子ネットの近似 MST 配線の 一手法,” 平成 27 年度電気関係学会 四国支部連合大会 1-36(2015 年 9 月 26 日高知工科大)
(a)準 Hanan 格子 (b)提案手法による配線 図 4.1 10 端子の実験結果 (a)準 Hanan 格子 (b)提案手法による配線 図 4.2 20 端子の実験結果 (a)準 Hanan 格子 (b)提案手法による配線(ループがある) 図 4.3 40 端子の実験結果 (a)準 Hanan 格子 (b)提案手法による配線(ループがある) 図 4.4 50 端子の実験結果
名称 配線長 厳密長 時間 準H長 短縮率 A 82 82 1.11 238 34.0% B 103 103 1.01 302 34.0% C 131 131 1.03 360 36.0% D 151 151 1.03 434 35.0% E 71 71 1.23 145 49.0% 平均 107.6 107.6 1.082 295.8 37.6% 名称 配線長 厳密長 時間 準H長 短縮率 A 188 188 1.17 549 34.0% B 97 97 1.28 254 38.0% C 121 121 1.17 410 30.0% D 114 114 1.16 375 30.0% E 174 174 1.16 540 32.0% 平均 138.8 138.8 1.188 425.6 32.8% 名称 配線長 厳密長 時間 準H長 短縮率 A 142 142 1.5 311 46.0% B 135 135 1.33 443 30.0% C 173 173 1.39 536 32.0% D 191 191 1.34 638 30.0% E 168 168 1.34 552 30.0% 平均 161.8 161.8 1.38 496 33.6% 名称 配線長 厳密長 時間 準H長 短縮率 A 169 169 1.66 496 34.0% B 187 187 1.54 625 30.0% C 222 222 2.68 631 35.0% D 175 175 1.65 516 34.0% E 94 94 1.68 274 34.0% 平均 169.4 169.4 1.842 508.4 33.4% 表1.1 3端子における線分長比較 表1.2 4端子における線分長比較 表1.3 5端子における線分長比較 表1.4 6端子における線分長比較 名称 準H長 配線長 短縮率 時間 A 728 206 28.0% 3.38 B 963 310 32.0% 3.37 C 655 160 24.0% 3.31 D 626 195 31.0% 3.33 E 841 235 28.0% 2.73 平均 762.6 221.2 28.6% 3.224 名称 準H長 配線長 短縮率 時間 A 1501 420 28.0% 12.4 B 1485 401 27.0% 11.94 C 1210 363 30.0% 10.68 D 1195 308 26.0% 14.18 E 1184 401 34.0% 11.74 平均 1315 378.6 29.0% 12.188 名称 準H長 配線長 短縮率 時間 A 1691 520 31.0% 28.9 B 1470 470 32.0% 32.5 C 1615 511 32.0% 32.62 D 1587 458 29.0% 33.39 E 1473 482 33.0% 33.01 平均 1567.2 488.2 31.4% 32.084 名称 準H長 配線長 短縮率 時間 A 1800 577 32.0% 69.6 B 1855 632 34.0% 69.21 C 1706 563 33.0% 73.02 D 1904 582 31.0% 72.78 E 1653 539 33.0% 72.58 平均 1783.6 578.6 32.6% 71.438 名称 準H長 配線長 短縮率 時間 A 1931 630 33.0% 137.61 B 2157 726 34.0% 141.76 C 2114 705 33.0% 134.97 D 1931 681 35.0% 135.27 E 2076 724 35.0% 136.12 平均 2041.8 693.2 34.0% 137.146 表1.9 50端子における線分長比較 表1.5 10端子における線分長比較 表1.6 20端子における線分長比較 表1.7 30端子における線分長比較 表1.8 40端子における線分長比較
