@techreport{oai:ipsj.ixsq.nii.ac.jp:00091775,
 author = {小池, 敦 and 定兼, 邦彦 and Hoa, Vu and Atsushi, Koike and Kunihiko, Sadakane and Hoa, Vu},
 issue = {12},
 month = {May},
 note = {本稿では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) である．, 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).},
 title = {AGPUモデルでの並列ソートアルゴリズムの計算量について},
 year = {2013}
}