Downloads: 193

Files in This Item:
File Description SizeFormat 
ipsjjip.20.128.pdf1.52 MBAdobe PDFView/Open
Title: Parallel Graph Traversals using Work-Stealing Frameworks for Many-core Platforms
Authors: Yasugi, Masahiro
Hiraishi, Tasuku  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0003-4285-893X (unconfirmed)
Umatani, Seiji  kyouindb  KAKEN_id
Yuasa, Taiichi
Author's alias: 八杉, 昌宏
平石, 拓
馬谷, 誠二
湯淺, 太一
Keywords: work stealing
graph traversals
spanning tree
many-core
Issue Date: Jan-2012
Publisher: Information Processing Society of Japan
Journal title: Journal of Information Processing
Volume: 20
Issue: 1
Start page: 128
End page: 139
Abstract: 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, naïve 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.
Rights: © 2012 by the Information Processing Society of Japan
URI: http://hdl.handle.net/2433/168288
DOI(Published Version): 10.2197/ipsjjip.20.128
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.