Istituto di Scienza e Tecnologie dell'Informazione     
Capannini G. Designing Efficient Parallel Prefix Sum Algorithms for GPUs. In: CIT 2011 - IEEE 11th International Conference on Computer and Information Technology (Pafos, Cyprus, 31 August - 2 September 2011). Proceedings, pp. 189 - 196. IEEE, 2011.
This paper presents a novel and efficient method to compute one of the simplest and most useful building block for parallel algorithms: the parallel prefix sum operation. Besides its practical relevance, the problem achieves further interest in parallel-computation theory. We firstly describe step-by-step how parallel prefix sum is performed in parallel on GPUs. Next we propose a more efficient technique properly developed for modern graphics processors and alike processors. Our technique is able to perform the computation in such a way that minimizes both memory conflicts and memory usage. Finally we evaluate theoretically and empirically all the considered solutions in terms of efficiency, space complexity, and computational time. In order to properly conduct the theoretical analysis we used a novel computational model proposed by us in a previous work: K-model. Concerning the experiments, the results show that the proposed solution obtains better performance than the existing ones.
URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6036747
DOI: 10.1109/CIT.2011.11
Subject GPGPU
algorithms performance

Icona documento 1) Download Document PDF
Icona documento 2) 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