Contact at mumbai.academics@gmail.com or 8097636691
Responsive Ads Here

Friday, 23 February 2018

A Novel Parallel Scan for Multicore Processors and Its Application in Sparse Matrix-Vector Multiplication(2012)



A Novel Parallel Scan for Multicore

 Processors and Its Application in Sparse 

Matrix-Vector Multiplication(2012)

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.
Existing Method :
First, those algorithms for supercomputers and for many-core GPUs often assume unlimited number of processors. But the same assumption cannot be made by a scan algorithm for multicore processors. On x86 multicore processors, the performance of an application is often determined by the efficiency of caching or/and memory bandwidth. The concerns for designing algorithms on multicore processors are very different from those when working with supercomputers. Second, the current best known parallel scan algorithm “Prefix Sums and Their Applications,” for the same platform works only when the number of processors is a power of two, because it needs to compute a balanced binary tree over the input. But as the introduction of Intel’s and AMD’s hex-core processors, a scan algorithm without this constraint will be more desirable.
Proposed Method :
The parallel scan proposed in this paper works on any number of processors. Parallelization is achieved through concurrent running threads. Its implementation was tested on a machine with dual-socket _ quad-core Intel Xeon E5405 (Harpertown) at 2.0 GHz, and the proposed method was found outperforming the current best known parallel reference. Based on this proposed scan, we then designed a novel approach to sparse matrix-vector multiplication. The existing scan-based solutions [12], [13] to SpMV use backward segmented operations, whose access patterns will cause inefficiencies for x86 caches. But the SpMV we designed use forward segmented sum and scan, which will result in a more efficient caching. The SpMV was implemented and compared with the general SpMV in Intel’s Math Kernel Library (MKL) 10.1 for Linux, and merits were found in our method.
Modules :
1) User Interface
2) Processor Module
3) Pre sum
HARDWARE REQUIREMENTS
ü Processor             -Pentium –III
ü Speed                             -    1.1 Ghz
ü RAM                    -    256 MB(min)
ü Hard Disk            -   20 GB
ü Floppy Drive       -    1.44 MB
ü Key Board            -    Standard Windows Keyboard
ü Mouse                  -    Two or Three Button Mouse
ü Monitor                -    SVGA
SOFTWARE REQUIREMENTS
v   Operating System          : Windows95/98/2000/XP
v   Application  Server       : Tomcat5.0/6.X
v   Front End                      : Java, JSP
v    Script                            : JavaScript.
v   Server side Script          : Java Server Pages.
v   Database                        : Oracle

No comments:

Post a Comment