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

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

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