МЕТОДЫ РАСПАРАЛЛЕЛИВАНИЯ РЕШАТЕЛЯ УРАВНЕНИЙ  MIMD – МОДЕЛИ СЕТЕВОГО ДИНАМИЧЕСКОГО ОБЪЕКТА

 

 

Святный В.А., Смагин А.Н., Солонин А.Н.

кафедра ЭВМ ДонНТУ,

solonin@cs.dgtu.donetsk.ua

 

 

Abstract

 

Svjatniy V., Smagin A., Solonin A. Interchange subsystem of information of distributed parallel simulation environment. In distributed parallel simulation environment as a new form of system-software organizations of complex dynamic systems is offered to select interchange subsystem of information.

 

 

1. Введение

 

В рамках научного сотрудничества кафедры ЭВМ ДонНТУ с институтом параллельных и распределенных вычислительных систем (IPVS) Штуттгартского университета разработана версия распределенной параллельной моделирующей среды (РПМС) для динамических систем с сосредоточенными (ДССП) и распределенными (ДСРП) параметрами [1].  Параллельными вычислительными ресурсами среды являются ЭВМ MIMD – архитектуры (CRAY T3E, Hitachi, VOLVOX, MIMD – кластер рабочих станций). Для разработки параллельных программ в РПМС предусмотрено применение C – реализации библиотеки MPI [2, 3, 4]. Основной задачей, решаемой на вычислительных ресурсах РПМС, является моделирование сложных динамических систем (СДС) [5, 6] и в частности – сетевых объектов (СО). В статье предлагаются методы распараллеливания решателя уравнений MIMD – модели СО и их MPI – реализация, дается сравнительный анализ методов.

 

2. Подходы к распараллеливанию моделей решателя уравнений СО

 

          Анализируя СO  различной физической природы, можно заключить, что они относятся к сложным динамическим системам [1, 5, 8]:

Сложность СО определяет ключевую роль моделирования как метода исследования и сопровождения проектов  реальных систем во всех областях техники. Формальное описание СО является основой для построения математических моделей, имеет следующие составные части [5]:

Топологическое описание.

          Топологии сетевых объектов описываются ориентированными графами G(U,V), которые кодируются таблицей вида [6]:

          NUJ KUJ QI PAR KOM,                                              (1)

Где NUJ KUJ- номера начальных и конечных узлов ориентированных ветвей; QI – номера ветвей, PAR – параметры ветвей, КОМ – коментарии; |V|=m – число ветвей, |U|=n – число узлов.

          Из таблицы 1 генерируется дерево и антидерево графа, матрица инциденций А и матрица контуров S [7, 9, 10], которые связывают топологическое описание с уравнениями процессов для СО.

Уравнения динамических процессов.

Для сетевых объектов с сосредоточенными параметрами узловые уравнения неразрывности имеют вид:

AQ=0                                                                   (2)

Где А – матрица инциденций, Q  - векторы расходов воздуха.

Контурные уравнения для вентиляционной сети произвольной топологии записываются в виде [6]:

.                                                         (3)

Здесь S – матрица инциденций; R, K – диагональные матрицы  аэродинамических параметров, Z – вектор с элементами вида Qi|Qi|; H – вектор давлений вентиляторов. Элементы этих векторов могут быть нелинейными функциями  H_i(Q_i).

Систему линейных алгебраических и обыкновенных дифференциальных уравнений преобразовывают к виду, удобному для численного решения [5, 6]:

   .

  Y = Hu – Ru*Z

  X = - W*Y                                                                                                (4)

 

W = Ax^-1*Ay

Hu = (Sy*Ky – Sx*Kx*W )^-1*S*H                                                   (5)

Ru = (Sy*Ky – Sx*Kx*W )^-1*S*R

Моделирующее программное обеспечение, реализующее модели сетевых объектов (1)-(5), разделяют на три последовательные части [5]:

·        Топологический анализатор (ТА);

·        Генератор уравнений (ГУ);

·        Решатель уравнений (РУ).

·        Решатель уравнений является наиболее требовательным к производительности  доступных вычислительных ресурсов. Разработке РУ для СО посвящены работы [13, ], при этом необходимо отметить, что в настоящее время SIMD – ЭВМ практически не используются и наибольшее внимание следует уделить разработке MIMD – моделей РУ.

 

Решатель уравнений должен представлять собой программу, реализующую циклический алгоритм численного решения матрично -  векторной системы уравнений (4)-(5). Рассмотрим подходы к распараллеливанию решателя уравнений .

На рис.1 приведен граф тестового сетевого объекта (m=9, n=6).

 

      Рис. 1 – Граф тестового сетевого объекта

 

Блок-схема последовательного алгоритма функционирования решателя уравнений  представлена на рис.2 (имеются в виду матрично – векторные операции). В решателе уравнений используется итерационный численный метод (в данном случае метод Адамса - Башфорта), распараллеливание обычно проводится по SPMD – принципу, результатом работы РУ являются файлы, содержащие значения неизвестных параметров (потоков воздуха в вентиляционной сети). Схема распараллеливания программы по SPMD – принципу  приведена на рис. 3. Данная схема является изображением виртуальной MIMD - модели.

Виртуальная MIMD - модель – модель описывающая абстрактное разбиение процесса решения на MIMD – процессы и распределение данных между этими процессами, будем при этом считать количество процессоров неограниченным. Назовем такой подход (виртуальную модель) распараллеливания – по количеству ветвей СО.

В данной виртуальной модели существуют m – виртуальных процессов сооветствующих ветвям сетевого объекта, каждый из которых ведет вычисления с определенными строками матриц X, Y и W, после вычисления очередных значений векторов Y происходит обмен информацией между процессами, далее вычиляется вектор Q и опять происходит обмен. Порядок вычилений и обменов ведется в соответствии с системой (5). Модели “по количеству ветвей” тестовых объектов такой сложности  были исследованы в работе [ ]. Модель СО реальной сложности, представляющий собой вентиляционную сеть [ ], был промоделирован авторами на ЭВМ CRAY T3E Штуттгартского вычислительного центра, с использованием программного обеспечения разработанного авторами работ [ ], были использованы 117 процессоров, время моделирования составило 2,2 секунды, однако среднее время ожидания программы на обслуживание составило около 2 минут (так как необходимое число процессоров превышало 64 и задача не могла быть решена в режиме on – line). В данном подходе было проведено 100% отображение виртуальной модели на реальную MIMD – ЭВМ.

Рассмотрим еще несколько подходов:

·совмещения виртуальных процессов или выравнивания загрузки: как видно из рис.3 Х – процессы простаивают существенную часть времени, кроме того количество операций выполняемых этими процессами  меньшее чем у Y – процессов, есть смысл выполнить объединение некоторых Х – процессов с целью уравнять нагрузку на процессоры, предварительно определив критерии сложности процессов;

·        в зависимости от ветвей антидерева: при  = n-1 есть смысл произвести объединение Х – и Y – процессов - на  i – м виртуальном процессе  вычислять X_i, Y_i. Необходимо проанализировать ситуацию при  < > n-1;

·отказ от Х – процессов: случай похож на предыдущий, отличие заключается в отсутствии в явном виде Х – процессов, при этом Y – процессы  содержат массивы со значениями вектора Х. Этот подход можно применять при малой размерности вектора Х (n-1<10000);

·партиционирование графа сети при минимизации обменов: процессам приходится обмениваться информацией между собой на каждом шаге решения, необходимо таким образом объединять ветви в процессах (партиционировать граф), чтобы минимизировать количество операций обмена между ними.

 

 

Рис. 2 - Блок-схема алгоритма функционирования решателя

   уравнений

Рис. 3 -  Схема распараллеливания программы по SPMD-принципу
 

 

3. Девиртуализация моделей на целевую машину

 

В виртуальных MIMD – моделях не учитываются такие важные факторы:

·        количество доступных процессоров  MIMD – ЭВМ;

·        параметры коммуникационной системы MIMD – ЭВМ и библиотеки реализующей обмен информацией (в данном случае MPI).

При разработке программного обеспечения реализующего виртуальные модели необходимо распределять данные и процессы  в MIMD – ЭВМ таким образом, чтобы оптимизировать работу модели в зависимости от приведенных выше факторов. 

Назовем этот процесс девиртуализацией, MIMD – ЭВМ на которую происходит отображение виртуальной модели – целевой машиной, а реализацию виртуальнуй модели – девиртуализированной моделью.

Большое влияние на процесс девиртуализации оказывает используемая реализация коммуникационой библиотеки MPI. От типа применяемой библиотеки зависит возможность или невозможность запуска нескольких виртуальных процессов на одном процессоре.

 

4. Предлагаемые методы девиртуализации

 

Метод равномерного распределения  представляет собой модифицированный метод рассмотренный выше и заключается в следующем:

пусть

m – количество ветвей СО,

n – количество вершин, 

(n-1) – количество ветвей дерева

 – количество ветвей антидерева

= m – (n-1) – цикломатическое число (количество независимых контуров)

Р - количество виртуальных процессов (Р = m = n+)

N_CPU  - количество доступных процессоров (1N_CPU  P)

Необходимо равномерно распределить Р виртуальных процессов ([n-1] и ) между N_CPU  доступными процессами, то есть создать масштабируемое распараллеливание РУ.

Будем распределять виртуальные процессы соответствующие ветвям дерева P₁=n-1 и антидерева P₂=, где Р=Р₁+Р₂, между двумя группами процессоров N₁ и N₂  соответсвенно, где N_CPU=N₁+N₂.

Обозначим quot[F] – целую часть числа F, а rem[F] – дробную часть, тогда:

N₁=quot ;

N₂=;

Р₁  можно представить следующим образом: Р₁=F₁ *N1+E₁; (E₁<N₁; N₁=D₁+E₁)

          Распределим Р₁ виртуальных процессов на N₁ – процессорах следующим образом:

на D₁ процессорах – (F₁)– виртуальных процессов,

на E₁ процессорах – (F₁ +1)– виртуальных процессов,

(D₁*F₁+E₁*(F₁+1)=n-1=P₁);

Р₂  можно представить следующим образом: Р₂=F₂ *N₂+E₂; (E₂<N₂; N₂=D₂+E₂)

          Распределим Р₂ виртуальных процессов на N₂ – процессорах следующим образом:

на D₂ процессорах – (F₂)– виртуальных процессов,

на E₂ процессорах – (F₂ +1)– виртуальных процессов,

(D₂*F₂+E₂*(F₂+1)==P₂)

          Таким образом найдены параметры распределения виртуальных процессов MIMD – модели СО на линейку доступных процессоров (m, n, , D₁, D₂, E₁, E₂, F₁, F₂, P₁, P₂ ).

          Метод равномерного распределения по ветвям антидерева  представляет собой модифицированный метод равномерного

 распределения рассмотренный выше и заключается в следующем:

пусть m – количество ветвей СО,

n – количество вершин,  (n-1) – количество ветвей дерева

 – количество ветвей антидерева

= m – (n-1) – цикломатическое число (количество независимых контуров), отметим следующее: как видно из рис.3 виртуальные процессы Х_i большую часть работы программы простаивают, кроме этого существенное время тратится на обмен по матрице коммутации W. Суть  метода равномерного распределения по ветвям антидерева заключается в отсутствии в явном виде группы Х – виртуальных процессов. В программе присутствуют только Y – процессы, каждый из которых содержит свою копию данных соответсвующих Х – процессам. То есть вычисление вектора Y распределено между  – виртуальными процессами:

     (6)

Каждый из которых вычисляет свою составляющую вектора Х:

 

X=-W*Y;

X=     (7)

    

то есть в виртуальном процессе Y_i находится массив слагаемых вектора Х:

 

Y_i : {X_1(Yi)=W₁*Y; X_2(Yi)=W₂*Y; . . . ;X_n-1(Y1)=W_n-1,*Y;}                (8)

 

После вычисления вектора Y, каждый Y – процесс вычисляет свою часть вектора Х и производится глобальная операция редукции с суммированием.

Распределение виртуальных процессов между процессорами:

Р - количество виртуальных процессов (Р = )

N_CPU  - количество доступных процессоров (1N_CPU  P)

Р  можно представить следующим образом:

Р=F *N_CPU+E; (E<N_CPU; N_CPU=D+E)

          Распределим Р виртуальных процессов на N_CPU – процессорах следующим образом:

на D процессорах – (F)– виртуальных процессов,

на E процессорах – (F +1)– виртуальных процессов,

(D*F+E*(F+1)=  = P);

Таким образом найдены параметры распределения виртуальных процессов MIMD – модели СО на линейку доступных процессоров (m,n,,D, E, F₂, P).

 

 

 

 

5. Сравнительный анализ разработанных методов

 

Автором создано программное обеспечение реализующее данные методы распределения и проведены эксперименты на ЭВМ CRAY T3E Штуттгартского вычислительного центра с моделью вентиляционной сети шахты [ ] Зависимость времени моделирования от количества используемых процессоров показано на рис. 4.  По оси ординат показано время работы программы, а по оси абсцисс – количество применяемых процессоров. Минимум времени моделирования приходится на 24 процессора и составляет 0,42 секунды. Таким образом разработанный метод равномерного распределения является масштабируемым, имеет большее быстродействие и требует применения меньшего числа процессоров сравнительно с методом описаным в [ ].

Необходимо отметить что с увеличением числа используемых процессоров свыше 30 происходит постепенное увеличение времени моделирования, процессоры начинают «мешать» друг другу – время затрачиваемое на обмен данными между процессорами увеличивается.

 

 Минимум времени моделирования приходится на 22 процессора и составляет 0,34 секунды.

 

Необходимо провести сравнительный анализ новых методов.

На рис. 7 приведены совмещенные диаграммы зависимостей времени моделирования от числа применяемых процессоров. Синим цветом отмечены значения для равномерного метода, красным – для метода распределения по антидереву. Оба разработанных метода имеют преимущества перед методом в работе [ ]. Очевидно что метод распределения виртуальных процессов по ветвям антидерева имеет несколько большее быстродействие, чем метод равномерного распределения. Однако необходимо отметить, что моделируемый СО шахтной вентиляционной сети относительно прост (m=117, n=61)  и необходимы дальнейшие исследования с другими объектами такой же сложности (m<1000) и более высокой сложности (m>>1000) – например

электрическими сетями.

 

5. Выводы и перспективы дальнейшей работы

 

По результатам полученным при исследовании разработанных методов можно сделать следующие выводы:

·        полученные методы имеют более высокое быстродействие чем ранее известные;

          Рис. 7 – Сравнительный анализ методов распараллеливания

 

·        требуют меньшего количества процессоров;

·        метод распределения по ветвям антидерева представляется более предпочтительным;

·        необходима проверка методов на моделях реальных СО аналогичной сложности;

·        необходима проверка методов на моделях СО высокой сложности;

·        представляется необходимым разработка генератора тестовых СО высокой сложности (m>>1000)

 

Благодарности

 

          Автор благодорит руководство Штуттгартского вычислительного центра в лице проф. М. Рэша за предоставленную возможность проведения экспериментов на ЭВМ CRAY T3E, непосредственного руководителя работы докторанта Н. Курле-Линде. Особую признательность автор выражает своему научному руководителю д.т.н. проф. Святному В.А. за множество ценных замечаний и поддержку в работе.

Литература

 

1. Святний В.А., Солонін О.М., Надєєв Д.В., Степанов І., Ротермель К., Цайтц М. Розподілене паралельне моделююче середовище.- Наукові праці ДонДТУ. Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. Випуск 29:-Донецьк, ДонДТУ, 2001. – С.229 – 234.

3. MPI: A Message-Passing Interface Standart Esprit Project P6643 (PPPE), 1994, 227p.

 

5. Святний В.А. Проблемы паралельного  моделювання складних динамiчних систем.- Науковi працi ДонДТУ, серiя IКОТ, вип. 6, Донецьк, 1999, С. 6-14.

6. Аноприенко А.Я., Святный В.А. Высокопроизводительные информационно-моделирующие среды для исследования, разработки и сопровождения сложных динамических систем.- Наукові праці ДонДТУ. Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. Випуск 29:-Донецьк, ДонДТУ, 2001. – С.346 – 367

7. Абрамов Ф.А., Фельдман Л.П., Святный В.А. Моделирование динамических процессов рудничной аэрологии. Киев, Наукова думка, 1981г. 283с.

8. Святный В.А. Моделирование аэрогазодинамических процессов и разработка систем управления проветриванием угольных шахт. Диссертация на соискание ученой степени доктора технических наук, Донецк, 1985, 440 с.

9. Разинков В.В. Разработка параллельных алгоритмов топологического анализа динамических сетевых объектов с сосредоточенными параметрами, Сборник трудов факультета вычислительной техники и информатики, Выпуск 1, Донецк – 1996

10. Перерва А.А. Топологический анализатор параллельной модели сетевого объекта. Наукові праці Донецького  державного технічного університету, Серія: Информатика, кібернетика, та обчислювальна техніка, Випуск 6, Донецьк –1999

11. Святный В.А., Молдованова О.В. Генератор уравнений параллельной модели сетевого динамического объекта с распределенными параметрами. Наукові праці Донецького  державного технічного університету, Серія: Проблеми моделювання та атоматизації проектування динамічних систем, Випуск 10, Донецьк –1999

13. Перерва А.А.  Генератор и решатель уравнений проблемно ориентированной параллельной моделирующей среды для сетевых объектов с сосредоточенными параметрами. Наукові праці Донецького  державного технічного університету, Серія: Проблеми моделювання та атоматизації проектування динамічних систем, Випуск 10, Донецьк –1999

14. Святный В.А. . Распараллеливание в технологически ориентированных моделирующих средах . Наукові праці Донецького  державного технічного університету, Серія: Информатика, кібернетика, та обчислювальна техніка, Випуск 15, Донецьк –2000

15. Бройнль Т. Паралельне програмування. К.-ВШ 1997- 358 с.