Parallel Graph Traversals using Work-Stealing Frameworks for Many-core Platforms

• Yasugi Masahiro

  Graduate School of Informatics, Kyoto University

• Hiraishi Tasuku

  Academic Center for Computing and Media Studies, Kyoto University

• Umatani Seiji

  Graduate School of Informatics, Kyoto University

• Yuasa Taiichi

  Graduate School of Informatics, Kyoto University

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.

Journal

• Journal of Information Processing

  Journal of Information Processing 20 (1), 128-139, 2012

  Information Processing Society of Japan

Keywords

• Regular Paper

Details

• CRID: 1390001205293822720
• NII Article ID: 130002116405
• NII Article ID: 130002073575
• NII Book ID: AA00700121
• ISSN: 03875806
• ISSN: 18826652
• ISSN: 18810896
• DOI: 10.2197/ipsjjip.20.128
• DOI: 10.11185/imt.7.73
• HANDLE: 2433/168288
• Web Site: http://id.nii.ac.jp/1001/00080328/
• Web Site: http://www.jstage.jst.go.jp/article/ipsjjip/20/1/20_1_128/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed