分散メモリ環境における並列グラフマイニングの実現に向けて

• Item type: Trans(1)
• 公開日: 2016-06-06
• タイトル: 分散メモリ環境における並列グラフマイニングの実現に向けて
• タイトル / 言語: en
• タイトル: Towards Parallel Graph Mining in Distributed Memory Environments
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 京都大学学術情報メディアセンター
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属: 産業技術総合研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): 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
• 論文抄録 / 内容記述: 本発表では，各頂点がアイテムの集合を持つようなグラフからユーザが指定した閾値以上の数の共通アイテム集合を持つ連結部分グラフを全抽出するグラフマイニングの，タスク並列言語Tascellを用いた分散メモリ環境向けの実装について報告する．我々はすでに，この問題を解く探索アルゴリズムCOPINEの共有メモリ環境向けの並列実装を提案している．この実装では，探索中に蓄えた知識に基づいて不要な探索を回避するため，1つの情報管理テーブルを全ワーカで共有する．しかし分散メモリ環境でこの手法を用いると，通信コストが大きくなってしまう．そこで，ノードをまたぐワークスティールのタイミングで，そのノード間のテーブル情報の差分を送信する手法を実装した．また，COPINEではタスク生成のコストが大きいため，ノード間のスティール回数の最小化を指向する従来のTascellのスティール戦略では，ノード内で小さい仕事を多く盗み合うことによる性能劣化が大きくなってしまう．そこで，ノード外へのタスク要求を増やすことにより大きな仕事を得やすくするスティール戦略の検討，実装も行った．これらの工夫により，一定の性能改善効果が得られることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper reports a parallelized implementation of graph mining that extracts all connected subgraphs with common itemsets whose size is not less than a given threshold from a graph and itemsets associated with vertices of the graph, in distributed memory environments using the task-parallel language Tascell. For this problem, we have already proposed a backtrack search algorithm called COPINE and its parallel implementation in shared memory environments. In this implementation, all workers share a single table that contains the knowledge acquired during search in order to avoid useless search. This sharing method will crucially increase the cost for internode communications in distributed memory environments. Therefore, we implemented a sharing method where the difference of table information between computing nodes is sent when an internode work-steal occurs. There is another problem that the task creation cost is high for COPINE and thus the conventional work-stealing strategy in Tascell, which aims to minimize the number of internode work-steals, significantly degrades the performance since it increases the number of intranode work-steals for small tasks. Therefore, we implemented and evaluated work-stealing strategies that promotes workers to request tasks to external nodes to increase the opportunity to obtain large tasks. We confirmed that we can get the performance improvement using these methods.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 9, 号 3, p. 22-22, 発行日 2016-06-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会