JPH07334366A

JPH07334366A - グラフリダクション機構の最適化方法および装置

Info

Publication number: JPH07334366A
Application number: JP12503694A
Authority: JP
Inventors: Hideki Yamanaka; 英樹山中
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1994-06-07
Filing date: 1994-06-07
Publication date: 1995-12-22

Abstract

(57)【要約】【目的】部分的な再計算を繰り返す計算に必要とされ
るメモリ空間および時間量を大幅に削減すること。【構成】リダクションの対象となる全体のグラフＳが
第１の記憶手段１に保持され、第２の記憶手段２には、
グラフＳの全ての部分グラフのハッシュ値を記憶するハ
ッシュテーブル２ａを持ち、過去に存在した部分グラフ
と現在到達しているそのリダクション先の部分グラフの
組を記憶している。リダクション手段３は第１の記憶手
段１に保持された部分グラフをリダクションし、リダク
ション先の部分グラフが、第２の記憶手段２に登録され
ていないとき、リダクション先の部分グラフを、元の部
分グラフに対応付けて第２の記憶手段２に登録する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、グラフリダクション機
構の最適化方法および装置に関し、特に本発明は、グラ
フリダクションに必要とされるメモリ空間、および、時
間をヒューリスティクにたよらず削減することができる
グラフリダクション機構の最適化方法および装置に関す
るものである。

【０００２】

【従来の技術】関数型言語ＬＩＰＳの実現研究より発し
たヒープ領域（動的割り当て可能なアドレス空間）の再
利用技術であるガベージコレクションは、今まで様々な
方法が提案されてきた。その主なアプローチは、コピー
方式、マーク・スキャン方式とリファレンス・カウント
方式である。

【０００３】ヒープ領域は、通常、左右の２個のポイン
タをもつセルと呼ばれる単位で割り当て、回収再利用が
なされる。コピー方式は上記したヒープ領域を２つに割
り、ガベージコレクションの度に一方から他方へガベー
ジでない全てのセルをコピーする。割り当て可能な領域
は、コピーで使われなかった連続したメモリ領域であ
る。

【０００４】マーク・スキャン方式は、各セルにマーク
ビットと呼ばれる１ビットのフラグを設けて、ガベージ
コレクションの前処理として、ヒープ領域を直線的に辿
ることにより、全てのセルのマークビットをクリアして
おく。次に、現在使用されている全てのセルをルートか
らポインタを辿って行くことにより、そのマークビット
をセットし、最後にヒープ領域を直線的に辿って、マー
クビットがセットされていない全てのセルをフリーリス
トと呼ばれる再割り当て可能なセルのリストとして得
る。

【０００５】リファレンス・カウント方式では、各セル
にリファレンス・カウンタと呼ばれる他のセルからの参
照回数を保持するカウンタを設ける。そして各リスト処
理の演算で、他のセルからの参照が増減する毎に上記リ
ファレンス・カウンタを増減させるが、ガベージコレク
ションは単に、ヒープ領域を直線的に辿り、リファレン
ス・カウンタが０である全てのセルを集めて、フリーリ
ストとして再構築する。あるいは、リファレンス・カウ
ントが０になったときにフリーリストに回収してしまう
だけですむ。

【０００６】上記したガベージコレクションの機構は、
現在様々な高級プログラミングで現実に使われている。
副作用のない純関数型言語は、初期のＬＩＰＳの意味論
であるラムダ計算系、あるいは、等式理論に基づく計算
機構としての項書換え系を意味論として持ち、リダクシ
ョンと呼ばれる項の書換えにより計算が進んでいく。

【０００７】例えば、次のようにフィナボッチ関数ｆｉ
ｂの定義を与え、 fib(0) =0 fib(s(0)) =s(0) fib(s(s(X))) =fib(s(X))+ fib(X) 0 + X =X s(X) + Y =s(X+Y) fib(s(s(s(0)))) を計算してみる。

【０００８】 fib(s(s(s(0)))) →fib(s(s(0))) +fib(s(0)) →fib(s(0))+fib(0)+ fib(s(0)) → … →s(s(0)) となり、計算結果s(s(0)) を得る。ここで、s(X)は、Ｘ
より１だけ大きい自然数を表し、0,1,2,3,…は0,s(0),s
(s(0)),s(s(s(0))), …と対応付けられ、任意の自然数
は、それと同じ数のｓと１個の０で表すことができる。
なお、実際の計算では、このように自然数を表現せず、
始めから組み込まれた型としての整数を使うが、ここで
は、典型的な容易な例として示した。

【０００９】上の例を厳密にトレースすると、まず、書
き換えられる項の部分項と関数の定義の左辺のどれか一
つの項がマッチング（後者の変数に適当な項を代入し、
前者と後者が一致）するかどうかを調べる。そして、マ
ッチングした場合には、マッチングした部分項を、定義
の左辺をコピーしてそれにマッチングに使われた代入
（変数をそれに対応する項のコピーで置き換える）を施
した項で置き換え、置き換えられた元の部分項全体がガ
ベージになるというプロセスを繰り返す。

【００１０】例えば、fib(s(s(s(0)))) はfib(s(s(X)))
にマッチングするので、fib(s(s(X)))をコピーして、Ｘ
をs(0)で置き換えて、fib(s(s(0))) +fib(s(0)) を得
て、fib(s(s(s(0)))) をガベージとする。通常の関数型
言語における実現では、このような効率の悪いコピーを
避けるため、代入をポインタによる部分項の共有で置き
換える。ポインタの共有によって項の表現がダグ（非循
環有向グラフ）になり、この上でリダクションが行われ
るので、このような計算はグラフリダクションと呼ばれ
る。

【００１１】上記例では、計算の途中にfib(s(0)) とい
う部分項が２個重複して現れるが、これは、変数に代入
されたことがないので、変数による共有の枠組では共有
できない。これもポインタにより共有させるためには、
グラフのすべての部分項をハッシュしておいて、リダク
ションが行われる毎に書き換えられた部分項を含む全て
の部分項のハッシュテーブルを更新し、常に同じ部分項
がポインタで共有されるようにしなければならない。

【００１２】もし、このハッシュテーブルの更新のオー
バヘッドが問題の大きさに関して、線形オーダ程度であ
れば、セルの消費量の削減の現実的な方法と言えると考
えられる。さらに、例えば、前の例のような素朴なフィ
ナボッチ関数のように指数オーダの計算時間・空間消費
量をもつ関数の計算を考えると、この共有によって線形
オーダの空間消費量だけでなく、計算時間を画期的に削
減することができる。

【００１３】一方、計算時間・空間消費量を削減する古
くからある方法に、過去に行った部分的な計算の断片を
記録しておき、それを再利用することにより同じ計算を
繰り返さないという手法がある。例えば、次の組み込み
関数型の整数を使ったフィナボッチ数列を計算するifib
プログラムを考えてみる。

【００１４】ifib(X)=if(eq(X,0),0, if(eq(X,1),1, +(ifib(-(X,1)),ifib(-(X,2))))) 上記式は、もし、Ｘが０であればifib(X) は０となり、
Ｘが１であればifib(X) は１となる。また、Ｘが２であ
れば、ifib(X) は +(ifib(-(X,1)),ifib(-(X,2))) 、す
なわち、ifib(2-1)+ifib(2-2) でifib(1)+ifib(0) とな
る。

【００１５】同様に、Ｘが３であれば、ifib(2)+ifib
(1) 、すなわち、（ifib(1)+ifib(0)）+ifib(1)とな
る。すなわち、通常のCall-by-value （深さ優先の逐次
計算）で ifib(5)を計算すると、図１０に示すように、
計算を表す木が得られる。図１０において、計算の手順
は矢印に示すように、まず、 ifib(5)を得るためifib
(4) を求め、次に、ifib(4) を求めるために、ifib(3)
を求め、以下同様に、(1) 〜(14)に示す手順で行われ
る。ここで、同図の点線で囲まれた領域（同図において
再計算部分として示した部分）の計算は、既に一度計算
されている。例えば、同図の(8)(9)の再計算部分ifib
(2) は(4),(5) で既に計算されている。

【００１６】したがって、計算の途中で、ifib(1),ifib
(2),ifib(3) とその計算結果を組にして適当な場所に記
録しておいて、計算の定義通りに進める前にこの組を検
索して、既に計算結果が得られていれば、それで置き換
えるようにすることによって計算時間・空間量を減らす
ことができる。一般に、ifib(N+2) の計算では、ifib
(N) はifib(N+1) の計算の中で既に計算されているの
で、再度計算する必要がない。そして、ifib(N+1) の結
果を得てからifib(N+2) を計算するためには、足し算を
一度するだけなので、ifib(N+2) の計算量は線形オーダ
となる。ただし、過去の計算結果の検索が十分高速で、
計算量が線形オーダ以下であれば。（通常、検索にはハ
ッシングが使われるので個々の検索の計算量は定数オー
ダとなり、また、ifib(N+2) の計算全体ではＮ回の検索
が行われるので、合計は線形オーダの計算量となる。）

【００１７】

【発明が解決しようとする課題】以上のように、過去の
計算結果を登録し、それを再利用して部分的な再計算を
繰り返さずに計算処理を行う手法においては、過去の計
算結果の検索が十分高速で、計算量が線形オーダ以下で
あれば、メモリ空間・時間量にナイーブな、例えば上記
したフィボナッチ数列の計算を線形オーダの計算量で計
算することができる。

【００１８】しかしながら、従来の手法は、過去の計算
結果、すなわち、部分的な計算断片とその計算結果の組
をテーブル等に記録しそれを再利用するものであり、シ
ステムにより、過去の計算結果を自動的、かつ、動的に
登録することはできず、また、計算の中間結果を登録し
再利用することはできなかった。本発明は上記した従来
技術を考慮してなされたものであって、本発明の第１の
目的は、部分的な計算の断片と、計算の中間結果のグラ
フのルートノードのセルを対応付け、この対応付けられ
ている部分グラフを、さらに計算された中間結果により
動的に更新していくことにより、部分的な再計算を繰り
返す計算に必要とされるメモリ空間、および、時間量を
大幅に削減したグラフリダクション機構の最適化方法お
よび装置を提供することである。

【００１９】本発明の第２の目的は、記憶空間を使い果
たすまで、全ての計算の断片を登録し続け、ガベージコ
レクションに同期して、現在の全体のグラフを最大に共
有させるために必要な部分を除いた全ての登録を削除す
ることにより、登録された部分的な計算の断片を効率的
に削除して記憶空間を回収することができるグラフリダ
クション機構の最適化方法および装置を提供することで
ある。

【００２０】

【課題を解決するための手段】図１は本発明の原理図で
ある。同図において、１はリダクションの対象となる全
体のグラフＳを保持する第１の記憶手段、２はグラフＳ
の全ての部分グラフのハッシュ値をハッシュテーブル２
ａに記憶するとともに，過去に存在した部分グラフと現
在到達しているそのリダクション先の部分グラフの組を
記憶する第２の記憶手段、３は第１の記憶手段１に保持
された部分グラフをリダクションして第２の記憶手段２
に登録するリダクション手段、４はガベージコレクショ
ンに同期して、ガベージを回収するガベージコレクタで
ある。

【００２１】上記課題を解決するため、本発明の請求項
１の発明は、ハッシュテーブル２ａによりグラフＳを共
有化し、ある部分グラフｇ３について、ハッシュ値を求
め、求めたハッシュ値に基づき、ハッシュテーブル２ａ
を参照してハッシュテーブル２ａに登録されたポインタ
により、上記部分グラフｇ３と同一構造の部分グラフｇ
１のリダクション先の部分グラフｇ２を求め、上記部分
グラフｇ３のポインタをリダクション先の部分グラフの
ポインタｇ２に置き換えることにより、過去の計算断片
を再利用して部分的な再計算を繰り返さずに計算を行う
ようにしたものである。

【００２２】本発明の請求項２の発明は、請求項１の発
明において、記憶空間を使い果たすまで、全ての部分グ
ラフを登録しつづけ、ガベージコレクションに同期し
て、現在の全体グラフを最大に共有できる部分を除い
た、全ての登録を削除して記憶空間を回収するようにし
たものである。本発明の請求項３の発明は、グラフリダ
クション機構の最適化装置を、リダクションの対象とな
る全体のグラフＳを保持する第１の記憶手段１と、第１
の記憶手段１に記憶されたグラフＳの全ての部分グラフ
のハッシュ値をハッシュテーブル２ａに記憶するととも
に，過去に存在した部分グラフと現在到達しているその
リダクション先の部分グラフの組を記憶する第２の記憶
手段２と、第１の記憶手段１に保持された部分グラフを
リダクションし、リダクション先の部分グラフが、第２
の記憶手段２に登録されていないとき、リダクション先
の部分グラフを、元の部分グラフに対応付けて第２の記
憶手段２に登録するリダクション手段３とから構成した
ものである。

【００２３】本発明の請求項４の発明は、請求項３の発
明において、ガベージコレクションに同期して、現在の
全体のグラフを最大に共有させるために必要な部分を除
いた全ての登録を削除するガベージコレクタ４を設けた
ものである。

【００２４】

【作用】前記したようにハッシングにより共有可能部分
を見つけ、ポインタの共有に置き換えるだけでなく、こ
のハッシュテーブルを拡張して、過去に存在した部分グ
ラフと、それが現在どの部分グラフまでリダクションさ
れて来ているかを対応付けるようにし、過去に行われた
全てのリダクシヨンを繰り返さないようにすれば、計算
時間・空間消費量を大幅に削減することができる。な
お、現在までその部分グラフのどのグラフもリダクショ
ンされていなければ、拡張前と同じ対応となる。

【００２５】ここで、注意が必要なのは、前記したよう
な古くからある計算結果の再利用と異なり、部分的な計
算の断片とその計算結果の組を記憶するだけではなく、
部分的な計算の断片と計算の中間結果のグラフのルート
ノードのセルを対応付ける。しかも、この対応付けられ
ている部分グラフは、計算対象となっているグラフの一
部を構成しているので、それに対する直接あるいは関節
的なリダクションによって、動的にさらに計算された中
間結果あるいは、完全な計算結果となって行く。

【００２６】ただし、リダクションにより部分グラフは
書き換えられるがそのルートノードのセルは不変である
ので、中間結果をセルのアドレスとして対応付けておけ
ば、常に最新の中間結果を得ることができる。しかしな
がら、このような計算結果の再利用は、全体の計算結果
が進むにつれて膨大な計算の断片を登録することにな
り、記憶空間を消費して行く（なお、各計算の中間結果
は、全体のグラフ中の部分グラフとして共有されている
ので、その登録は、単にポインタ１個分の記憶空間しか
必要としない）。

【００２７】上記のように登録された全ての断片が再利
用されるとは限らないので、何らかの方法で再利用され
る可能性の低いものを削除して記憶空間の再利用を促す
必要がある。しかしながら、将来に再利用される可能性
があるかないかを予測するの非常に難しい。そこで、ヒ
ューリスティックに頼らずに、記憶空間を使い果たすま
で全ての計算の断片を登録し続け、その後ガベージコレ
クションに同期して、現在のグラフを最大に共有させる
ために必要な部分を除いた全ての登録を削除して記憶空
間を回収する。すなわち、何度も再利用されるものは一
旦削除されても再計算され、それがまた再利用されるの
で、オーバヘッドはかなり小さくなると予想されるから
である。

【００２８】また、小さな計算では、一度もガベージコ
レクションを起こすことなく計算できるので、ヒューリ
スティクに頼るよりも良い結果が得られる。本発明は上
記考え方に基づき、グラフリダクション機構の最適化を
図ったものであり、次に、本発明におけるハッシュ・テ
クニックと、計算断片の登録、検索、更新、削除につい
て説明する。（１）ハッシュテクニックグラフのハッシングの機構は、グラフのハッシュ関数と
登録・削除の機構からなる。

【００２９】今、ｇをダグ、ｆをｇのルート・ノードの
関数記号、ｇ1 ，ｇ2 ，…，ｇn をｇの引数を表す子の
ダグとする。ハッシュ関数hash: Ｇ→Ｎ（Ｇはダグの集
合、Ｎは自然数）を考えると、グラフが構造を持つデー
タであることから、通常次のような再帰的な形で与える
ことになる。 hash(g)=α(h(f),hash(g1),hash(g2),… hash(gn)), ここで、α：Ｎ⁺→Ｎとｈ：Ｆ→Ｎとする（Ｎ⁺は自然
数の有限列で、Ｆは関数記号の集合）。すなわち、ハッ
シュ値hash(g) はそのルート・ノードの関数記号f によ
り定まる値h(f)と、その子ノードのハッシュ値hash(g
1),hash(g2),… hash(gn) から定まる再帰的な形で与え
られる。

【００３０】ハッシュ関数は、検索を高速化するための
ヒントを得るためのものなので、本来任意のもので良い
訳であるが、ハッシュ関数自身の計算が十分高速で本来
の計算のオーバヘッドとならず、また、検索が最も高速
に行われるためには、ハッシュ関数が単射に近いことが
望ましいとされる。上のハッシュ関数は、再帰的である
が、実際の計算では、子のグラフは既にハッシュによっ
て共有化されていて、ルートのセルのアドレスをそのハ
ッシュ値と見なして計算を簡略化しても、十分有効なハ
ッシュ関数となる。

【００３１】すなわち、次の関数の形となる。 hash(g)=α(h(f),#(g1),#(g2),… #(gn)), ここで、#(g)は、ダグｇのルートのセルのアドレスであ
る。また、組み込み型の値は、実際上無限個あるので、
これらの値をハッシュ・テーブルに登録するのは現実的
でない。そこで、グラフのマッチングのアルゴリズムを
改良して、たとえ２つの組み込み型の値が同じセルの上
になくても、同じ値であるときは、同じセルを共有して
とみなすようにする。

【００３２】また、ハッシュ関数も、子グラフが組み込
み型の値のときには、そのセルのアドレスでなく、その
値自身を使うことにすれば、事実上、組み込み型のデー
タは、値が同じであれば、常に全て同じセルを共有して
いると見なすことができる。さらに、ハッシュテーブル
を関数記号ごとに分割することにすると、h(f)を計算す
る必要はなく、ハッシュ値は次のようになる。

【００３３】hash(g)=α(#(g1),#(g2), … #(gn)), ただし、giが組み込み型の値のときは、#(gi) を値その
もの、すなわち、giそのものとする。また、ハッシュテ
ーブルを始めに一度で割り当ててしまうと、あまり使わ
れない関数記号とよく使われる関数記号のハッシュテー
ブルが同じだけメモリ空間を使ってしまい、効率がよく
ない。そこで、ハッシュテーブルを２次元とし、１次元
の部分ハッシュテーブルとそのハッシュテーブルへのポ
インタの配列の構成とし、部分ハッシュテーブルはハッ
シュ関数の値により、そのテーブルが必要になったとき
動的に割り当てるようにする。（２）計算断片（部分グラフ）の登録、検索、更新、削
除図２は本発明におけるハッシュの仕組みを説明する図で
あり、同図を参照して本発明における計算断片（部分グ
ラフ）の登録、検索、更新について説明する。なお、図
１０で説明したifib(1),ifib(2),ifib(3) のような計算
断片を部分グラフと呼ぶ。

【００３４】図２において、大きくハッチングされた領
域Ｓは全体のグラフを示し、全体のグラフが既に登録さ
れハッシュされていると仮定し、ここでは説明のため、
同図のＡ，Ｂ，Ｃの３個のハッチングされた多角形の部
分（グラフ）について考える。また、グラフＡはリダク
ションされるグラフ、グラフＢはリダクション先のグラ
フ、グラフＣはグラフＡと同じハッシュ値を持つグラフ
である。

【００３５】同図において、各グラフはセルを単位とし
て構成され、各セル１１ａ，１１ｂ，１１ｃには、図３
に示すように、通常、そのセルに割り当てられている
関数記号（あるいは組み込む型の値、同図では関数ｆが
示されている）、その引数を表す部分グラフのルート
セルへの何個かのポインタＰ１，Ｐ２，Ｐ３，…、そ
の関数記号に割り当てられている属性リスト１２へのポ
インタＰli、さらに、この枠組では、グラフ構造のハッ
シングを行うので、ハッシュテーブルの保守のための
ポインタＰm が付いている。

【００３６】図２にもどり、１２は属性リストであり、
ハッシュテーブルが各関数毎に分割されているので、各
関数毎に設けられた属性リスト１２には、その関数のハ
ッシュテーブル全体をたどるためのポインタＰhaが入れ
られている。ハッシュテーブルは、前記したように２次
元構造となっており、一次元の部分ハッシュテーブル１
４ａ〜１４ｂと、その部分ハッシュテーブル１４ａ〜１
４ｂへのポインタを格納した配列１３から構成され、部
分ハッシュテーブル１４ａ〜１４ｂのポインタは、複数
のグラフに対応したハッシュリスト１５ａを指してい
る。

【００３７】なお、ハッシュテーブルのメモリ空間は、
全てが予め割り当てられていないので、登録する場所に
空間が割り当てられていないときは、その都度割り当て
る。また、違うグラフに同じハッシュ値が割り当てられ
ることがあるので、一般的には複数のグラフが登録され
る。例えば、図２に示すように、グラフＡと同じハッシ
ュ値を持つ異なった構造のグラフとして、グラフＣが登
録されている。

【００３８】登録は、同図に示すように、ハッシュリス
ト１５ａの最後に、新しい３要素からなるハッシュリス
ト１５ｂを作ってつなぎ、その第１の要素１５１と第２
の要素１５２にハッシュしようとするグラフへのポイン
タＰg1，Ｐg2（最初は同一のセルを指している）を入
れ、最後の要素１５３には空リストを入れる。そして、
グラフがリダクションされたとき、ハッシュリスト１５
ａに示されるように、上記ポインタＰg2はリダクション
先のグラフ（例えば、同図のグラフＢ）を指すようにな
る。また、新たに登録するときには、上記最後の要素１
５３に新たなハッシュリストへのポインタＰg3を入れ
る。

【００３９】図２において、ある部分グラフ（これを以
下グラフＸという）をハッシュしようとすると、まず、
その部分グラフＸからハッシュ関数でハッシュ値を得
る。次に、その部分グラフＸのルートセルから属性リス
ト１２を得て、その部分グラフＸの関数のハッシュテー
ブル１３，１４を得る。ついで、既に計算してあったハ
ッシュ値に対応するハッシュテーブル内の位置にそのグ
ラフＸのルートセルへのポインタを登録する。

【００４０】ここで、前記したように、ハッシュテーブ
ルのメモリ空間は、全てが予め割り当てられていないの
で、登録する空間に割り当てられていないときには、割
り当てる。そして、登録する位置に何も登録されていな
いときには、上記部分グラフＸを登録し、他のグラフの
ハッシュリストが登録されてるときには、その中に同じ
構造のグラフがあるか否かを判定し、無ければそのハッ
シュリストにハッシュしようとするグラフＸを登録す
る。

【００４１】すなわち、ルートセルのアドレスが一致す
るか、あるいは、その全ての引数のグラフのルートセル
のアドレスが登録しようとしているグラフの対応する引
数のそれと一致するグラフ（これを同じ構造のグラフと
いう）が登録されていなければ、そのハッシュリストに
ハッシュしようとするグラフＸを登録する。例えば、同
図において、グラフＣを新たに登録する場合には、前記
したように、ハッシュリスト１５ａの最後に、新しい３
要素からなるハッシュリスト１５ｂを作ってつなぎ、ハ
ッシュリスト１５ｂの第１要素１５１，１５２に登録し
ようとするグラフＣのルートへのポインタを登録する。

【００４２】また、もし、同じ構造のグラフが登録され
ている場合には，このグラフへのポインタがあるハッシ
ュリストの第２の要素のグラフで、ハッシュしようとし
たグラフＸを置き換える。図２の例においては、あるグ
ラフＸをハッシュしようとしたとき、そのグラフと同じ
構造のグラフＡが既に登録されていれば、グラフＡへの
ポインタがあるハッシュリスト１５ａの第２要素１５２
が指すグラフＢで、ハッシュしようとしたグラフＸを置
き換える。上記ハッシュリスト１５ａの第２要素１５２
には、後述するように、グラフＡのリダクション先のグ
ラフＢを指すポインタＰg2が登録されているので、上記
置き換えにより、ハッシュしようとしたグラフＸは、リ
ダクション先のグラフＢにより置き換えられる。

【００４３】上記置き換えは、グラフＸのルートのセル
への全てのポインタ（このセルからは、どのセルから指
されているかは分からない）の置き換えであるが、イン
ダイレクション法（回り道法）と呼ばれる方法を使い、
置き換えを先延ばしする。すなわち、図４に示すよう
に、ハッシュしようとしたグラフのセルからでている引
数へのポインタ（図４においては、ポインタＰ１，Ｐ
２）をクリアし、そのかわりに、置き換え先のセルへの
ポインタを入れ、グラフのセルには、インダイレクシヨ
ンに使われていることを表す属性を付ける（このような
属性が付けられたセルをインダイレクションセルと呼
ぶ）。

【００４４】上記のようにしておいて、後に、全体のグ
ラフを辿りながら、このインダイレクションセルを見つ
けたその都度、このセルへのポインタをこのセルの先の
ポインタに置き換えて行く。このようにすることによ
り、実際にはインダクレンションなしでハッシュ時に全
てのルートセルへのリンクを置き換えたのと同じことに
なる。

【００４５】ここで、前記したようにハッシュリストの
第２の要素のグラフで置き換えるのは、この中に第１要
素のグラフを何度かリダクションした先のグラフが入っ
ているからである。最初グラフを登録したときには、ハ
ッシュリストの第１の要素と第２の要素は同じグラフを
指している（例えば、図３に示したように、ハッシュリ
スト１５の第１の要素１５１と第２の要素１５２は同じ
グラフを指している）。

【００４６】そして、任意のグラフをリダクションする
ときに、そのグラフのルートセルから保守用のポインタ
Ｐm を使って、自分自身のハッシュリストを見つけ（そ
のグラフのルートセルからは自分自身のハッシュリスト
は分からない）、それの第２要素にリダクションされた
先のグラフへのポインタを入れる。例えば、図２におい
て、グラフＡをリダクションするとき、そのルートセル
１１ａからハッシュリスト１５ａは分からないので、保
守用のポインタＰm を使ってハッシュリスト１５ａを見
つけ、ハッシュリスト１５ａの第２要素１５２にリダク
ション先のグラフＢのルートセル１１ｂへのポインタを
入れる。

【００４７】さらに、リダクションされたグラフの部分
グラフがリダクションされると、上記第２要素の先は、
２回リダクションされた先になり、そのサイクルが何度
も繰り返される。その結果、間接的に、また、動的に第
２要素が最もリダクションされた先へのポインタへと変
わって行くことになる。すなわち、過去にリダクション
された全ての部分グラフとその現在最新のリダクション
された先の部分グラフの組が動的に更新されていく。

【００４８】ただし、ハッシュリストの第２要素を更新
するときには、第１要素の先のグラフ（つまり、リダク
ションされるグラフ）を一部書き換える必要がある。こ
れは、インダイレクション法を使っているので、前記し
たように、リダクションされるグラフのルートセルがリ
ダクションされた先のグラフを作るのに使われてしまう
からである。

【００４９】そこで、リダクションが終わる前に、第１
要素の先のグラフのルートセルを、引数の部分グラフへ
のポインタも含めてコピーし、第１要素のポインタをリ
ダクションされるグラフから、このコピーへと付け換え
ることが必要となる。ここで、このコピーされたセルを
参照するセルが存在しないことに注意する必要がある。
すなわち、このコピーされたセルは、ガベージコレクタ
にとってはガベージであるから、ヒープ領域が使い果た
さるとガベージとして回収される。

【００５０】図５は上記したグラフの共有を説明する図
であり、同図は前記したifibプログラムにおけるグラフ
を共有を示している。同図において、前記したようにif
ib(3) はifib(2)+ifib(1) であるので、同図（ａ）に示
すifib(3) のグラフがリダクションされると、同図
（ｂ）に示すように、ifib(3) のグラフがコピーされて
ガベージとなり、そのセルはインダイレクションノード
となる。そして、インダイレクシヨンノードには、リダ
クション先の部分グラフ（この場合には、ifib(2)+ifib
(1) ）のセルへのポインタが入れられる。また、前記し
たように、ハッシュリストの第１の要素は上記ifib(3)
を指し、第２要素が上記インダイレクションノードを指
すようになる。

【００５１】同図（ｂ）に示す状態から、さらにifib
(2) のグラフがリダクションされると、同図（ｃ）に示
すように、ifib(2) のグラフがガベージとなり、インダ
イレクシヨンノードには、リダクション先の部分グラフ
（この場合には、ifib(1)+ifib(0) ）のセルへのポイン
タが入れられる。ここで、同図の点線で囲まれた部分Ａ
とＢは同一のグラフであり、共有可能である。そこで、
前記したように、上記部分Ｂのグラへのポインタが付け
換えられる。

【００５２】図６および図７は計算履歴を考慮したグラ
フの共有を説明する図であり、同図により、前記したif
ibプログラムにおける計算履歴を考慮したグラフの共有
について説明する。図６（ａ）において、ルートセルの
ポインタはそれぞれifib(2) とifib(3) の部分グラフを
指しており、ハッシュリスト１５ａ，１５ｂの第１要
素、第２要素は、それぞれともにifib(2) とifib(3) の
部分グラフのセルを指している。

【００５３】同図（ａ）の状態からifib(2) の部分グラ
フがリダクションされると、同図（ｂ）に示すように、
ifib(2) のセルがコピーされてガベージとなり、インダ
イレクシヨンノードには、リダクション先の部分グラフ
（この場合には、ifib(1)+ifib(0) ）のセルへのポイン
タが入れられる。また、前記したように、ハッシュリス
ト１５ａの第１の要素は上記ガベージとなったifib(2)
を指し、第２要素が上記インダイレクションノードを指
すようになる。さらに、ifib(1) のセルへのポインタが
ハッシュリスト１５ｃの第１要素と第２要素に入れられ
る。

【００５４】さらに同図（ｂ）の状態から、ifib(3) の
部分グラフがリダクションされると、図７に示すよう
に、ifib(3) のセルがコピーされてガベージとなり、ハ
ッシュリスト１５ｂの第１要素はガベージとなったifib
(3) のセルを指すようになり、また、第２要素はインダ
イレクションノードを指すようになる。ここで、ifib
(3) はifib(2) とifib(1) の部分グラフにリダクション
されるが、図６（ａ）から図６（ｂ）へのリダクショク
により、ifib(2) の部分グラフが既に登録されており、
これらは共有可能である。同様に、ifib(1) の部分グラ
フについても、ifib(1) の部分グラフが既に登録されて
おり、これらは共有可能である。そこで、ifib(3) のリ
ダクションにより生成されたifib(2) の部分グラフは既
に登録されているifib(2) の部分グラフに置き換えられ
る。

【００５５】すなわち、ifib(3) のリダクションにより
生成されたインダイレクションノードが指すセルにおい
て、ifib(2) の部分グラフを指すポインタの先が、同図
に示すように、既に登録されているifib(2) の部分グラ
フに置き換えられる。同様に、ifib(3) のリダクション
により生成されたifib(1) の部分グラフは既に登録され
ているifib(1) の部分グラフに置き換えられる。（３）計算断片（部分グラフ）の削除上記したように、リダクションが終わる前に、第１要素
の先のグラフのルートセルを、引数の部分グラフへのポ
インタも含めてコピーし、第１要素のポインタをリダク
ションされるグラフから、このコピーへと付け換え、こ
のコピーされたセルをヒープ領域が使い果たされたと
き、ガベージとして回収する。

【００５６】例えば、前記した図５（ｃ）において、ガ
ベージとなったifib(2) 、ifib(3)のセルは回収され
る。これにより、現在のグラフを最大に共有させるため
に必要な部分、すなわち、前記図３に示した、ハッシュ
リスト１５の第１要素１５１と第２要素１５２のポイン
タが共に同じセルを指しているものを除き、全ての登録
が削除される。

【００５７】しかし、このままでは、ハッシュテーブル
に、回収されたセルへのポインタ（例えば、上記 ifib
(2) 、ifib(3) のセルへのポインタ）が残ってしまうこ
とになって、後のリダクションで矛盾が起こってしま
う。そこで、ガベージコレクション時に、カベージとし
て回収されるセルへのポインタを持つハッシュテーブル
のエンリトを削除しなければならない。

【００５８】各セルにハッシュの保守用のポインタＰm
があるのは、この削除を高速に行うためである。すなわ
ち、ガベージコレクタが、ガベージのセルを見つける
と、それのハッシュの保守用ポインタを辿って、そのセ
ルを指すハッシュリストへのポインタを得る。次に、そ
のハッシュリストの次のリストへのポインタを次の次の
リストへのポインタで置き換える。

【００５９】例えば、前記図２において、セル１１ａが
カベージであるとすると、保守用のポインタＰm を辿っ
てハッシュリスト１５ａを指すハッシュテーブル１４ｂ
のポインタをハッシュリスト１５ａの次のハッシュリス
ト１５ｂを指すポインタに置き換える。これにより、カ
ベージとして回収されるセルへのポインタを持つハッシ
ュテーブルのエンリトが削除される。

【００６０】また、先に、インダイレクションセルへの
リンクが見つかったその都度、そのリンク先をそのセル
の先のセルへ付け換えることで、実際には、インダイレ
クションセルがないのと同じになると説明したが、詳し
くみると、このリンクを付け換えるときに、リンク先の
アドレスが変わってしまう。すなわち、本発明において
は、前記したように、部分グラフのルートセルのアドレ
スに基づいたハッシュ関数を使っているので、この部分
グラフを含む全ての部分グラフのハッシュ値を再計算し
て、登録する場所を移動しないと、ハッシュに不要なエ
ンリトが溜まって計算の効率が落ちる。

【００６１】しかしなから、この再計算のコストは膨大
なので、許容できない程不要なエントリが残らない程度
の部分グラフの再ハッシュを行う。このため、インダイ
レクションセルへのリンクをもっていたセルをルートと
する部分グラフだけを再ハッシュする。このハッシュで
この部分グラフの置き換えが起こらなければ、すなわ
ち、ルートのアドレスが変わらなければ、それを含む部
分グラフのハッシュ値は再計算しても元のままで、再計
算の必要はない。

【００６２】一方、部分グラフの置き換えが起こったと
きには、それを含む部分グラフの再ハッシュをし直さな
いと、全体のグラフを常時、最大の共有構造のダグに保
つことはできなくなる。つまり、ハッシュテーブルに登
録されていない部分グラフができて、後で、別の部分グ
ラフで構造が同じものができたときに、前の部分グラフ
と共有されず、この前の部分グラフは、どこかで再ハッ
シュが行われないと、いつまでも共有の対象から外れる
ことになる。

【００６３】しかし、この場合でも、この部分グラフを
含む外側のグラフのハッシュは有効である。すなわち、
これらのクラフのハッシュに関係するセルのアドレスは
変わっていないからである。本発明は上記した原理に基
づき、前記課題を解決したものであり、本発明の請求項
１の発明においては、ハッシュテーブル２ａによりグラ
フＳを共有化し、ある部分グラフｇ３について、ハッシ
ュ値を求め、求めたハッシュ値に基づき、ハッシュテー
ブル２ａを参照してハッシュテーブル２ａに登録された
ポインタにより、上記部分グラフｇ３と同一構造の部分
グラフｇ１のリダクション先の部分グラフｇ２を求め、
上記部分グラフｇ３のポインタをリダクション先の部分
グラフのポインタｇ２に置き換えるようにしたので、過
去の計算断片を再利用して部分的な再計算を繰り返さず
に計算を行うことができ、部分的な再計算を繰り返す計
算に必要とされるメモリ空間、および時間量を大幅に削
減することができる。

【００６４】本発明の請求項２の発明においては、請求
項１の発明において、記憶空間を使い果たすまで、全て
の部分グラフを登録しつづけ、ガベージコレクションに
同期して、現在の全体グラフを最大に共有できる部分を
除いた、全ての登録を削除して記憶空間を回収するよう
にしたので、ヒューリステックに頼らずに、オーバヘッ
ドを小さくして記憶空間を効率的に回収することができ
る。

【００６５】本発明の請求項３の発明においては、グラ
フリダクション機構の最適化装置を、リダクションの対
象となる全体のグラフＳを保持する第１の記憶手段１
と、第１の記憶手段１に記憶されたグラフＳの全ての部
分グラフのハッシュ値をハッシュテーブル２ａに記憶す
るとともに，過去に存在した部分グラフと現在到達して
いるそのリダクション先の部分グラフの組を記憶する第
２の記憶手段２と、第１の記憶手段１に保持された部分
グラフをリダクションし、リダクション先の部分グラフ
が、第２の記憶手段２に登録されていないとき、リダク
ション先の部分グラフを、元の部分グラフに対応付けて
第２の記憶手段２に登録するリダクション手段３とから
構成したので、過去にリダクションされた全ての部分グ
ラフとその最新のリダクション先の部分グラフの組を動
的に更新していくことができ、過去の計算断片を再利用
して計算を行う際のメモリ空間、および時間量を大幅に
削減することができる。

【００６６】本発明の請求項４の発明においては、請求
項３の発明において、ガベージコレクションに同期し
て、現在の全体のグラフを最大に共有させるために必要
な部分を除いた全ての登録を削除するガベージコレクタ
４を設けたので、ヒューリステックに頼らずに、オーバ
ヘッドを小さくして記憶空間を効率的に回収することが
できる。

【００６７】

【実施例】図８は本発明の実施例を示す図であり、同図
において、２１は書き換えの対象となる全体のグラフ
（セルを単位とする）を保持する第１の記憶装置、２２
は書き換えのルール（あるいは、検索の高速化のため
に、ルールに何らかの変換を加えたもの）を保持する第
２の記憶装置、２３は本発明に係わる第３の記憶装置で
あり、記憶装置２３は後述するリダクション装置２５と
ガベージコレクタ２６との間で通信しながらデータをや
り取りし、第１の記憶装置２１に記憶されたグラフの全
ての部分グラフをハッシュテーブルに記憶するととも
に，過去の存在した部分グラフとそれが現在書き換えら
れて到達している先の部分グラフの組を記憶する。

【００６８】２４は各セルに付加する属性（関数記号、
型情報、各種ハッシュテーブル）を記憶する第４の記憶
装置、２５は書き換えルールと部分グラフのマッチング
を取りながらグラフを書き換えるリダクション装置、２
６はガベージコレクション時にガベージを回収するガベ
ージコレクタである。なお、同図においては、記憶装置
を第１から第４の記憶装置に分割しているが、記憶装置
は必ずしも４つの装置を設ける必要はなく、物理的には
一つの装置とし、その中を分けて使ってもよい。

【００６９】次に図８に示した本発明の実施例の動作に
ついて説明する。本実施例の装置はリダクション装置２
５を中心にして周辺の記憶装置２１，２２，２３，２４
と通信しながら動作する。また、ガベージコレクタ２６
は、リダクション装置２５とは独立に動作し、記憶装置
２１の中のセルがリダクション装置２５により使い尽く
されたのを検出して、自動的にこのセルの中で他から参
照されないもの、すなわち、ガベージを回収して再び利
用可能な状態とする。

【００７０】図９は本実施例におけるリダクション装置
２５の動作を示すフローチャートであり、同図を参照し
てリダクション装置２５の動作を説明する。なお、図９
には図示していないが、リダクション装置２６には入出
力装置が設けられ、これを介して記憶装置２１，２２，
２３，２４とデータをやり取りする。

【００７１】リダクション装置２６は、先ず、図９のス
テップＳ１に示すように、第１の記憶装置２１の全て
のセルを利用可能な状態に初期化し、書き換えルール
を第２の記憶装置２２にロードし，初期グラフ（書き
換え対象のグラフ）をロードする。また、これに付随し
て各種の属性を第４の記憶装置２４にロードする。ス
テップＳ２において、第１の記憶装置２１の初期グラフ
の全ての部分グラフを第３の記憶装置のハッシュテーブ
ルに登録する。

【００７２】ステップＳ３において、リダクション装置
２６は記憶装置２１からリダクション可能な部分グラフ
を見つけ、ステップＳ４において、第２の記憶手段２２
のルールを参照して、それにマッチしたルールで部分グ
ラフをリダクションする。ステップＳ５において、上記
リダクションされた後の部分グラフが、記憶装置２３の
ハッシュテーブルに既に登録されているかどうかを調
べ、登録されていない場合には、登録する。

【００７３】そして、そのハッシュ結果として、その部
分グラフと組になっている、その部分グラフがさらにリ
ダクションされた先を記憶装置２３に返す。ここで、前
記したように、書き換えたグラフの登録ののち、そのグ
ラフを包含するグラフの再ハッシュの再計算が必要であ
る。上記処理を繰り返し、もうこれ以上リダクションで
きる部分が無くなると、ステップＳ７において、書き換
え終わった全てのグラフを出力して計算を終了する。以
上のようにして、リダクションを行い、利用可能なセル
がなくなることが検出されると、ガベージコレクタ２６
はガベージの回収にかかり、第２の記憶装置２３と通信
してガベージをそれが登録されているハッシュテーブル
から削除する。

【００７４】

【発明の効果】以上説明したように、本発明において
は、部分的な再計算を繰り返すに必要とされるメモリ空
間、および時間をヒューリスティクに頼らずに大幅に削
減することができる。例えば、Ｏ（２^N）のメモリ空
間、時間量のナイーブなフィボナッチ数列の計算を、問
題の大きさＮが小さく、ハッシュテーブルの検索がほと
んど一定時間で可能で、ガベージコレクションが計算の
最中に起こらないとすれば、動的に、すなわちプログラ
ムによる変換なしで、Ｏ（Ｎ）程度の計算とすることが
できる。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明のハッシュの仕組みを説明する図であ
る。

【図３】グラフのセルの構造を示す図である。

【図４】インダイレクション法による置き換えを説明す
る図である。

【図５】本発明におけるグラフの共有を説明する図であ
る。

【図６】計算履歴を利用したグラフの共有を説明する図
である。

【図７】計算履歴を利用したグラフの共有を説明する図
（続き）である。

【図８】本発明の実施例の構成を示す図である。

【図９】本発明の実施例の動作を示すフローチャートで
ある。

【図１０】再計算を行う計算木の一例を示す図である。

【符号の説明】

１第１の記憶手段２第２の記憶手段２ａハッシュテーブル３リダクション手段４ガベージコレクタ１２属性リスト１１ａ，１１ｂ，１１ｃセル２１第１の記憶装置２２第２の記憶装置２３第３の記憶装置２４第４の記憶装置２５リダクション装置２６ガベージコレクタｇ１，ｇ２，ｇ３部分グラフＳグラフ

Claims

【特許請求の範囲】

【請求項１】ハッシュテーブル(2a)によりグラフ(S)
を共有化し、ある部分グラフ(g3)について、ハッシュ値を求め、求めたハッシュ値に基づき、ハッシュテーブル(2a)を参
照してハッシュテーブル(2a)に登録されたポインタによ
り、上記部分グラフ(g3)と同一構造の部分グラフ(g1)の
リダクション先の部分グラフ(g2)を求め、上記部分グラフ(g3)のポインタをリダクション先の部分
グラフのポインタ(g2)に置き換えることにより、過去の
計算断片を再利用して部分的な再計算を繰り返さずに計
算を行うことを特徴とするグラフリダクション機構の最
適化方法。
【請求項２】記憶空間を使い果たすまで、全ての部分
グラフを登録しつづけ、ガベージコレクションに同期し
て、現在の全体グラフを最大に共有できる部分を除い
た、全ての登録を削除して記憶空間を回収することを特
徴とする請求項１のグラフリダクション機構の最適化方
法。
【請求項３】リダクションの対象となる全体のグラフ
(S) を保持する第１の記憶手段(1) と、第１の記憶手段(1) に記憶されたグラフ(S) の全ての部
分グラフのハッシュ値をハッシュテーブル(2a)に記憶す
るとともに，過去に存在した部分グラフと現在到達して
いるそのリダクション先の部分グラフの組を記憶する第
２の記憶手段(2) と、第１の記憶手段(1) に保持された部分グラフをリダクシ
ョンし、リダクション先の部分グラフが、第２の記憶手
段(2) に登録されていないとき、リダクション先の部分
グラフを、元の部分グラフに対応付けて第２の記憶手段
(2) に登録するリダクション手段(3) とを備えたことを
特徴とするグラフリダクション機構の最適化装置。
【請求項４】ガベージコレクションに同期して、現在
の全体のグラフを最大に共有させるために必要な部分を
除いた全ての登録を削除するガベージコレクタ(4) を備
えたことを特徴とする請求項３のグラフリダクション機
構の最適化装置。