チャネルルーチング問題
チャネルとは、二つの平行軸からなり、軸上にはターミナルがある。 上の軸のターミナルにはt(1)、t(2)のように、下の軸のターミナルにはb(1)、 b(2)のように番号が付けられている。 ネットとは、線で繋がなければな らないターミナルの集合である。 接続要求はネットの集合として与えら れる。 チャネルルーチング問題とは、チャネルと接続要求を与え、接続 要求を満たし、しかも線が重ならないように配線を求める問題で、配線領域を 最小化し、配線の長さを最短化することを目的としている。
チャネルと配線に違う制約を与えることによって、さまざまな問題を作れる。 ここでは、nHV型のチャネルとdoglegなしの配線を考える。図 --1は一つのHV型チャネルを示す。配線領域は水平層と 垂直層からなる。一つのネットに対する配線は、一本の水平線と何本かの垂直 線からなる。水平線は水平層のどれかのトラックに置かなければならず、垂直 線は垂直層に置かなければならない。水平線と垂直線はvia-holeと呼ばれるも のによって結ばれる。nHV型のチャネルとは、n個のHVペアからなる。一つのネッ トに対する配線は、一つのHVペアに置かなければならない。つまり、二つ以上 のペアに跨ることは許されない。
チャネルルーチング問題は一種の制約充足問題で、ネットが変数であり、層と トラックのすべての組合せが変数のドメインである。線が重ならない制約を二 つの制約グラフを用いて表す。
定義２ 垂直制約グラフG v ＝（Ｖ，Ａ）。ここで Ｖ はネットの集合で Ａは above 関係を表す。 above(u,v) は、もし u と v を同じ水平層に置くならば、 u を v の上（番号が大きいトラック）に置かなければならないことを 意味する。この関係を次のように作る。
垂直層が一つしかない場合には、関係aboveは推移的であるが、垂直層が二つ 以上ある場合には推移的ではなくなる。
定義３ 平行制約グラフ G h ＝（Ｖ，ＮＥ）。 ここで Ｖ はネットの集合で ＮＥは 不等関係 neqを表す。 neq(u,v) は、u と v が同じトラックに置けないことを 意味する。この関係を次のように作る。
ここでは、 u.minと u.maxはそれぞれ uの一番小さいターミ ナル番号と一番大きいターミナル番号を表す。
図--2に一つの例を示す。
CMGTPのプログラム
CMGTPは基本的に既存の関係を組み合わせることによって新しい関係を構築す るというボトムアップ的な証明方法を取っている。変数のドメイン及び変数間 の制約を関係として記述すれば、制約充足問題はCMGTPで自然に記述できる。 チャネルルーチング問題においては、ネットに対して層と層の中のトラックと の二つの値を決めなければならないため、変数のドメインは整数の集合ではな く、タプルの集合になる。
次に、CMGTPのプログラムを示す。プログラムを実行するのに、問題に依存す るデータとしてネット数N、層の総数MaxL、トラックの数MaxT及び接続 要求から得られた関係neqとaboveを与えればよい。
(1) net(N) --> p(N,1,1);...;p(N,MaxL,MaxT).
(2) p(N1,L,T),p(N2,L,T),neq(N1,N2) --> false.
(3) p(N1,L,T1),p(N2,L,T2),above(N1,N2),{T1=<T2} --> false.
ルール(1)は、ドメインの定義を行なっている。それぞれのネットに対して、
ドメインは(1,1)から(MaxL,MaxT)までのすべてのペアからなる。ルール(2)は、
G hを記述している。任意の二つのネットN1とN2に対して、もしneq(N1,N2)
であれば、N1とN2は同じトラックに置いてはならない。ルール(3)は、G vを
記述している。任意の二つのネットN1とN2に対して、もしabve(N1,N2)で、か
つN1とN2を同じ層に置くならば、N1をN2の上に置かなければならない。
KLICのプログラム
KLICはcommitted-choice型の言語であるが、並行性を利用して非決定性を実現 できることはよく知られている。例えば、次のProlog述語search(Tree)につい て考える。
search((A;B)):-search(A).
search((A;B)):-search(B).
この述語をKLICで次のように記述できる。
search(Tree,stop).
alternatively.
search((A;B),Sig):-true |
search(A,Sig),search(B,Sig).
(A;B)に対して、二つのプロセスsearch(A,Sig)とsearch(B,Sig)を生成する。
Sigはプロセスが通信するための変数で、あるプロセスが解を見つけたら、Sig
はアトムstopに束縛される。Sigを用いることによって、一旦解が見つかった
らほかのプロセスを停止させることができる。
この考え方に基づいて書いたプログラムを次に示す。
(1) route(Nets,L,T,MaxL,MaxT,Sol,stop).
alternatively.
(2) route([],L,T,MaxL,MaxT,Sol,Sig):-true | Sig=stop.
(3) route(Nets,L,T,MaxL,MaxT,Sol,Sig):-
L<MaxL,T>MaxT :
route(Nets,~(L+1),1,MaxL,MaxT,Sol,Sig).
(4) route([Net|Nets],L,T,MaxL,MaxT,Sol,Sig):-
L=<MaxL,T=<MaxT |
check_constr(L,T,Sol,Res),
(Res=no->route([Net|Nets],L,~(T+1),MaxL,MaxT,Sol,Sig)
;(route(Nets,1,1,MaxL,MaxT,[net(Net,L,T)|Sol],Sig),
route([Net|Nets],L,~(T+1),MaxL,MaxT,Sol,Sig))).
otherwise.
(5) route(Nets,L,T,MaxL,MaxT,Sol,Sig).
ルール(1)は、呼びだしの最後の引数がstopであれば、探索を中止させる。ルー
ル(2) は、配線するネットがなくなれば、全部の探索を終了させる。ルール
(3)は、L層内のトラックが全部駄目であったら、次の層から調べることにす
る。ルール(4)は、まずネットNetに対して、層とトラックのペア(L,T)がよ
いかどうかをチェックする。 もしも駄目であったら、次のトラックから考え
るようにする。もし(L,T)が良ければ、二つのプロセスを生成し、平行的に探
索させる。
CLP(FD)のプログラム
CLP(FD)は、有限領域上の制約を宣言的に記述できる制約論理プログラミング 言語である。CLP(FD)では、変数のドメインが整数の集合でないといけないた め、上のように制約充足問題として定式化されたチャネルルーチング問題をそ のままの形で記述することはできない。そこで、ドメインの定義を変更するこ とが必要である。
平行層の総数をMaxL、一層当たりのトラック数をMaxTとすると、各変数の ドメインをすべてのトラックの集合とし、トラックに0からMaxL×MaxT−１までのグローバルな番号をつける。グローバルな番号が分かれば、平 行層及びその層の中のトラックの番号も簡単に計算できる。
次に、CLP(FD)でのプログラムを示す。
route(N,MaxL,MaxT):-
generate_vars(N,MaxL,MaxT,Vars),
generate_constraints(Vars,MaxT),
label_ff(Vars).
generate_vars(N,MaxL,MaxT,Vars)はN個の変数を生成し、変数のドメ
インを宣言する。 genereate_constraints( Vars,MaxT)は制約を生成
する。任意の 二つの変数XとYに対して、もしG hにおいてneq(X,Y)ならば、
X#\=Yという制約を生成する。 また、もしG v においてabove(X,Y)な
らば、次の述語を呼び出す。
delay above(X,Y,MaxT) :- var(X), var(Y).
above(X,Y,MaxT):-
nonvar(X),!
Y notin X..(X//MaxT)*MaxT+MaxT-1.
above(X,Y,MaxT):-
X notin (Y//MaxT)*MaxT..Y.
この述語は、条件付き制約aboveを記述している。もし、XとYが変数であれば、
制約を遅延させ、もしXとYのどちらかが束縛されたら伝搬を行なう。
結果
作成したプログラムを走らせ、ネット数が10から218までのいくつかの問題を 解かせてみた。CLP(FD)プログラムを実行するのにB-Prolog(2.1)を利用した。
CMGTPプログラムは、記述が一番簡潔ではあるが、大規模の問題をひとつも解 けなかった。また、一番小さな問題(ネット数が10)の全解をUltra-SPARCで求 めるのに、CMGTPは200秒あまりの時間がかかったが、 SICStus-Prologのほう は1/11の時間で全解を求められた。
表--1では、各ルータが5分の時間内で求めた解の必要なトラック 数を表す。列Bestは、現在までに知られている最適な解の必要なトラック数を 表す[6,4,7]。 CLP(FD)は、すべての問題に対して最適解を 見つけただけではなく、二番目の問題に対してはこれまでの記録よりよい解を 見つけることができた。KLICは、最後の問題以外に対して、最適解を見つける ことができた。
図 --3: Deutsch問題の解(HV型,28トラック)
図 --4: Deutsch問題の解(2HV型,10トラック)
図 --5: Deutsch's問題に対するDoglegありの配線(21トラッ
ク)
