ダウンロード数: 264
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
ipsjjip.20.128.pdf | 1.52 MB | Adobe PDF | 見る/開く |
タイトル: | Parallel Graph Traversals using Work-Stealing Frameworks for Many-core Platforms |
著者: | Yasugi, Masahiro Hiraishi, Tasuku https://orcid.org/0000-0003-4285-893X (unconfirmed) Umatani, Seiji Yuasa, Taiichi |
著者名の別形: | 八杉, 昌宏 平石, 拓 馬谷, 誠二 湯淺, 太一 |
キーワード: | work stealing graph traversals spanning tree many-core |
発行日: | Jan-2012 |
出版者: | Information Processing Society of Japan |
誌名: | Journal of Information Processing |
巻: | 20 |
号: | 1 |
開始ページ: | 128 |
終了ページ: | 139 |
抄録: | 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. |
著作権等: | © 2012 by the Information Processing Society of Japan |
URI: | http://hdl.handle.net/2433/168288 |
DOI(出版社版): | 10.2197/ipsjjip.20.128 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。