Параллельное программирование для ресурсоёмких задач численного моделирования в физике В.О. Милицин, Д.Н. Янышев, И.А. Буткарев Центр компьютерной физики Кафедра общей физики и волновых процессов Международный лазерный центр

2

Содержание лекции n Общие рекомендации по программированию с OpenMP n Общие принципы сеточных методов

Зависимость по данным Для эффективного распараллеливания необходимо обеспечить независимость по данным между петлями (итерациями) циклов операторов do/for Если зависимости по данным между петлями циклов отсутствуют, то они называются независимыми по данным Часто зависимости по данным между петлями циклов могут быть исключены с помощью модификации алгоритмов Пример рекурсии с зависимостью по данным Элементарное распараллеливание

Зависимость по данным Reduction Распараллеливание осуществляется с помощью применения конструкции reduction к циклу do

Зависимость по данным Циклы с условными выходами не распараллеливаются Вложенные циклы: в следующем примере Распараллеливание возможно только на самом верхнем уровне по k

Проблемы отладки OpenMP программ: условия состязательности (race conditions) При работе программ с общей памятью возникает ряд специфических ошибок, одна из которых связана с так называемыми условиями состязательности (race conditions) Эти ошибки состоят в непредсказуемом времени завершении параллельных потоков и возникновении в результате этого непредсказуемых результатов вычислений Пример Результат в этом примере зависит от того как и в какой последовательности выполняются параллельные потоки

Проблемы отладки OpenMP программ: мертвая блокировка (deadlock) В процессе выполнения программ с общей памятью возможна ситуация, когда поток ожидает освобождения доступа к объекту, который никогда не будет открыт В следующем примере видно, что такая ситуация возникает, когда объект А заблокирован в одном потоке, а объект В в другом В случае, если оба объекта заблокированы в одном потоке, то возникает условие состязательности Пример

Проблемы отладки OpenMP программ: некоторые дополнительные опасные ситуации Используемые в программах библиотеки должны быть безопасны с точки зрения потокового выполнения. Стандартные библиотеки всегда удовлетворяют этому требованию Следует иметь ввиду, что операции ввода/вывода в параллельных потоках завершаются в непредсказуемом порядке Следует внимательно прослеживать пересечение в параллельных потоках переменных типа private с глобальными переменными Следует тщательно отслеживать однозначность значений переменных в общей памяти. Для этого при необходимости следует пользоваться функцией FLUSH Следует помнить, что предложение NOWAIT удаляет неявные барьеры (barriers) Средства отладки OpenMP программ: Intel Thread Checker и Intel VTune Performance Analyzer (работает под Windows и Linux и позволяет вести отладку с Windows-компьютера на удаленных Linux кластерах)

Настройка программ в OpenMP: основные стратегии Если есть возможность, то сперва следует воспользоваться средством авто-распараллеливания программы Для нахождения наиболее трудоемких участков программы следует воспользоваться возможностью профилирования (profiling) Затем следует добавить в программу инструкции OpenMP для распараллеливания наиболее затратных участков программы В случае неэффективного распараллеливания конструкций do/for следует учесть Высокую стоимость инициализации параллельных потоков (порядка 1000 операций деления) Неэффективность распараллеливания небольших циклов Несбалансированность потоков Многочисленные ссылки к переменным в общей памяти Ограниченный объем кэша Высокую стоимость операции синхронизации Высокую стоимость доступа к удаленной общей памяти (на NUMA-компьютерах) При распараллеливании вложенных циклов следует сперва распараллеливать внешние петли При распараллеливании циклов следует иметь в виду, что петли циклов по объему вычислений могут быть зачастую треугольными и порождать несбалансированные параллельные потоки. Чтобы избежать несбалансированности при работе программы следует использовать инструкцию schedule

Настройка программ в OpenMP: пример распараллеливания Исходная программаПараллельная программа

Настройка программ в OpenMP: автоматическое распараллеливание Основные современные языки программирования имеют возможности автоматического распараллеливания программ в OpenMP: –openmp –parallel – par_report[0|1|2|3] –par_threshold[x], (0

Настройка программ в OpenMP: иерархия памяти Современные параллельные системы имеют следующую иерархию памяти Регистры Кэш 1-го уровня Кэш 2-го уровня Кэш 3-го уровня Локальную память Удаленную память (с доступом через interconnect) Время доступа к памяти существенно возрастает при движении по иерархии сверху вниз В связи с этим становиться актуальной задачи эффективности загрузки кэша и регистров, а также минимизация доступа к удаленной памяти Для более эффективной загрузки кэша следует принимать дополнительные меры по выравниванию строк (в C/C++) или столбцов (в FORTRAN) массивов Для более эффективного распараллеливания циклов следует по возможности обеспечить независимость петель вложенных циклов

Настройка программ в OpenMP: настройка кэша Для эффективного использования кэш памяти рекомендуется использовать многомерные массивы в одномерном виде Вложенные циклы следует модифицировать так, чтобы обеспечить последовательный быстрый доступ к элементам массива без скачков по индексам На NUMA (non-uniform memory access) платформах важно учитывать следующие особенности Где запущены потоки Какие данные загружены в локальную память Стоимость доступа к удаленной памяти Для NUMA платформ вышеперечисленные возможности сильно зависят от архитектуры систем OpenMP предоставляет следующие возможности по управлению потоками Запуск потока на определенном процессоре Размещение данных в определенном месте памяти Эти задачи решаются с помощью системных инструкций, которые могут быть различными на различных платформах и зависеть от загруженного системного программного обеспечения

Общие принципы сеточных методов

Параллельные методы решения дифференциальных уравнений в частных производных например

Принципы распределения данных Ленточное разделение области расчетов

Эффект сериализации (serialization) Причина в интенсивной синхронизации

Эффект состязания потоков (race condition) Возможность неоднозначности вычислений

Проблема взаимоблокировки

Исключение неоднозначности вычислений Схема чередования обработки четных и нечетных строк Шахматное разбиение

Волновые схемы параллельных вычислений методов волновой обработки данных (wavefront или hyperplane methods)

Организация волны вычислений при ленточной схеме разделения данных

Блочное представление сетки расчетов Увеличение эффективности использования кэша