シーケンスペア

ウィキペディア

シーケンスペア

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/04 08:06 UTC 版)

シーケンスペア（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)$

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

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

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

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

シーケンスペアについて

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

一般構造の表現

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

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

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

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

定義

シーケンスペアは、n個の矩形の相対位置関係を、矩形名の順列${\displaystyle \Gamma _{+}}$

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