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

Размещено на http://www.allbest.ru

Автореферат магистерской работы

Тема работы: "Исследование способов распределения вычислительной нагрузки при моделировании сетевого динамического объекта с распределенными параметрами"

Выполнена на кафедре "Вычислительной техники"

"Донецкого национального технического университета"

Автоp: Доста Максим Алексеевич

ВВЕДЕНИЕ

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

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

Целью данной работы является исследование различных подходов к распределению задач между процессорами с целью повышения быстродействия программы, а также применение этих способов распределения нагрузки к сетевому динамическому объекту с распределенными параметрами.

Достижение поставленной задачи выполняется путем:

- исследования способов распределения нагрузки;

- исследования сложного динамического объекта с распределенными параметрами;

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

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

Эта работа докладывалась на семинаре научно-исследовательских работ на кафедре ЭВМ в апреле 2004 г.

СПОСОБЫ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ

Представление задачи в виде графа

Все задачи распределения нагрузки можно разделить на два класса [3]:

1. Статическое распределение, при котором задача не меняется в процессе выполнения программы.

2. Динамическое, в котором задача может изменяться во время выполнения программы, т.е. могут появляться новые процессы или исчезать старые.

Для СДО в дальнейшем будет рассматриваться только статическое распределение нагрузки, т.к. сетевой динамический объект имеет наперед известную структуру, которая не изменяется во время выполнения программы, и на каждом шаге выполняются одни и те же вычисления.

Сетевой динамический объект c распределенными параметрами можно представить в виде неориентированного графа G(V, Q), ребра (Q) которого будут представлять собой ветви объекта, описываемые дифференциальными уравнениями, а вершины (V) связи между ними. Для распределения нагрузки требуется представить граф в виде «графа задач» T (P, M) - вершины которого (P) будут представлять вычисления, а ребра (M) - обмен данными между соответствующими вершинами.

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

Пример перехода от одного графа к другому представлен на рисунке 1.



Рисунок 1. Переход от исходного графа топологии к графу задач

Пусть граф G(V, Q), имеет n узлов и m ветвей, тогда аэродинамические процессы вызываются vent<=m вентиляторами и r

Апроксимирую уравнения, которые описывают СДО по методу прямых, получают следующие уравнения для j - участка, i - ветви (dx - шаг апроксимации) [8]

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

И исходя из этого, вес каждой вершины (Р) можно будет положить равным длине ветви исходного графа, которая разделена на шаг аппроксимации. Вес ветвей (М) можно взять равным единицы, так как между всеми процессами выполняется обмен данными одинакового размера.

Связь между вершинами графа Т отображает, между какими вершинами происходит обмен данными. Обмен данными выполняется на основании того, что некоторые процессы не вычисляют значение давления в конечных точках ветви, а используют эти значения принимая их от других процессов, которые занимаются вычислением ветви, которая тоже входит в этот узел (например процесс Р4 не вычисляет значение в точке 8, а принимает его из процесса Р3).

С другой стороны все процессы, которые описывают ветви, которые выходят из одной точки, должны получать давление в этой точке, вычисленное в процессе, который описывает ветвь, которая входит в эту точку (например давление в точке 2 из процесса Р1 передается к процессам Р2, Р5, Р6).

Также для вычисления давления в точке, в процесс, который вычисляет это значение, должны поступать начальные расходы из всех ветвей, которые выходят из этой точки и конечные расходы из тех, что входят (например, к процессу P3 должны поступать Q₇₁, Q₄₃).

Общий алгоритм формирования связей обмена данными можно сформулировать следующим образом (анализ структуры графа выполняется на основе матрицы инцидентности):

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

-если есть узел в графе G, в который входят ветви, то считается, что давление в узле вычисляется при моделировании ветви с младшим индексом, которая в него входит. Всем остальным ветвям, которые входят и выходят из него это значение передается. Для вычисления давления необходимо к этой ветви передать все расходы воздуха на начальных участках для ветвей, которые выходят и конечные - для тех, что входят.

На рисунке 2 приведен пример перехода, где:

- Qi - исходные ветви;

- Pri - полученные из них процессы;

- Pkn1 - давление в точке kn1, которое расчитано в процессе Pri;

- Qik - расход воздуха в ветви і, в последнем аппроксимированном промежутке;

- Qin - расход воздуха в ветви і, в первом аппроксимированном промежутке.

Стрелками показано направление передачи данных.

Рисунок 2. Анимированный пример перехода от исходного графа к графу алгоритма с указанными направлениями передачи данных.

Структура ЭВМ

ЭВМ, на которой будет выполняться программа, также можно представить в виде неориентированного графа. Вершинами этого графа будут являться процессорные элементы, а ребра будут представлять собой связи между процессорными элементами.

Пусть:

T( P, M ) - граф задач, где P -вершины графа (вычисления), а M - его ребра (обмен информации между вычислениями).

C( PE, K ) - граф отображающий целевую ЭВМ ( PE - процессорные элементы (ПЭ) , K - линии связи между ПЭ).

Тогда задача статического распределения нагрузки сводится к задаче отображения одного графа на другой. Пусть f - функция отображения, тогда: f: T -> C ставит в соответствие каждую вершину принадлежащую T вершине принадлежащей C [4]. И следовательно каждое ребро отображается на какой-то путь

.

Но задача отображения значительно облегчается для таких машин как IBM SP, Parsytec GC/CC, которые имеют не статические линии связи, а динамические. И такие ЭВМ могут быть представлены в виде кликов, т.е. полностью связных графов. Тут больше не учитывается длина пути соединяющего две вершины, т.к. коммуникации между любыми двумя ПЭ возможны примерно за одно и то же время. Из чего можно сделать вывод, что задача отображения для таких машин сводится к задаче разбиения графа T( P, M ) на N равных частей.

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

АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФА

Критерии разбиения графа

Пускай T(P, M), будет искомым графом с вершинами V и неориентированными дугами E. Пускай n=|P| будет количеством вершин, а m=|M| - количеством ребер.

Пусть f: P -> {0,1,...,N-1} будет разбиением графа T, которое распределяет на N процессорных элемента вершины графа.

Введем две главные характеристики, которые будут отражать эффективность разбиения графа.

Пусть:

bal(f)=max[max{|P_i|;0<=i<=N}-min{|P_i|;0<=i<=N}] будет балансом разбиения f, т.е. этот показатель будет говорить о том, насколько равномерно распределены вершины;

cut(f)=|{{v,w}M;f(v)<>f(w)} будет количеством связей разбиения f, т.е. это суммарное количество всех ветвей графа, которые связывают вершины распределенные на разные ПЭ.

Тогда при оптимальном разбиении оба параметра должны быть минимальными [2]. И эффективность того или иного алгоритма будет оцениваться исходя из этих двух параметров.

Классификация алгоритмов

Существует очень большое количество алгоритмов разбиения графа. Так как это NP полная задача то применения различных алгоритмов, выполняемых за полиномиальное время, дает разную эффективность разбиения.

Все алгоритмы разбиения можно разделить на три класса [1 1-40 cтр.]:

- глобальные;

- локальные (улучшающие, итерационные);

- многоуровневые.

Глобальные алгоритмы, получая входной граф, выполняют его разбиение на несколько частей.

Локальные - только улучшают разбиение входного графа, путем перестановки вершин между кусками.

Многоуровневые алгоритмы применяются для больших графов у которых очень большое количество вершин. В основу многоуровневых алгоритмов заложены три основных этапа:

- этап сборки ( coarsening ) на котором по определенному правилу вершины объединяются и образуют новую вершину с весом равным сумме весов исходных. Данные действия продолжаются пока не будет получен граф нужного размера.

- этап разбиения, на котором уже полученный граф разбивается на несколько частей.

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

На рисунке 2 представлена схема работы алгоритма.



Рисунок 2. Схема работы многоуровневого алгоритма

Общая схема, отображающая общую классификацию наиболее используемых алгоритмов разбиения графа, представлена на рисунке 3



Рисунок 3. Классификация алгоритмов разбиения графа

Каждый из данных алгоритмов может быть модифицирован для выполнения на параллельной ЭВМ. Однако каждый из них имеет разную степень параллелизации - степень, с которой данные алгоритмы могут быстрее выполняться на параллельной ЭВМ.

Распараллеливание многоуровневых алгоритмов дает высокую степень ускорения работы алгоритма. [10]

АЛГОРИТМЫ РАЗМЕЩЕНИЯ ГРАФА НА ЭВМ

В случае если целевая ЭВМ имеет статические линии связи, например Cray T3D (у которой коммуникационная сеть - трехмерный тор), Intel Paragon (коммуникационная сеть - двумерная прямоугольная решетка). То после этапа разбиения графа также требуется производить распределение кусков графа на ЭВМ потому как максимальный обмен данными должен производиться междй соседними элементами.

Для целевой ЭВМ строится матрица геометрии D, в которой находятся расстояния между соответствующими ПЭ. Расстояние между соседними ПЭ берется равным 1.

Тогда необходимо найти отображение, при котором обеспечивается экстремум целевой функции:

<>

dij - элемент матрицы геометрии

rij - элемент матрицы смежности.

Существует два вида алгоритмов для решения данной задачи:

- последовательный алгоритм размещения:

- итерационный алгоритм (который только улучшает разбиение).

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

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

ПРОГРАММЫ РАЗБИЕНИЯ ГРАФА

На текущий момент можно выделить 4 основные программы разбиения графа.

1. Библиотека METIS, разработанная в университете Миннесоты. В данной программе используются многоуровневые алгоритмы разбиения графа. Существуют модификации данной программы для разбиения гиперграфов (HMETIS) и для параллельного разбиения графа (PARMETIS). PARMETIS использует библиотеку передачи сообщений MPI, и основывается на параллельных многоуровневых алгоритмах. Функции данной библиотеки можно вызывать из программ, написанных на языках С и Fortran.

2. Библиотека SCOTCH, разработанная в университете г. Бордо [9]. В отличии от METIS данная библиотека предоставляет возможность не только разбивать граф, но и отображать его на целевую ЭВМ.

3. Библиотека JOSTLE, разработанная в университете г. Гринвич. Эта библиотека предназначена для параллельного или последовательного разбиения графов.

4. PARTY - это библиотека, разработанная в Heinz Nixdorf институте и университете г. Падерборн. Эта программа основывается на алгоритмах «бисекции» графа (деления пополам).

ПРОГРАММА МОДЕЛИРОВАНИЯ СДО РП С АВТОМАТИЧЕСКИМ РАСПРЕДЕЛЕНИЕМ НАГРУЗКИ

Опыт создания языков моделирования свидетельствует о том, что сейчас все большее распространение получают объектно-ориентированные языки моделирования, такие как Modelica, MVS, Omola, Simula, SmallTallk [13].

Графическое представление графов

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

Dot - свободно распространяемая программа компании Graphviz, которая служит для построения графов, используя информацию про топологию графа [16].

В качестве выходных данных программы могут быть разные файлы, как рисунки в форматах *.jpg, *.bmp, *.gif, *.png, так и в файлах формата PostScript и др.

Выходные рисунки исходного графа и полученного из него графа алгоритма приведены ниже.



Рисунок 5. Исходный граф. Рисунок 6. Полученный граф алгоритма.

Принцип передачи данных

Принцип построения системы передачи данных взят из концепции NUMA (Non Uniform Memory Access), представителем которых является BBN Butterfly [11]. Этот компьютер состоял из набора кластеров, которые соединялись через межкластерную шину. Каждый кластер соединял процессор, контроллер памяти, модуль памяти и некоторые устройства ввода/вывода. Когда процессору нужно было выполнить операции чтения или записи, он посылал запрос с необходимым адресом своему контроллеру памяти. Контроллер анализировал адрес, по которому и определял, в каком модуле содержаться необходимые данные. Если адрес локальный, то запрос выставлялся на локальную шину, в противном случае запрос отправлялся через межкластерную шину.

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

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

Таблицы маршрутизации заполняются уже во время начала моделирования, когда уже известно на каком процессорном находится тот или иной объект. Если объект хочет передать данные другому, который находится на этом же ПЭ, то данные записываются в локальную память по определенному адресу. В другом случае маршрутизатор посылает данные на другой ПЕ. Обмен данными выполняется при помощи механизма обмена сообщений MPI (Message Passing Interface) [14].

Рисунок 7. Общая схема обмена данными.

Синхронизация процессов и моделирование объектов

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

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

После того как какой-то объект вычислил свое значение, то оно записывается в память, или сразу при помощи MPI функции Isend отсылается к другому объекту, расположенному на другом ПЭ (при передаче данных при помощи этой функции ПЕ, который передает данные не ждет пока другой ПЕ примет эти данные). Это позволяет равномерно распределить нагрузку сети при передаче данных.

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

Общий алгоритм моделирования объектов представлен ниже.



Рисунок 8. Общая блок схема алгоритма моделлирования.

ЗАКЛЮЧЕНИЕ

В этой работе было выполнено исследование способов распределение вычислительной нагрузки для параллельных систем. Также на основе предыдущего опыта моделирования СДО, создания языков моделирования, создания языков параллельного моделирования и основных архитектур параллельных ЭВМ было создана объектно-ориентированная программа моделирования СДО с распределенными параметрами с автоматической балансировкой нагрузки.

Далее планируется исследование эффективности распределения нагрузки для СДО на разных архитектурах и с использованием разных алгоритмов разбиения графа. Также будет реализована динамическая балансировка нагрузки с целью возможности использования численных методов с переменным шагом, и возможности во время работы программы создавать новые объекты моделирования или удалять старые (т.е. менять структуру входного графа, описывающего топологию сети).

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

1. Schoegel K., Karypis G., Kumar. V. „Graph Partitioning for High Perfomance Scientific Simulations" CRPC Parallel Computing Handbook 2000, 40 с.

2. Elsner U. "Graph Partitioning", 1997, 52 с.

3. Diekmann R., Preis R. "Statische und dynamische Lastverteilung fьr parallele numerische Algorithmen", 1996, 35 с.

4. Diekmann R., Monien B., Preis R. "Load Balancing Strategies for Distributed Memory Machines".

5. Karypis G., Kumar V. "Multilevel k-way Partitioning Scheme for Irregular Graphs" 1998 г.

6. Кристофидес Н. Теория графов. М.: Наука, 1978, 398 с.

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

8. М. Гэри, Д. Джонсон "Вычислительные машины и труднорешаемые задачи" М.: Мир 1982, 230 с.

9. Pelligrini F. "Scotch and libScotch 3.4. User's Guide" 2001, 180 с.

10. Karypis G., Kumar V. "Parallel Multilevel k-way Partitioning scheme for Irregular Graphs" 1998, 45 с.

11. Воеводин В.В., Воеводин Вл. В. "Параллельные вычисления" СпБ. 2002, 490 с. [ 60-78, 219-324 стр.]

12. Hanf G. "Modellirung und Simulation der instationдren Grubenbewetterung auf verteilten Rechnerarchitekturen" Magdeburg 2002 г. [ с. 7-89 ]

13. Бенькович Е., Колесов Ю., Сениченков Ю. "Практическое моделирование динамических систем" СПб 2002 г. [стр. 127-208, 260-280]

14. MPI 2.0 Standart www.mpi-forum.org/docs

15. Буч Г. "Объектно-ориентированный анализ и проектирование" М. 2000 г. [стр. 21-256]

Размещено на Allbest.ru