Parallelization of Graph Mining using Backtrack Search Algorithm

 本研究では，各頂点がアイテムの集合を持つようなグラフから共通アイテム集合を持つ連結部分グラフ（アイテム共有部分グラフ）を抽出するという，非常に複雑なグラフマイニングの並列化を行った．ここで共通アイテム集合とは，連結部分グラフに含まれるすべての頂点が持つアイテム集合の積集合を意味する．本研究では，ユーザが指定した閾値以上の数の共通アイテム集合を持つアイテム共有部分グラフの全抽出を対象とする．このグラフマイニングは，ソーシャルネットワークや生体ネットワークの分析などに応用できる．

 アイテム共有部分グラフを効率良く抽出する逐次アルゴリズムとして，COPINEというバックトラック探索アルゴリズムがすでに提案されている．COPINEは探索中に蓄えた知識に基づく枝刈りを行うことで不要な探索を回避する．この枝刈りは，複数のワーカにそれぞれ固有の部分木（タスク）を割り当てる並列探索でも同様に行われるべきである．しかし，他のワーカによって蓄えられた知識を無条件に利用すると過剰な枝刈りが行われる可能性がある．本研究では，他のワーカが蓄えた知識の参照に制約を加えることで，そのような過剰な枝刈りを回避できることを形式的に証明した．また，この制約に基づいてCOPINEを拡張することで，並列探索に対応したCOPINEアルゴリズムを設計した．

 COPINEの探索木は不規則な構造を持つため，並列実装には動的負荷分散を導入するのが有効であると考えられる．不規則な構造を持つ問題の動的負荷分散を用いた並列実装は，タスク並列言語を用いて行うのが効率的である．タスク並列言語は，並列に実行されるタスクの動的な生成と，生成されたタスクのワーカへの割付を自動的に行うことができる．本研究では，タスク並列言語の中でも，バックトラック探索の並列化で特に高い性能を得られることが確認されているTascellを用いてCOPINEの並列実装を行った．

 並列探索で枝刈りを効率良く実現するためには，探索中に蓄えた知識を上記の制約を満たしつつワーカ間で効率良く共有することが求められる．特に，分散メモリ環境ではノード間通信が発生するため，通信コストも考慮する必要がある．そこで，他のワーカが蓄えた知識をできるだけ多く共有することと，共有のためのコストをできるだけ小さくすることのトレードオフを勘案した，効率的な手法を共有・分散メモリ環境向けにそれぞれ実装した．また，枝刈り効率を向上させる問題分割・タスク生成戦略の考案・実装も行った．

 並列探索では探索順序も性能に影響を与える．逐次実行時には，不要と判断された部分探索木は必ず探索が行われる前に枝刈りされる．一方で並列探索時には，他のワーカが不要な探索を開始した後に枝刈りが行われる場合もある．枝刈りを無視して不要な探索が続けられると，探索空間が増大し性能に悪影響を与える．このような探索空間の増大は，枝刈り時に不要な探索を行っているワーカを検出し，そのワーカに不要な探索を中断するよう促すことで最小限に抑えることができる．この中断処理は，例外により脱出したtryブロック内で並列実行中の全タスクを自動的に中断するような例外処理機能を持つタスク並列言語を用いることで簡潔に効率良く実装できる．Tascellはこのような例外処理機能をサポートしていなかったため，この言語機能を追加した上で，中断処理を行うCOPINEの並列実装を行った．

 本研究では，タンパク質ネットワークの実データを用いてこれまで述べた並列実装の性能評価を行い，共有・分散メモリ環境での並列探索で性能向上が得られることを確認した．