GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management

The authors present a new algorithm, GPUTeraSort, to sort billion-record wide-key databases using a Graphics Processing Unit (GPU). Their algorithm uses the data and task parallelism on the GPU to perform memory-intensive and compute-intensive tasks while the CPU is used to perform I/O and resource management. They therefore exploit both the high-bandwidth GPU memory interface and the lower-bandwidth CPU main memory interface and achieve higher memory bandwidth than purely CPU-based algorithms. GPUTera-Sort is a two-phase task pipeline: read disk, build keys, sort using the GPU, generate runs, write disk; and read, merge, write.