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

DOI Web Site 被引用文献1件 参考文献13件 オープンアクセス
  • 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

書誌事項

公開日
2017
資源種別
journal article
DOI
  • 10.2197/ipsjjip.25.256
公開者
一般社団法人 情報処理学会

説明

<p>This paper proposes a parallel implementation of graph mining that extracts all connected subgraphs with common itemsets, of which the size is not less than a given threshold, from a graph and from itemsets associated with vertices of the graph, in distributed memory environments using the task-parallel language Tascell. With regard to this problem, we have already proposed parallelization of a backtrack search algorithm named COPINE and its implementation in shared memory environments. In this implementation, all workers share a single table, which is controlled by locks, that contains the knowledge acquired during the search to obviate the need for unnecessary searching. This sharing method is not practical in distributed memory environments because it would lead to a drastic increase in the cost of internode communications. Therefore, we implemented a sharing method in which each computing node has a table and sends its updates to the other nodes at regular time intervals. In addition to this, the high task creation cost for COPINE is problematic 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. We solved this problem by promoting workers to enable them to request tasks from external nodes. We also employed a work-stealing strategy based on estimation of the sizes of tasks created by victim workers. This approach enabled us to achieve good speedup performance with up to 8 nodes × 16 workers.</p>

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (13)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ