8.2 グラフ構造探索問題
8.2.3 並列パターンマッチング
次に前節と同様に並列パターンマッチングの効果を評価する計測をグラフ構造探索問題 を使用して行った.
この例題の特徴として, アトムの伝搬が頻繁に起こらないことが挙げられる. グラフ中 のノードのうち,三角形の形成に関わるノード数の割合にも依存するが,ルール適用ごとの 関係は最短経路問題よりも薄い. 本計測で使用するグラフ中のノードは, どのノードも三 角形の構造に2つ以上関与していないことを前提に作成している. したがってアトムの伝 搬は全く起こらず,並列パターンマッチングの効果が期待できる例題となっている.
使用するグラフは疎な連結グラフであるが,グラフを形成するノードに対して三角形の 構造に関わるノード数の割合を4種類(10, 1, 0.1, 0.01%) 用意し, それぞれのグラフに対 して評価実験を行った. また,パターンマッチング手法として,依存型と非依存型の2つの 戦略方法をそれぞれ適用して計測を行った.
依存型の戦略で並列パターンマッチングを行った計測結果を図8.5, 8.6, 8.7, 8.8,非依存 型の戦略で並列パターンマッチングを行った計測結果を図8.9, 8.10, 8.11, 8.12に示す.
図8.5から図8.12の結果より,パターンマッチンの戦略に関わらずどの割合においても 逐次実行と比較して実行時間を削減し,並列化による高速化を実現することができた. 各割 合の速度比を比較すると, グラフ中において書き換えられるノードの割合が多くなると並 列化による効果が薄くなっている. これはグラフ書換え回数に比例して並列化によるオー バーヘッドの割合が増えてしまい, 結果として速度向上につながらないことが理由に挙げ られる.
今回最大10コアのCPUを使用して計測した結果,逐次実行と比較して最大5倍の速度 向上を達成することができた(図8.11). 理想的な速度向上は使用したコア数分の速度が見 込めるが,理想的な速度向上にならない理由として,グラフ書換え,並列化によるオーバー ヘッド,スレッド同士の同期によるオーバーヘッドなどが原因として考えられる.
並列パターンマッチングの戦略の違いに関して考察する. 依存型の実行結果は非依存型 と比較すると若干劣っていることが読み取れる. これは完全性を保つために再度確認のグ ラフパターンマッチングを行っていることが大きな要因であることが考えられる. 各ス レッドがルール適用ごとに一番適用しやすいアトムからパターンマッチする利点よりも再 確認のグラフパターンマッチングを行う欠点の方が影響が大きくなってしまったため, 毎 回担当するアトムを再分配する非依存型の方が勝る結果となった.
今回の評価実験は疎グラフを扱ったが,密グラフを使用した場合はさらに並列化による
効果が期待されると考える. 理由として, エッジ数が増えると探索すべき範囲が増えるた め, グラフパターンマッチングの処理時間がさらに増加すると考察できる. 結果として, さ らなる並列化による効果が期待できると予想できる. まとめると,グラフパターンマッチ ング処理の割合が増えると並列化による効果が顕著に表れる.
最後に並列パターンマッチングによる速度向上率が最も大きかった図8.11の条件に対 し, さらにスレッド数を増やして計測を行った. 実験結果を図 8.13に示す. この結果より, 最大8倍まで速度向上を達成することができた.
Ϭ ϭϬϬ ϮϬϬ ϯϬϬ ϰϬϬ ϱϬϬ ϲϬϬ ϳϬϬ ϴϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.5 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 10%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ ϯ͘ϱ ϰ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.6 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 1%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ ϯ͘ϱ ϰ ϰ͘ϱ ϱ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.7 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.1%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ ϯ͘ϱ ϰ ϰ͘ϱ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.8 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.01%)
Ϭ ϭϬϬ ϮϬϬ ϯϬϬ ϰϬϬ ϱϬϬ ϲϬϬ ϳϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.9 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 10%)
Ϭ ϭϬϬ ϮϬϬ ϯϬϬ ϰϬϬ ϱϬϬ ϲϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ ϯ͘ϱ ϰ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.10 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 1%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
ϭ Ϯ ϯ ϰ ϱ ϲ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.11 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.1%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ
ϯϬϬϬϬϬϬϬ Ϭ
Ϭ͘ϱ ϭ ϭ͘ϱ Ϯ Ϯ͘ϱ ϯ ϯ͘ϱ ϰ ϰ͘ϱ ϱ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.12 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.01%)
Ϭ ϱϬ ϭϬϬ ϭϱϬ ϮϬϬ ϮϱϬ ϯϬϬ ϯϱϬ ϰϬϬ ϰϱϬ ϱϬϬ
Ϭ ϱ ϭϬ ϭϱ ϮϬ Ϯϱ ϯϬ
ƚŝŵĞƐ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
Ϭ Ϯ ϰ ϲ ϴ ϭϬ ϭϮ
Ϭ ϱ ϭϬ ϭϱ ϮϬ Ϯϱ ϯϬ
ƐƉĞĞĚƵƉ
ĐŽƌĞ
ϯϬϬϬϬϬϬ ϲϬϬϬϬϬϬ ϵϬϬϬϬϬϬ ϭϮϬϬϬϬϬϬ ϭϱϬϬϬϬϬϬ ϭϴϬϬϬϬϬϬ ϮϭϬϬϬϬϬϬ ϮϰϬϬϬϬϬϬ ϮϳϬϬϬϬϬϬ ϯϬϬϬϬϬϬϬ
(a)実行時間 (b)速度向上
図8.13 図8.11の計測の続き
第 9 章
まとめと今後の課題
9.1 まとめ
本研究はLMNtal実行時処理系SLIMにおいて,ルール適用時におけるグラフパターン
マッチングの改善を行った. その結果,複数の例題において従来よりも高速にグラフパター ンマッチングが行えるようになった. 具体的には, アトムの動的操作によって想定する時 間計算量より悪く動作したプログラムの計算量を改善し,並列グラフパターンマッチング によって逐次実行と比較して10コアを使用したときに最大5倍の速度向上を達成した.