A Novel Parallel Scan for Multicore Processors and Its Application in Sparse Matrix-Vector Multiplication
Author:
- 16 June 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 23 (3) , 397-404
Abstract
We present a novel parallel algorithm for computing the scan operations on x86 multicore processors. The existing best known parallel scan for the same platform requires the number of processors to be a power of two. But this constraint is removed from our proposed method. In the design of the algorithm architectural considerations for x86 multicore processors are given so that the rate of cache misses is reduced and the cost of thread synchronization and management is minimized. Results from tests made on a machine with dual-socket \times quad-core Intel Xeon E5405 showed that the proposed solution outperformed the best known parallel reference. A novel approach to sparse matrix-vector multiplication (SpMV) based on the proposed scan is then explained. The approach, unlike the existing ones that make use of backward segmented operations, uses forward ones for more efficient caching. An implementation of the proposed SpMV was tested against the SpMV in Intel's Math Kernel Library (MKL) and merits were found in the proposed approach.Keywords
This publication has 10 references indexed in Scilit:
- Parallel symmetric sparse matrix–vector product on scalar multi-core CPUsParallel Computing, 2010
- A novel parallel prefix sum algorithm and its implementation on multi-core platforms2010
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- The Connection Machine2007
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Implementation of a Portable Nested Data-Parallel LanguageJournal of Parallel and Distributed Computing, 1994
- Scans as primitive parallel operationsIEEE Transactions on Computers, 1989
- Data parallel algorithmsCommunications of the ACM, 1986
- UltracomputersACM Transactions on Programming Languages and Systems, 1980
- A programming language1962