Rectangular Dualに基づくマクロセル配置手法

概要

論文の詳細を見る
カスタムLSI、 Sea-Of-Gate等のレイアウト設計では、任意形状マクロセルの配置問題を解くことが必要となる。このマクロセル配置問題に対する従来手法として、Sechenらの手法と、Uptonらの手法が報告されている。両者は共にsimulated annealingを用いた繰り返し改善手法である。Sechenらは、マクロセル同士のオーバーラップを認めながら配置変換を行なう。この際、マクロセルのオーバーラップをコスト関数に組み込み、オーバーラップを解消するように最適プロセスを方向づける。しかし、オーバーラップを持った配置は、面積・ネット長の評価力が正確ではない。さらに、オーバーラップを導入することにより解空間が拡がるため、オーバーラップを認めない手法に比べ、最適解を探索するための手数が大きくなる。Uptonらはマクロセルの相対配置をslicing木で表現する。しかし、slicing木で表現できない(non-slicing)配置が多数存在する。本手法は、rectangular dual(矩形双対グラフ)を用いて、マクロセルの相対配置を表現する。これによって、オーバーラップが無く、non-slicingな配置を簡潔に表現することが可能となった。さらに、rectangular dualを使った、マクロセルの配置変更が定義可能である。本配置手法では、この配置変更法を基に、simulated annealingによる繰り返し配置改善を行なう。
一般社団法人情報処理学会の論文
1991-02-25

Rectangular Dualに基づくマクロセル配置手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク