A novel parallel scan for multicore processors and its application in sparse matrix-vector multiplication

Nan Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

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 languageEnglish
Article number5887318
Pages (from-to)397-404
Number of pages8
JournalIEEE Transactions on Parallel and Distributed Systems
Volume23
Issue number3
DOIs
Publication statusPublished - Mar 2012

Keywords

  • Multicore computing
  • Parallel algorithms
  • Parallel scan
  • Prefix sum
  • Sparse matrix-vector multiplication

Fingerprint

Dive into the research topics of 'A novel parallel scan for multicore processors and its application in sparse matrix-vector multiplication'. Together they form a unique fingerprint.

Cite this