Параллельные модели

ПАРАЛЛЕЛЬНЫЕ МОДЕЛИ

Введение
Модели физической области – уровни представления
1. Физическая модель
2. Математическая модель
3. Дискретная вычислительная модель
4. Программно-аппаратная модель
Параллелизм на разных уровнях представления
1. «Естественный» параллелизм физической модели
2. Параллельные программные системы
  1. Процессно-ориентированные модели
  2. Объектно-ориентированные модели
  3. Средства синхронизации параллельных вычислений - синхронизация эволюции частей модели
  4. Средства связи частей модели
3. Параллельные дискретные вычислительные модели
  1. Традиционные методы распараллеливания последовательных алгоритмов
  2. Методы декомпозиции/композиции областей – описание интерфейсов между подобластями
    1. Метод Шварца для декомпозиции областей
    2. Метод композиции вычислительных объектов – построение области путем композиции первичных подобластей с выделением приграничных полос между подобластями
    3. Использование приграничных «потоков» для композиции подобластей
4. Уравнения и параллелизм – уровень математической модели
Эффективность распараллеливания
1. Коэффициент ускорения при распараллеливании
2. Соотношения между количеством данных, обрабатываемых в узле МВС на каждом шаге вычислений, и количеством данных, пересылаемых между узлами в конце шага
3. Оптимальное соотношение между производительностью процессорных узлов, скоростью обмена между узлами и объемом памяти в узлах
Программирование примеров для МВС
1. Параллельное умножение матриц
  1. Реализация через MPI и С++
  2. Реализация через OST
2. Решение уравнения параболического типа на интервале [0,L]
  1. Реализация через MPI и С++
  2. Реализация через OST

Введение.

Рассмотрим последовательность шагов по получению параллельной программно-аппаратной модели для некоторой физической области. В настоящее время при построении вычислительной модели некоторой физической области обычно используется последовательность «физическая модель – математическая модель – дискретная вычислительная модель – программно-аппаратная модель». Основной нашей целью будет рассмотрение параллельной эволюции частей модели и взаимодействие этих частей в процессе эволюции для вычислительного и программно-аппаратного уровней представления. Если нам нужен параллельный счет на многих процессорах, то из этого однозначно следует необходимость разбиения модели на взаимодействующие и параллельно эволюционирующие части. При этом возникает вопрос – на каких уровнях представления модели кроме программно-аппаратного такое разбиение необходимо? Ответ не является однозначным. В данной работе в качестве неформальной обобщенной схемы построения моделей на любом уровне представления принята следующая схема построения:

- модель на любом уровне состоит из параллельно эволюционирующих, связанных друг с другом и через эти связи взаимодействующих в процессе эволюции частей. Статический случай рассматривается как частный случай эволюции;

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

используется архитектура «натурного цифрового» моделирования, в которой модель строится из виртуальных цифровых частей по аналогии с натурным моделированием, при котором модель строится из материальных частей;
проблема, возникшая при построении модели на одном уровне представления, обязательно имеет аналог на других уровнях представления. При выборе варианта решения очень часто целесообразно рассмотреть, как решается эта проблема на других уровнях представления. Другая формулировка этого правила — нужно видеть физический смысл действий с вычислительными моделями.

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

Кратко рассмотрим возможные уровни представления физической области.

Модели физической области – уровни представления
1. Физическая модель.

Это – описание физической области в терминах физических законов. Так как нашей целью является рассмотрение параллельных вычислительных и программно-аппаратных моделей, то этот уровень нам нужен лишь в качестве части обобщенной картины построения моделей. Такая обобщенная картина использована как неформальное основание для принятия тех или иных конкретных решений на подробно рассматриваемых уровнях. Тем не менее, в рамках принятой за основу архитектуры уже на этом уровне желательно выделение параллельно эволюционирующих частей и связей между ними. Из принципа подобия моделей на разных уровнях представления, в частности, следует, что часть физической модели отображается, в конце концов, на программно-аппаратном уровне на отдельный возможно виртуальный процессор.

Математическая модель.

Это обычное описание физической области в виде систем уравнений, начальных и граничных условий. В случае декомпозиции области на параллельно эволюционирующие части еще на уровне физической модели для каждой подобласти создается своя система уравнений. Тогда для «внутренних» границ между подобластями граничные условия должны быть заданы в виде уравнений, связывающих значения существенных переменных, условно выражаясь, на «левых» и «правых» сторонах этих внутренних границ.

Дискретная вычислительная модель.

Вычислительная модель некоторой физической области обычно представляется в виде некоторого набора матриц, векторов, чисел и некоторого последовательного алгоритма для их обработки. Мы рассматриваем параллельную вычислительную модель физической области из одновременно эволюционирующих и независимо описанных подобластей. В этом случае естественно возникает проблема граничных условий на внутренних границах, разделяющих соседние подобласти. Ясно, что до начала счета невозможно определить значения существенных граничных переменных. Эти значения должны определяться в результате взаимодействия подобластей в процессе их эволюции. Поэтому традиционные граничные условия необходимо заменить на описание некоторого интерфейса между взаимодействующими подобластями. Широко известны такого рода алгоритмы на основе метода декомпозиции области, предложенного Шварцем [1]. В качестве другого примера можно привести использование граничных потоков, как, например, в методе С.К. Годунова [2]. В настоящей работе используется алгоритм взаимодействия подобластей, основанный на использовании «приграничных» областей. Этот алгоритм отличается минимальными требованиями к типу физической области. Единственным условием применимости предлагаемого алгоритма является конечность скорости распространение возмущений от границ подобластей [3].

Программно-аппаратная модель.

На программно-аппаратном уровне модель физической области в нашем случае представлена в виде множества программ, одновременно выполняющихся на множестве процессоров и взаимодействующих друг с другом во время выполнения путем межпроцессорных обменов. В настоящее время между собой конкурируют две архитектуры построения параллельных программных систем:

- процессно-ориентированная, в которой каждая часть модели оформляется в виде процесса (например, в контексте операционной системы UNIX). Эти процессы, распределяются по разным процессорам, и взаимодействуют, посылая друг другу сообщения;

- объектно-ориентированная, в которой каждая часть модели оформляется в виде программного объекта (например, в контексте языка С++). Эти объекты распределяются по разным процессорам и взаимодействуют, вызывая друг в друге операции. Вызов операции в из одного объекта в другом объекте реализуется путем удаленного вызова подпрограмм.

Параллелизм на разных уровнях представления

3.1. «Естественный» параллелизм физической модели

Имея в виду цель в виде построения параллельной программно-аппаратной модели, будем рассматривать физическую область как множество частей и множество физических процессов, параллельно протекающих в этих частях. При этом процессы могут быть как разделены по пространству или времени, так и совмещены. Подчеркнем, что необходимо отобразить физические части и процессы на соответствующие программные конструкции и, желательно, взаимно однозначным образом. По мнению автора именно параллельность или последовательность действий в физической модели должна непосредственно браться за основу при построении параллельных программных моделей. К сожалению, в настоящее время основные усилия и средств затрачиваются на автоматизацию распараллеливания последовательных программ, в которых от естественного параллелизма исходной физической системы осталось очень мало информации.

3.2. Параллельные программные системы

Для представления на программном уровне частей физической системы и физических процессов в этих частях в настоящее время предлагаются системы программирования, основанные на двух альтернативных архитектурах — процессно-ориентированные и объектно-ориентированные. Следует отметить, что несмотря на «непримиримый» антагонизм некоторых сторонников той или иной архитектуры, по моему мнению, они эволюционируют навстречу друг другу, заимствуя лучшие черты у соперника. Дело в том, что любая система программирования должна дать возможность описать данные, программы, обрабатывающие эти данные, и процессы исполнения программ обработки данных. Различия в архитектурах описания этих базисных элементов проявляются в той или иной сложности (трудоемкости) создания достаточно больших программных систем. В контексте нашей проблемы создания распределенных программных моделей, состоящих из многих взаимодействующих и параллельно эволюционирующих частей, в качестве критериев сравнения естественно использовать оценки сложности для описания компонент создаваемой параллельной системы:

- самих частей,

- связей между этими частями,

- синхронизации взаимодействия частей.

3.2.1. Процессно-ориентированные модели

В этой архитектуре часть физической системе предлагается представлять процессом. В контексте конкретной операционной системы и системы программирования процесс это стандартизованная конструкция, создаваемая командой «создать процесс» с указание программы, которая начнет выполняться после создания этого процесса. Кроме задания исполняемой программы при создании процесса указываются или устанавливаются по умолчанию значения различных атрибутов процесса. В качестве примера можно указать приоритет процесса, указания на ресурсы, которые процесс может использовать во время своего исполнения и т.п. С точки зрения построения системы, состоящей из многих процессов, главным атрибутом является идентификатор процесса, который необходим для указания адресата сообщения при посылке сообщений между процессами. Простейший используемый способ идентификации это присвоение последовательных номеров процессам по ходу их создания. Соответствие между номерами процессов, указываемыми в операциях обмена сообщениями, и сложными физическими адресами процессов (адрес процессора в сети, идентификатор задачи в процессоре, адрес системного описания процесса в оперативной памяти, выделенной задаче) поддерживается в виде некоторых таблиц соответствия, управляемых системой управления счетом.

Достоинства архитектуры:

- простота основных примитивов работы с процессами, а именно примитива создания процесса с конкретным номером и примитива посылки сообщения от одного процесса к другому процессу с указанным номером.

Недостатки архитектуры:

- вне архитектуры осталось описание данных и программ, реализующих операции с этими данными. Из за отсутствия соответствующих стандартизованных компонент остаются не стандартизованными описания частей физической модели в виде данных и программ, становится, в частности, затруднительным автоматическое распределение процессов по процессорам,

- «ручное» построение связей между процессами в виде сохранения номеров «соседних» процессов, с которыми необходимо взаимодействие,

- низкоуровневый способ синхронизации через сообщения, который плохо защищен от ошибок программиста.

Очевидно, что недостатки архитектуры являются следствием ее основного достоинства — простоты. В ней не нашли отражения многие существенные черты физических моделей.

3.2.2. Объектно-ориентированные модели

В этой архитектуре часть физической системы предлагается представлять программным объектом. Программный объект создается командой «создать объект» с указанием экземпляра данных и набора подпрограмм, реализующих операции с этими данными. Результатом операции создания является ссылка на объект, через которую осуществляется доступ к объекту (вызов операций в объекте). Вызов операции должен быть удаленным в том случае, когда вызываемый и вызывающий объекты расположены в разных процессорах. Понятие процесса и соответствующая программная конструкция существенно используется и в объектно-ориентированной модели. Содержательно в рамках процесса идет исполнения подпрограмм, входящих в состав объектов и вызов операций из одного объекта в другом. При этом процесс «перетекает» из одного объекта в другой. Так как вызывающий и вызываемый объекты могут располагаться в разных процессорах, то естественно обобщить традиционное понятие локального процесса на «распределенный» процесс, в рамках которого совершается последовательные вызовы из подпрограммы в подпрограмму в цепочке объектов, распределенных по сети процессоров. В этом, в частности, заключается существенное архитектурное отличие двух рассмотренных архитектур, так как в процессно-ориентированной архитектуре каждый процесс локализован в конкретном процессоре. Конечно, можно использовать различные критерии при сравнении архитектур, однако в данной работе предлагается использовать принцип подобия различных представлений одной физической области. В случае выбора между «локальными» и «распределенными» процессами этот принцип можно использовать следующим образом. Рассмотрим в качестве примера некоторую физическую среду через которую распространяется какая то волна. В физической области естественно представлять себе процесс распространения волны через все части области как единое целое. Распределенный программный процесс полностью соответствует этому представлению, а локальный нет. Это означает, что программисту придется при создании распределенной программной модели как то вручную оформлять соответствующее понятие в виде цепочки локальных процессов. Заметим, что в других случаях для физической модели может быть адекватным представление о цепочке физических процессов, но в О-О архитектуру укладывается представление как локальных, так и распределенных процессов.

Предпочтительное соотношение конструкций «объект-процесс» можно охарактеризовать как «много-много». Это соотношение означает, что один процесс может пройти через много объектов, а в один объект могут войти и одновременно существовать много процессов. По указанному соотношению можно классифицировать многие современные программные системы, которые могут соответствовать вариантам «один-один», «много-один» и «один-много».

Достоинства архитектуры:

- для основных понятий физической модели (физического объекта, физического процесса, распределенного по физической области) имеются однозначно соответствующие понятия (программного объекта, процесса, распространяющегося через части программной модели, расположенные на разных процессорах),

Недостатки базовой объектно-ориентированной архитектуры:

- «ручное» построение связей между объектами в виде сохранения ссылок на «соседние» объекты, с которыми необходимо взаимодействие,

- множество способов синхронизации (порядка десятка, практически эквивалентных), плохо защищенных от ошибок программиста.

3.2.3. Средства синхронизации параллельных вычислений - синхронизация эволюции частей модели

Методы синхронизации процессов рассматривались еще в 1960-х гг. в пионерской работе Э. Дейкстры [17], который механизм синхронизации с помощью «семафоров». С тех пор появились много других конструкций — критические области, мониторы, мьютексы, сообщения и т.д.[] . Все эти конструкции достаточно просто сводятся одна к другой и не решают основной проблемы синхронизации с точки зрения прикладного программиста — обеспечение гарантированно безошибочной синхронизации с малыми трудозатратами при планировании и программировании.

Рассмотрим пример синхронизации с помощью семафоров.

В работе [] предлагается принципиально другой способ синхронизации путем разметки синхронизируемых действий и данных временными метками. Действие над данными разрешается только тогда, когда и действие и данные помечены одним и тем же временем.

Рассмотрим пример синхронизации с помощью времни.

3.2.4. Средства связи частей модели

В обеих конкурирующих архитектурах для организации связей используются концептуально одни и теже средства. Программной конструкции, на которую отображается часть модели, при создании присваивается некоторый идентификатор. Это может быть, например, последовательный номер создаваемого процесса или уникальный идентификатор (УИД) создаваемого объекта. Отображение идентификатора на реальный физический адрес части осуществляет системой управления счетом. В управлении связями следует различать две фазы:

- фаза создания связей. Точнее это фаза создания модели, в которой создаются сами части модели и устанавливаются связи между ними. В базовых систем управления процессами (например, MPI) или объектами (например, ) прикладной программист сам программирует установления связей путем сохранения идентификаторов частей в переменных, которые находятся в тех частях модели, которым нужна некоторая конкретная связь. В ряде надстроек над базовыми системами связи устанавливаются автоматически, например, по описанию топологии системы[], или полностью автоматически в случае автоматической декомпозиции исходной модели на одном из уровней представления[];

- фаза использования связей для обмена информацией между частями.

3.3. Параллельные дискретные вычислительные модели

3.3.1. Традиционные методы распараллеливания последовательных алгоритмов

3.3.2. Методы декомпозиции/композиции областей – описание интерфейсов между подобластями.

3.3.3.1. Метод Шварца для декомпозиции областей

Пусть у нас имеется разностная схема для решения дифференциальных уравнений, определенных на всей области, тогда логично использовать ее же для подобластей. Но нам не хватает граничных условий, ведь они заданы только на границе “большой” области, а границы подобластей будут совпадать с ней только частично. Для решения этой проблемы существуют методы декомпозиции области, один из которых – метод Шварца.

Суть метода Шварца проста: изначально угадывается граничное условие на одной из подобластей, ищется решение на этой подобласти, которое затем используется для определения граничных условий для других подобластях. После этого подсчета других подобластей (для чего, возможно, придется еще брать произвольные граничные условия) используются для определения граничных условий первой подобласти, решение на ней ищется заново, а затем вновь используется другими областями. Эти итерации постепенно приближают текущее решение на подобластях к реальному, тому которое было бы получено, если бы мы не делили область. Есть несколько модификаций метода Шварца, каждая может быть применена к определенному типу уравнений. Здесь будет рассмотрен метод Шварца с пересекающимися подобластями для параболических уравнений.

Рассмотрим уравнение в частных производных параболического типа на интервале [0,L] с заданными начальным условием и граничными условиями на концах интервала:

Будем считать, что начальные данные удовлетворяют условиям необходимым для существования и единственности решения. Для функции определим норму следующим образом:

Разобьем область на две пересекающиеся подобласти и . На первой подобласти рассмотрим функцию , а на второй , которые удовлетворяют решаемому уравнению, а также новым граничным условиям и .

Для это уравнения:

Для

Если возьмем на соответствующих подобластях, то это будет решением этих уравнений. Из единственности решения уравнения на всей области и уравнений на подобластях получаем, что решения уравнений на подобластях будут равны решению уравнения всей области.

Найти точные значения функций мы не можем. Однако, можно постепенно приближать их значения к точному, используя метод Шварца. Мы будем по очереди находить промежуточные функции, все время, используя новые граничные условия: на k+1 итерации мы получаем функцию , используя значения на части границы , принадлежащей и полученные на предыдущей итерации. Для нахождения используем соответственно значения на части границы , принадлежащей . Таким образом, получаем уравнения:

следующая страница>