Top

Cluster Computing

Published in:

31-08-2018

A fast GPU-based hybrid algorithm for addition chains

Authors: Hatem M. Bahig, Khaled A. AbdElbari

Published in: Cluster Computing | Issue 4/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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

previous article Migration cost and profit oriented cloud federation formation: hedonic coalition game based approach

next article Towards operational cost minimization for cloud bursting with deadline constraints in hybrid clouds

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Campeotto, F., Dovier, A., Fioretto, F., Pontelli. E.: A GPU implementation of large neighborhood search for solving constraint optimization problems. In: Proceedings of the European Conference on Artificial Intelligence (ECAI). pp. 189–194 (2014)

Hawick, K., Leist, A., Playne, D.: Parallel graph component labelling with gpus and cuda. Parallel Comput. 36(12), 655–678 (2010)CrossRef

Harish, P., Narayanan, P.J.: Accelerating large graph algorithms on the GPU using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) High Performance Computing-HIPC. Lecture Notes in Computer Science, pp. 197–208. Springer, New York (2007)

Chen, C., Schmidt, B., Weiguo, L., Muller-Wittig, W.: GPU-MEME: Using graphics hardware to accelerate motif finding in DNA sequences. Pattern Recognition in Bioinformatics, Third IAPR International Conference, PRIB, Melbourne. Lecture Notes in Computer Science, Springer. pp. 52–65 (2008)

Zhou, Y., Xu, W., Donald, B.R., Zeng, J.: An efficient parallel algorithm for accelerating computational protein design. Bioinformatics 30(12), 255–263 (2014)CrossRef

Biryukov, A., Großschädl, J.: Cryptanalysis of the full AES using GPU-like special-purpose hardware. Fundam. Inform. 114, 221–237 (2012)MathSciNetMATH

Pan, W., Zheng, F., Zhao, Y., Zhu, W.T., Jing, J.: An efficient elliptic curve cryptography signature server with GPU acceleration. IEEE Trans. Inform. Forensics Secur. 12(1), 111–122 (2017)CrossRef

Milob, F., Bernaschia, M., Bissonb, M.: A fast, GPU based, dictionary attack to openPGP secret keyrings. J. Syst. Softw. 84, 2088–2096 (2011)CrossRef

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inform. Theory 22(6), 644–654 (1976)MathSciNetCrossRef

10.

ElGamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory 31, 469–472 (1985)MathSciNetCrossRef

11.

Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM. 21(2), 120–126 (1978)MathSciNetCrossRef

12.

Takagi, T.: Fast RSA-type cryptosystem modulo \(p^k q.\) In: Advances in Cryptology—CRYPTO'98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998. Lecture Notes in Computer Science, vol. 1462, pp. 318–326 (1998)

13.

Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) Advances in Cryptology—EUROCRYPT’92, Workshop on the Theory and Application of Cryptographic Techniques, Balatonfured, Hungary, May 24-28, 1992. Lecture Notes in Computer Science, vol. 658, pp. 200–207. Springer, New York (1992)

14.

Bos, J., Coster, M.: Addition chain heuristics. In: Brassard, G. (ed.) Advances in Cryptology—CRYPTO’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989. Lecture Notes in Computer Science, vol. 435, pp. 400–407. Springer, New York (1989)

15.

De Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: Helleseth, T. (ed.) Advances in Cryptology—EUROCRYPT’94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994. Lecture Notes in Computer Science, vol. 950, pp. 389–399. Springer, New York (1994)

16.

Gordon, D.M.: A survey of fast exponentiation methods. J. Algorithms 122, 129–146 (1998)MathSciNetCrossRef

17.

Fathy, K., Bahig, H., Ragab, A.: A fast parallel modular exponentiation algorithm. Arab. J. Sci. Eng. 43, 903–911 (2018)CrossRef

18.

Bahig, H.: A fast optimal parallel algorithm for a short addition chain. J. Supercomput. 74(1), 324–333 (2018)CrossRef

19.

Downey, P., Leong, B., Sethi, R.: Computing sequences with addition chains. SIAM J. Comput. 10(3), 638–646 (1981)MathSciNetCrossRef

20.

Bahig, H., Bahig, H.: A new strategy for generating shortest addition sequences. Computing 91, 285–306 (2011)MathSciNetCrossRef

21.

Knuth, D.E.: Art of Computer Programming, Volume 2: Seminumerical Algorithm, pp. 461–485. Addison-Wesley, Reading (1997)

22.

Bleichenbacher, D., Flammenkamp, A.: An efficient algorithm for computing shortest addition chains. http://www.homes.uni-bielefeld.de/achim/additionchain.html (unpublished)

23.

Chin, Y.H., Tsai, Y.H.: Algorithms for finding the shortest addition chain. In: Proceedings of national computer symposium, Kaoshiung, Taiwan. December 20–22, pp. 1398–1414 (1985)

24.

Thurber, E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28, 1247–1263 (1999)MathSciNetCrossRef

25.

Bahig, H.: Improved generation of minimal addition chains. Computing 78, 161–172 (2006)MathSciNetCrossRef

26.

Bahig, H.: Star reduction among minimal length addition chains. Computing 91, 335–352 (2011)MathSciNetCrossRef

27.

Clift, N.M.: Calculating optimal addition chains. Computing 91(3), 265–284 (2011)MathSciNetCrossRef

28.

Schnhage, A.: A lower bound for the length of addition chains. Theor. Comput. Sci. 1, 1–12 (1975)MathSciNetCrossRef

29.

Thurber, E.G.: The Scholz–Brauer problem on addition chains. Pac. J. Math. 49, 229–242 (1973)MathSciNetCrossRef

30.

NVIDIA. NVIDIA CUDA C Programming Guide, CUDA Toolkit Documentation

31.

Mahafzah, B., Mohammad, A.: The optical chained-cubic tree interconnection network: topological structure and properties. Comput. Electr. Eng. 38(2), 330–345 (2012)CrossRef

32.

Mahafzah, B., Sleit, A.: The OTIS hyper hexa-cell optoelectronic architecture. Computing 94(5), 411–432 (2012)MathSciNetCrossRef

33.

Mahafzah, B.: Performance evaluation of parallel multithreaded A* heuristic search algorithm. J. Inform. Sci 40(3), 363–375 (2014)CrossRef

34.

Mahafzah, B.: Parallel multithreaded IDA* heuristic search: algorithm design and performance evaluation. Int. J. Parallel Emerg. Distrib Syst. 26(1), 61–82 (2011)MathSciNetCrossRef

Title: A fast GPU-based hybrid algorithm for addition chains
Authors: Hatem M. Bahig
Khaled A. AbdElbari
Publication date: 31-08-2018
Publisher: Springer US
Published in: Cluster Computing / Issue 4/2018
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-018-2840-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2018

An implementation of matrix–matrix multiplication on the Intel KNL processor with AVX-512

Planning of distributed data production for High Energy and Nuclear Physics

Towards operational cost minimization for cloud bursting with deadline constraints in hybrid clouds

A novel task scheduling approach based on dynamic queues and hybrid meta-heuristic algorithms for cloud computing environment

A self-scalable distributed network simulation environment based on cloud computing

Migration cost and profit oriented cloud federation formation: hedonic coalition game based approach

Premium Partner