A novel parallel prefix sum algorithm and its implementation on multi-core platforms
Author:
- 1 April 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, V2-66
Abstract
This paper presents a novel parallel prefix sum algorithm on n numbers by p processors. A parallel time analysis shows that this proposed algorithm is more efficient and easy-scalable than Blelloch's classic parallel solution for the same problem. Unlike Blelloch's method, the proposed algorithm does not require the number p of processors to be a power of 2, and it needs no extra buffers apart from the array that holds the numbers. For practical considerations, a variant of the proposed algorithm is further developed which incurs less overhead due to thread management and synchronisation. The Blelloch's algorithm and the variant of the proposed method are implemented via POSIX Threads, and are tested on two multicore platforms. The results showed that the variant outperformed the Blelloch's method provided that the size of the array not exceeded the total capacity of the L2 cache of the host machine. In some of the tested cases, the increase in performance was as high as 50%.Keywords
This publication has 5 references indexed in Scilit:
- An efficient parallel prefix sums architecture with domino logicIEEE Transactions on Parallel and Distributed Systems, 2003
- Optimal deterministic approximate parallel prefix sums and their applications2002
- The parallel complexity of integer prefix summationInformation Processing Letters, 1995
- Faster optimal parallel prefix sums and list rankingInformation and Computation, 1989
- Data parallel algorithmsCommunications of the ACM, 1986