シーケンスペア

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

概要

技術的背景

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

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

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

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

スライス構造

図1: Ottenのスライス構造の例（左）と、それに対応する多分木（右）

Ottenによるスライス構造の提案

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

図2: スライス構造（左）に対応するWong & Liuのスライス木（右）

スライス木

このスライス構造をフロアプラン問題に応用したのが、テキサス大のD.F. Wongとイリノイ大のC.L. Liuの二人である。Ottenの提唱したスライス構造のデータが多分木であったが、1986年にWongらは水平線分による分割であれば＋記号を、垂直線分による分割であれば＊記号を木の節点に与えて二分木表現にした。そして、この二分木の各々の葉に分割後の各領域に割り当てるモジュールの名前をつけ、この木をスライス木と呼んだ。ちなみにスライス木は全二分木(full binary tree)、すなわち全ての節点が葉であるか、2つの子を持つ。また、同じスライス構造を表現するスライス木が複数存在するが、親と右の子が同じ＊もしくは＋記号を持たないスライス木を、非平衡スライス木(skewed slicing tree)と呼ぶ。図2はスライス構造と、それに対応する非平衡スライス木の例である。

標準化ポーランド記法

Wongらは、非平衡スライス木を逆ポーランド記法で表現し、これを標準化ポーランド記法(normalized polish expression)と呼んだ。これはすなわち、モジュール配置を文字列にエンコードしたことになる。なお、標準化ポーランド記法では＊もしくは＋記号が連続することはない。このことは非平衡スライス木を見れば明らかである。例えば、図2のスライス構造を表す標準化ポーランド記法は、21＋745＊6＊＋3＋＊となる。

スライス木は全二分木であることから、モジュール数（すなわち葉の数）がnのとき、葉以外の節点の数はn-1なので、モジュールn個の配置を2n-1個の文字にて表現することができる。この文字列から元の配置をデコードするには各文字を1回ずつなめれば良いので、$O(n)$時間でデコード可能である。

Wongらはさらに、標準化ポーランド記法の文字列において、文字と文字を入れ替え一定のルールを作り、元の文字列が表すモジュール配置とは異なる配置の生成を可能にした。これを元の解の隣接解とし、デコード後のモジュール配置を囲む最小の長方形の面積を評価関数とすれば、焼きなまし法を用いることで、モジュールを出来るだけ小さい矩形領域内に配置するフロアプラン問題の準最適な解を求めることが可能になる。

図3: スライス構造では表現できない構造

スライス構造では表現できない構造

しかしながら、スライス構造は垂直線分または水平線分にて再帰的に分割した構造なので、畳の四畳半のような構造を表すことができない。つまり、n個のモジュール配置の準最適解をスライス構造を用いて焼きなまし法で探索した場合、そもそも四畳半構造を表すことができないので、nが4以上では探索範囲が必然的に限定されてしまうことになる。

これは、もしn個のモジュール配置の準最適解の殆どが四畳半構造を含んでいた場合、スライス構造を用いて探索する限り、これらの解を得ることが不可能なことを意味している。それゆえ、研究の方向は一般構造の表現、すなわちスライス構造だけでなく、四畳半を含んだ構造も表現可能な方法の開発に進んでいく。

シーケンスペアについて

図4: BSG構造の例。真ん中の部屋(C)と各部屋との相対位置関係が、A:上、B:下、L:左、R:右と定まる。

一般構造の表現

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

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

余談だが、BSGもシーケンスペアも、その理論の証明には北陸先端大近辺の温泉が一役買っている。どちらも議論の際には格子構造を考える必要があるが、温泉のタイルが格子状であり、湯船につかりながら温泉が閉店するまでタイルを見つめて考えていた、とのことである。それもあってシーケンスペアの論文はよく練られて掲載されたためか、Google Scholarによれば約330本の論文に引用されているとのことで、この分野では突出した引用件数である。また、これらBSGとシーケンスペアの著者は同じ4名（中武、村田、藤吉、梶谷）で、現在村田はEDAツールベンダーを起業、他3名は東京と福岡で大学教員を続けている。

図5: シーケンスペア(1 3 2 4 5 6 ; 2 1 4 6 3 5)に対応する矩形配置。

定義

シーケンスペアは、n個の矩形の相対位置関係を、矩形名の順列$\Gamma _{+}$と$\Gamma _{-}$の対$(\Gamma _{+};\Gamma _{-})$で表す。

矩形同士の相対位置関係は次に述べる「上下左右制約」として表される。いま矩形aと矩形bがあり、$\Gamma _{+}$と$\Gamma _{-}$で共にaがbの前にあるとき、すなわち(a b;a b)は、矩形aが矩形bの左にあることを表す。また、$\Gamma _{+}$でaがbの前にあり、$\Gamma _{-}$でaがbの後ろにあるとき、すなわち(a b;b a)は、矩形aが矩形bの上にあることを表す。

例として、6個の矩形からなるシーケンスペア(1 3 2 4 5 6 ; 2 1 4 6 3 5)に対応する配置を図5に示す。矩形4と5に着目すると、$\Gamma _{+}$と$\Gamma _{-}$で共に4は5の前にある。従って、矩形4は矩形5の左に配置される。また、矩形1と2に着目すると、$\Gamma _{+}$では1は2の前に、$\Gamma _{-}$では1は2の後ろにあるので、矩形1は矩形2の上に配置される。どの矩形同士についても、シーケンスペアと図5の配置が対応していることが確認できる。

シーケンスペアは、どのような矩形配置でもシーケンスペアにエンコードすることが可能であり、逆に任意のシーケンスペアから矩形配置にデコードすることも可能である、という特色を持つ。

図6: Sequence-pair(1 3 2 4 5 6 ; 2 1 4 6 3 5)に対応する斜格子。

斜格子

シーケンスペアそのものは単なる順列の対なので、このままでは矩形同士の相対位置関係を捉えにくい。そこで斜格子と呼ばれる図を書くと、大変分かりやすくなる。

サイズnの斜格子とは、平面上に描いた$+45$度の傾きのn本の平行線と、$-45$度の傾きのn本の平行線からなる平面上の格子構造を言う。 $+45$度の平行線には、左上の線から順に$\Gamma _{+}$の矩形名が与えられ、$-45$度の平行線には左下から順に$\Gamma _{-}$の矩形名が与えられる。この双方の傾きの平行線の中で、同じ矩形名が与えられた線同士が交差する部分に、その矩形名の交点を与える。 以上の手順で作成された図をみると、シーケンスペアが表す上下左右制約を簡単に読みとることができる。例えば、矩形aに着目したとき、交点aの右側90度の範囲に入っている交点に対応する矩形は全て、矩形aの右側にあると制約されている。上側、下側、左側の制約についても同様に読みとることが出来る。

図5の配置に対応するシーケンスペア(1 3 2 4 5 6 ; 2 1 4 6 3 5)の斜格子を、図6に示す。 この図を見ると、矩形4の右側に制約されている矩形が5と6であることが簡単に分かるだろう。

図7: Sequence-pair(1 3 2 4 5 6 ; 2 1 4 6 3 5)に対応する水平制約グラフ（左）と垂直制約グラフ（右）。

デコード

シーケンスペアが示唆する上下左右制約を守って各矩形をできるだけ左下詰めにした配置は、水平／垂直制約グラフを用いた次の手順により求めることができる。

水平制約グラフの作り方は次の通り。

1. 各矩形が点に対応し、その矩形の横幅を点の重みとする。
2. 左右制約関係にある全ての矩形対について、左側の矩形に対応する点から右側の矩形に対応する点に有向枝を張る。
3. このグラフに、大ソース点と大シンク点を付加する。

このグラフにおける大ソース点から各点までの最長パス長が、対応する矩形の左下角x座標となる。 また垂直制約グラフの作るには、水平制約グラフの作り方にならって、点重みが矩形の高さとなり、枝を全ての矩形対の上下制約関係により張り、これに大ソース点と大シンク点を付加すればよい。垂直制約グラフの大ソース点から各点までの最長パス長は、対応する矩形の左下角y座標になる。以上の方法を用いると、矩形数がnのシーケンスペアを$O(n^{2})$時間で求めることができる。

シーケンスペア(1 3 2 4 5 6 ; 2 1 4 6 3 5)の水平制約グラフを図7の左に、垂直制約グラフを右に示す。

ところで、上記の方法はスライス木のデコード時間($O(n)$)よりも遅いため、確率的探索の1回毎の解の評価に時間がかかってしまい、良質な解を得るのにスライス木よりも多くの時間を要してしまう。これに対し、2001年にシーケンスペア上の最長共通部分列(longest common subsequence)を求めて$O(n\log \log n)$時間でデコードするFAST-SPが、2003年にはシーケンスペアの冗長性を排除することで$O(n)$時間でデコードするSelected Sequence-pairが提案されている。

図8: 図5の矩形配置からグリッディングによりSequence-pair(1 3 2 4 5 6 ; 2 1 4 6 3 5)を導出した例。

エンコード

与えられた矩形配置をシーケンスペアにエンコードする方法に、Griddingがある。Griddingの方法は以下のとおり。図5の矩形配置をGriddingによりシーケンスペアにエンコードした例を、図8に示す。

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

n個の矩形配置をGriddingによってシーケンスペアにエンコードするには、$O(n^{2})$時間を必要とする。これに対し、計算幾何学のplane-sweepと呼ばれる手法を用いて矩形配置から1次元コンパクショングラフを求め、このグラフからシーケンスペアにエンコードするFAST-griddingがある。この方法を用いると$O(n\log n)$時間でエンコード可能である。

特徴

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

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

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

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

関連項目

• 集積回路設計
• 組合せ最適化
• 焼きなまし法
• 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に関する国際会議。