Premium
Parallel space saving on multi‐ and many‐core processors
Author(s) -
Cafaro Massimo,
Pulimeno Marco,
Epicoco Italo,
Aloisio Giovanni
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4160
Subject(s) - parallel computing , computer science , xeon , xeon phi , multi core processor , space (punctuation) , core (optical fiber) , many core , shared memory , out of core algorithm , value (mathematics) , element (criminal law) , operating system , telecommunications , machine learning , political science , law
Summary Given an array A of n elements and a value 2≤ k ≤ n , a frequent item or k ‐majority element is an element occurring in A more than n / k times. The k ‐majority problem requires finding all of the k ‐majority elements. In this paper, we deal with parallel shared‐memory algorithms for frequent items; we present a shared‐memory version of the Space Saving algorithm, and we study its behavior with regard to accuracy and performance on many and multi‐core processors, including the Intel Phi accelerator. We also investigate a hybrid MPI/OpenMP version against a pure MPI‐based version. Through extensive experimental results, we prove that the MPI/OpenMP parallel version of the algorithm significantly enhances the performance of the earlier pure MPI version of the same algorithm. Results also prove that for this algorithm the Intel Phi accelerator does not introduce any improvement with respect to the Xeon octa–core processor.