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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1007/s11227-020-03473-x | The Journal of Supercomputing |
Keywords | DocType | Volume |
Prefix computation, Parallel algorithm, High-cost operation, Multicore | Journal | 77 |
Issue | ISSN | Citations |
6 | 0920-8542 | 0 |
PageRank | References | Authors |
0.34 | 14 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hazem M. Bahig | 1 | 24 | 7.61 |
Khaled A. Fathy | 2 | 0 | 0.34 |