An efficient parallel strategy for high-cost prefix operation
Bahig, Hazem; Fathy, Khaled A.;
Abstract
The prefix computation strategy is a fundamental technique used to solve many problems in computer science such as sorting, clustering, and computer vision. A large number of parallel algorithms have been introduced that are based on a variety of high-performance systems. However, these algorithms do not consider the cost of the prefix computation operation. In this paper, we design a novel strategy for prefix computation to reduce the running time for high-cost operations such as multiplication. The proposed algorithm is based on (1) reducing the size of the partition and (2) keeping a fixed-size partition during all the steps of the computation. Experiments on a multicore system for different array sizes and number sizes demonstrate that the proposed parallel algorithm reduces the running time of the best-known optimal parallel algorithm in the average range of 62.7–79.6%. Moreover, the proposed algorithm has high speedup and is more scalable than those in previous works.
Other data
Title | An efficient parallel strategy for high-cost prefix operation | Authors | Bahig, Hazem ; Fathy, Khaled A. | Keywords | High-cost operation;Multicore;Parallel algorithm;Prefix computation | Issue Date | 1-Jun-2021 | Publisher | SPRINGER | Journal | Journal of Supercomputing | Volume | 77 | Start page | 5267 | End page | 5288 | ISSN | 09208542 | DOI | 10.1007/s11227-020-03473-x | Scopus ID | 2-s2.0-85095584679 | Web of science ID | WOS:000587110200004 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.