VLSIレイアウト配置問題のためのsequence-pair理論の拡張

今年度は主に下記の1,2について、研究とデモプログラム作成を行なった。共に4月に発表予定である。1. レクトリニア多角形のパッキング:sequence-pairは矩形パッキングのために提案されたが、近年のVLSIの大規模化に伴い、レイアウトにおいて既設計モジュールの再利用が望まれ、そのためにはL型やT型を含む多角形のモジュールも配置できることが必要である。そこで前年度では、比較的単純な多角形にsequence-pair理論を拡張対応させて、L型に対応させたパッキング手法を提案し証明した。今年度はこれを更に拡張し、複雑なレクトリニア多角形(辺が水平/垂直線分だけ)に対応させた理論を構築し、パッキング手法を提案した。また、提案手法による多角形パッキングには適用できないsequence-pairがあるため、適用可能(全多角形をパッキング可能)なことの必要十分条件を求め、これを証明した。2. 一般構造フロアプランのSimulated Annealing法探索;VLSIレイアウト設計では配置の前に、チップを表す矩形を部屋(矩形)に分割してモジュールを割り当てた「フロアプラン」を求める。フロアプラン研究ではスライス構造が多く用いられていたが、近年、sequence-pairをフロアプランに変換する手法が提案され、非スライス構造を含めた全ての一般構造フロアプランが列挙可能になった。しかしこの手法には、割り当てられるモジュールのない「空部屋」が生じたものが混ざるという欠点があった。そこで、空部屋のない一般構造フロアプランだけを、Simulated Annealing法を用いて効率的に探索するための隣接解を提案し、この隣接解を効率的に求めることができる巧妙な手法を述べ、この解空間の直径が線形サイズであることを証明した。また、提案した解空間とスライス構造の解空間を実験により比較検討した。

今年度は主に下記の1,2について、研究とデモプログラム作成を行なった。共に4月に発表予定である。1. レクトリニア多角形のパッキング:sequence-pairは矩形パッキングのために提案されたが、近年のVLSIの大規模化に伴い、レイアウトにおいて既設計モジュールの再利用が望まれ、そのためにはL型やT型を含む多角形のモジュールも配置できることが必要である。そこで前年度では、比較的単純な多角形にsequence-pair理論を拡張対応させて、L型に対応させたパッキング手法を提案し証明した。今年度はこれを更に拡張し、複雑なレクトリニア多角形(辺が水平/垂直線分だけ)に対応させた理論を構築し、パッキング手法を提案した。また、提案手法による多角形パッキングには適用できないsequence-pairがあるため、適用可能(全多角形をパッキング可能)なことの必要十分条件を求め、これを証明した。2. 一般構造フロアプランのSimulated Annealing法探索;VLSIレイアウト設計では配置の前に、チップを表す矩形を部屋(矩形)に分割してモジュールを割り当てた「フロアプラン」を求める。フロアプラン研究ではスライス構造が多く用いられていたが、近年、sequence-pairをフロアプランに変換する手法が提案され、非スライス構造を含めた全ての一般構造フロアプランが列挙可能になった。しかしこの手法には、割り当てられるモジュールのない「空部屋」が生じたものが混ざるという欠点があった。そこで、空部屋のない一般構造フロアプランだけを、Simulated Annealing法を用いて効率的に探索するための隣接解を提案し、この隣接解を効率的に求めることができる巧妙な手法を述べ、この解空間の直径が線形サイズであることを証明した。また、提案した解空間とスライス構造の解空間を実験により比較検討した。