Presentation	2013-05-17 On Complexities of Parallel Sort Algorithms on AGPU model Atsushi KOIKE, Kunihiko SADAKANE, Hoa VU,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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_ 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).
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	GPGPU / AGPU model / sorting / bitonic sort
Paper #	COMP2013-13
Date of Issue

Conference Information
Committee	COMP
Conference Date	2013/5/10(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On Complexities of Parallel Sort Algorithms on AGPU model
Sub Title (in English)
Keyword(1)	GPGPU
Keyword(2)	AGPU model
Keyword(3)	sorting
Keyword(4)	bitonic sort
1st Author's Name	Atsushi KOIKE
1st Author's Affiliation	National Institure of Informatics()
2nd Author's Name	Kunihiko SADAKANE
2nd Author's Affiliation	National Institure of Informatics
3rd Author's Name	Hoa VU
3rd Author's Affiliation	National Institure of Informatics
Date	2013-05-17
Paper #	COMP2013-13
Volume (vol)	vol.113
Number (no)	50
Page	pp.pp.-
#Pages	6
Date of Issue