Premium
Fast and scalable algorithm for product large data on multicore system
Author(s) -
Bahig Hazem M.,
Bahig Hatem M.,
Fathy Khaled A.
Publication year - 2019
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.5259
Subject(s) - scalability , computer science , algorithm , multiplier (economics) , parallel algorithm , parallel computing , multi core processor , freivalds' algorithm , theoretical computer science , dijkstra's algorithm , graph , database , shortest path problem , economics , macroeconomics
Summary The problem of designing efficient parallel algorithms to calculate the product of n numbers when the multipliers are large is a fundamental problem in many applications of computer science such as cryptography. In this work, we present a new parallel algorithm on exclusive read shared memory model. The performance of the introduced algorithm is measured based on three factors, namely, (1) the number of cores, (2) the size of the array, and (3) the size of the multiplier. The experimental study on a multi core system reveals that the introduced algorithm is faster than the best‐known optimal parallel algorithm. The improvement of the proposed algorithm in processing time compared to the best known parallel algorithm is 80 % when the size of the array was 2 20 and the sizes of the multiplier were 1024, 2048, and 4096 bits. Moreover, our algorithm is a highly scalable parallel algorithm compared with the best‐known optimal parallel algorithm.