TY - JOUR

T1 - Анализ исполнения фрагментированных программ на основе факторов SLOW

AU - Киреев, Сергей Евгеньевич

N1 - Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН FWNM-2022-0005. Киреев, С. Е. Анализ исполнения фрагментированных программ на основе факторов SLOW / С. Е. Киреев, В. С. Литвинов // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. – 2024. – Т. 13, № 2. – С. 77-96. – DOI 10.14529/cmse240205.

PY - 2024

Y1 - 2024

N2 - При исполнении параллельных программ, основанных на парадигме параллелизма задач, требуется решать ряд проблем, таких как выбор порядка запуска задач с учетом зависимостей между ними, распределение данных и задач по параллельным процессам, балансировка нагрузки на ресурсы. Эти проблемы относятся к области системного параллельного программирования, и их решение, как правило, обеспечивается специальной исполнительной системой. От качества решения этих проблем, а также от структуры и свойств прикладного алгоритма, лежащего в основе параллельной программы, зависит получаемая производительность. Если производительность программы недостаточна, то требуется ее оптимизация, а для этого нужно знать те причины («узкие места»), которые ограничивают ее производительность. Для определения узких мест программы обычно применяется профилирование, т.е. сбор некоторых характеристик исполнения, которые могут указать на источник проблемы. Однако обычные широко используемые средства профилирования параллельных программ не позволяют дать ответ в требуемых понятиях из-за сложности анализа асинхронного исполнения множества задач, а также из-за неспособности выделить в исполняющейся программе прикладную (множество задач) и системную (исполнительная система) компоненты. Поэтому для таких программ требуется разработка новых методов профилирования и анализа. В статье рассматривается проблема получения «понятных» характеристик выполнения параллельных программ на основе параллелизма задач для анализа производительности и оптимизации. Предлагается количественно оценить степень влияния следующих факторов: нехватка работы (Starvation), передача данных (Latency), накладные расходы (Overhead) и конфликт при доступе к общим ресурсам (Waiting for contention resolution). Представлен алгоритм получения соответствующих характеристик для системы фрагментированного программирования LuNA, а также способ их анализа для оптимизации LuNA-программ. Корректность подхода продемонстрирована на ряде синтетических экспериментов. Показано применение подхода к анализу «реальной» программы численного моделирования.

AB - При исполнении параллельных программ, основанных на парадигме параллелизма задач, требуется решать ряд проблем, таких как выбор порядка запуска задач с учетом зависимостей между ними, распределение данных и задач по параллельным процессам, балансировка нагрузки на ресурсы. Эти проблемы относятся к области системного параллельного программирования, и их решение, как правило, обеспечивается специальной исполнительной системой. От качества решения этих проблем, а также от структуры и свойств прикладного алгоритма, лежащего в основе параллельной программы, зависит получаемая производительность. Если производительность программы недостаточна, то требуется ее оптимизация, а для этого нужно знать те причины («узкие места»), которые ограничивают ее производительность. Для определения узких мест программы обычно применяется профилирование, т.е. сбор некоторых характеристик исполнения, которые могут указать на источник проблемы. Однако обычные широко используемые средства профилирования параллельных программ не позволяют дать ответ в требуемых понятиях из-за сложности анализа асинхронного исполнения множества задач, а также из-за неспособности выделить в исполняющейся программе прикладную (множество задач) и системную (исполнительная система) компоненты. Поэтому для таких программ требуется разработка новых методов профилирования и анализа. В статье рассматривается проблема получения «понятных» характеристик выполнения параллельных программ на основе параллелизма задач для анализа производительности и оптимизации. Предлагается количественно оценить степень влияния следующих факторов: нехватка работы (Starvation), передача данных (Latency), накладные расходы (Overhead) и конфликт при доступе к общим ресурсам (Waiting for contention resolution). Представлен алгоритм получения соответствующих характеристик для системы фрагментированного программирования LuNA, а также способ их анализа для оптимизации LuNA-программ. Корректность подхода продемонстрирована на ряде синтетических экспериментов. Показано применение подхода к анализу «реальной» программы численного моделирования.

KW - Анализ производительности

KW - параллельное программирование

KW - ФРАГМЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ

KW - Параллелизм задач

KW - СИСТЕМА LUNA

KW - PERFORMANCE ANALYSIS

KW - Parallel programming

KW - Fragmented programming

KW - TASK PARALLELISM

KW - LUNA SYSTEM

UR - https://www.mendeley.com/catalogue/17ea76c7-493f-3d59-b448-a425a5f3cf69/

U2 - 10.14529/cmse240205

DO - 10.14529/cmse240205

M3 - статья

VL - 13

SP - 77

EP - 96

JO - Bulletin of the South Ural State University. Series "Computational Mathematics and Software Engineering"

JF - Bulletin of the South Ural State University. Series "Computational Mathematics and Software Engineering"

SN - 2305-9052

IS - 2

ER -