Sequence-Pair表記された一般構造フロアプランのSimulated Annealing法探索

摘要

VLSIレイアウト設計では，配置問題を解く前にしばしば「フロアプラン」を求める．フロアプランとはチップを表す方形をいくつかの方形状の部屋に分割してモジュールを割り当て，モジュールと配線チャネルの位置を大まかに決めたものである．フロアプラン研究においてはスライス構造を用いたものが多用されていたが，近年，方形パッキングの表現方法であるsequence-pairをフロアプランに変換する手法が提案され，非スライス構造を含めたすべでの一般構造フロアプランを列挙することができるようになった．しかしこの手法には，割り当てられるモジュールのない「空部屋」が生じてしまうことがあるという欠点があった．そこで本論文では，空部屋をもたない一般構造フロアプランだけを，Simulated Annealing法を用いて効率的に探索するための隣接解を提案し，この隣接解を効率的に求めることができる巧妙な手法を述べ，この解空間の直径が多項式サイズで奉ることを証明する．また，提案した解空間とスライス構造の解空間を実験により比較検討する．