Back to Search
Start Over
A fast GPU-based hybrid algorithm for addition chains.
- Source :
-
Cluster Computing . Dec2018, Vol. 21 Issue 4, p2001-2011. 11p. - Publication Year :
- 2018
-
Abstract
- A graphics processing unit (GPU) has been widely used to accelerate discrete optimization problems. In this paper, we introduce a novel hybrid parallel algorithm to generate a shortest addition chain for a positive integer e. The main idea of the proposed algorithm is to divide the search tree into a sequence of three subtrees: top, middle, and bottom. The top subtree works using a branch and bound depth first strategy. The middle subtree works using a branch and bound breadth first strategy, while the bottom subtree works using a parallel (GPU) branch and bound depth first strategy. Our experimental results show that, compared to the fastest sequential algorithm for generating a shortest addition chain, we improve the generation by about 70% using one GPU (NVIDIA GeForce GTX 770). For generating all shortest addition chains, the percentage of the improvement is about 50%. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13867857
- Volume :
- 21
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Cluster Computing
- Publication Type :
- Academic Journal
- Accession number :
- 132697545
- Full Text :
- https://doi.org/10.1007/s10586-018-2840-5