Imperial College London
Portrait Picture

Dr Lluis Vilanova

Faculty of Engineering, Department of Computing

Senior Lecturer
 
 
 
//

Contact

 

+44 (0)20 7594 8328vilanova Website

 
 
//

Location

 

556Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Tanasic:2013:10.1145/2458523.2458524,
author = {Tanasic, I and Vilanova, L and Jordà, M and Cabezas, J and Gelado, I and Navarro, N and Hwu, WM},
doi = {10.1145/2458523.2458524},
pages = {1--11},
title = {Comparison based sorting for systems with multiple GPUs},
url = {http://dx.doi.org/10.1145/2458523.2458524},
year = {2013}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - As a basic building block of many applications, sorting algorithms that efficiently run on modern machines are key for the performance of these applications. With the recent shift to using GPUs for general purpose compuing, researches have proposed several sorting algorithms for single-GPU systems. However, some workstations and HPC systems have multiple GPUs, and applications running on them are de- signed to use all available GPUs in the system. In this paper we present a high performance multi-GPU merge sort algorithm that solves the problem of sorting data distributed across several GPUs. Our merge sort algorithm first sorts the data on each GPU using an existing single- GPU sorting algorithm. Then, a series of merge steps pro- duce a globally sorted array distributed across all the GPUs in the system. This merge phase is enabled by a novel pivot selection algorithm that ensures that merge steps always distribute data evenly among all GPUs. We also present the implementation of our sorting algorithm in CUDA, as well as a novel inter-GPU communication technique that enables this pivot selection algorithm. Experimental results show that an efficient implementation of our algorithm achieves a speed up of 1.9x when running on two GPUs and 3.3x when running on four GPUs, compared to sorting on a single GPU. At the same time, it is able to sort two and four times more records, compared to sorting on one GPU. Copyright 2013 ACM.
AU  - Tanasic,I
AU  - Vilanova,L
AU  - Jordà,M
AU  - Cabezas,J
AU  - Gelado,I
AU  - Navarro,N
AU  - Hwu,WM
DO  - 10.1145/2458523.2458524
EP  - 11
PY  - 2013///
SP  - 1
TI  - Comparison based sorting for systems with multiple GPUs
UR  - http://dx.doi.org/10.1145/2458523.2458524
ER  -
Download