WEKO3
アイテム
AGPUモデルでの並列ソートアルゴリズムの計算量について
https://ipsj.ixsq.nii.ac.jp/records/91775
https://ipsj.ixsq.nii.ac.jp/records/91775ed41a3eb-63cc-4f83-bc4b-28aa3c6fb455
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]()
2100年1月1日からダウンロード可能です。
|
Copyright (c) 2013 by the Institute of Electronics, Information and Communication Engineers
This SIG report is only available to those in membership of the SIG. |
|
AL:会員:¥0, DLIB:会員:¥0 |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2013-05-10 | |||||||
タイトル | ||||||||
タイトル | AGPUモデルでの並列ソートアルゴリズムの計算量について | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | On Complexities of Parallel Sort Algorithms on AGPU model | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
国立情報学研究所 | ||||||||
著者所属 | ||||||||
国立情報学研究所 | ||||||||
著者所属 | ||||||||
国立情報学研究所 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
National Institure of Informatics | ||||||||
著者所属(英) | ||||||||
en | ||||||||
National Institure of Informatics | ||||||||
著者所属(英) | ||||||||
en | ||||||||
National Institure of Informatics | ||||||||
著者名 |
小池, 敦
定兼, 邦彦
Hoa, Vu
× 小池, 敦 定兼, 邦彦 Hoa, Vu
|
|||||||
著者名(英) |
Atsushi, Koike
Kunihiko, Sadakane
Hoa, Vu
× Atsushi, Koike Kunihiko, Sadakane Hoa, Vu
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 本稿ではAGPUモデルにおける並列ソートアルゴリズムの計算量を扱う.まず,既存のバイトニックソートとGPU-Warpsortの計算量を解析する.次に,AGPUモデルでの比較ソートのI/O計算量の下界を与える.1マルチプロセッサ内のコア数をb, 総コア数をp, マルチプロセッサ内の総共有メモリ量をMワードとすると,n要素の比較ソートに必要なグローバルメモリ読み込み回数はΩ(n/blog M/p n/b)である.さらに,I/O計算量がこの下界に一致するソートアルゴリズムを提案する.時間計算量はO(n/p log n/b log b) である. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | This paper is concerned with complexities of parallel sorting algorithms on AGPU model. First, we analyze known sort algorithms such as bitonic sort and GPU-Warpsort. Next, we give a lower bound of I/O complexities of comparison-based sorting algorithms on AGPU model. Let b be the number of cores in a multiprocessor, p be the total number of cores, and M be the total number of words in shared memories in multiprocessors. Then the necessary number of global memory accesses to comparison-sort n elements is shown to be Ω(n/b log M/p n/b). We also propose a sorting algorithm whose I/O complexity matches this lower bound. Its time complexity is O(n/p log n/b log b). | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
研究報告アルゴリズム(AL) 巻 2013-AL-144, 号 12, p. 1-6, 発行日 2013-05-10 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |