SP Placeトライアル報告

1. はじめに

SP Placeアルゴリズムを実装し、評価したので報告する。SP(Sequence Pair)は元UCB客員研究員村田博士によって開発されたアルゴリズムであり、自動フロアプランナの基礎となるブロック配置アルゴリズムである。本来の自動フロアプランナであれば配線可能性等を考慮する必要があるが、今回は簡単化のためモジュール間配線数とモジュール間距離の積を総配線長として、チップサイズと共に目的関数とした。

2. 実行環境

実行環境を以下の表に示す。

3. ベンチマークデザイン

ベンチマークに使用したデザインはSP Placeの評価のために作成した以下のようなデザインである。


図1.ベンチマークデザイン

プロセッサコアに相当するモジュールbから2本のバスA,Bによりモジュールが接続されており、他のこまかい信号線は図では省略されている(実際には与えている)。

4. 評価目的

評価の主眼は主に目的関数と同じく次の2つである。

SP Placeによりどのようなフロアプランが出力されるかを評価する。さらに、それにかかった時間も評価する。

5. テストフロー

  • データ

    上記出力ファイルを別プログラムであるSP ViewerにかければX-Windows上でフロアプランが確認できる。

    6. 実行結果

    メタヒューリスティックアルゴリズムとしてSA(Simulated Annealing)を採用しているため、乱数を使用している。そのため毎回同じにはならないものの、実行結果の例(出力ファイル)を以下に示す。


    図2. 出力ファイル

    左からSP, チップサイズの幅、高さ、その積（面積）、モジュール率および配線長（モジュール間距離）である。

    これをみると2回のくり返しでほぼ最適なSPに到達している。このときのフロアプランを図3に示す。上下は変わっているものの、人間のフロアプランと完全に同じであった。


    図3. フロアプラン実行結果

  • 実行時間

    図3の場合は10秒程度であった。

    7. 考察

    SP Placeアルゴリズムを配線を考慮して実装した。サンプルフロアプランにおいては人間がプランニングしたものと等価なものが出力された。当然だがSP Placeは配線を考慮しないと全く使用できないフロアプランを生成する。しかし、比較的単純な配線長計算によりある程度optimalなフロアプランが得られる見とおしができたため、次期実設計に使用して改良する予定である。

    問題点としては2モジュール間の接続性のみを見ているため、配線がバスの場合に評価値が合わなくなる可能性がある。例えばモジュールa, b, cが直線上に配置されている場合がバス配線長は最小となるが、今回の目的関数のようにモジュール間距離だと最小ではない場合がある。

    8. 参考資料

    H.Murata, K.Fujiyoshi, S.Nakatake and Y.Kajitani "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.15, No.12, December 1996, pp.1518-1524.

    以上
    mail to:asakurai@m1.interq.or.jp