Paper 2012/482

Approaches for the Parallelization of Software Implementation of Integer Multiplication

Vladislav Kovtun and Andrew Okhrimenko

Abstract

In this paper there are considered several approaches for the increasing performance of software implementation of integer multiplication algorithm for the 32-bit & 64-bit platforms via parallelization. The main idea of algorithm parallelization consists in delayed carry mechanism using which authors have proposed earlier [11]. The delayed carry allows to get rid of connectivity in loop iterations for sums accumulation of products, which allows parallel execution of loops iterations in separate threads. Upon completion of sum accumulation threads, it is necessary to make corrections in final result via assimilation of carries. First approach consists in optimization of parallelization for the two execution threads and second approach is an evolution of the first approach and is oriented on three and more execution threads. Proposed approaches for parallelization allow increasing the total algorithm computational complexity, as for one execution thread, but decrease total execution time on multi-core CPU.

Note: Changed formating of the table.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
multiplicationintegersparallelizationOpenMPsoftware implementationcryptographic transformationspublic key cryptosystem
Contact author(s)
vladislav kovtun @ gmail com
History
2012-08-22: revised
2012-08-21: received
See all versions
Short URL
https://ia.cr/2012/482
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/482,
      author = {Vladislav Kovtun and Andrew Okhrimenko},
      title = {Approaches for the Parallelization of Software Implementation of Integer Multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2012/482},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/482}},
      url = {https://eprint.iacr.org/2012/482}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.