で最短化する方法がとられた. たとえば, 図 2(a) は, 図 1(c) のスタイナー木の分岐点を SP とし, 端子,, と SP を含めて 2 端子分割することで図 2(b) のような最短経路が得られる. しかし, 実際の配線では, スタイナー木の線分上に障害物がある場合があり, その回避

Size: px

Start display at page:

Download "で最短化する方法がとられた. たとえば, 図 2(a) は, 図 1(c) のスタイナー木の分岐点を SP とし, 端子,, と SP を含めて 2 端子分割することで図 2(b) のような最短経路が得られる. しかし, 実際の配線では, スタイナー木の線分上に障害物がある場合があり, その回避"

あきみみねむら
5 years ago
Views:

1 Technical Reports on Information and omputer Science from Kochi Vol. 8 (2016), No. 11 障害物回避を考慮したスタイナー木配線法 n Obstacle voiding pproximate 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 以上の多端子ネットでは最短経路が求められない問題があった. これは, 迷路配線法が, 配線領域をデザインルールで決めた格子間隔上で始点から終点までの経路を横型探索 (readth First Search) で求める方法であるからである. 配線を格子上で求める理由は,VLSI 製造上の制約からである. 迷路配線法を端子数 3 以上へ適用するためには, 多端子ネットをあらかじめ 2 端子ペアに分割するためネット全体の最短化が狙えない. 例えば, 図 1 (a) に端子,, の3 端子ネットの配線例では,- および - を 2 端子ペアとすると図 1(b) のように冗長な配線長をもつ配線結果となる. この例では, 図 1(c) の方がより配線長が短いことがわかる. (a) 端子数 3 のネット (b) 端子数 3 の配線 (c) 端子数 3 の最短経路 ( スタイナー木 ) 図 1 端子数 3のネットの配線例そこで多端子ネットとして図 1(c) の経路を計算する方法 ( スタイナー木計算 [2]) により多端子間の分岐点 ( スタイナー点 ) を含めた 2 端子分割を迷路配線法で配線すること 1

2 で最短化する方法がとられた. たとえば, 図 2(a) は, 図 1(c) のスタイナー木の分岐点を SP とし, 端子,, と SP を含めて 2 端子分割することで図 2(b) のような最短経路が得られる. しかし, 実際の配線では, スタイナー木の線分上に障害物がある場合があり, その回避のため, 迷路配線法で配線が冗長になる場合がある. 本論文は, 障害物回避を考慮したスタイナー木配線法を提案するものである. 提案手法は,3 つのステップで構成する. まず, 第 1 に準 Hanan 格子を求め, 第 2 にその準 Hanan 格子の線分を, ランダムな枝刈で端子間を結ぶ最小木を作り, 第 3 に, 第 2 の方法を繰返して最短経路を持つスタイナー木を求めるものである.Hanan 格子 [4] は, 各端子から水平垂直に線分を生成して作った格子である, 図 4 に多端子,, の Hanan 格子の例 ( 破線 ) を示す. (a) スタイナー点 SP 図 4 Hanan 格子の例 (b) 点 SP と端子の配線図 2 障害物のある配線例本提案手法では, 端子から水平垂直の線分検索において, 障害物か他の検索線分を見つけた場合に, そこで線分生成をやめて得られた新たな近似的な Hanan 格子 ( 準 Hanan 格子 )[5] を新たに定義する. 多端子,, の準 Hanan 格子の例, および障害物を含む場合の例を図 5(a), 図 5(b) にそれぞれ示す. しかし, 実際の配線問題では図 3 の矩形で表したような障害物があるため, 配線の迂回が生じる場合がある [3]. そのため, スタイナー点を利用しても最短な配線が得られなくなる. よって, 障害物を含めた多端子ネットの最短配線手法が求められる. (a) 準 Hanan 格子の例図 3 障害物による配線の迂回の例 (b) 障害を考慮した準 Hanan 格子の例図 5 準 Hanan 格子の例 2

3 提案する配線法で最短な配線が得られるかどうかを評価するため, 様々な端子数をもつ多端子ネットのテストデータを生成し, 評価実験をおこなったところ, 端子数 3,4,5,6 のネットでは, スタイナー木と一致する配線経路が得られることが判明した. また端子数 10, 20, 30, 40, 50 のネットでは, 準 Hanan 格子の配線長の 30% の配線長まで短縮化した配線経路が得られることがわかった. 以下の 2 章では, 本手法について詳細な説明をおこない,3 章では, 評価実験について紹介し, その効果を示す. 最後に 4 章でまとめを述べる. (a) 配線領域の格子モデル 2. 障害物回避を考慮した擬似スタイナー木生成法提案手法のアルゴリズムを図 1 に示す. まずステップ 1 は, 多端子ネットの全端子について, 準 Hanan 構成を生成する処理である. まず, 配線領域内で上下左右の 4 方向の隣接点 P を調べ, もし点 P が配線可能であれば,P にトレースバックコード T( 検索方向情報 ) を設定する処理である. (b) 端子からの線分探索 (c) 準 Hanan 格子図 1. 障害物回避を考慮した擬似スタイナー木生成法同点 P について, ステップ 1.1 において場合わけ処理を行う. まず, ステップ 1.1a として, 点 P の T 方向への隣接点 P が配線可能なら, リストへ点 P* を追加する, あるいは, ステップ 1.1b として, 点 P が障害物で別方向の隣接点 P* が配線可能なら P* をリストへ追加する, あるいは, ステップ 1.1c として, 隣接点 P が他の端子からの T なら Step1 を終了する. 上記のステップ 1.1a とステップ 1.1b の場合は, ステップ 1.2 として, リストの点を P として再びステップ 1.1 から繰り返す処理である. 次にステップ 2 において, 準 Hanan 格子から枝刈を 300 回試みる. まず, ステップ 2.1 において, 準 Hanan 格子の線分をランダムに 1 本除去, ステップ 2.2 において, 同線分の除去により端子が未接続なら元に戻す処理である. (d) 枝刈と繰返しで得られた線分図 2. 障害物回避を考慮した擬似スタイナー木生成例次にステップ 3 において, 前述のステップ 2 を 2000 回試行し, 準 Hanan 格子から様々な順番で枝刈したものから, 配線長が最短となる配線経路を求める処理である. 3 端子ネット,, のスタイナー木生成例を図 2 で説明する. 図 2 では, 配線格子を線, 格子点をとして配線領域をあらわし, ラベル,,はネットの端子位置を示 3

4 すものとする. ステップ 1 における, 多端子ネットの全端子について, 準 Hanan 構成を生成する処理で, 配線領域内の端子の上下左右の 4 方向の隣接点 P を調べている様子を図 2(b) に示す. 同図ではどの隣接点 P も配線可能であるため, トレースバックコード T( 矢印 ) が設定されている. 図 2.(c) は, ステップ 1.1 で生成された格子 ( 準 Hanan 格子 ) の結果を示している. 次にステップ 2 において, 図 2.(c) の準 Hanan 格子から線分をランダムに 1 本除去し, ステップ 2.2 において, 同線分の除去により端子が未接続なら元に戻す処理を 300 回試みた結果を図 2.(d) に示す. 次にステップ 3 において, 前述のステップ 2 を 2000 回試行するが, 本例では, ステップ 2 の結果と同じ図 2.(d) となる. 縮率は 28.6%, 端子数 20 の結果を示す表 1.6 によれば, における 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 端子においてループが残される結果も見られる. 3. 評価実験提案する障害物回避を考慮した擬似スタイナー木生成法を言語 (MinGW/ygwin) で実装し,Windows7 環境で実行した. 実験データは格子の配線領域に端子数 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 種類のデータ,,,D,E を作成して評価した. 表の記号は先ほどと同じである. 端子数 10 の結果を示す表 1.5 によれば, における短 4. まとめ高性能 VLSI の配線設計でより短い配線を得るため, 障害物回避を考慮した多端子配線の新手法を提案した. 提案手法は, 準 Hanan 格子を生成し, 同格子からランダムに線分を削除することで最短配線経路を得る. 提案法を実装した計算機実験で, 端子数 6 以内では, スタイナー木の厳密解を得た. また端子数 10, 20, 30, 40, 50 の多端子ネットでは, 配線長が準 Hanan 格子の線分長の 28.8% から 34.0% にまで削減でき,6 端子までの準 Hanan 格子の線分長と厳密解との短縮率と同等であることがわかった. なお, 本手法では 40, 50 端子において, 一部ループが残る問題が見られる. 今後, ループ除去の機能追加が望まれる. 参考文献 [1] Lee,. Y. (1961). n algorithm for path connections and its applications. Electronic omputers, IRE Transactions on, (3), [2]Hanan, Maurice. "On Steiner's problem with rectilinear distance." SIM Journal on pplied Mathematics 14.2 (1966): [3] jwani, G., hu,., & Mak, W. K. (2011). FORS: FLUTE based obstacle-avoiding rectilinear steiner tree construction. omputer-ided Design of Integrated ircuits and Systems, IEEE Transactions on, 30(2), [4] Snyder, Timothy Law. "On the exact location of Steiner points in general dimension." SIM Journal on omputing 21.1 (1992): [5] 川真田雅則, 豊永昌彦多端子ネットの近似 MST 配線の一手法, 平成 27 年度電気関係学会四国支部連合大会 1-36(2015 年 9 月 26 日高知工科大 ) 4

5 (a) 準 Hanan 格子 (a) 準 Hanan 格子 (b) 提案手法による配線図端子の実験結果 (b) 提案手法による配線 ( ループがある ) 図端子の実験結果 (a) 準 Hanan 格子 (a) 準 Hanan 格子 (b) 提案手法による配線図端子の実験結果 (b) 提案手法による配線 ( ループがある ) 図端子の実験結果 5

6 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % 3.31 D % 3.33 E % 2.73 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較 % % % D % E % 平均 % 表端子における線分長比較名称準 H 長配線長短縮率時間 % % % D % E % 平均 %

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法組合せ計画問題組合せ計画問題とは : 有限個のものの組合せの中から, 目的関数を最小または最大にする組合せを見つける問題例 1: 整数計画問題全般