文献

J-GLOBAL ID：201702288512382285   整理番号：17A0440799

分散メモリ環境における共通項目集合を用いた連結部分グラフの並列化

Parallelization of Extracting Connected Subgraphs with Common Itemsets in Distributed Memory Environments

著者 (5件)： Okuno Shingo (Graduate School of Informatics, Kyoto University) ,  Hiraishi Tasuku (Academic Center for Computing and Media Studies, Kyoto University) ,  Nakashima Hiroshi (Academic Center for Computing and Media Studies, Kyoto University) ,  Yasugi Masahiro (Department of Artificial Intelligence, Kyushu Institute of Technology) ,  Sese Jun (National Institute of Advanced Industrial Science and Technology)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 25  ページ： 256-267(J-STAGE)  発行年： 2017年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文は,分散メモリ環境において,タスク並列言語Tascellを使用して,タスクを用いてグラフから,そしてグラフの頂点に関連した項目集合から,共通の項目集合を持つ(その大きさが所定の閾値以上である)連結された部分グラフをすべて抽出するグラフマイニングの並列実装を提案した。この問題に関して,筆者らは共有メモリ環境でのCOPINEという名前のバックトラック検索アルゴリズムの並列化とその実装を既に提案した。この実装では,全てのワーカが,ロックによって制御される単一のテーブルを共有し,そのテーブルは,不要な検索の必要性を排除するために検索中に取得した知識を含んだ。この共有方法は,ノード間通信のコストが大幅に増加するため,分散メモリ環境では実用的ではない。そこで,筆者らは各コンピューティングノードがテーブルを持ち,定期的な時間間隔で他のノードに更新を送信する共有方法を実装した。これに加えて,COPINEの高いタスク作成コストは問題であり,したがって,ノード間のワークスチール数を最小にすることを目指すTascellにおけるワークスチール戦略は,小タスクに対するノード内ワークスチール数を増加するために,性能をかなり低下させた。筆者らはこの問題を,外部ノードからタスクを要求できるようにワーカを促すことによって解決した。筆者らはまた,犠牲者ワーカが作成したタスクの規模の見積もりに基づいたワークスチール戦略を採用した。このアプローチにより,最大8ノード×16ワーカで優れたスピードアップ性能を達成できた。(翻訳著者抄録)

シソーラス用語： *分散メモリ ,  グラフ ,  *部分グラフ ,  *並列化 ,  プログラミング言語 ,  知識獲得 ,  実装 ,  バックトラッキング ,  計算機アルゴリズム ,  方式 ,  検索アルゴリズム
準シソーラス用語： *連結グラフ ,  並列言語 ,  グラフマイニング ,  並列実装 ,  バックトラック ,  ワークスチール

著者キーワード (5件)： backtrack search ,  graph mining ,  task-parallel languages ,  distributed memory environments ,  dynamic load balancing

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (18件)：

• [1] Seki, M. and Sese, J.: Identification of Active Biological Networks and Common Expression Conditions, Proc. 8th IEEE International Conference on BioInformatics and BioEngineering, BIBE '08, pp.1-6 (2008).
• [2] Sese, J., Seki, M. and Fukuzaki, M.: Mining Networks with Shared Items, Proc. 19th ACM International Conference on Information and Knowledge Management, CIKM '10, pp.1681-1684 (2010).
• [3] Hiraishi, T., Yasugi, M., Umatani, S. and Yuasa, T.: Backtracking-based Load Balancing, Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '09, pp.55-64 (2009).
• [4] Okuno, S., Hiraishi, T., Nakashima, H., Yasugi, M. and Sese, J.: Parallelization of Extracting Connected Subgraphs with Common Itemsets, IPSJ Trans. Programming, Vol.7, No.3, pp.22-39 (2014).
• [5] Hiraishi, T., Yasugi, M. and Umatani, S.: Evaluation of the Tascell Dynamic Load Balancing Framework in Widely Distributed and Many-Core Environments, Proc. Symposium on Advanced Computing Systems and Infrastructures 2011, SACSIS 2011, pp.55-63 (2011). (in Japanese).

タイトルに関連する用語 (6件)： 分散メモリ ,  環境 ,  集合 ,  連結部分 ,  グラフ ,  並列化