2024-03-29T06:11:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000795212022-10-21T05:24:51Z00581:06276:06633
Parallel Graph Traversals using Work-Stealing Frameworks for Many-core PlatformsParallel Graph Traversals using Work-Stealing Frameworks for Many-core Platformseng特集:情報爆発時代におけるIT基盤技術http://id.nii.ac.jp/1001/00079521/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=79521&item_no=1&attribute_id=1&file_no=1Copyright (c) 2011 by the Information Processing Society of JapanGraduate School of Informatics, Kyoto UniversityAcademic Center for Computing and Media Studies, Kyoto UniversityGraduate School of Informatics, Kyoto UniversityGraduate School of Informatics, Kyoto UniversityMasahiro, YasugiTasuku, HiraishiSeiji, UmataniTaiichi, YuasaParallel programming/execution frameworks for many/multi-core platforms should support as many applications as possible. In general, work-stealing frameworks provide efficient load balancing even for irregular parallel applications. Unfortunately, naive parallel programs which traverse graph-based data structures (e.g., for constructing spanning trees) cause stack overflow or unacceptable load imbalance. In this study, we develop parallel programs to perform probabilistically balanced divide-and-conquer graph traversals. We propose a programming technique for accumulating overflowed calls for the next iteration of repeated parallel stages. In an emerging backtracking-based work-stealing framework called “Tascell,” which features on-demand concurrency, we propose a programming technique for long-term exclusive use of workspaces, leading to a similar technique also in the Cilk framework.------------------------------ 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.20(2012) No.1 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.128------------------------------ Parallel programming/execution frameworks for many/multi-core platforms should support as many applications as possible. In general, work-stealing frameworks provide efficient load balancing even for irregular parallel applications. Unfortunately, naive parallel programs which traverse graph-based data structures (e.g., for constructing spanning trees) cause stack overflow or unacceptable load imbalance. In this study, we develop parallel programs to perform probabilistically balanced divide-and-conquer graph traversals. We propose a programming technique for accumulating overflowed calls for the next iteration of repeated parallel stages. In an emerging backtracking-based work-stealing framework called “Tascell,” which features on-demand concurrency, we propose a programming technique for long-term exclusive use of workspaces, leading to a similar technique also in the Cilk framework.------------------------------ 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.20(2012) No.1 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.128------------------------------ AN00116647情報処理学会論文誌52122011-12-151882-77642011-12-09