Pat

J-GLOBAL ID：200903030570999305

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

Inventor： 山中 英樹
Applicant, Patent owner： 富士通株式会社
Agent (1)： 京谷 四郎
Gazette classification：公開公報
Application number (International application number)：1994125036
Publication number (International publication number)：1995334366
Application date： Jun. 07, 1994
Publication date： Dec. 22, 1995
Summary：

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

Claim (excerpt)：

ハッシュテーブル(2a)によりグラフ(S) を共有化し、ある部分グラフ(g3)について、ハッシュ値を求め、求めたハッシュ値に基づき、ハッシュテーブル(2a)を参照してハッシュテーブル(2a)に登録されたポインタにより、上記部分グラフ(g3)と同一構造の部分グラフ(g1)のリダクション先の部分グラフ(g2)を求め、上記部分グラフ(g3)のポインタをリダクション先の部分グラフのポインタ(g2)に置き換えることにより、過去の計算断片を再利用して部分的な再計算を繰り返さずに計算を行うことを特徴とするグラフリダクション機構の最適化方法。

IPC (2)：

G06F 9/44 501 ,  G06F 9/44 510