概要
配置問題とは、LSIのレイアウト設計において、与えられた回路データとセル情報をもとに、チップ上の配線領域が最小となるような、個々のセル位置を求めるものである。
しかしLSIを構成するセル数は非常に多く、配線領域を最小化するためには、膨大なセル配置の組合わせを調べなければならない。このような組合わせ最適化問題に対し、シミュレーテッドアニーリング(SA)と呼ばれる逐次アルゴリズムが有効であることが知られている。
並列SAは、逐次SAを適用する際に問題となる、「温度」と呼ばれる制御パラメタの設定を自動化するために、新たに考案した並列計算機向きのアルゴリズムである。
本実験システムは、並列SAを用い、PIM上でLSI設計における配置問題を解くものである。
設計対象LSI
本実験システムの対象は、ポリセル
型のスタンダードセルである。
これは高さが一定で幅がまちまちな
セルで構成され、セルの集合であるセ
ル列を複数並べた構造をもつ。
このLSIの各セルおよびチップ周辺に
存在する端子問を結ぶ配線の総延長を、
最小化することが目的である。
逐次SAアルゴリズム
逐次SAは確率的アルゴリズムの一種であり、疑似乱数を用いて、繰返し解を改善する。
セル配置に適用した場合には、セル位置をランダムに変更しながら、配置を繰返し改善する。このとき、処理の初期段階では大域的な改善が、後半では局所的な改善が行われるように「温度」と呼ばれるパラメタを使用して制御を行う。温度は低い程、局所的な改善が行われる。
「温度」の制御は対象とする問題に依存し、最適な制御が異なるため、逐次SAの適用にあたっては、個別に調整が必要である。
並列SAアルゴリズム
並列SAは、逐次SAで問題となる温度制御を自動化するものである。
並列SAでは、異なるプロセッサに対して別々の一定温度を与え、個別に乱数を用いた配置改善を実行する。そして値の近い温度をもつプロセッサ間で、一定の期間毎に双方のセル配置の比較及び交換を試みる。このとき、温度の高い方のセル配置の評価が、低い方の評価より良いか、両者が接近していれば、互いの処理しているセル配置を交換する。
この結果、大域的な改善と、局所的な改善が処理の進行に伴い適宜選択され、温度制御の自動化が実現される。最終的には、一番低い温度をもつプロセッサ上に、最も改善の進んだセル配置が現れることになる。
デモ概要
Mu1ti-PSI(64PE)を使用して、以下のデモを行う。
並列SAの実行は、63の異なる温度パラメタで並列に配置改善を行い、残りの1PEで改善経過を監視する。
(1)最適解が分かっている人工的な小規模データを用い、並列SAで最適解へ到達する様子を示す。
●データは、25セル、40ネット規模であり、5x5の方形にセルが正しく並ぶと、評価値が最良になる。
(2)実データを用いて、配置改善を行う。
●データ規模は、125セル、147ネット、24入出力
●まずランダムに初期配置を行い、その評価値及び評価の目安となる配線密度を表示する。初期配置図におけるX軸、Y軸上の棒グラフが配線密度を表している。このグラフが、全体的に低く均一に分散していれば、良い評価値が得られる。
●改善状況は、評価値の実行時表示で監視する。
●一定時間配置改善を行ない、結果を表示する。評価値が良くなっていること、配線密度表示の山が全体的に低くなっていることを確認する。
論理アーキテクチャ設計支援システム「RODIN」
概要
本システムは、Pascal言語で記述された動作仕様からレジスタ・トランスファ(RT)レベルの回路を合成する。システムの開発を通して、各種設計問題に応用可能なシミュレーテッド・アニーリング法への知識の導入とその並列化の有効性を実証する。
特徴
ルールペースト・アニーリング(RA)
ランダムな変換だけでなく、ヒューリスティックな変換(ルール)を加え、ルール毎のコスト減少率に応じてルール選択確率を動的に変化させ、与えられた最適化時間内で良質な解を得る。
RAの並列処理方式
受理率に応じて複数のPEでクラスタを構成し、クラスタ内のPEが協調して1つの状態を最適化することにより、中低温時の受理率を増加させる。
概要
現在、LSIの設計方法は、機能記述(動作仕様)やRTレベル記述(レジスタや演算器を組み合わせた記述)、ゲートレベル記述(AND回路やOR回路などのゲート回路を組み合わせた記述)をその抽象度に合わせて記述し、設計する方法が主流になりつつある。既に、論理合成や配置・配線は自動化されているが、機能記述からRTレベルの回路を作成する段階(機能合成)は自動化されてなく、複雑な最適化を設計者が行なう必要があった。我々の研究対象は、この機能合成の自動化である。
機能合成の処理過程
●構文解析部、スケジュール表作成部ではシステムヘ入力されたPasca1言語を二項演算式に展開し、その式を実行する演算器とタイムステップを適当に定め、初期スケジュール表を作成する。
●最適化部では、なるべく小さいチップ面積、早い処理速度のLSIが生成できるように初期スケジュール表を最適化する。
●レジスタ・アロケーション部では、最適化したスケジュール表の変数を、どのレジスタに割り付けるか決定する。
●ハードウエア記述言語作成部では、最適化されたスケジュール表とレジスタ・アロケーションの結果からハードウエア記述言語を生成する。