• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版

HOMEエレクトロニクス電子設計 > 学習データやFPGAを活用、多層配線問題のコンテスト

ニュース

学習データやFPGAを活用、多層配線問題のコンテスト

DAシンポジウム2016聴講レポート

  • 島村光太郎=DAシンポジウム2016幹事、日立製作所
  • 2017/02/03 09:01
  • 1/2ページ

 システムとLSIの設計技術に関する研究会「DAシンポジウム2016」(2016年9月14日~16日に石川県で開催、DAはDesign Aitomationの略)では、基調講演や招待講演、一般論文発表に加えて、「アルゴリズムデザインコンテスト」(関連ページ)と呼ぶコンテストが行われた。同企画は2012年に開始し、今回で5回目となる。

 今年のコンテストでは、「ナンバーリンク」(※ナンバーリンクはニコリの登録商標)と呼ぶパズルを多層配線に拡張した問題が出題された。参加者はこの問題を自動で解くソフトウエアやハードウエアを会場に持ち込み、制限時間内でどれくらい多くの問題を解けるかを競い合う。参加チーム数は5チームだった。

 ナンバーリンクとは、盤面の格子中に数字が配置されていて、同じ数字同士を縦横の線で結ぶというパズルである(図1)。1マスに線は1本しか引けず、線は交差してはいけない。このパズルは、LSIやボード上の配線経路を求める「1層配線問題」と親和性が高い。本来のナンバーリンクは解が1つしか存在しないが、前回のDAシンポジウムでは解の複数ある問題で線の長さや曲がる回数の少ない解を探索する最適化問題に拡張して、DA分野との親和性を更に高めた(日経テクノロジーオンライン関連記事)。

図1●ナンバーリンクの例 DAシンポジウムの図。

 今回のDAシンポジウムでは、問題がこれまでの1層配線から多層配線に拡張された(図2)。参加者の技術レベルが向上して、より複雑な問題を解くことができるようになってきたためである。多層配線では異なる層間を接続する線(「ビア」と呼ぶ)が必要になる。今回の問題ではビアの位置は予め指定されている。ビアの位置を自由に選択できる問題と比べると解の探索範囲が狭くなるが、1層配線問題と比べると格段に難易度が高まっていると考えられる。例えばビアの数をn個とすると、数字とビアの組み合わせの場合の数はnの階乗であり、nの増加とともに指数関数的に増える。参加者が難易度の高まりにどの様に対処するかが見所だった。

図2●ナンバーリンクの多層配線化 「a」及び「b」と書かれたマスを上下に接続する線が予め指定されたビアである。DAシンポジウムの図。
[画像のクリックで拡大表示]

おすすめ