WEKO3
アイテム
A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
https://ipsj.ixsq.nii.ac.jp/records/62763
https://ipsj.ixsq.nii.ac.jp/records/62763e178c1c9-53ab-4a1b-bde3-d8f92e0c1b05
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-HPC09121002.pdf (172.9 kB)
|
Copyright (c) 2009 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2009-07-28 | |||||||
| タイトル | ||||||||
| タイトル | A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 集合通信 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Graduate School of Informatics, Kyoto University | ||||||||
| 著者所属 | ||||||||
| ACCMS, Kyoto University | ||||||||
| 著者所属 | ||||||||
| Graduate School of Informatics, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Informatics, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| ACCMS, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Informatics, Kyoto University | ||||||||
| 著者名 |
Bingbing, Zhuang
× Bingbing, Zhuang
|
|||||||
| 著者名(英) |
Bingbing, Zhuang
× Bingbing, Zhuang
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper proposes a memory-efficient algorithm of variable-size all-to-all communication based on bitonic sort and in-place merge. The algorithm takes O(N log2 P) computation and communication time and requires merely O(P) extra space for the communication among P processes having N elements of data to be exchanged for each. We also discuss another algorithm which takes O(MP log P) time where M is the size of the largest chunk which a process must send to another process and thus is expected to be O(N/P) in most practical applications to make the time complexity O(N log P). We implemented the first sort-based algorithm to show it works with reasonable efficiency. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper proposes a memory-efficient algorithm of variable-size all-to-all communication based on bitonic sort and in-place merge. The algorithm takes O(N log2 P) computation and communication time and requires merely O(P) extra space for the communication among P processes having N elements of data to be exchanged for each. We also discuss another algorithm which takes O(MP log P) time where M is the size of the largest chunk which a process must send to another process and thus is expected to be O(N/P) in most practical applications to make the time complexity O(N log P). We implemented the first sort-based algorithm to show it works with reasonable efficiency. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10463942 | |||||||
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC） 巻 2009-HPC-121, 号 2, p. 1-6, 発行日 2009-07-28 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
