| Item type |
SIG Technical Reports(1) |
| 公開日 |
2020-07-23 |
| タイトル |
|
|
タイトル |
適応的分割法によるPARADISの高速化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Accelerate PARADIS by adaptive partitioning |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
アルゴリズム高速化 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
慶應義塾大学 |
| 著者所属 |
|
|
|
ヤフー株式会社 |
| 著者所属 |
|
|
|
ヤフー株式会社 |
| 著者所属 |
|
|
|
慶應義塾大学 |
| 著者名 |
尾城, 拓真
宮崎, 崇史
清水, 伸幸
川島, 英之
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
メニーコアの有する高並列性を活用する並列 sort アルゴリズムに PARADIS がある．PARADIS はほかの並列 sort 法と比較しても高い並列性を示すことが論文に示されているが，性能劣化を引き起こす挙動に関する解析は不十分である．本研究では PARADIS を再実装し，特定の場合において PARADIS の処理が逐次的に行われてしまうケースを明らかにし，そのケースに対応するための新しい PARADIS の手法，適応的分割法を提案する．適応的分割法は，従来の PARADIS では不可能であった Repair フェーズ内のバケット中の操作を並列化することを可能にした．適応的分割法を導入した PARADIS は実験の結果，最大で 57% の性能向上を実現した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
PARADIS is fast parallel in-place radix sort. In PARADIS paper, author show PARADIS sclable in terms of parallelism, but analysis of behavior causing performance degredation is insufficient. In this paper, we reimplement PARADIS, and clarify cases where PARADIS is performed sequentially in specific cases. Then, We propose a new PARADIS method adaptive partitioning method, to deal with the case. The adaptive partitioning method achive parallelizing operations in repair phase, which was not possible with original PARADIS. As a result of experiments, PARADIS which intoroduced the adaptive partitioning method, achieved a performance improvement of 57%. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10463942 |
| 書誌情報 |
研究報告ハイパフォーマンスコンピューティング（HPC）
巻 2020-HPC-175,
号 4,
p. 1-8,
発行日 2020-07-23
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8841 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-HPC20175004.pdf (1.7 MB)
