シーケンスペア

技術的背景

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

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

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

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

オッテンによるスライス構造の提案

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

スライス木

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

標準化ポーランド記法

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

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

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

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

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

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

一般構造の表現

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

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

定義

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

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

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

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

斜格子

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

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

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

デコード

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

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

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

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

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

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

エンコード

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

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

${\displaystyle n}$個の矩形配置をグリッディングによってシーケンスペアにエンコードするには、${\displaystyle O(n^{2})}$時間を必要とする。これに対し、計算幾何学のプンレーン・スイープと呼ばれる手法を用いて矩形配置から1次元コンパクショングラフを求め、このグラフからシーケンスペアにエンコードする高速グリッディング。この方法を用いると${\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年に相当する。

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

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