解説 VLSI CADにおける組合せ最適化手法

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.6 (2018/6) 目次へ

前の記事へ次の記事へ


解説

VLSI CADにおける組合せ最適化手法

Combinatorial Optimization for VLSI CAD

髙島康裕

髙島康裕 正員 北九州市立大学国際環境工学部情報メディア工学科

Yasuhiro TAKASHIMA, Member (Faculty of Environmental Engineering, The University of Kitakyushu, Kitakyushu-shi, 808-0135 Japan).

電子情報通信学会誌 Vol.101 No.6 pp.574-578 2018年6月

©電子情報通信学会2018

abstract

 VLSI CADでは,製造時の制約を考慮する必要上,組合せ最適化問題として定式化されることが数多い.しかし,実用上考慮される最適化問題のほとんどがNP-困難である.そのため,様々な手法がこれまでも提案されている.ここで,近年の計算機性能の向上とアルゴリズムの開発により,これまでに利用されてこなかった解法がVLSI CADに利用されてきている.本稿では,その中で,モンテカルロ木探索による解法と,制約充足問題による解法を取り上げる.

キーワード:VLSI CAD,組合せ最適化問題,モンテカルロ木探索,制約充足問題

1.は じ め に

 VLSI CADは,集積回路が大規模化するにつれて,重要性が高まっていった.ここで,集積回路の製造上の制約を考慮すると,離散問題として考慮することが自然であった.そのため,ほとんどの問題が組合せ最適化問題として定式化されたきた.しかし,これらの定式化された問題は,大多数がNP-困難である(1).その対応として,数多くの解法が提案されたきた.

 近年,計算機性能の飛躍的な向上とその上で動作する高性能なアルゴリズムの開発により,VLSI CADをはじめとする組合せ最適化問題に,新たな解法の利用がなされるようになってきた.本稿では,モンテカルロ木探索(MCT)と制約充足問題を取り上げ,これらの組合せ最適化問題への適用についての一例を示す.

2.VLSI設計における組合せ最適化問題

 1.で述べたように,CAD等の問題は組合せ最適化問題として定式化される.VLSI設計で発生する問題も含めて,組合せ最適化問題において,NP-困難である問題に対しては,現実的な時間で解を得ることはできないと予想されている(2).そこで,これまで,多数の解法が提案されてきた.これらの解法は,出力される解質に応じて,①厳密解法,②近似解法,③発見的手法,等にクラス分けされる.厳密解法は,出力される解が最適解であることが保証される反面,解が得られるまでの時間は問題の入力サイズの多項式を超える計算時間を認める解法である.以前は,理論的な側面が強調されていたが,最近,SATソルバ(3)やILPソルバ(4),(5)の性能向上が著しく,実用的にも注目されている解法である.近似解法は,厳密解法よりも高速に,かつ,出力解の最適解からの劣化度合いが理論的に保証される解法である.理論的には非常に興味深い手法であるが,実際には,この性能を保証できる問題が余り存在せず,実用的とは言えない状況である.そして,発見的手法は,実行時間が実用的である反面,解質に対する保証がない手法である.この発見的手法の性能評価は,ベンチマークと呼ばれる入力に対する解で行われることが一般的である.また,メタヒューリスティックと呼ばれる確率を用いた手法,例えば,Simulated Annealing(SA)法(6)やGenetic Algorithm(GA)法(7)等は,得られる解質の良さと適用の容易さから広く利用されてきた.これらは無限の計算時間を掛ければ,確率的に最適解に到達可能であることが証明されている.一方で,ある程度の時間を掛けないと,良質な解を得ることができない.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。