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 × 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.
Original language | English |
---|---|
Article number | 5887318 |
Pages (from-to) | 397-404 |
Number of pages | 8 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Volume | 23 |
Issue number | 3 |
DOIs | |
Publication status | Published - Mar 2012 |
Keywords
- Multicore computing
- Parallel algorithms
- Parallel scan
- Prefix sum
- Sparse matrix-vector multiplication