LSIの配線問題 -DAシンポジウムの配線問題解法コンテスト-：2．機械学習とFPGAを用いた配線問題解法への取り組み

全文

(1)小特集. Special Feature. 2 機械学習と FPGA. を用いた配線問題解法への取り組み川村一志長谷川健人多和田雅師戸川望. 基応専般. 早稲田大学. LSI 設計に欠かせない配線問題への取り組み. の“経験則”をアルゴリズム上で再現するための技術と. 近年のモバイル・IoT（Internet of Things）デバイス. 線問題の解空間を効率的に限定するために機械学習. の普及とアプリケーションの多様化に伴い，デバイス上. がどのように活用されるのかを解説する．さらに，ヒュー. の計算処理量が増加し，大規模なシステムを集積化し. リスティック配線の探索時間を削減するための取り組. 1 つの LSI（Large-scale integrated circuit）に封入す. みとして FPGA（Field-programmable gate array, 再. ることが要求されている．大規模システムではモジュー. 構成可能なハードウェア）を用いた配線問題解法シス. ル間の通信量が多くなり，端子と端子を接続する配線. テムを紹介する．. して機械学習が注目されている．本稿では機械学習を用いた 2 次元および 3 次元の配線手法を紹介し，配. の面積が LSI の大部分を占める．配線の面積などハードウェアコストを最小化するように端子間を配線で接続する問題は組合せ最適化問題の一種であり配線問題と. 228. 機械学習を用いた 2 次元配線手法. 呼ばれる．配線問題は NP 困難問題であり，最適解を. 広大な解空間を持つ配線問題においては，探索. 求めるために膨大な計算時間を要する．加えて，微細. 対象となる解空間を適切に限定することが重要となる．. LSI 製造技術の光学的な限界から，集積度を高めるた. その方法の 1 つとして，機械学習の活用が考えられる．. めの LSI 3 次元積層技術が研究されており，配線問題. 機械学習では，あらかじめ用意された解答データベー. を解くのにかかる計算時間はますます大きくなっている．. スを教師データとして学習することで，未知の問題から. 解の候補となる配線パターンの集合（解空間）が大. 解答を予測する解答予測器を構成可能である．過去の. きい配線問題においては，厳密な最適解を求めること. 配線パターンを反映した配線結果を解答予測器により. が現実的に不可能となる．一方で，配線問題の解は. 得ることができれば，解探索時の大きな手助けとなる．. 厳密な最適解ではなく近似された準最適解でも実用に. 機械学習を用いた 2 次元配線手法のフローを図 -1. 耐える可能性がある．そのため実際には，計算時間と. に示す．フローは 5 つのフェーズからなる．Phase 1 では，. 解の最適度を考慮して，近似された準最適解を求める. 配線データベースを機械学習し，配線予測器を構成す. ヒューリスティックなアプローチが使用される．ヒューリ. る．ニューラルネットワークを用いて配線予測器を構成. スティックなアプローチでは，探索と呼ばれる行為を繰. することにより，過去の配線パターンが持つ潜在的か. り返し，解候補を列挙，あるいは解空間を限定し最終. つ複雑な特徴を反映することができる．Phase 2 では，. 的な準最適解を求める．有限の時間で探索を終了させ. Phase 1 で構成した配線予測器を用いて，配線問題の. るためには，効率よく解空間を限定していく，ある意. 配線を予測する．我々が実施した計算機シミュレーショ. 味熟練者の経験則のようなものを実装すればよい．こ. ンの結果，Phase 2 の時点で約 79% の配線が正しく. 情報処理 Vol.59 No.3 Mar. 2018 小特集 LSI の配線問題─ DA シンポジウムの配線問題解法コンテスト─.

(2) 予測できていることを確認している．Phase 3 以降で. 得られなかった場合は，Phase 5 で改善範囲を拡張し. は，Phase 2 の時点で正しく配線することのできなかっ. て再度 Phase 4 のルーティングを試みる．. た配線を再配線する．Phase 3 にて，配線が途切れて. 機械学習を用いた 2 次元配線手法における配線予. いる等の理由から正しく配線できていない領域を改善. 測（Phase 2）の詳細を図 -2 に示す．配線予測フェー. 範囲として指定し，Phase 4 で改善範囲に対してのみ. ズでは，配線領域中の各マスの配線形状をニューラル. ヒューリスティックなルーティングアルゴリズムを適用す. ネットワークで構成された配線予測器を用いて予測する．. る．Phase 4 で用いるルーティングアルゴリズムとして. 図 -2 にあるように，対象となるマスの周囲に存在する. さまざまな手法が候補に挙がるが，たとえば，タッチ. 端点の配置情報に基づいて配線予測がなされる．我々. 1）. & クロス法に基づくルーティングアルゴリズムを採用. が実施した計算機シミュレーションを通して，高い予測. することが考えられる．Phase 4 で正しい配線結果が. 精度を得るためには周囲 9 × 9 マス以上の端点情報が必要であることが分かっている．本手法により，ヒュー. 配線データベース. 配線問題（2D） 1 2. 1 3 5 4. 3 5 2 4. リスティックなルーティング手法のみでは解を導出できなかった配線問題（36 × 36 マス相当の問題）に対しても解を導出することに成功している．. Phase 1：トレーニング. Phase 2：配線予測. 機械学習を用いた 3 次元配線手法. 配線予測器. Phase 3：改善範囲選択. X. Y. 3 次元の配線問題では，平面的な配線だけでなく階. ニューラルネットワーク. 層を跨いだ配線が必要となる．配線が階層を跨ぐため. Phase 4：ルーティング. にはビアと呼ばれる接続ポイントを通過する必要があり，. 反復回数以内に解が見つかったか？. 配線結果. 通常，複数の配線が 1 つのビアを共有することは許され. Phase 5：改善範囲拡張 1 2 3 5 2 4. ない．したがって，3 次元の配線をする際には端点とそ. 1 3 5 4. の端点が通過するビアの対応関係を決めておく必要があり，その組合せ数により（2 次元の配線問題と比較して）. 図 -1 機械学習を用いた 2 次元配線手法. ①中心が配線領域であるようなN×Nの windowを抽出 1. 0. 0. 0. 0. 0. 5. 0. 1. 0. 1. 1. 18 15. 4. 1. 1. Y. 1. 0. 9. 3. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 2 10 9. 4. …. X. Y. 5 6. …. 17. ②中心を除いたN2-1個の領域を二値に分類（1：端点，0：配線領域）. ③配線予測器を用いて，N2-1個のデータから中心の配線形状を予測 or. or. or. or. or. or. 図 -2 配線予測（図 -1，Phase 2）. 2. 機械学習と FPGA を用いた配線問題解法への取り組み情報処理 Vol.59 No.3 Mar. 2018. 229.

(3) 小特集. Special Feature. 解空間が一気に大きくなる．機械学習により過去の配. 用いて，各端点が通過するビアの位置を尤度リストと. 線パターンから端点とビアの対応関係をあらかじめ限定. して出力する．すなわち，Phase 2 にて各端点が通過. することができれば，解探索時の大きな手助けとなる．. するビアが「おおよそどの位置にありそうか」を予測し，. 機械学習を用いた 3 次元配線手法のフローを図 -3. Phase 3 で探索する解空間を限定する．Phase 3 では，. に示す．フローは 3 つのフェーズからなる．Phase 1 で. Phase 2 の結果に基づき，ヒューリスティックなルーティ. は，配線データベースを機械学習し，ビア予測器を構. ングアルゴリズムを適用し，配線結果を得る．. 成する．ビア予測器は 2 次元配線問題における配線. 機械学習を用いた 3 次元配線手法におけるビア予測. 予測器同様，ニューラルネットワークで構成され，端点. （Phase 2）の詳細を図 -4 に示す．ビア予測フェーズ. が通過するビアのおおよその位置を予測するものであ. では，各端点が通過するビアのおおよその位置をニュー. る．Phase 2 では，Phase 1 で構成したビア予測器を. ラルネットワークで構成されたビア予測器を用いて予測し，尤度リストとして出力する．尤度リストには，8 通. 3. 4 a 4. りの位置（遠・近と 4 方向の組合せ）のそれぞれにつ. 配線データベース. 配線問題（3D）. いて，対象となる端点が通過するビアがその位置に存. 2 b. b. 1 2 a 1 3. Phase 2：ビア予測. に，ビア予測は対象となる端点の周囲に存在するほかの端点およびビアの配置情報に基づいてなされる．. ビア予測器. ビア予測結果尤度. 北東／近接via 北西／近接via 南西／近接via 南東／近接via 北東／遠方via 北西／遠方via 南西／遠方via 南東／遠方via. 在する可能性を数値化して記録する．図 - 4 にあるよう. Phase 1：トレーニング. X. FPGA を用いた配線システム. Y. ヒューリスティックなルーティング手法を用いて配線. ニューラルネットワーク. 問題を解くためには高速な解法システムが必要となる．. Phase 3：ルーティング 4 a 4. 3. 配線結果. 1 2 a 1 3. また，解の収束性を考慮に入れると，複数のパラメー. 2 b. タで同時並列的に試行するような解法システムが望ま. b. しい．これらをソフトウェアで実現するためには高性能. 図 -3 機械学習を用いた 3 次元配線手法. ①端点を中心とするN×Nの windowを抽出 2 端点（1） Layer z1. 1 3 a. 対応する端点. 端点（2） Layer z2. （1.0：ビア，0.5：端点，0.0：配線領域）. 0.0 0.0 0.5 0.0 1.0 0.5 0.0 0.0 0.5 0.0 0.0 0.0. 4 b. 0.0 0.0 1.0 0.0 0.0. 1. 0.0 0.0 0.5 0.0 0.0. 3 d. X. 0.0 0.0. Y. 0.0 1.0 0.0 0.5 0.0. 0.0 0.0 0.0 0.0 0.0 0.0 0.0. 0.0 0.0. 1.0 0.0 0.0 0.0 0.0. c. 230. c 4. ③ビア予測器を用いて， 2（N2-1）個のデータから端点（1）が使用するビアの位置を予測. ②中心を除いたN2-1個の領域を三値に分類. 0.0 1.0 0.0 0.0 0.0. Y. 尤度リスト. “端点（1）が使うビアはどの辺にありそうか？”を表現. 北東／近接via 北西／近接via 南西／近接via 南東／近接via 北東／遠方via 北西／遠方via 南西／遠方via 南東／遠方via. 情報処理 Vol.59 No.3 Mar. 2018 小特集 LSI の配線問題─ DA シンポジウムの配線問題解法コンテスト─. 図 -4 ビア予測（図 -3，Phase 2）.

(4) な CPU が必要となることから，我々は複数の FPGA. このとき，予測器を用いて得た予測結果も同時に送信. に配線手法を実装し，複数のパラメータで並列実行可. する．乱数のシード値はそれぞれのボードで異なる値と. 能な配線問題解法システムを構築することにした．本. し，8 台の PYNQ-Z1 上で与えられたシード値に基づ. 章では，我々が構築した FPGA を用いた配線問題解. き問題を解く．解が収束した場合は Raspberry Pi に. 法システムを紹介する．. 解答を送信する．解が収束せずに解答が得られなかっ. 図 -5 に FPGA を用いた配線問題解法システムの外. た場合も Raspberry Pi にその旨を送信する．Rasp-. 観を示す．本システムは我々が 2017 年に構築したもの. berry Pi では各 PYNQ-Z1 から解答を回収し，最も. であり，配線手法を実装するための FPGA ボードとし. 早く解けたものを解答とする．一定時間以内にいずれ. て Xilinx 社の PYNQ-Z1 ボードを 8 台使用している．. の PYNQ-Z1 からも解答が得られなかった場合，シス. PYNQ-Z1 ボードには ZYNQ コア（FPGA）と ARM. テム全体として解答が得られなかったものとする．. プロセッサが搭載されている．これらは共有メモリを介. 表 -1 に FPGA 上で実際に 3 次元配線問題を解い. して接続されており，1 つのボードで Linux OS 上での. たときの解答時間を示す．比較対象として用いたのは，. ソフトウェア動作と FPGA 上でのハードウェア動作が. Raspberry Pi 上で動作させたソフトウェアである．ソー. 実現される．さらに，これらのボードを集中管理する. スコードは C++で実装した同一のものであり，Rasp-. ホストマシンとして Raspberry Pi を使用した．. berry Pi で動作させる場合はソフトウェアとしてコンパ. 配線問題を解く際は，Raspberry Pi から 8 台の. イルし，FPGA 上で動作させる場合は高位合成ツール. PYNQ-Z1 に対して問題と乱数のシード値を配信する．. （Xilinx 社の VivadoHLS 2016.1）を用いて実装した．本稿で紹介したような“機械学習や FPGA を活用. ホスト. して配線問題を解くシステム”は現状実用レベルに達し. クライアント. 無線LAN. ていない．しかしながら，今後ますます複雑化する配線問題の効率的な解決に向け，これらの技術が非常. HUB. に重要な意味を持つであろうことが予想される．. Ethernet. 参考文献 1） Kawamura, K., Shindo, T., Shibuya, T., Miwatari, H. and Ohki, Y. : Touch and Cross Router, 1990 IEEE International Conference on Computer-Aided Design, pp. 56 - 59 ( Nov. 1990). （2017 年 11 月 21 日受付）. （a）システム外観. ■川村一志（正会員） [email protected] 2016 年に早稲田大学大学院情報理工学専攻修了．博士（工学）．現在，同大学理工学術院総合研究所次席研究員． ■長谷川健人（学生会員） [email protected]. （b）実際のシステム図 -5 8 台の FPGA ボードを用いた配線問題解法システム. 2017 年に早稲田大学大学院情報理工・情報通信専攻修士課程修了．現在，同博士後期課程在籍． ■多和田雅師（正会員） [email protected]. 表 -1 3 次元配線問題の解答時間比較 [sec] 問題 A B C D. Size 端点の総数 72 × 72 × 8 6 8×8×4 20 15 × 15 × 4 81 60 × 60 × 4 999. CPU 0.208 0.137 10.018 9.389. FPGA 0.00409 0.00167 0.236 0.274. 2015 年に早稲田大学大学院情報理工学専攻修了．博士（工学）．現在，同大学情報通信学科助教． ■戸川望（正会員） [email protected] 1997 年に早稲田大学大学院電気工学専攻修了．博士（工学）．現在，同大学情報通信学科教授．. 2. 機械学習と FPGA を用いた配線問題解法への取り組み情報処理 Vol.59 No.3 Mar. 2018. 231.

(5)