Parallelization of Implementations of Purely Sequential Algorithms
- Authors: Bugerya A.B.1, Kim E.S.2, Solovev M.A.2
-
Affiliations:
- Keldysh Institute of Applied Mathematics, Russian Academy of Sciences
- Ivannikov Institute for System Programming, Russian Academy of Sciences
- Issue: Vol 45, No 7 (2019)
- Pages: 381-389
- Section: Article
- URL: https://journals.rcsi.science/0361-7688/article/view/176938
- DOI: https://doi.org/10.1134/S0361768819070053
- ID: 176938
Cite item
Abstract
The work is dedicated to the parallelization of programs in especially difficult cases when the used algorithm is purely sequential, there are no parallel alternatives to this algorithm, and its execution time is unacceptably high. Various parallelization methods for software implementations of such algorithms and resulting computational load balancing are considered that make it possible to considerably accelerate the execution of application programs using purely sequential algorithms. The proposed methods are illustrated with examples of their application to two algorithms used in a dynamic binary code analysis toolset. The main goal of this paper is to show that the use of a purely sequential algorithm in a software implementation does not necessarily imply that its execution is inevitably sequential. The proposed methods of parallelizing implementations of such algorithms and balancing the resulting computational load can help develop efficient parallel programs that fully utilize the hardware capabilities of modern computers.
About the authors
A. B. Bugerya
Keldysh Institute of Applied Mathematics, Russian Academy of Sciences
Author for correspondence.
Email: shurabug@yandex.ru
Russian Federation, Moscow, 125047
E. S. Kim
Ivannikov Institute for System Programming, Russian Academy of Sciences
Author for correspondence.
Email: eugene.kim@ispras.ru
Russian Federation, Moscow, 109004
M. A. Solovev
Ivannikov Institute for System Programming, Russian Academy of Sciences
Author for correspondence.
Email: icee@ispras.ru
Russian Federation, Moscow, 109004