LSI設計自動化とは、コンピュータを用いてLSIの設計を自動的に行うことです。 単にLSIが正しく動くように設計するだけでなく、回路規模(LSIチップ面積)や動作速度、消費電力などの性能を最大化することが求められます。
LSI設計自動化は、組み合わせ最適化問題として定式化することができます。 例えば、LSI設計の中で行われるLSI高位設計では、LSI実現しようとする処理を構成する演算(加算や乗算など)の最適実行スケジュールを求めるスケジューリング設計を含みます。 これは、データ依存に基づく演算間先行制約を満たす複数通りのスケジュールから、目的関数を最小化または最大化するスケジュールを選ぶ組み合わせ最適化問題となります。 組み合わせ最適化問題を整数計画問題(ILP) に変換し、ILP求解プログラム(ILPソルバ)を計算機上で実行して最適解を得ることができます。 しかし、問題サイズが大きくなると指数関数的にILPソルバ実行時間が増大するため、大規模な問題に対してILPに変換する手法を適用して最適解を求めることは現実的ではありません。 この問題を解決するため、最適化問題ごとにその性質を分析して、適切な発見的アルゴリズムを考案・開発することが行われています。 良質なアルゴリズムが開発できれば、ILP求解に比べてはるかに短時間で最適解に極めて近い解を得ることができますが、その一方でアルゴリズム開発が困難かつ時間を要するという問題があります。
焼きなまし法(Simulated Annealing)は、組み合わせ最適化問題求解のための発見的メタアルゴリズムとしてよく知られています。 LSI設計分野では、配置配線といった物理設計最適化に広く用いられています。 LSI高位設計における前述の問題に対して、焼きなまし法の枠組みを利用して複数通りの候補スケジュールを生成し、評価関数を準最適化するスケジュールを選ぶ手法を提案しています。 そこでは各候補スケジュールは演算間先行制約を満たしていることが必須であり、条件を満たす候補スケジュールを効率よく生成する手法を考案しました。 この手法を用いることで、最適化問題ごとに発見的アルゴリズムを開発する必要がなくなり、十分な数の組み合わせを探索して準最適解を求める手段を容易に得ることが可能です。 この手法を用いて、演算スケジュール、演算と演算器の割り当て、演算器配置配線が相互に関連する複雑な組み合わせ最適化問題となる以下のような問題に対する解法を提案しています。