A fast GPU-based hybrid algorithm for addition chains

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%.