シーケンスペアとは？ わかりやすく解説

シーケンスペア（英: sequence-pair）は、矩形配置の表現方法のこと。矩形同士の相対位置関係を矩形名の順列の対により表すことができる。集積回路設計の一工程である配置計画（フロアプラン）での利用を目的として開発されたが、発見的探索法（メタヒューリスティックアルゴリズム）である焼きなまし法と組合わせて用いると、離散数学の組合せ論でNP困難な問題である矩形パッキング問題に有効なことが知られている。

集積回路設計の一工程である配置計画（フロアプラン）では、回路として実現するために必要な様々なモジュール（記憶素子や演算器など）を、シリコン基板上にどのように配置するかを検討する。半導体ビジネスでは、1枚のシリコンウェハーから出来るだけ多くの集積回路を製造することが収益面で不可欠である。そのため、集積回路そのものを出来るだけ小さく設計することが望まれる。

「集積回路を出来るだけ小さく設計する」という要求は、配置計画において「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置する」という要求に置き換えられる。近年の集積回路設計では、性能及び生産性向上の観点から複雑な配置制約を課されるため、単に隙間無く配置すればよいわけではない。しかし、隙間無く配置する作業はモジュールが数個から十数個程度であればまるでパズルのようだが、これが数百、数千、それ以上となると、とても人間が手に負える規模ではないことが明らかだろう。

このような理由から、「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置せよ」という要求はフロアプラン問題と呼ばれ、1980年代になると集積回路設計の自動化に取り組む内外の研究者の格好の研究対象となった。彼らは、フロアプラン問題を人間が解くのではなく、計算機に自動的に解かせるためにはどうしたらよいかを研究したのであった。

フロアプラン問題はモジュールの形状を矩形に限定すると、大きさの異なる矩形をできるだけ隙間無く詰め込む問題となる。この問題は矩形パッキング問題と呼ばれ、NP困難であり^[1]、多項式時間で最適解を得る方法は知られていない。ブロックの数が増えれば増えるほど配置のバリエーションが爆発的に増えていくため、問題解決のために配置の全バリエーションを探索するのは非現実的である。

フロアプラン問題の解法として画期的であった従来手法に、スライス構造がある。1982年にIBMワトソン研究所のラルフ・オッテン^[2]が提唱したスライス構造は、元々はモジュールを配置するための領域をシリコンチップ上に割り当てる方法であった^[3]。 スライス構造とは、集積回路のシリコンチップ全面を垂直線分または水平線分にて再帰的に分割した構造のことであり、分割後の矩形領域を節点（ノード）とした多分木にて表すことができた（図1）。

このスライス構造をフロアプラン問題に応用したのが、テキサス大のD.F. Wongとイリノイ大のC.L. Liuの二人である。オッテンの提唱したスライス構造のデータが多分木であったが、1986年にWongらは水平線分による分割であれば＋記号を、垂直線分による分割であれば＊記号を木の節点に与えて二分木表現にした。そして、この二分木の各々の葉に分割後の各領域に割り当てるモジュールの名前をつけ、この木をスライス木と呼んだ^[4]。ちなみにスライス木は全二分木、すなわち全ての節点が葉であるか、2つの子を持つ。また、同じスライス構造を表現するスライス木が複数存在するが、親と右の子が同じ ${\displaystyle *}$

しかしながら、スライス構造は垂直線分または水平線分にて再帰的に分割した構造なので、畳の四畳半のような構造を表すことができない。つまり、 ${\displaystyle n}$

一般構造の表現方法についてブレークスルーになったのは、1994年に当時北陸先端科学技術大学院大学の学生であった中武らにより提案された、BSG^[7]と呼ばれる構造である^[8]。小さい規模のBSG構造を図4に示すが、その構造は四畳半構造の連続となっていて興味深い。

BSGを斜めの格子構造で説明し、代数表現にしたのがシーケンスペアである。シーケンスペアは、BSG提案の一年後である1995年に北陸先端科学技術大学院大学の学生であった村田らによって提案された^[9]。シーケンスペアという名前の由来は、矩形名の順列の対によって、矩形同士の相対位置関係を表すことから来ている。

与えられた矩形配置をシーケンスペアにエンコードする方法にグリッディング^[14][9]がある。グリッディングの方法は以下のとおり。図5の矩形配置をグリッディングによりシーケンスペアにエンコードした例を、図8に示す。

1. ${\displaystyle \Gamma _{+}}$の導出：各々矩形の右上頂点から右上に向かって右上折れ線^[15]を引く。右上折れ線は、他の矩形や他の右上折れ線とはトポロジー的に交差せずに上、右、上、右、・・・の順に上方向と右方向に交互に引かれる。右上折れ線同士は接し合って間隔がゼロとなっても構わないが、交差は許されない。右上方向に引き出した全ての右上折れ線について、それが発した矩形の名前を左から順に読んだものが ${\displaystyle \Gamma _{+}}$である。
2. ${\displaystyle \Gamma _{-}}$の導出： ${\displaystyle \Gamma _{+}}$の導出と同様に、各々の矩形の左上頂点から左上に向かって左上折れ線^[16]を、上、左、上、左、・・・の順に上方向と左方向に交互に引く。そして、左上方向に引き出した全ての左上折れ線について、それが発した矩形の名前を左から順に読んだものが ${\displaystyle \Gamma _{-}}$となる。

${\displaystyle n}$個の矩形配置をグリッディングによってシーケンスペアにエンコードするには、 ${\displaystyle O(n^{2})}$時間を必要とする。これに対し、計算幾何学のプンレーン・スイープ^[17]と呼ばれる手法を用いて矩形配置から1次元コンパクショングラフを求め、このグラフからシーケンスペアにエンコードする高速グリッディング^[18][19]。この方法を用いると ${\displaystyle O(n\log n)}$時間でエンコード可能である。

シーケンスペアは順列の対なので、 ${\displaystyle n}$個の矩形配置を表すシーケンスペアの全バリエーションは ${\displaystyle (n!)^{2}}$通り存在する。これを全て列挙するということは、従来不可能であった配置の全列挙が可能であることを意味し、これは大変に意義深い。しかしながら、シーケンスペアは冗長な表現を含んでいるため、 ${\displaystyle (n!)^{2}}$が ${\displaystyle n}$個の矩形配置の全バリエーションとは等価ではないことに注意されたい。

ちなみに、 ${\displaystyle n}$が ${\displaystyle 8}$の時のシーケンスペアの全バリエーションは16億2570万2400であり、仮に1個の解の評価に0.01秒を要すると、全ての解の評価に約1600万秒を必要とする。これは約188日分に相当し、たった8個の矩形配置の全探索に半年を要する計算になる。 ${\displaystyle n}$が9個になると約188日の81倍となり、これはおよそ42年に相当する。

シーケンスペアはそれ単独では単なる表現方法に過ぎない。しかし先述のスライス構造と同様に、焼きなまし法などの確率的探索アルゴリズムと組み合わせて用いることで、矩形パッキング問題に対し、準最適な配置を実用的な時間で求めることができる。最近ではシーケンスペアを用いた配置検討工程の応用例として、バス配線経路をモジュール配置制約として与えた配置手法や^[20]、アナログ回路設計特有のモジュール配置制約を課した手法^[21]などが発表されている。

集積回路設計以外では、建築設計における室配置計画への応用も報告されている^[22]。 またシーケンスペアは矩形しか扱えないが、矩形の集合で表現できる多角形、すなわち垂直もしくは水平線分で描かれる多角形（レクトリニア多角形と呼ぶ）はパッキング可能である^[23]。これを利用すると、任意の多角形をレクトリニア多角形に近似すれば、例えば自動車の板金や洋服の型紙を効率よく切り出すパターンの探索が可能になる^[24]。

• 集積回路設計
• 組合せ最適化
• 焼きなまし法
• NP困難
• DAC
• オペレーションズ・リサーチ

• H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packing-based module placement," in Proceedings of IEEE International Conference on Computer-Aided Design, 472-479, 1995.
• 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.
• S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, "Module packing based on the BSG-structure and IC layout applications," IEEE Trans. on Computer-Aides Design of Integrated Circuits and Systems, 17(6): 519-530, June 1998

• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Seuqnece-pairの原著論文が掲載された論文誌。

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 設計自動化に関する論文が掲載される国内発行の論文誌。Seuqnece-pairの関連論文も掲載されている。

• Design Automation Conference 設計自動化、EDAに関する世界最大の国際会議、及び展示会。

• International Conference on Computer-Aided Design EDAに関する権威ある国際会議。ここでSequence-pairの最初の論文が発表された。

• Asia and South Pacific Design Automation Conference 隔年で日本で開催されるEDAに関する国際会議。