分散環境での並列グラフマイニングにおけるタスク中断処理による冗長探索削減

• Item type: Trans(1)
• 公開日: 2018-02-08
• タイトル: 分散環境での並列グラフマイニングにおけるタスク中断処理による冗長探索削減
• タイトル / 言語: en
• タイトル: Reducing Redundant Search in Parallel Graph Mining Using Task Abortion in Distributed Memory Environments
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科／現在，株式会社富士通研究所
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 産業技術総合研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University / Presently with Fujitsu Laboratories Ltd.
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology
• 著者名: 奥野, 伸吾; 平石, 拓; 中島, 浩; 八杉, 昌宏; 瀬々, 潤
• 著者名(英): Shingo, Okuno; Tasuku, Hiraishi; Hiroshi, Nakashima; Masahiro, Yasugi; Jun, Sese
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，各頂点がアイテムの集合を持つようなグラフからユーザが指定した閾値以上の数の共通アイテム集合を持つ連部結分グラフを全抽出するグラフマイニングアルゴリズムCOPINEの，タスク並列言語Tascellを用いた既存実装の改善を提案する．COPINEは，左深さ優先の探索木走査中に得た知識を蓄えるテーブルを利用した枝刈りにより不要な探索を回避するが，並列探索では，枝刈りの実行が他ワーカによる走査開始後になることがあるため，無視できない量の無駄な探索が生じてしまう．これを解決するため，脱出対象となるtryブロック内の全並列タスクを自動的に中断する機能を持つ例外処理を用いて無駄な探索を速やかに中断させる手法を提案し，すでに共有メモリ環境ではその効果を確認している．本研究では，この手法を分散環境にも適用した．この結果，16ノード×16ワーカを用いた性能評価で探索空間削減効果が得らることが確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This presentation proposes an improvement of an existing parallel implementation of the graph mining algorithm called COPINE using the Tascell task parallel language. COPINE extracts all connected subgraphs with common itemsets, of which the size is not less than a given threshold, from a graph and itemsets associated with vertices of the graph. This algorithm avoids unnecessary searches using a pruning mechanism that depends on the knowledge acquired during the left- and depth-first traversal of its search tree. In the parallel search, a problem arises that a worker may prune the subtree after another worker has started to traverse it, resulting in a large number of redundant searches. Such redundancy can be significantly reduced by letting a worker abort such redundant traversals as soon as possible. This abortion can be implemented efficiently using exception handling whereby all parallel tasks running in a try block with an exception are automatically aborted. We have already proposed this mechanism and realized performance improvements in shared memory environments. In this research, we applied it to distributed memory environments. As a result, we successfully reduced search space in performance evaluations using 16 nodes × 16 workers.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 11, 号 1, p. 29-29, 発行日 2018-02-08
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会