冷却過程のばらつきを利用したシミュレーテドアニーリング法による配置手法(システムLSI設計及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
近年のVLSI設計は, 配線抵抗や, 電圧降下, 熱集中など様々なDeep-Submicron (DSM)問題への対処が不可欠となっている.このような多数の因子からなる複雑な問題の近似解を求める方法として, シミュレーテドアニーリング(SA)法が用いられる.シミュレーテドアニーリング(SA)法は, 多数の要素の組み合わせ問題に対して擬似温度Tにおける評価関数(擬似エネルギー)と乱数により熱平衡解を一旦求めた後に, 徐冷によりごく低温における組み合わせを近似解として求める方法で, 経験的なアルゴリズムに比べて高品質であることが知られている.SA法では, 擬似乱数や熱平衡までの繰返し回数, 冷却割合により解の品質が影響されるが, 得られる解のばらつきについて定量的な実験は, 我々の知る限り報告されていない.本報告では, われわれは簡単な配置問題に限ってSA法が近似解に至る過程について, そのばらつき範囲の上限, 下限を得る実験をおこなう.我々の実験では, まず素子数をNとして, 各温度TでM・N回のSA判定毎に熱平衡解をn個サンプリングする.次に, n個の解の中から評価値が最大, 最小となる解Smax, Sminを次温度T'の初期解として繰り返す.これにより最大評価値の履歴と最小評価値の履歴をばらつきの上限, 下限として定量化するものである.実験の結果, 最終解の評価値の差は30-50%程度になることが判明した.本手法は, よりよい解を安定して得るアルゴリズムとしても用いることができると考える
- 一般社団法人情報処理学会の論文
- 2005-05-19
著者
関連論文
- 論理回路レべルにおけるクロストークによる遅延変動の推定方法(ディペンダブル設計,FPGA応用及び一般)
- 論理回路レベルにおけるクロストークによる遅延変動の推定方法(ディペンダブル設計,FPGA応用及び一般)
- 論理回路レベルにおけるクロストークによる遅延変動の推定方法(ディペンダブル設計,FPGA応用及び一般)
- クロストークによる遅延変動を考慮した論理シミュレーション(物理設計,デザインガイア2009-VLSI設計の新しい大地)
- クロストークによる遅延変動を考慮した論理シミュレーション(物理設計,デザインガイア2009-VLSI設計の新しい大地-)
- 配線層数の最小化を目指す多層再配線手法(システムLSI設計及び一般)
- 冷却過程のばらつきを利用したシミュレーテドアニーリング法による配置手法(システムLSI設計及び一般)
- 冷却過程のばらつきを利用したシミュレーテドアニーリング法による配置手法(システムLSI設計及び一般)
- 配線層数の最小化を目指す多層再配線手法(システムLSI設計及び一般)