Work-stealing Strategies That Consider Work Amount and Hierarchy

• Item type: Trans(1)
• 公開日: 2021-06-15
• タイトル: Work-stealing Strategies That Consider Work Amount and Hierarchy
• タイトル / 言語: en
• タイトル: Work-stealing Strategies That Consider Work Amount and Hierarchy
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] parallel programming languages, work stealing, priority, weight, concurrency, many-core, Barnes-Hut algorithm
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
• 著者所属: Department of Computer Science and Networks, Kyushu Institute of Technology
• 著者所属: Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology／Presently with Ad-Sol Nissin Corporation
• 著者所属: Academic Center for Computing and Media Studies, Kyoto University
• 著者所属: Department of Information Sciences, Faculty of Science, Kanagawa University
• 著者所属(英): en
• 著者所属(英): Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Networks, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology / Presently with Ad-Sol Nissin Corporation
• 著者所属(英): en
• 著者所属(英): Academic Center for Computing and Media Studies, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Sciences, Faculty of Science, Kanagawa University
• 著者名: Ryusuke, Nakashima; Masahiro, Yasugi; Hiroshi, Yoritaka; Tasuku, Hiraishi; Seiji, Umatani
• 著者名(英): Ryusuke, Nakashima; Masahiro, Yasugi; Hiroshi, Yoritaka; Tasuku, Hiraishi; Seiji, Umatani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper proposes work-stealing strategies for an idle worker (thief) to select a victim worker. These strategies avoid small tasks being stolen to reduce the total task-division cost. We implemented these strategies on a work-stealing framework called Tascell. First, we propose new types of priority- and weight-based steal strategies. Programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as “priorities” or “weights”. With a priority-based strategy, a thief selects the victim that has the highest known priority at that time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. Second, we propose work-stealing strategies to alleviate excessive intra-node work stealing and excessive “steal backs” (or leapfroggings); for example, we allow workers to steal tasks from external nodes with some frequency even if work remains inside the current node. Our evaluation uses a parallel implementation of the “highly serial” version of the Barnes-Hut force-calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.; ------------------------------; 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.29(2021) (online); ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes work-stealing strategies for an idle worker (thief) to select a victim worker. These strategies avoid small tasks being stolen to reduce the total task-division cost. We implemented these strategies on a work-stealing framework called Tascell. First, we propose new types of priority- and weight-based steal strategies. Programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as “priorities” or “weights”. With a priority-based strategy, a thief selects the victim that has the highest known priority at that time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. Second, we propose work-stealing strategies to alleviate excessive intra-node work stealing and excessive “steal backs” (or leapfroggings); for example, we allow workers to steal tasks from external nodes with some frequency even if work remains inside the current node. Our evaluation uses a parallel implementation of the “highly serial” version of the Barnes-Hut force-calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.; ------------------------------; 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.29(2021) (online); ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 14, 号 3, 発行日 2021-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会