CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Counting and Occurrence Sort for GPUs using an Embedded Language

Josef Svenningsson (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)) ; Joel Svensson (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)) ; Mary Sheeran (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
The 2nd ACM SIGPLAN Workshop on Functional High-Performance Computing, FHPC'13 Vol. 48 (2013), 12, p. 37-45.
[Konferensbidrag, refereegranskat]

This paper investigates two sorting algorithms: counting sort and a variation, occurrence sort, which also removes duplicate elements, and examines their suitability for running on the GPU. The dupli- cate removing variation turns out to have a natural functional, data- parallel implementation which makes it particularly interesting for GPUs. The algorithms are implemented in Obsidian, a high-level do- main specific language for GPU programming. Measurements show that our implementations in many cases outperform the sorting algorithm provided by the library Thrust. Furthermore, occurrence sort is another factor of two faster than ordinary counting sort. We conclude that counting sort is an impor- tant contender when considering sorting algorithms for the GPU, and that occurrence sort is highly preferable when applicable. We also show that Obsidian can produce very competitive code.

Nyckelord: Sorting, Embedded language



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-08-27. Senast ändrad 2015-09-21.
CPL Pubid: 182284

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)

Ämnesområden

Informations- och kommunikationsteknik
Programvaruteknik

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Embedded Languages for Data-Parallel Programming