Распараллеливание реализаций сугубо последовательных алгоритмов
Автор: Бугеря А.Б., Ким Е.С., Соловьев М.А.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 2 т.30, 2018 года.
Бесплатный доступ
Работа посвящена теме распараллеливания программ в особо сложных случаях - когда используемый алгоритм является сугубо последовательным, параллельных альтернатив используемому алгоритму нет, а время его выполнения неприемлемо велико. Рассматриваются различные методы распараллеливания программных реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки, позволяющие получить значительное ускорение выполнения прикладных программ, в которых используются сугубо последовательные алгоритмы. Приведенные методы иллюстрируются практикой их применения к двум алгоритмам, используемым в среде динамического анализа программ. Основная цель данной работы - показать, что использование в программной реализации сугубо последовательного алгоритма не означает неизбежность его последовательного выполнения. Предложенные методы распараллеливания реализаций таких алгоритмов и балансировки получающейся вычислительной нагрузки могут способствовать созданию эффективной параллельной программы, полностью использующей предоставленные ей аппаратные возможности современных вычислительных систем.
Параллельное программирование, распараллеливание программ, балансировка вычислительной нагрузки
Короткий адрес: https://sciup.org/14916523
IDR: 14916523 | DOI: 10.15514/ISPRAS-2018-30(2)-2
Parallelization of implementations of purely sequential algorithms
The work is dedicated to the topic of parallelizing programs in especially difficult cases - when the used algorithm is purely sequential, there are no parallel alternatives to the algorithm used, and its execution time is unacceptably high. Various parallelization methods for software implementations of such algorithms and resulting computational load balancing are considered, allowing to obtain significant performance acceleration for application programs using purely sequential algorithms. The above methods are illustrated by the practice 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 inevitability of its sequential execution. The proposed methods of parallelizing implementations of such algorithms and balancing the resulting computational load can help to develop efficient parallel program that fully utilize the hardware capabilities of modern computing systems.
Список литературы Распараллеливание реализаций сугубо последовательных алгоритмов
- V.A. Padaryan, A.I. Getman, M.A. Solovyev, M.G. Bakulin, A.I. Borzilov, V.V. Kaushan, I.N. Ledovskich, U.V. Markin, S.S. Panasenko. Methods and software tools for combined binary code analysis. Trudy ISP RAN/Proc. ISP RAS, 2014, vol. 26, issue 1, pp. 251-276 DOI: 10.15514/ISPRAS-2014-26(1)-8
- V.A. Padaryan. On representation used in the binary code reverse engineering. Trudy ISP RАN/Proc. ISP RAS, 2017, vol. 29, issue 3, pp. 31-42 DOI: 10.15514/ISPRAS-2017-29(3)-3
- Alexander Getman, Vartan Padaryan, Mikhail Solovyev. Combined approach to solving problems in binary code analysis. Proceedings of the 9th International Conference on Computer Science and Information Technologies (CSIT), 2013, pp. 295-297.
