Система
уравнений примет вид:
.
Y
= Hu – Ru*Z
X = - W*Y
W
= Ax-1*Ay
Hu
= (Sy*Ky – Sx*Kx*W )-1*S*H (Нu - преобразованное)
Ru
= (Sy*Ky – Sx*Kx*W )-1*S*R (Ru - преобразованное)
Матрицы W, Hu, Ru
расчитываются на подготовительном этапе и они описаны ниже:
Матрица HU:
1.1
1.0
0.9
0.8
Матрица RU:
0.0011 0.0032 -0.0005 0.0032 -0.0005 0.0108
-0.0038 -0.0006 -0.0002
0.0010 0.0028 -0.0004 0.0028 -0.0004 -0.0076
0.0052 -0.0004 -0.0002
0.0009 -0.0010 0.0014 -0.0010 0.0014 -0.0006
-0.0002 0.0106 -0.0039
0.0008 -0.0008 0.0012 0.0008 0.0012 -0.0004
-0.0002 -0.0078 0.0051
Матрица W:
-1 -1 -1 -1
-1 -1 0 0
0 0 -1 -1
-1 -1 0 0
0 0 -1 -1
В общем случае матрицы сетевого объекта имеют вид:
Kx 0
K = 0
Ky ;
Rx
0
R = 0
Ry ;
2. Постановка задачи моделирования.
Разработать MIMD-модель сетевого объекта, по
возможности в общем виде для m-ветвей
и n-узлов. Должно быть рассмотрено 3
подхода к постановке параллельной модели:
Ø
уравнение-ориентированный
подход (последовательный аналог – язык ACSL),
Ø
блочно-ориентированный
подход (последовательный аналог – язык SIMULINK),
Ø
объектно-ориентированный
подход (последовательного аналога в виде языка моделирования нет).
Для отладки модели использовать тестовые значения установившихся расходов
воздуха.
Таблица
2.1. Тестовые значения установившихся
расходов воздуха.
|
Пар.
|
X1
|
X2
|
X3
|
X4
|
X5
|
Y1
|
Y2
|
Y3
|
Y4
|
|
Q уст.
|
23.71
|
10.04
|
13.66
|
10.04
|
13.66
|
4.15
|
5.88
|
5.66
|
8.00
|
3. Краткое описание алгоритмической структуры
модели.
На рисунке 3. приведена алгоритмическая структура модели, базирующаяся на
уравнениях объекта.
Рисунок 3.
Описание
блоков алгоритмической структуры модели:
СДС – сложная динамическая система любой физической природы, в которой
происходят переходные или динамические процессы.
Математическая модель – аппаратно-программные средства, в которых с заданной
или требуемой точностью воспроизводятся динамические процессы, протекающие в
СДС. Основой для разработки мат. модели СДС является ее формальное описание.
Топологический анализатор (ТА) – аппаратно-программные средства, обеспечивающие
удобное описание топологии на некотором входном языке (формально-вербальном),
кодирование топологии, формирование описаний топологий, по которым могут быть
составлены уравнения протекания процессов. Топологический анализатор решает
следующие задачи:
-
кодирование
графа сети,
-
построение
дерева и антидерева графа,
-
формирование
матриц инциденций A, AX, AY,
-
формирование
матриц контуров S, SX, SY,
-
перестановка
элементов векторов расходов Q в
форме Q=(X,Y)T.
В данном тестовом примери анализатор не программируется, матрицы A (AX, AY),
S
(SX, SY) заданы.
Генератор уравнений (ГУ) – программное средство, которое по данным ТА и по
уравнениям элементов СДС формирует систему уравнений всей СДС в целом.
Генератор уравнений выполняет матрично-векторные операции, соответствующие
переходу от одной системы уравнений к другой, удобную для численного решения.
Решатель уравнений (РУ) – аппаратно-программное средство, которое реализует
некоторый численный метод решения сформированных уравнений. РУ включает блок
инициализации (ввод параметров из файла, задание векторов начальных условий Y(0)), блок цикла с управлением по
точности или по заданному времени интегрирования и блок визуализации.
Визуализация результатов моделирования (ВРМ) – представляет собой средства
компьютерной графики, с помощью которых в наглядной форме представляются
результаты моделирования.
Подсистема диалога – програмное средство, обеспечивающее для пользователя
«доброжелательный» интерфейс со всеми функциональными блоками СДС.
3.1. ГЕНЕРАТОР УРАВНЕНИЙ.
Генерирование уравнений сводится к матричным операциям. Расположим их в
порядке, допускающем параллельное выполнение программ-процессов.
Рассмотрим несколько вариантов:
Таблица
3.1.1.
|
Процесс 1
|
Процесс 2
|
|
 AXI=(AX)-1
|
W1=SX*KX
|
|
 W=AXI*AY
|
W3=SY*KY
|
|
W2=W1*W
|
|
|
W4=W3-W2
|
|
|
W5=(W4)-1
|
|
|
TP=W5*S
|
|
|
RU=TP*R
|
|
Таблица
3.1.2.
|
Процесс 1
|
Процесс 2
|
|
AXI=(AX)-1
|
W1=SX*KX
|
|
 W=AXI*AY
|
W3=SY*KY
|
|
|
W2=W1*W
|
|
|
W4=W3-W2
|
|
|
W5=(W4)-1
|
|
|
TP=W5*S
|
|
|
RU=TP*R
|
3.2. решатель УРАВНЕНИЙ.
Решатель уравнений должен представлять собой программу, реализующую циклический
алгоритм численного решения матрично-векторных систем уравнений. Как и ранее
воспользуемся численным методом Адамса-Бошфорта, который реализован в
существующих последовательных языках моделирования.
Сделаем попытку унифицировать процессы решателя уравнений в дополнение к
тому, что они структурированы матрично-векторной формой записи.
По-видимому, есть смысл этот этап делать в таком порядке:
-
схема решателя
(пункт 3.2.1.)
-
анализ подходов
к распараллеливанию программы РУ (пункт 3.2.2.)
-
расcмотрение SPMD – принципа (пункт 3.2.3.)
-
организация
связи между процессами (пункт 3.2.4.)
-
визуализация
(пункт 3.2.5.)
3.2.1. схема решателя УРАВНЕНИЙ.
«Для ясности» составить блок-схему обычной последовательной программы, имея в
виду матрично-векторные операции (рис. 3.2.1):
Рисунок
3.2.1. Блок-схема алгоритма функционирования решателя уравнений.
3.2.2. анализ подходов к распараллеливанию программы решателя
уравнений.
Рассмотрим два подхода к распараллеливанию программы РУ:
-
основан на MIMD структуре,
-
основан на SPMD структуре.
Поиск варианта MIMD -
распараллеливание можно вести в рамках следующих трех программных структур.
Процесс Т1 запускает выполнение процессов. До начала возможного параллельного
выполнения Т1 … Тn «ведущий»
процесс выполняет большое число последовательных операций, чтобы «порадить»
(произвести подготовку к запуску) параллельные управляющие потоки Т2 … Тn.
Далее эти процессы работают параллельно и достигают каждый окончания
своей программы и операции объединения, которая ведет к синхронизации с
процессом Т1 и к терминированию указаных потоков. Для каждой параллельной нити
в программе генерируются заново и заканчиваются управляющие потоки (рис.
3.2.2.1).
Генерирование и детерминирование управляющих потоков вызывает большие
затраты ресурсов. Их экономия достигается в SPMD – модели распараллеливания.
Рисунок
3.2.2.1. Схема взаимодействия потоков.
В SPMD – модели параллельные процессы
(управляющие потоки порождаются только один раз при запуске программы).Эти
процессы терминируются в конце выполнения программы.
Последовательные части программы выполняются всеми процессами, т.е. речь
идет о многократном выполнении последовательных кодов программы. Каждый процесс
выполняет одну параллельную ветвь программы над своими локальными данными.
Рисунок
3.2.2.2. SPMD-модель.
Оба выше описанных методов объединяет метод Reusable-thread-pool-модель
(рис. 3.2.2.3).
С
помощью которого нам удается:
-
уменьшить объем
работ, связанных с многократным генерированием и терминированием управляющих
потоков (процессы) (рис. 3.2.2.1)
-
исключить
многократное исполнение последовательных частей программы (рис.
3.2.2.2).
Основная идея заключается в том, что новые процессы генерируются, если они
требуются в программе, т.е. к началу параллельной части программы. В конце
параллельного блока программы управляющие потоки переводятся в состояние
«недействующий» и к началу следующего параллельного участка снова
активизируются. Таким образом последовательная часть программы выполняется
только одним управляющим потоком.
Рисунок 3.2.2.3.
Reusable-thread-pool-модель.
Анализ этих структур
показывает, что надо ориентироваться на SPMD-организацию решателя, выполнять программу (рис.
3.2.1) в нескольких MIMD-процессорах.
При этом в каждом процессоре будут свои исходные и конечные данные. Это общий
подход. Рассмотрим его детально в следующей главе.
3.2.3. рассмотрение SPMD-принципа.
Этапы вычислений и данные, над
которыми проводятся вычисления, необходимо подразделить в возможно малые задачи
с возможно наибольшим параллелизмом выполнения.На этом этапе игнорируются
аспекты реализации параллельной модели (РЕ-конфигурация, число процессов,
структура сети связей между процессами).
Схема приведена на рис. 3.2.3.1.
Рисунок
3.2.3.1. Схема распараллеливания программы по SPMD-принципу.
3.2.4. организация связи между процессами.
Схема на рис. !!!! позволяет перейти к организации связей между процессами и
обмена информацией.
Логические связи между процессами определяются топологическими матрицами
(сформированы 3 матрицы): матрица W размерностью [W] =
(n -1)*j, матрица TP
размерностью [TP] = j*m и матрица RU
размерностью [RU]
= j*m.
На этом шаге выполняется операция: X = -W*Y. Эти значения должны вычисляться в процессах TX1 … TX5 с порядком выполнения расчетов и обмена
данными, которые изображены на рис. 3.2.4.1.
Рисунок
3.2.4.1. Порядок расчетов и обмена данными.
Таким образом
векторно-матричная запись X =
-W*Y разворачивается в (n-1) операций вида:
Эти операции требуют следующую виртуальную структуру обмена данными
между процессами (рис. 3.2.4.2.)
Рисунок
3.2.4.2. Структура обмена данными от TYk к TX.
Так как каждый TХ – процесс требует ввода данных от
всех процессов TY,
то отправитель TYk
после вычисления своей компоненты Yk(i) должен выполнить посылку типа «broadcast» (рис. 3.2.4.3.)
Рисунок
3.2.4.3. Операция типа «broadcast».
Виртуальный обмен осуществляется по алгоритму, приведенному на рис. 3.2.4.4.
Рисунок
3.2.4.4. Блок-схема виртуального объекта.
При максимальном распараллеливании операции «broadcast» передачу вектора Y каждому процессу TX можно осуществлять за 5 шагов (рис.
3.2.4.4).
Изложенные соображения используем при отображении виртуального обмена
(коммуникаций) на распределенный кластер.
3.2.5. визуализация результатов моделирования.
После окончания циклического параллельного цикла, каждый процесс имеет
компоненту вектора вычисления как функции времени на интервале 0 ≤ t ≤ IT (IT=h*i) с шагом h.Число точек iMax =IT/h.
Надо сформировать графическое представления компонент. Яркий пример
визуализации результатов моделирования приведен в 4-й главе (рис. 4.4.1).
С графическим пакетом надо заранее ознакомиться, узнать его возможности.
Результаты должны выдаваться на экран для просмотра.
4. Пример моделирования сетевого объекта.
4.1. Ввод
исходных данных.
В качестве примера программирования с использованием стандарта рассмотрим
модель тестового объекта, состоящего из 6 узлов и 9 ветвей. Уравнения и матрицы
сетевого объекта описаны в методических указаниях и представлены ниже:
Матрица HU:
1.1
1.0
0.9
0.8
Матрица RU:
0.0011 0.0032 -0.0005 0.0032 -0.0005 0.0108
-0.0038 -0.0006 -0.0002
0.0010 0.0028 -0.0004 0.0028 -0.0004 -0.0076
0.0052 -0.0004 -0.0002
0.0009 -0.0010 0.0014 -0.0010 0.0014 -0.0006
-0.0002 0.0106 -0.0039
0.0008 -0.0008 0.0012 0.0008 0.0012 -0.0004
-0.0002 -0.0078 0.0051
Матрица W:
-1 -1 -1 -1
-1 -1 0 0
0 0 -1 -1
-1 -1 0 0
Таблица
4.1.1. Параметры модели.
|
Пар.
|
X1
|
X2
|
X3
|
X4
|
X5
|
Y1
|
Y2
|
Y3
|
Y4
|
|
R
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
|
K
|
120
|
100
|
120
|
100
|
120
|
100
|
120
|
100
|
120
|
|
H
|
1000
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
Q уст.
|
23.71
|
10.04
|
13.66
|
10.04
|
13.66
|
4.15
|
5.88
|
5.66
|
8.00
|
4.2.
Программирование с использованием MPI.
MPI (Message Passing Interface) – стандарт, предложенный для
организации взаимо-действия процессов (процессоров) в параллельной
вычислительной среде. В качестве такой среды могут быть использованы
параллельные компьютеры CRAY,
Paragon, … или кластер компьютерной сети,
состоящий из однотипных компьютеров типа Sun, SGI,
HP, PC (кластер может состоять и из разнотипных машин –
тогда говорят о гетерогенной сети).
Данная модель была реализована на языке высокого уровня «С» с использованием
функций стандарта MPI.
Тестирование программы было проведено на кластере из 9 персональных компьютеров
класса IBM
PC AMD 5 под
управлением OC
Windows NT 4.0 и на
супер ЭВМ Paragon в лаборатории Донецкого
Государственного Технического Университета. Текст программы с комментариями
находится в приложении 1.
4.3. Структура и
функции программы.
Так как программа основана на решении системы дифференциальных уравнений 1-го
порядка, записанных в матричном виде, определим матрично-векторные операции:
ü инициализация матрицы
int InputMatrix( char*
FileName, Matrix Mat, const int m, const int n )
ü инициализация вектора
int InputArray( char*
FileName, Array Arr, const int n )
ü
элемент вектора,
полученный умножением i-ой
строки матрицы на вектор
float CreateElement( Matrix
Mat, Array Arr, int NoLine )
Функции инициализации считыват из подготовленных заранее файлов данные (в
будущем эти файлы должен генерировать топологический анализатор) и присваивают
элементам векторов и матриц полученные данные.
Функция CreateElement(…) вычисляет i-ый элемент вектора, где i – номер процесса (процессора), в
котором проводятся вычисления.
В основной части программы декларируются необходимые для работы переменные и
осуществляется инициализация MPI.
Для этого необходимы следующие функции:
MPI_Init
(&argc, &argv);
MPI_Comm_rank
(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size
(MPI_COMM_WORLD, &p);
С помощью этих функций
выделяется запрошенное пользователем число процессоров и им присваиваются
логические имена от 0 до n–1.
С деталями можно ознакомиться в [1].
После этого в 0 процессоре (процессе) происходит инициализация начальных
данных. Для более удобного реализации программы размерности матриц будут [M],[M], а массивов [M].
В то время как 0-ой процесс занят
инициализацией, остальные процессы находятся в состоянии ожидания. Для того,
чтобы гарантировать запуск остальных процессов только после окончания работы
0-го, используется функция:
MPI_Barrier(MPI_COMM_WORLD),
т.е. все процессы ждут окончания инициализации.
Алгоритм выполнения программы
предусматривает, что значения матриц и векторов известны не только 0-му, но и
всем остальным процессам. Для передачи сообщений служит функция Broadcast:
MPI_Bcast(W,
M*M, MPI_FLOAT, 0, MPI_COMM_WORLD);
Аргументы функции подробно описаны в [1]. Здесь
же стоит упомянуть, что 0-ой процесс (4-й аргумент) посылает матрицу W всем остальным
процессам ("остальные" - это MPI_COMM_WORLD).
MPI_Barrier(MPI_COMM_WORLD) как и раньше позволяет
гарантировать окончание всех операций Broadcast до начала следушего
программного сегмента.
Полученные в результате
моделирования данные должны быть сохранены для последующего анализа и
визуализации. Для этого каждый процесс открывает файлы с именами OutFile''номер процесса"
и записывает туда свои данные.
После проведения
подготовительных операций начинается непосредственно решение уравнений (их
интегрирование).
Сначала вычисляются (в каждом
процессе отдельно) компоненты вектора X (в программе они названы localX). Затем вычисляются
компоненты векторов Zx и Zy (соответственно localZ).
Затем в каждом процессе
вычисляется правая часть ОДУ (переменная Vlocal ), которая используется
для интегрирования системы уравнений по методу Адамса-Башфорта. Процесс
интегрирования ведется с шагом h до момента времени ITl или до выхода на
стационарный режим. Для проверки условия стационарности (тах(∆Х, ∆У)
≤ Delta), где ∆Х и ∆У максимальное изменение компонент векторов X и У между i и i + 1 шагами
интегрирования, используется еще одна функция MPI:
MPI_Allreduce( &localDQ,
&localZDK, 1, MPI_FLOAT, MPI_MAX,
MPI_COMM_WORLD )
В данном случае эта функция находит максимальное
значение среди переменных localDQ и сохраняет его в переменной localZDK в каждом процессе.
Формирование и рассылка
вектора Y происходит с помощью функции MPI:
MPI_Allgather( &localY, 1, MPI_FLOAT, Buf, 1, MPI_FLOAT,
MPI_COMM_WORLD )
Эта функция собирает все значения localY
в один массив и рассылает всем процессам.
После окончания интегрирования закрываются файлы выходных данных и выполняется
завершающая все процессы функция MPI_Finalize().
4.4. Результаты
моделирования.
Для визуализации полученных результатов были использованы графические
возможности системы Matlab.
Происходящие в сети процессы показаны на рис. 4.4.1. Установившемуся значению
расхода воздуха (в м3/с) соотвествует параметр:
23.71 - X1
10.04 - X2
13.66 - X3
10.04
- X4
13.66 - X5
4.15 - Y1
5.88 - Y2
5.66 - Y3
8.00 - Y4
При этом выполняются условия:
X1 = X2 + X3
X2 = Y1 + Y2
X3 = Y3 + Y4
Y1 + Y2 = X4
Y3 + Y4 = X5
X4 + X5 = X1
Рис. 4.4.1.
Результаты моделирования:
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
4.5. Заключение.
В данной работе представлена программная реализация на языке «С» модели
тестового сетевого объекта, описанного в методических указаниях.
Даны комментарии и пояснения по использованию функций MPI.
Данная тестовая модель сетевого динамического объекта протестирована на
кластере из 9 персональных компьютеров класса IBM PC AMD 5 под управлением OC Windows NT 4.0 и на супер ЭВМ Paragon в лаборатории Донецкого
Государственного Технического Университета.
Q2 Q3
