概要

配置問題とは、LSIのレイアウト設計において、与えられた回路データとセル
情報をもとに、チップ上の配線領域が最小となるような、個々のセル位置を求め
るものである。
しかしLSIを構成するセル数は非常に多く、配線領域を最小化するためには、
膨大なセル配置の組合わせを調べなければならない。このような組合わせ最適化
問題に対し、シミュレーテッドアニーリング(SA)と呼ばれる逐次アルゴリズムが
有効であることが知られている。
並列SAは、逐次SAを適用する際に問題となる、「温度」と呼ばれる制御パ
ラメタの設定を自動化するために、新たに考案した並列計算機向きのアルゴリズ
ムである。
本実験システムは、並列SAを用い、PIM上でLSI設計における配置問題を解
くものである。

設計対象LSI

本実験システムの対象は、ポリセル
型のスタンダードセルである。

これは高さが一定で幅がまちまちな
セルで構成され、セルの集合であるセ
ル列を複数並べた構造をもつ。
このLSIの各セルおよびチップ周辺に
存在する端子問を結ぶ配線の総延長を、
最小化することが目的である。



スタンダードセルの例

逐次SAアルゴリズム

逐次SAは確率的アルゴリズムの一種であり、疑似乱数を用いて、繰返し解を
改善する。
セル配置に適用した場合には、セル位置をランダムに変更しながら、配置を繰
返し改善する。このとき、処理の初期段階では大域的な改善が、後半では局所的
な改善が行われるように「温度」と呼ばれるパラメタを使用して制御を行う。温
度は低い程、局所的な改善が行われる。
「温度」の制御は対象とする問題に依存し、最適な制御が異なるため、逐次SA
の適用にあたっては、個別に調整が必要である。


					- 36 -