表題番号：2005B-375 日付：2006/02/28
研究課題大規模システムLSI物理設計基盤技術の研究
研究者所属（当時） 資格 氏名
（代表者） 大学院情報生産システム研究科 教授 吉村　猛
研究成果概要
　本研究では大規模システムＬＳＩ物理設計基盤技術の確立を目指し，連結度の強いセル同士をまとめる「クラスタリング」，クラスタレベルでの配置の最適化を行う「フロアプラン」およびセルレベルでの「配置最適化」の各アルゴリズムの研究開発を行っている。
　平成17年度はまず3000個程度のクラスタを想定した最適化基盤技術の開発とプロトタイプ作成による評価実験を行った。具体的な研究実績は以下のとおりである。
(1)高速クラスタリングアルゴリズムの開発
　・セル連結度の評価関数の提案
　・連結度の強い順にセルをまとめていくための，Heapを利用した高速アルゴリズムの開発
を行い，プログラムの作成および標準ベンチマークデータによる評価を行った。実験では20万セルのデータの処理時間は3秒以下と極めて高速であった。
(2)大規模フロアプランアルゴリズムの開発：
　従来の局所探索法に替え，Simulated Annealing法をベースとしたフロアプランのための最適化アルゴリズムを開発し，企業から提供された実データを用いて評価を行った。その結果，3000ブロックレベルでの収束回数をこれまでの約1/3に減少できることを確認した。また，平行して，特定ブロックの位置を固定するための手法の理論的検討を行った。現在，評価中である。
(3)レイアウト配置最適化アルゴリズムの開発。
　LU分解法を用いた2次計画最適化手法による配置最適化手法を検討し，プロトタイプ開発した。実験による評価では，従来のCG法，SOR法に比べ，3倍程度の高速化を達成した。
(4)その他
　関連研究として，システムLSI設計方法論および演算のスケジューリング手法の研究開発を行った。