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

• Item type: Trans(1)
• 公開日: 2017-01-06
• タイトル: Parallelization of Extracting Connected Subgraphs with Common Itemsets in Distributed Memory Environments
• タイトル / 言語: en
• タイトル: Parallelization of Extracting Connected Subgraphs with Common Itemsets in Distributed Memory Environments
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] backtrack search, graph mining, task-parallel languages, distributed memory environments, dynamic load balancing
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Informatics, Kyoto University
• 著者所属: Academic Center for Computing and Media Studies, Kyoto University
• 著者所属: Academic Center for Computing and Media Studies, Kyoto University
• 著者所属: Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者所属: National Institute of Advanced Industrial Science and Technology
• 著者所属(英): 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
• 著者名(英): Shingo, Okuno; Tasuku, Hiraishi; Hiroshi, Nakashima; Masahiro, Yasugi; Jun, Sese
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 10, 号 1, 発行日 2017-01-06
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会