Parallelization of Implementations of Purely Sequential Algorithms
- Авторы: Bugerya A.1, Kim E.2, Solovev M.2
-
Учреждения:
- Keldysh Institute of Applied Mathematics, Russian Academy of Sciences
- Ivannikov Institute for System Programming, Russian Academy of Sciences
- Выпуск: Том 45, № 7 (2019)
- Страницы: 381-389
- Раздел: Article
- URL: https://journals.rcsi.science/0361-7688/article/view/176938
- DOI: https://doi.org/10.1134/S0361768819070053
- ID: 176938
Цитировать
Аннотация
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.
Об авторах
A. Bugerya
Keldysh Institute of Applied Mathematics, Russian Academy of Sciences
Автор, ответственный за переписку.
Email: shurabug@yandex.ru
Россия, Moscow, 125047
E. Kim
Ivannikov Institute for System Programming, Russian Academy of Sciences
Автор, ответственный за переписку.
Email: eugene.kim@ispras.ru
Россия, Moscow, 109004
M. Solovev
Ivannikov Institute for System Programming, Russian Academy of Sciences
Автор, ответственный за переписку.
Email: icee@ispras.ru
Россия, Moscow, 109004