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

Надеев Д.В.

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

ndv@cs.donntu.ru

Источник: Национальная библиотека Украины имени В.И. Вернадского. Научные работы Донецкого национального технического университета. Серия: Проблемы параллельного моделирования и автоматизации проектирования

Аннотация

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

Анотація

Надєєв Д.В. Девіртуалізація віртуальних паралельних моделей складних динамічних систем за критеріями балансування завантаження. У статті запропоновано реалізацію окремих компонентів моделі завантаження розподіленого паралельного моделюючого середовища, які забезпечують оптимальне виконання моделей складних динамічних систем за критеріями балансування завантаження.
Ключові слова: компоненти, паралельне моделююче середовище, модель, динамічні системи.

Аbstract

Nadyeyev D.V. The devitalisation of complex dynamic systems' parallel models in terms of load ballancing. This article presents a realization algorithm for components of the distributed parallel simulation environment. The proposed algorithm provides the highest performance and productivity of simulation models in terms of load balancing characteristics.
Keywords: components, parallel simulation environment, model, dynamic system.

Введение

Одной из задач разработки распределенных параллельных моделирующих сред (РПМС) различного назначения [1-8] является эффективная реализация моделей сложных динамических систем на целевых параллельных вычислительных системах. Для решения этой задачи в РПМС была выделена подсистема балансирования загрузки [9] ее ресурсов, в рамках подсистемы определена структура модели загрузки РПМС [10, 11]. Рассмотрим реализацию отдельных компонентов модели загрузки, позволяющих оптимально выполнять моделирование сложных динамических систем, используя РПМС.

Определение девиртуализации виртуальной параллельной модели

Определение 1. Под девиртуализацией виртуальной параллельной модели (ВПМ) сложной динамической системы (СДС) будем понимать ее преобразование по методам и алгоритмам, обеспечивающим оптимальное исполнение заявки на моделирование СДС в целевой параллельной вычислительной системе (ЦПВС).
Предлагается выбрать два критерия девиртуализации: критерий равномерной загрузки процессоров ЦПВС и минимально возможное время выполнения обработки ВПМ в РПМС.
В параллельной распределенной моделирующей среде девиртуализацию следует проводить в три этапа:
  1. Распределение виртуальных процессов в группы по критерию равномерной загрузки.
  2. Определение оптимального количества процессоров, на которое должен распределить транслятор виртуальную параллельную модель по критериям минимизации времени выполнения и равномерности загрузки.
  3. Выбор целевой параллельной вычислительной системы для реализации модели, распределение групп виртуальных процессов на процессорное пространство выбранной ЦПВС. Эту функцию следует возложить на транслятор виртуальной параллельной модели.
На первых двух этапах девиртуализации возникает необходимость формирования нового коммуникационного графа. Эту функцию в распределенной параллельной моделирующей среде предлагается возложить на подсистему обмена данными [12].

Критерии девиртуализации виртуальной параллельной модели СДС

Параметры виртуальной параллельной модели предлагается определить в виде вектора:
PВПМ=V(n,E,T),
где n – количество виртуальных процессов,
E - вектор, состоящий из n элементов, выражающих количественную меру сложности виртуального процесса.
T – параметр, описывающий коммуникационный граф.
Определение 2. Под сложностью виртуального процесса будем понимать количественную меру объема работ, необходимого для получения выходных данных процесса на одном шаге моделирования. Исходя из выше изложенного, первый этап девиртуализации можно представить в виде фукнции D:
K=D(PВПМ),(1)
где K – вектор, описывающий критерии, которых необходимо достигнуть в процессе девиртуализации виртуальной модели на целевую параллельную вычислительную систему,
PВПМ - параметры виртуальной параллельной модели сложной динамической системы.
В нашем случае вектор K имеет следующий вид:
K{k1, k2},
где k1 – критерий равномерной загрузки ресурсов;
k2 – минимальное время моделирования.

Оптимизация виртуальной параллельной модели

Определим первый этап девиртуализации как метод оптимизации виртуальной параллельной модели по относительным сложностям виртуальных процессов:
1. Ищем виртуальный процесс с максимальной сложностью.
2. Вычисляем относительные сложности остальных виртуальных процессов относительно максимальной сложности. Получаем преобразованный вектор сложностей:
где i=1..n.(2)
Если возможно, распределяем виртуальные процессы по группам так, чтобы сумма сложностей процессов в группе стремилась к единице.
Определим пространство групп виртуальных процессов через динамический вектор с элементом:
tp={H,ec} – минимальное время моделирования.
где H - вектор, состоящий из номеров виртуальных процессов, входящих в данную группу виртуальных процессов, при этом в h0 находится длина этого вектора.
ec – сумма сложностей виртуальных процессов, входящих в группу.
Из выше написанного следует, что на первом этапе девиртуализации должен формироваться вектор Tp. Это реализуется следующим алгоритмом оптимизации ВПМ по относительным сложностям виртуальных процессов:
  1. В первую очередь распределяем процессы с относительной сложностью, равной 1.
  2. Затем из оставшихся нераспределенных виртуальных процессов ищем процесс с максимальной относительной сложностью, распределяем его в отдельную группу виртуальных процессов, получаем общую сложность процессов в группе;
  3. Ищем виртуальный процесс, сумма сложности которого с общей сложностью в данной группе виртуальных процессов наиболее приближена к единице; если находим такой, распределяем его в ту же группу процессов и вычисляем новую общую сложность для данной группы виртуальных процессов. Повторяем пункт три, пока из нераспределенных виртуальных процессов такой процесс невозможно будет найти, тогда переходим к пункту 2.
  4. Повторяем пункты 2 и 3, пока не останется не распределенных виртуальных процессов.
Для оценки эффективности оптимизации ВПМ предложены следующие формулы расчета критериев равномерной загрузки: до оптимизации ВПМ – k1b и после оптимизации – k1e.
(3)
где eip - относительная сложность виртуального процесса виртуальной параллельной модели,
n – количество виртуальных процессов.
(4)
где eic - относительная сложность i-ой группы виртуальных процессов после оптимизации виртуальной параллельной модели,
m – количество групп виртуальных процессов, на которое распределена виртуальная параллельная модель.
Критерий k2 при данном алгоритме оптимизации ВПМ соблюдается автоматически.

Оптимизация MPI-программ, реализующих виртуальные параллельные модели СДС

После получения оптимизированной виртуальной параллельной модели сложной динамической системы по критерию равномерной загрузки (вектор Tp) вычислительных ресурсов РПМС возникает задача отправки ее на обработку в целевую параллельную вычислительную систему (ЦПВС). Для этого она должна быть представлена в программном коде этой системы. Наличие различных параллельных вычислительных платформ требует использования единого представления ВПМ СДС, из которого возможно создать параллельный код для любой ЦПВС, входящей в РПМС. Для такого представления используется MPI-стандарт.
Определение 3. Девиртуализатор виртуальной параллельной модели – это набор программных средств подсистемы балансирования загрузки, обеспечивающих оптимальное размещение процессов ВПМ СДС на целевой параллельной вычислительной системе и трансляцию ВПМ в исполнительный код ЦПВС.
На девиртуализатор ВПМ предлагается возложить следующие функции:
  1. Формирование масштабируемой MPI-программы, реализующей виртуальную параллельную модель СДС.
  2. Нахождение оптимального количества процессоров, необходимых для моделирования СДС для всех параллельных вычислительных систем, входящих в РПМС.
  3. Транслирование масштабируемой MPI-программы в код целевой параллельной вычислительной системы.
В качестве целевых параллельных вычислительных систем в РПМС целесообразно использовать системы с так называемой скрытой топологией, которая предполагает гарантированный обмен данными на определенной скорости по схеме «каждый с каждым».
Предложена следующая формула времени расчета выполнения модели на ЦПВС с топологией «каждый с каждым»:
(5)
где i – идентификатор типа виртуального процесса;
a – количество виртуальных процессов в группе;
m – количество групп виртуальных процессов, из которых состоит оптимизированная виртуальная параллельная модель;
n – количество процессоров, на которые распределяются группы виртуальных процессов;
ki – коэффициент изменения времени выполнения виртуального процесса i-того типа от количества исходных данных;
r – коэффициент прироста производительности ЦПВС по сравнению с эталонной;
Ci – экспериментально полученное время выполнения виртуального процесса i-того типа для ki = 1 на эталонной ЦПВС;
BMPIS – общее количество данных, передаваемых через функции MPI одиночного обмена;
BMPIC – общее количество данных, передаваемых через функции MPI коллективного обмена;
BR – гарантируемая скорость передачи данных;
LT[n] – задержка функций обмена MPI.
Итак, получаем оптимальное количество процессоров для распределения программы для каждой ЦПВС:
Nopt=n[min(T(n))].(6)
После этого формируем векторы времен выполнения для каждой ЦПВС:
Tir={T(1),...,T(Nopt))},(7)
где ir – идентификатор целевой параллельной вычислительной системы.

Выводы

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

Литература

  1. Аноприенко А.Я., Святный В.А. Высокопроизводительные информационно-моделирующие среды для исследования, разработки и сопровождения сложных динамических систем. Наукові праці ДонДТУ. Серія "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 29. – Донецьк, ДонДТУ 2001. – С. 346 – 367.
  2. Надєєв Д., Ротермель К., Святний В.А., Солонін О.М., Степанов І.С., Цайтц М. Розподілене паралельне моделююче середовище. Збірник наукових праць ДонНТУ "Проблеми моделювання та автоматизації проектування динамічних систем". Вип. 29. – 2001. – С. 229-233.
  3. Святний В.А. Проблеми паралельного моделювання складних динамічних систем. Научные труды Донецкого государственного технического университета. Серия: Информатика кибернетика и вычислительная техника. (ИКВТ-99) выпуск 6. – Донецк, ДонГТУ 1999. – С. 104-113
  4. Святный В.А., Фельдман Л.П., Чепцов А.А. Проблемы параллельного моделирования сложных динамических систем. Первая международная научно-техническая конференция «Моделирование и компьютерная графика». – Донецк. – 4-7 октября 2005.
  5. Svjatnyj V.A., Nadeev D.V., Solonin A.N., Zeitz M., Rothermel K. Die Subsysteme einer verteilten parallelen Simulationsumgebung fur dynamische Systeme. Збірник наукових праць ДонНТУ "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 78. – 2005. – С. 261-268.
  6. Svjatnyj V., Masjuk A., Smagin.O., Bungartz H.-J. Interaktive Modellierung, Simulation und Prozessfuhrung in einer parallelen problemorientierten Simulationsumgebung. In: F.Hulsemann u.a. (Hrsg.). Tagungsband 18. ASIM-Symposium Simulationstechnik Erlangen 2005. – SCS 2005. – С. 742-747.
  7. Svjatnyi V.A., Feldman L.P., Lapko V.V., Gilles E.-D., Zeitz M., Reuter A., Rothermel K. Paralelle Simulationstechnik. Сборник научных работ ДонГТУ "Проблемы моделирования и автоматизированного проектирования динамических систем". Вып. 10. – 1999. – С. 9-19.
  8. Svjatnyj V.A., Gilles E.-D., Zeitz M., Reuter A., Rothermel K. Simulationssoftware fur eine verteilte parallele Simulationsumgebung fur dynamische Systeme. Збірник наукових праць ДонНТУ "Проблеми моделювання та автоматизованого проектування динамічних систем". Вип. 29. – 2001. – С. 12-17.
  9. Cвятний В.А., Надєєв Д.В. Підсистема балансування завантаження ресурсів розподіленого паралельного моделюючого середовища. Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка. (ИКВТ-02) випуск 39. – Донецьк, ДонНТУ. – 2002. – С. 264-270.
  10. Rothermel K. Grundlagen der verteilten Systeme. – IPVR der Universitat Stuttgart. 1998.
  11. Надеев Д.В. Структура модели загрузки распределенной параллельной моделирующей среды. Збірник наукових праць ДонНТУ "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 78. – 2006. – C. 44-52.
  12. Солонин А.Н. Подсистема обмена информацией распределенной параллельной моделирующей среды. Наукові праці ДонДТУ. Серія "Проблеми моделювання та автоматизації проектування динамічних систем". Випуск 52. – Донецьк, ДонДТУ. – 2002. – С. 35-40.