|
Sequence-pair（シーケンスペア）は、矩形配置の表現方法のこと。矩形同士の相対位置関係を矩形名の順列の対により表すことができる。集積回路設計の一工程である配置計画（フロアプラン）での利用を目的として開発されたが、発見的探索法（メタヒューリスティックアルゴリズム）である焼きなまし法と組合わせて用いると、離散数学の組合せ論でNP困難な問題である矩形パッキング問題に有効なことが知られている。 == 概要 == === 技術的背景 === 集積回路設計の一工程である配置計画（フロアプラン）では、回路として実現するために必要な様々なモジュール（記憶素子や演算器など）を、シリコン基板上にどのように配置するかを検討する。半導体ビジネスでは、1枚のシリコンウェハーから出来るだけ多くの集積回路(IC, LSI)を製造することが収益面で不可欠である。そのため、集積回路そのものを出来るだけ小さく設計することが望まれる。 「集積回路を出来るだけ小さく設計する」という要求は、配置計画において「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置する」という要求に置き換えられる。近年の集積回路設計では、性能及び生産性向上の観点から複雑な配置制約を課されるため、単に隙間無く配置すればよいわけではない。しかし、隙間無く配置する作業はモジュールが数個から十数個程度であればまるでパズルのようだが、これが数百、数千、それ以上となると、とても人間が手に負える規模ではないことが明らかだろう。 このような理由から、「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置せよ」という要求はフロアプラン問題と呼ばれ、1980年代になると集積回路設計の自動化（Design Automation）に取り組む内外の研究者の格好の研究対象となった。彼らは、フロアプラン問題を人間が解くのではなく、計算機に自動的に解かせるためにはどうしたらよいかを研究したのであった。 フロアプラン問題はモジュールの形状を矩形に限定すると、大きさの異なる矩形をできるだけ隙間無く詰め込む問題となる。この問題は矩形パッキング問題と呼ばれ、NP困難であり〔 H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 15(12):1518–1524, December 1996.〕、多項式時間で最適解を得る方法は知られていない。ブロックの数が増えれば増えるほど配置のバリエーションが爆発的に増えていくため、問題解決のために配置の全バリエーションを探索するのは非現実的である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sequence-pair」の詳細全文を読む スポンサード リンク
|