Проблемы и возможности разработки параллельных программ с динамической балансировкой вычислительной нагрузки для решения задач механики сплошной среды

Беляев С. П., Дегтяренко Л. И., Турутина И. Ю.
Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. Тезисы докл. Междунар. математич. конф 1997. Вып.1. С. 9.

      Программы для параллельных систем с распределенной памятью должны:
      — обеспечить взаимодействие процессоров с помощью передачи сообщений;
      — добиться равномерной загрузки процессоров;
      — использовать аппаратное совмещение передачи сообщений и счета на процессоре.
      Для задач механики сплошной среды с изменяющейся во времени вычислительной нагрузкой можно реализовать динамическое выравнивание нагрузки за счет передачи счетных точек от более нагруженных процессоров менее нагруженным.
      Возможность передачи произвольной точки с процессора на процессор приводит к необходимости реализации поточечного распараллеливания.
      Параллельную программу газодинамики можно организовать как последовательность этапов, на каждом из которых считаются гранично-процессорные точки, для которых требуются межпроцессорные обмены, а время ожидания заполняется счетом внутри процессорных точек. Передача сообщений производится по инициативе передающего как только точка сосчитана, сразу же инициируются необходимые передачи соседним процессорам и одновременно с передачами начинается счет величин для следующей точки. Такая организация проще и позволяет уменьшить суммарные ожидания в сравнении с другими подходами.
      Параллельную программу теплопроводности можно создать на базе параллельно-конвейерного подхода, при котором каждая линейка процессоров считает группу одномерных прогонок в конвейерном режиме и все линейки процессоров работают параллельно. Параллельно-конвейерный алгоритм реализуется также для произвольного множества точек на процессоре.
      Счетные программы создаются как программы обработки событий. За счет специального порядка обработки событий в программу закладываются максимальные совмещения счета и обменов.
      Для максимального совмещения счета и обменов также используются неблокирующие обмены и введен запрет на использование глобальных операций обменов.
      Для повышения эффективности предусмотрена буферизация обменов.
      Динамическое выравнивание нагрузки не зависит от используемой математической методики, может выполняться после заданного числа счетных шагов, и реализовано на базе следующих принципов:
      — минимизации дальних обменов;
      — локальности принятия решений о перераспределении вычислительной нагрузки.

      Параллельные программы, предназначенные для счета на вычислительных системах с распределенной памятью, должны учитывать основные особенности таких систем. В первую очередь необходимо:
      — обеспечить взаимодействие процессов, считающихся на разных процессорах, с помощью передачи сообщений;
      — добиться равномерной загрузки процессоров;
      — использовать аппаратное совмещение передачи сообщений и счета на процессоре.
      В многомерных задачах механики сплошной среды с изменяющейся вычислительной нагрузкой можно реализовать динамическое выравнивание вычислительной нагрузки за счет передачи счетных точек тэт более нагруженных процессоров менее нагруженным.
      От алгоритмов автоматического перераспределения точек между процессорами не требуется высокая точность. Если алгоритмы автоматического перераспределения обеспечивают эффективность параллельных вычислений 70-80% на системе из 10 процессоров и порядка 50% на системе из 100 процессоров для заметной чг1сти производственных задач, то можно считать, что они успешно выполняют свою работу. По предварительным оценкам для этого достаточно в процессе вычислений уменьшить дисбаланс нагрузки до 10-20%.
      В то же время представляются необходимыми следующие свойства алгоритмов перераспределения: простота вычислительной процедуры для определения количества передаваемых точек при минимуме информации и локальность принятия решений о перераспределении.
      Предполагается, что перед работой алгоритма каждый процессор получил от каждого из соседей информацию о конце шага, содержащую время счета и количество точек, которое может принять от данного процессора данный сосед. Общий алгоритм состоит из следующих последовательных шагов: .
      1. Вычисление количества точек, которые надо передать каждому соседнему процессору.
      2. Составление списков на передачу.
      3. Передача точек.
      4. Построение новых управляющих списков.
      5. Определение количества принимаемых точек для последующего шага балансировки.
      Только на шаге 3 процессоры взаимодействуют между собой. Все остальные шаги каждый процессор выполняет независимо.