Istituto di Scienza e Tecnologie dell'Informazione     
Capannini G., Baraglia R., Nardini F. M., Silvestri F. Sorting using BItonic netwoRk wIth CUDA. In: LSDS-IR '09 - 7th Workshop on Large-Scale Distributed Systems for Information Retrieval (Boston, 19-23 July 2009). Proceedings, pp. 33 - 40. Claudio Lucchese, Gleb Skobeltsyn, Wai Gen Yee (eds.). LSDS-IR, 2009.
Novel"manycore" architectures, such as graphics processors, are high-parallel and high-performance shared-memory architectures [7] born to solve specific problems such as the graphical ones. Those architectures can be exploited to solve a wider range of problems by designing the related algorithm for such architectures. We present a fast sorting algorithm implementing an efficient bitonic sorting network. This algorithm is highly suitable for information retrieval applications. Sorting is a fundamental and universal problem in computer science. Even if sort has been extensively addressed by many research works, it still remains an interesting challenge to make it faster by exploiting novel technologies. In this light, this paper shows how to use graphics processors as coprocessors to speed up sorting while allowing CPU to perform other tasks. Our new algorithm exploits a memory-efficient data access pattern maintaining the minimum number of accesses to the memory out of the chip. We introduce an efficient instruction dispatch mechanism to improve the overall sorting performance. We also present a cache-based computational model for graphics processors. Experimental results highlight remarkable improvements over prior CPU-based sorting methods, and a significant improvement over previous GPU-based sorting algorithms.
URL: http://lsdsir09.isti.cnr.it/LSDSIR09.pdf
Subject Multicore
Parallel computing
I.3.1 Parallel processing

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional