並列配線システムAmaterousの改良と評価

全文

(1)ハイパフォーマンス 93−10 コンピューティング（２００３．３．１１）. 並列配線システム荒. 久y. 井直. Amaterous の改良と評価野和彦y. 大. 浩y. 中島. 本論文では, 並列自動配線において大域／詳細配線間の依存を解消し, 独立に処理する並列配線システム Amaterous の端子接続の改良について述べる. Amaterous では, 大域配線の前に準備処理を行って局所的な配線容量を最大化するような仮想的な経路 (capacity path (c-path)) の集合を求め, 大域配線では各ネットの経路を c-path を選択することによって決定する. そのため, 詳細配線経路に依存せず大域配線経路を決定する事ができる. しかし従来の Amaterous の準備処理では, 端子が存在する小領域（パーティション）と, それに隣接するパーティションの双方を通過する c-path に端子を接続するため, 配線長が増大するという欠点があった. 本論文では, 端子とそれを含むパーティションの両端とを接続する経路を求める新たなアルゴリズムを提案し, 評価を行ったところ,5∼16%の配線長を削減でき, アルゴリズムの有効性を確認できた.. An Improved and Evaluation of Amaterous Parallel Wire Router Naohisa Arai,y Kazuhiko Ohnoy. and. Hiroshi Nakashimay. This paper proposes an improved terminal connection algorithm of the Amaterous parallel wire router, in which the global and detailed routers work independently without the feedback. In Amaterous, a set of capacity paths (c-paths) to maximize local wireability is obtained prior to global routing which the paths are chosen to form a global path. However the current implementation of Amaterous draws redundantly long paths because it connects a terminal to a c-path which penetrates two partitions including that contains the terminal. Thus, we propose a new algorithm to

(2) nd a path to connect the terminal and both edges of the partition where the terminal resides, in order to prevent, the problem of redundantly long paths. As a result of the experiment, sucessfully reduced wiring length by 5 to 16 %, and proved the e ectiveness of the algorithm.. 1.. .. はじめに. , VLSI. (PCB). ,. 近年やプリント基板の高集積化大規模化にともない回路設計を支援するツールの処理時間も著しく増加する傾向にあるそこで処理ツールを並列化する研究が時間の短縮のために多く行われている我々の研究対象である配線処理では並列化の有効な手法として大域・詳細の段階配線が知られているこの方法では各ネットの経路探索がネットの配線領域を大まかに見積もる「大域配線」とその領域内で実際のグリッド単位の探索を行う「詳細配線」の段階で処理されるため並列性を高めることが可能であるこのような段階配線では大域配線で詳細経路を常に仮想的に扱いながら経路の見積もりを立てており実際の詳細経路との誤差を少なくするために詳細配線での実際の配線状況を大域配線にフィードバックし大域経路の見積もり誤差を常に小さくしておく必要が. ,. .. CAD. ,. 2. 2. ,. CAD .. .. , ,. 2. ,. ,. y 豊橋技術科学大学. . ,. あるしかしこのフィードバックを頻繁に行うと配列処理が逐次化され頻度を小さくすると配線品質が悪化するという問題点があるそこで我々はこのフィードバックを除去するために大域配線以前にあらかじめ仮想的な経路を配線することにより配線経路を把握し大域／詳細配線を独立し 1) て行う新たな並列配線システムの開発を行っているこれまでの研究の結果は従来の並列配線システムに比べて高速でありかつ配線困難な問題に対する耐性が高いことが明らかになっには配線長が大きいといているしかしう問題がありその主な原因として仮想的経路と端子の接続アルゴリズムの不備が挙げられているそこで本論文ではこの問題を解決する新たな端子接続アルゴリズムを提案する. ,. .. ,. ,. , Amaterous , Amaterous ,. .. .. ,. , Amaterous. .. .. ,. 2.. 並列配線システム Amaterous. Amaterous ,. ,. の配線処理は「配線空間のそれぞれの単位領域に同時に存在できる全ての経路をあらかじめ仮想的に把握しておき大域配線ではその仮想的な. Toyohashi University of Technology. 1 −55−. ,.

(3) マスタ. マスタ. マスタ. スレーブ. スレーブ. スレーブ. スレーブ. スレーブ. スレーブ. 準備処理. 大域配線. 図1. 今回の探索順番前回の移動方向. 2. 詳細配線. 1. 並列処理の流れ. 図3. Y方向レイヤ. X方向レイヤ. 3. 「右手法」による探索. (c). (a) パーティション. 図2. スライス. 配線空間の分割. 経路を消費していく事で経路を決定する」というモデルに基づいている全ての仮想経路をあらかじめ求めておき管理することで大域配線の時点で経路の配線性が完全に把握できることになるこれによって詳細配線から独立した大域配線の一括処理が可能になるにおいて大域配線はこの仮想経路の中から適切なものを選択する処理であり詳細配線はそれらの冗長性を除去する変形処理であるは一つのマスタプロセスと複数のスレーブプロセスが存在するマスタ―スレーブ型の構成を持ちマスタからスレーブに指示を送ることにより各スレーブが並列に配線処理を行っていく準備処理と詳細配線では各スレーブが分割された配線領域の担当部分の処理を独立に行い領域間の情報交換のためスレーブ間通信を各々一度だけ行う大域配線ではネットの並列性を利用して、各スレーブが異なるネットの配線処理を独立に行いマスタはネット間の整合性チェックを行う図 2.1 配線空間の分割の配線空間はグリッドからなる矩形面を多層にしたものであり各層をレイヤと呼ぶ各レイヤはパーティションと呼ぶ矩形に分割され各々が大域配線の探索単位である大域配線での配線方向はレイヤごとにまたは方向に制約されておりこの方向に沿ってパーティションを連結したものをスライスと呼ぶまたスライスは準備処理と詳細配線の処理単位でもあるレイヤ間の移動は隣接するレイヤのみを接続するビアによって行う 2.2 Amaterous の配線方式 2.2.1 準備処理準備処理では大域配線で経路を探索するための情報を集めまたその配線性を保証するための処理を行. .. ,. ,. .. Amaterous. ,. Amaterous ,. .. .. ,. .. ,. Amaterous. ,. ,. ,. ,. ,. .. ,. ( 1).. .. ,. ,. ,. . ,. x. .. .. .. y. ,. (b). (d) 図4. c-path 探索の停止条件. .. ,. う処理はスライス単位で独立に行う為ほぼ完全な並列処理が可能である準備処理ではまずスライスに（以下）と呼ぶ仮想的な経路を配線するの配線は迷路探索法の一つである「右手法」図を用いて行う「右手法」による経路は冗長なため実際の配線経路としては採用できないが常にパーティションの配線本数を最大化する経路をとるため大域配線での選択経路の候補数が最大化されるの停止条件としてスライスの右端に達した図一度通過したパーティションの境界に達した図. c-path c-path ( 3). .. ,. ,. Capacity path .. .. ,. .. ,. c-path , ( 1) ( 4(a)) ( 2) ( 4(b)) ( 3) スライスの上端に達した (図 4(c)) があげられ、2 または 3 の場合には, 最後に通過したパーティションの境界以後の軌跡は削除する. この結果, 図 4(d) のように配線される. 続いて各端子を図 5のように c-path に接続する. その際、各々の端子について, 端子が接続するパーティションに隣接するパーティションを貫通する c-path を選択して接続する. したがって端子から隣接するパーティションへの接続が保証され, 大域配線では隣接パーティションを経路の始点／終点とみなすことができる. 2.2.2 大域配線大域配線では各ネットの経路を端子間のマンハッタン距離の短い順にパーティションを単位とするコスト最小探索により求めるここで経路のコストはパーティションごとのコストの総和であり各パーティショ本ンのコストは配線容量すなわち使用可能な. 2 −56−. ,. ,. .. ,. ,. c-path.

(4) x-layer. y-layer. 図7 図5. layer と端子の並び. , 50%, ,. 切なパーティション選択による損失は各端子について望ましくない方向に行く可能性がまたその場合の損失がパーティションと考えると平均して端子あたりパーティション幅程度であると見積もることができと他の配線システムとの配線長の差のほとんどがこの問題に起因することが明らかになっている. 端子の接続. 2. 1. , Amaterous .. 3.. 図6. 冗長な経路. .. ,. ,. 数に反比例するすなわち経路長を短くすることと他のネットの配線を妨げないことの双方に配慮した経路が求められるまた経路を構成するパーティション列の各々について列中の全パーティションを通過するが存在することを必要条件としそのような群を経路に占有的に割り当てるしたがって各経路が固有の群を持つことすなわち必ず配線可能であることが保証される 2.2.3 詳細配線準備処理で配線されたは各パーティションの配線容量を最大化している半面それぞれの経路は迂回が多く実際の配線回路としては冗長であるそこで詳細配線ではパーティション列を通過するという性質を保ちつつ経路の短縮直線化を行うまたそれに続いてレイヤ間配線のためのビア位置を定めるために経路の交差点を求めビアとパーティション端の間の不要経路を削除して配線処理を完了する 2.3 冗長な配線経路節で述べたように準備処理での端子との接続処理では端子から隣接パーティションへの経路が確保されるその際左右あるいは上下のどちらに隣接するパーティションが選択されるかは端子との接続容易性のみにより定まるしたがって図に示すように接続すべき端子対から互いに遠ざかる方向のパーティションが選択され配線経路が冗長になる可能性がある実際この不適. ,. .. ,. c-path. .. ,. ,. .. ,. ,. ,. c-path c-path. c-path , ,. , ,. .. ,. .. ,. .. 2.2.1. c-path. , .. , 6. ,. c-path. ,. ,. .. ,. .. ,. ,. 新しい端子接続アルゴリズム. 2.3. 本論文で提案するアルゴリズムは節で述べた問題を以下のように解決する端子を通りパーティションの両端に達するパスを引くこのようなパスが得られた端子については大域配線の始点を端子が存在するパーティ節で述べた損失はションとすることができ生じないのようなパスが配線不可能あるいは他の端子に関する接続処理の妨げになる場合従来と同様に一方の隣接パーティションを通過するに接続する端子接続と平行して配線を行いパーティションを通過するが十分確保できるようにする準備処理をつのターンに分けターン目でパスと接続できなかった端子はレイヤを移動してターン目で再び接続を試みる 3.1 端子のレイヤ割当て実際の回路では端子が直線上に並んでいる事が多いこのような場合端子の並びと垂直方向のレイヤに接続パスを配線すると領域の使用効率が高くなる図. .. ( 1). ,. .. ,2.3. .. ( 2) 1.. ,. .. ( 3) ( 4). 2. ,. c-path. c-path c-path. .. ,. ,1. ,2. .. ,. .. ,. (. 7).. ,. x. そこで本アルゴリズムでは端子を方向に並んでいるもの同じ座標を持つ物）方向に並んでいるもの（同じ座標を持つもの）の種類に分け前者の接続パス配線を方向レイヤで、後者を方向レイヤでそれぞれ行う例として図ののようなパーティションがあった場合端子では同じ座標を持つ端子がつ同じ座標を持つ端子がつなので方向レイヤに割. 3 −57−. (. y. ,. x. y. y . 8 (a). 1. x. ,y 2. ,x. x. ,. 2 ,.

(5) x-layer. y-layer. r. β α. (b) 図8. ,. 端子の接続レイヤ決定. .. 3. .. ,. .. y. 8 -(b) . ,1 ,2. x. 0,. x , ,x. ,x. ,x ,y. 3, y. 5. .. ,x 8-(c). ,x. ,y. y. ,. ,. ,. .. .. ,. c-path. c-path. ,. c-path. .. 1. . c-path. c-path. ,. ( 2). ,2. ,. 1. ( 1). x ,. x. .. .. (d). .. ,1. ,x. 9.(a) ,. . ,. c-path. .. ,. (e). 図9. ,y. 2. ,y. c-path ,. (c). (c). り当てる端子

(6) では同じ座標を持つ端子が同じ座標を持つ端子がつなので方向レイヤに割り当てる端子のように方向方向ともに同じ数の端子が存在する場合にはより端子が密集しているほうが配線しにくいため方向方向それぞれの端子列に関してもっとも遠いつの端子間の距離を比べ小さい方の端子列と垂直なレイヤに端子を割り当てる端子の場合方向が方向がなのでの端子列と垂直な方向レイヤに割り当てる以下他の端子に関しても同様に処理を行うと方向レイヤのように方向レイヤは図のようは図になるなおターン目においてパスと接続できなかった端子はターン目において方向レイヤのものは方向レイヤ方向レイヤのものは方向レイヤにそれぞれ移動してパスと接続する 3.2 端子の接続本節の冒頭でも述べたように端子を通りパーティションの両端に達するパスが望ましいパスである一方は端子を障害物とみなして配線されているのでこのような接続パスとして用いるには必ずしも適切ではないそこで本アルゴリズムでは、端子接続を行うパーティションについては一旦全てのを削除し接続パス配線を行うただし接続パス配線と並行してパーティションを通過する配線を行が減少する可能うので従来の方法に比べて性はごく小さく逆に後述のように従来の方法よりも増加することも期待できる 3.2.1 1 ターン目の処理ターン目にてパスに接続できなかった端子はターン目にてパスと接続できれば良いので隣接パーティションのパスの状況をターン目では無視し、処理の高速化と領域の有効活用をはかっている以下方向レイヤのパーティションを例にターン目のアルゴリズムの詳細を示すスライス単位でを引いた後（図）接続端子の存在するパーティション内の全てのを削除する先にスライス単位でを引くことにより端子接続に用いないパーティションにおいて複数のパーティションにまたがった長いパスを得ることができる端子とパーティションの両側に接続するために. y. (b). (a). (a). 新しい端子の接続方式（ 1 ターン目）. .. まず端子とパーティションの右端を接続するパーティションの右側から端子へのパスを下から順に左手法で求める（図端子と接続せずにパーティション左端にパスが達した場合には端子左側に仮想的な壁を作り端子を貫通するパスを引き直すまたパスと接続できた端子をキューに積むパーティション右端の全ての格子点に関して探索が終了後キューから端子を取りだし順番に端子からパーティション左端へのパスを引く図図の段階では端子とパーティションの両端は接続されているがが本もないなど配線領域を有効に活用しているとは言えないそこで領域を有効活用するためにの配線をおこないつつ端子接続パスを上方へ移動させるパーティションの右側の上から順番に今度は右手法でパスを配線するパスがパーティションの左側に達した場合はそれをとして保存し途中で端子あるいは端子に接続されたパスにぶつかった場合には端子につながれたパスを一度削除し端子を貫通するパスを引き直す図を右端の全ての格子点に対して繰り返すこの結果端子と両端を接続するパスとパーティションを通過するが得られる図なおターン目では隣接パーティションにパスがあることを保証していないため、パーティション両端に接続できない端子が発生した場合には再配線フラグを立てターン目にて配線しなおす図の例では上記のアルゴリズムによって全ての端子が両端に接続できかつ本のが得られる図従来の方法では端子接続の後で残存するは本であるので消費の削減という副次効果も得られている. ,. 9-(b)).. ,. . .. ( 3). ,. ,. ( 9-(c)). ( 4) ( 9-(c)) path. , .. ,. ( 5) 4. ,c-. ,. .. .. ,. ,. ( 9-(d).. ,. c-path. ,1. 9. ,c-path 1. ,. c-path. 4 −58−. ,. .. ( 9-(e)). c-path 1. ,. ,. . , ( 9-(e)).. ,2. ,. ,. 2. .. c-path. , c-path.

(7) ,. .. 手法で求め接続できた端子をキューに積む右側のマークを全て使用しても接続できない端子が存在する場合には左側のマークより右手法で接続を行うが例では省略するマークと端子を接続することにより隣接パーティションにパーティション分のパスを占有することができ大域配線の端点に設定することが可能となる全ての端子の片側接続が終わった後キューから端子を取りだし順番にパーティション左端左側のマークに接続した端子は右端へのパスを配線する図パーティション端に接続できないパスは削除し次の端子の処理に移る全ての端子についての処理が終了したらパーティション右端の一番上の格子点より右手法にの配線を行う途中でパーティショよってンの片側にしか接続できていない端子パスと衝突した場合はその端子からのパスを一度削除し右端の3マークのうち最も上のものからパスまたパーティションを引き直す図の両端に接続されている端子パスと衝突した場合にはそのパスを削除し端子を貫通するパスを右手法で引き直す図この時片側接続の端子とは異なりパーティションを貫通するパスが引けることが保証されているのでパーティション端の格子点にマークがついている必要はないこれらのパスの移動を行うことにより後の配線を妨げず配線容量を増加させることができるの処理を右端の格子点全てに対し行う図図において斜線の端子がパーティションの右端にしか接続されていないが 3マークによって隣接するパーティションに貫通するパスが存在することが保証されているため大域配線における端点は設定することができる. ,. (b) y-layer. (a). *. **. (d) x-layer. (f). ( 4). * * * *. **. 図 10. *. 2. 1. ,1. .. ,2. ,. ,. , c-path. ,y. ( 1). ( 2). .. 10-(c). ( 10-(b)),. 2. .. 1. 1. ,. . y. , ,y. ( 3) 2. ,. ( 10-(e) ).. ,. (x. x ( 10-(d)).. c-path. ,. ,. .. .. ( 10-(f)).. . c-path. ( 5) 4 (h)). 10-(h). ,. , ,. ,. ,. ,. .. ( 10,. ,. ,. .. ,. 3. ,. ,2. .. 10-(a). 10-(c). 1. .. ,. .. ). ( 10-(g)). ,. 2. ,. ( 10-(e)).. ,. 新しい端子の接続方式（ 2 ターン目）. ターン目の処理ターン目の処理が全てのパーティションにおいて終了したときつでも両端接続できない端子があればその端子を対となるレイヤに移動しターン目を実ターン目で処理するのは両端接続行するただしできなかった端子の移動元と移動先のパーティションのみでその他のパーティションに関してはターン目の結果をそのまま使用する移動元のパーティションに関しては移動する端子のパスを削除するだけでなく再び処理することにより移動する端子のパスに妨害され配線できなかったが配線可能となり配線容量を向上させることができる以下方向レイヤのパーティションを例にターン目のアルゴリズムの詳細を示す図のようなパーティションにおいてレイヤ割り当てを行い図ターンを実行すると図のような状態になる図においてつの斜線の端子はパーティションの片側しか接続されていないターンでは隣接パーティションにパスがあることを保証していないためこのような端子は大域配線の端点としてのパーティションを設定することができないそこで対となるレイヤ方向のレイヤでは方向方向のレイヤでは方向のレイヤ）に端子を移動する図ターン目ではパーティションの片側にしか接続できない端子も考慮しなければならないそこでパーティションの境界において隣接パーティションを貫通するとの交点にマークする図の3 その後パーティションの一番下のマークから順番に端子へのパスを左 3.2.2. ,. ,. c-path. (h). (g). , .. (. *. (e). * * ** **. *. * * * *. * * ** **. * *. * *. 1. (C). .. ,. 4.. 評. .. 価. 前説のアルゴリズムの有効性の評価を行うために. Pentium II(450MHz),16 台の PC クラスタにおいて MCM ベンチマークを用いて実験を行った. 2). 4.1 配線性能と実行時間はじめに端子のパーティション両端への接続成功率を調べてみたところ表のようになったこの結果より大部分の端子がパーティション両端への接続に成功しており後の大域配線において冗長な経路の選択の回避が期待できる次に本論文で提案する端子接続アルゴリズムを使用した場合と旧来のとの配線長の比較を行うために配線長とビア数の比較を行ったところ表のようになったなお「逐次」は台のにて実. ,. 1. ,. 2. 5 −59−. , ,. .. .. Amaterous. .. 1. PC.

(8) 表1. 端子のパーティション両端接続成功数両端接続成功端子数ベンチマーク全端子数 1 ターン目 2 ターン目 MCC1-75. 2043. 2043. 2043. MCC2-75. 14659. 14638. 14659. MCC2-45. 14659. 14648. 14654. 表2. 並列効果. 16. Amaterous MCC2-45. MCC ベンチマークの配線結果. 2. 配線長 ( 103 ). ビア数. 時間 (秒). 旧 (逐次) 新 (逐次). 477. 4990. 12.61. 436. 4321. 12.15. 旧 (16 並列) 新 (16 並列). 500. 4824. 2.41. 手法 MCC 1-75. 466. 4211. 2.59. 旧 (逐次) 新 (逐次). 7232. 39141. 459.99. 6221. 31970. 506.69. 旧 (16 並列) 新 (16 並列). 7439. 40089. 61.65. 6211. 32606. 75.36. 旧 (逐次) 新 (逐次). 10105. 31688. 638.61. 9515. 27515. 796.18. 旧 (16 並列) 新 (16 並列). 10385. 33482. 52.19. 9840. 28753. 97.31. MCC 2-75. MCC 2-45. 4. 4. 図 11. MCC1-75. 3600. 16.76. 17.64. MCC2-75. 38400. 23.64. 24.25. MCC2-45. 57600. 27.62. 27.99. 16. 2. ,. ,. .. , 3. 1. .. ,. ,. ,. .. .. .. ,. ,. c-path. ,. 1( 11. , ),2,4,8,16 .. .. 16. ま. と. .. め. , Amaterous .. ,. ホスト数. , .. ,. 5.. PC. 16. 4.7 8.2. 行を行い「並列」はプロセッサのクラスタにて並列に実行を行ったものである表の結果を見ると全てのベンチマークにおいて配線長ビア数ともに旧来の手法にくらべて減少しており今回提案した端子接続アルゴリズムの有効性を確認できたこれは新手法によって旧来の手法にみられた冗長な配線経路の選択を防ぐことができたのに加え表のようにパーティションあたりの配線容量が増加しているためだと思われるこの配線容量の増加は端子の密集しているパーティションに顕著に現れており旧来の手法では通過できなかったパーティションが通過できるようになりより配線長の減少に貢献したのではないかと思われる一方処理時間に関しては全てのベンチマークにおいて増加してしまっているこの原因としては準備処理における端子のレイヤ割り当てや端子との接続処理の複雑化が考えられるまた配線容量の増加によって大域配線における経路の探索時間も増加してしまっているため探索空間を制限するなどの処理を加えることによって処理の高速化が期待できる 4.2 台数効果今回提案したアルゴリズムと旧来の手法における並列効率を比較するために各ベンチマークについて、ホスト数を逐次台と変化させた時の速度台で向上率を図に示す今回提案した手法では. .. 8. ホスト数増加による並列効果. ∼ 倍の台数効果を得ることができたが旧来の手法に比べ並列効果が低下してしまっているこの主な原因は大域配線にかかる処理時間が旧来の手法にくらべ大きいことがあげられ大域配線を高速化することによって改善されるものと思われる. 表 3 1 パーティションあたりの平均配線容量ベンチマーク全 part 数旧手法新手法. , 16. Amaterous2 MCC2-45 Amaterous MCC2-75 Amaterous2 MCC2-75 Amaterous MCC1-75 Amaterous2 MCC1-75. 8. 本論文では大域／詳細配線を独立して行う並列配線システムにおける端子接続方式の改良を提案した従来のアルゴリズムでは端子を隣接パーティションを通過すると接続していたため平均して端子辺りパーティション幅程度の配線長増加が生じていた今回提案したアルゴリズムでは端子とパーティションの両端を接続するパスを求めることができるためこのような問題が生じない旧来の手法と提案した手法を比較したところ ∼ の配線長の減少に成功し当初の目標である端子辺りパーティションの幅程度の配線長の増加を防ぎさらにそれ以上の配線長の減少に成功したまたホスト並列における配線にて ∼ 倍の並列効果を得ることができた今後は実行時間の高速化配線長のさらなる減少を行っていく予定である. c-path. ,. ,. ,. .. ,. ,. .. 16%. 4.7 8.2. .. .. 1). ,5. ,. , 16. .. ,. 参考文献. . Amaterous: . , Vol. 42, No. 4, pp.732-744, April 2001. 2) Collaborative Benchmarking Laboratory, Dept. of Computer Science, North Carolina State Univ. 1995.. 6 −60−. 田中孝太郎，大野和彦，中島浩経路選択法による高性能並列ルータ情報処理学会論文誌. PDWorkshop'93. Benchmark. Set.. http://www.cbl.ncsu.edu/CBL Docs/ pdw93.html.

(9)