A fast GPU-based hybrid algorithm for addition chains
Bahig, Hatem M.; AbdElbari, Khaled A.;
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%.
Other data
Title | A fast GPU-based hybrid algorithm for addition chains | Authors | Bahig, Hatem M. ; AbdElbari, Khaled A. | Keywords | Addition chain;Branch and bound;Breadth first strategy;CUDA;Depth first strategy;GPU | Issue Date | 1-Dec-2018 | Publisher | SPRINGER | Journal | Cluster Computing | Volume | 21 | Start page | 2001 | End page | 2011 | ISSN | 13867857 | DOI | 10.1007/s10586-018-2840-5 | Scopus ID | 2-s2.0-85053422276 | Web of science ID | WOS:000457276800015 |
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.