Введение
Цель работы и возможная научная новизна:
Разработать моделирующее программное обеспечение, которое реализует функции подсистемы балансирования загрузки распределённой параллельной моделирующей среды, позволит улучшить дружественность РПМС к пользователям и разработчикам моделей, расширить сферу использования средств параллельного моделирования в разных предметных областях. Будут разработаны новые подходы к распараллеливанию, развита методика построения моделей сложных динамических систем в рамках функций подсистемы и экспериментально подтверждена целесообразность декомпозиции РПМС на подсистемы и работоспособность моделирующего программного обеспечения.
Основные задачи, подлежащие решению:
1. Анализ состояния разработок моделирующего программного обеспечения распределённой параллельной моделирующей среды.
2. Разработка концепций подсистемы (требования, функции, структура HW/SW-средств).
3. Разработка алгоритмов, структур, подходов, имплементация и экспериментальное исследование в составе версии РПМС.
Практическое значение работы:
Построение экспериментального образца подсистемы, использование моделирующего программного обеспечения в составе распределённой параллельной моделирующей среды. Тема работы является составной частью научного сотрудничества кафедры компьютерной инженерии с HLRS Штуттгартского университета. Результаты работы будут использованы в процессе обучения и в действующей РПМС.
Обзор исследований по теме
Одним из ключевых исследований по теме магистерской работы является статья из сборника научных работ ДонНТУ «Научная область: параллельное моделирование» [4]. Эта статья также была представлена как доклад на конференции ASIM-2009 (Advancing Substrate-Independent Minds) в качестве некоторого подведения итога научного сотрудничества ДонНТУ и Штуттгартского университета в области параллельного моделирования. В данной статье изложены основные концепции и определения, связанные с распределённой параллельной моделирующей средой (РПМС) и сложными динамическими системами (СДС), моделирование которых является областью научных интересов ДонНТУ. РПМС в целом рассматривается как сложная hardware/software-система, для проектирования которой целесообразно применить известный метод декомпозиции одной сложной задачи на подзадачи. Концепция декомпозиции РПМС на десять взаимодействующих подсистем (одной из которых является подсистема балансировки загрузки) также представлена в этой статье, описаны основные задачи, функции и требования к каждой из подсистем. Именно эта концепция декомпозиции РПМС на подсистемы положена в основу коллективного дипломного проекта.
Ещё одна ключевая статья по теме магистерской работы - «Девиртуализация виртуальных параллельных моделей сложных динамических систем по критериям балансирования загрузки» [5]. В этой статье предложена реализация отдельных компонентов модели загрузки распределенной параллельной моделирующей среды, обеспечивающих оптимальное выполнение моделей сложных динамических систем по критериям балансирования загрузки. Также вводится понятие девиртуализации виртуальной
параллельной модели и критерии девиртуализации применительно к параллельной модели сложной динамической системы, рассмотрены пути оптимизации виртуальной параллельной модели и собственно параллельной MPI-программы, реализующей эту модель.
Среди работ, выходящих за рамки ДонНТУ, стоит отметить работы профессора
Якобовского Михаила Владимировича
([11], [12], [13]). В данных работах проведены исследования статической и динамической балансировки загрузки применительно к различным задачам (в частности применительно к задачам интегрирования, к задачам горения и т.д.). Также рассматриваются критерии декомпозиции графов и сеточных моделей.
Основные результаты, имеющиеся к моменту написания автореферата
В настоящее время моделирование широко используется во многих отраслях науки и техники. Согласно определению в википедии, моделирование — исследование объектов познания на их моделях; построение и изучение моделей реально существующих объектов, процессов или явлений с целью получения объяснений этих явлений, а также для предсказания явлений, интересующих исследователя. Одним из самых популярных стал метод компьютерного моделирования, который предполагает в качестве модели компьютерную программу. Методика создания компьютерных моделей представлена в работе [4].
Большинству моделируемых объектов внутренне присуща сложность, которая переносится на компьютерную модель в виде вычислительной сложности моделирующей программы. В связи с большой вычислительной сложностью время выполнения моделирующей программы может превысить все допустимые границы. Для уменьшения времени выполнения моделирующей программы компьютерные модели должны быть распараллелены для параллельного выполнения на параллельной вычислительной машине. Таким образом, параллельная компьютерная модель (в дальнейшем параллельная программа) состоит из некоторого множества логических процессов, которые параллельно выполняются на некотором множестве процессоров параллельной вычислительной машины, взаимодействуют друг с другом посредством обменных (коммуникационных) операций и в совокупности решают задачу моделирования.
Сбалансированная загрузка вычислительных узлов (процессоров) подразумевает равномерную загруженность процессоров арифметическими операциями. Однако при сбалансированной загрузке процессоров арифметическими операциями может возникнуть дисбаланс нагрузки на сеть (коммуникационную среду), которая соединяет процессоры параллельной вычислительной машины между собой и обеспечивает обмен данными между логическими процессами. Таким образом, из-за перегрузки некоторых линий коммуникационной сети некоторые логические процессы могут простаивать большую часть своего времени в ожидании данных от других процессов, без которых они не могут продолжать свою работу.
Несбалансированность загрузки неизбежна по нескольким причинам, среди которых можно выделить неоднородность структуры модели (различные логические процессы требуют различных вычислительных мощностей) и неоднородность структуры параллельной вычислительной машины (различные вычислительные узлы могут иметь различную вычислительную мощность; между различными узлами может быть различная пропускная способность коммуникационной сети; в процессе работы параллельной программы могут освободиться ранее занятые узлы, которые могут быть использованы для разгрузки наиболее загруженных узлов или наоборот более привилегированный пользователь может запросить часть узлов для немедленного освобождения от текущей задачи с целью их использования в своей задаче; некоторые узлы могут использоваться одновременно для решения нескольких задач в режиме разделения времени, при этом доля процессорного времени, которая выделяется данным узлом на решение конкретной задачи, также может меняться в ту или иную сторону; некоторые вычислительные узлы или коммуникационные линии связи могут выйти из строя).
Таким образом, основной целью подсистемы балансировки загрузки является минимизация общего времени решения задачи (времени моделирования). При появлении новых заданий подсистема балансировки загрузки должна принять решение о том, где (на каком вычислительном узле) следует выполнять вычисления, связанные с этим новым заданием. Кроме того, балансировка предполагает перенос (миграцию) части вычислений с наиболее загруженных вычислительных узлов на менее загруженные узлы.
Балансировка загрузки применяется на двух этапах: на этапе декомпозиции задачи на подзадачи (процессы) и на этапе отображения этих процессов на вычислительную среду. Декомпозиция задачи является этапом процесса создания параллельной программы и предназначена для разделения приложения на подзадачи. В результате декомпозиции распределенного приложения появляется набор подзадач, которые параллельно решают задачу. Эти подзадачи могут быть независимыми или связанными друг с другом посредством обмена данными. Отображение подзадач на вычислительную среду является отдельным этапом, позволяющим распределить подзадачи, полученные на этапе декомпозиции, между процессорами.
Следует различать статическую и динамическую балансировки. Статическая балансировка выполняется до начала выполнения распределенного приложения. При распределении логических процессов по процессорам должен использоваться опыт предыдущих
выполнений. Однако предварительное размещение логических процессов по процессорам без каких-либо вмешательств во время выполнения не всегда даёт необходимый эффект по вышеописанным причинам неоднородности параллельной вычислительной машины и самого параллельного приложения. В таком случае целесообразно применять динамическую балансировку загрузки. Динамическая балансировка предусматривает перераспределение вычислительной нагрузки между узлами во время выполнения приложения. Программное обеспечение, реализующее динамическую балансировку загрузки, во время своей работы должно вычислять загрузку вычислительных узлов, пропускную способность линий связи, частоту обменов сообщениями между логическими процессами распределенного приложения и т.д. На основании собранных данных (как о распределенном приложении, так и вычислительной среде) принимается решение о переносе логических процессов с одного узла на другой. Обычно решение задачи балансировки загрузки состоит из четырех шагов: оценка загрузки вычислительных узлов, инициация балансировки загрузки, принятие решений о балансировке и перемещение объектов.
На этапе оценки загрузки вычислительных узлов для определения дисбаланса загрузки необходимы данные о работе процессора, которые включают загрузку процессора, время простоя процессора, скорость передачи информации по линиям связи и т.д., а также данные о работе распределенного приложения, которые включают время выполнения отдельной задачи, время простоя, интенсивность обмена информацией и др. Очень важно владеть такой информацией как коммуникационная модель. Коммуникационная модель содержит важную информацию для принятия решений о перемещении задач при балансировке загрузки. При необходимости переместить объект с перегруженного процессора A на недогруженный процессор B целесообразно выбрать для перемещения тот объект, который наиболее интенсивно сообщается с задачами, уже расположенными на B.
Оценка загрузки процессора и объекта может быть произведена несколькими способами. Один из способов (аналитический), обычно используемый при статической балансировке загрузки, состоит в приблизительной оценке загрузки каждого объекта на основе знаний о приложении. Этот метод позволяет предсказать предстоящее изменение загрузки и отреагировать на него. Недостаток же этого метода состоит в том, что он может быть довольно неточным в случае, если модель для оценки скорости выполнения приложений неточна. Другой способ сбора данных о загрузке состоит в измерении загрузки процессоров. Большинство современных вычислительных машин снабжено счетчиками времени (с точностью до микросекунд), которые могут быть использованы для измерения времени работы задачи и времени простоя. Приведенные два метода сбора данных о загрузке можно сочетать, дополняя метод, основанный на измерении производительности предсказывающей способностью аналитического метода оценки.
Слишком частое выполнение балансировки загрузки может привести к тому, что решение задачи только замедлится. Затраты на саму балансировку могут превзойти возможную выгоду от ее проведения. Следовательно, для продуктивности балансировки необходимо каким-то образом определять момент ее инициализации. Это может быть момент возникновения дисбаланса загрузки, определённый на основании измеренных значений загрузки процессоров или линий связи, либо предсказанный аналитически на основании знаний о структуре параллельного приложения. Далее следует определить степень необходимости балансировки путем сравнения возможной пользы от ее проведения и затрат на нее. При этом дисбаланс загрузки может определяться синхронно или асинхронно. При синхронном определении дисбаланса все процессоры прерывают работу в определенные моменты синхронизации и определяют дисбаланс загрузки путем сравнения загрузки отдельного процессора с общей средней загрузкой. При асинхронном определении дисбаланса каждый процессор хранит историю своей загрузки. В этом случае момент синхронизации для определения степени дисбаланса отсутствует. Вычислением объема дисбаланса занимается фоновый процесс, работающий параллельно с приложением. Таким образом, можно выделить централизованную и децентрализованную стратегии балансировки. При централизованной стратегии (рисунок 1) специальный управляющий процесс собирает глобальную информацию о состоянии всей вычислительной системы и принимает решение о перемещении задач для каждого из процессоров. При децентрализованной стратегии на каждом процессоре выполняется фоновый процесс, который занимается балансировкой загрузки и обменивается информацией о состоянии с другими процессорами.
Рисунок 1 - Основные этапы выполнения централизованной стратегии балансировки загрузки
Анимация состоит из 5 кадров, 6 циклов повторения, размер 492x322, объём - 116 КБ
Заключение
Для проведения балансировки загрузки во время решения целевой задачи необходимо разработать специальное программное обеспечение, которое включает в себя программные средства, обеспечивающие оценку состояния вычислительной среды, управляющую программу, принимающую решение о моменте проведения балансировки, и о том, какие логические процессы следует переместить с одного процессора на другой, а также программные средства, реализующие перемещение процесса с одного процессора на другой (миграции). В данный момент ведётся поиск и анализ возможностей различных библиотек для осуществления миграции процессов с учётом архитектуры и программных средств кластера ДонНТУ.
Важное замечание: При написании данного автореферата магистерская работа ещё не закончена. Окончательное завершение: 15 декабря 2011 г. Полный текст работы и материалы по теме могут быть получены у меня или у моего руководителя после указанной даты.
Литература
- Абрамов Ф.А., Фельдман Л.П., Святный В.А. Моделирование динамических процессов рудничной аэрологии. Киев, Наукова думка, 1981, 291 с.
- Святний В.А. Паралельне моделювання складних динамічних систем // Моделирование – 2006: Международная конференция. Киев, 2006 г. – Киев, 2006. – С. 83–90.
- Миков А.И., Замятина Е.Б., Козлов А.А. Оптимизация параллельных вычислений с применением мультиагентной балансировки. // Труды конференции ПАВТ-2009, с. 599-604, Нижний Новгород, Россия, 2009.
- Фельдман Л.П., Святный В.А., Рэш М., Цайтц М. Научная область: параллельное моделирование. / Научные работы Донецкого национального технического университета. Серия: Проблемы моделирования и автоматизации проектирования [Электронный ресурс]. — Режим доступа: http://www.nbuv.gov.ua/portal/natural/Npdntu/Pm/2008/08flpfps.pdf
- Надеев Д.В. Девиртуализация виртуальных параллельных моделей сложных динамических систем по критериям балансирования загрузки. / Научные работы Донецкого национального технического университета. Серия: Проблемы моделирования и автоматизации проектирования [Электронный ресурс]. — Режим доступа: http://www.nbuv.gov.ua/portal/natural/Npdntu_pm/2008/08ndvolb.pdf
- Cвятний В.А., Надєєв Д.В. Підсистема балансування завантаження ресурсів розподіленого паралельного моделюючого середовища. / Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка. (ИКВТ-02) випуск 39. – Донецьк, ДонНТУ. – 2002. – С. 264-270.
- Голуб С.В. Динамическая балансировка загрузки процессоров в многопроцессорных системах [Электронный ресурс] / Портал магистров ДонНТУ. — Режим доступа: http://masters.donntu.ru/2002/fvti/golub/magwork/index.html
- Xiao Qin, Hong Jiangy, Adam Manzanaresz, Xiaojun Ruan, Shu Yinyy Communication-Aware Load Balancing for Parallel Applications on Clusters [Электронный ресурс]. — Режим доступа: http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1051&context=csearticles&sei-redir=1
- Техническая документация по установке и использованию менеджера распределённых ресурсов для вычислительных кластеров torque [Электронный ресурс]. — Режим доступа: http://www.adaptivecomputing.com/resources/docs/torque/pdf/TORQUE_Administrator's_Guide.pdf
- Техническая документация по установке и использованию планировщика задач для вычислительных кластеров maui [Электронный ресурс]. — Режим доступа: http://www.adaptivecomputing.com/resources/docs/maui/pdf/mauiadmin.pdf
- Корнилина М.А., Якобовский М.В. Динамическая балансировка загрузки процессоров при моделировании задач горения. // Материалы конференции "Высокопроизводительные вычисления и их приложения", 30 октября - 2 ноября 2000 года, Черноголовка.
- Якобовский М.В. Балансировка загрузки процессоров [Электронный ресурс]. — Режим доступа: http://www.software.unn.ac.ru/ccam/files/ipa_f_2_01.pdf
- Якобовский М.В. Динамическая балансировка загрузки [Электронный ресурс]. — Режим доступа: http://lira.imamod.ru/lit/msu2009/MSU_5i.ppt