AGPUモデルでの並列ソートアルゴリズムの計算量について

• 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
• 著者名(英): 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
• 書誌レコードID / 収録物識別子: 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
• 出版者: 情報処理学会