Актуальность работы. Еще в 1960 году Джон Маккарти, получивший премию Тьюринга за работы в области искусственного интеллекта, говорил, что «вычислительная деятельность может быть со временем организована как общественная услуга». После этого потребовалось более тридцати лет, чтобы технологии достигли такого уровня, который позволил задумываться о практической реализации этой идеи. В середине 1990;х годов Ян Фостер из Аргоннской Национальной лаборатории и Чикагского университета и Карл Кессельман из Института информационных наук Университета Южной Калифорнии (США) вели активную работу в области объединения гетерогенных, географически распределенных ресурсов в единую инфраструктуру и предложили термин, который стал символом новой эпохи компьютерных технологий — GRID [1]. Этот термин произошёл от английского слова «grid» (буквальный перевод «решетка»), точнее от «power grid», что означает «электросеть» или «энергосистема». Статус компьютерных инфраструктур того времени можно было сравнить с состоянием электрических систем в самом начале 20 века. Тогда необходимость для каждого пользователя иметь свой генератор тормозила развитие отрасли. Революционным шагом стало возникновение электросетей, создание технологий передачи и распределения электроэнергии, создание стандартизованной службы универсального и гарантированного доступа к электроэнергии. В результате не только резко повысилась эффективность и снизалась стоимость использования электрических ресурсов, но и стали возможны принципиально новые направления развития.
В основополагающей работе [1] GRID-компьютинг определяется как «использование мощных вычислительных ресурсов, прозрачно доступных посредством коммуникационной среды». Основной идеей GRID-компьютинга является объединение и предоставление путем удаленного доступа заинтересованным пользователям разнообразных вычислительных ресурсов [2].
С момента появления GRID было создано множество различных GRID-систем [3], однако принципы их организации практически не изменились. Современные GRID строятся, как правило, по иерархической схеме: имеется некоторое количество (от одного и более) выделенных служебных вычислительных узлов (СВУ) — серверов, реализующих функции управления работой GRID, а так же множество исполнительных вычислительных узлов (ИВУ) — компьютеров, выполняющих непосредственно полезные вычисления. В общем виде современная GRID-система работает следующим образом: пользователь отправляет свою задачу в систему, задача попадает на СВУ, реализующий функции диспетчера, который выбирает ИВУ для решения задачи и отправляет её туда на решение [4]. Как только решение задачи на ИВУ завершено, результаты отправляются обратно на служебный сервер, а оттуда заинтересованному пользователю. Именно на такую схему построения вычислительной сети ориентировано большинство современных программных комплексов для организации GRID-компьютинга.
Основным управляющим элементом системы при этом является диспетчер GRID. Под диспетчером GRID понимается набор программно-аппаратных средств, отвечающих за распределение ресурсов GRID при решении поступающих задач [5]. Именно диспетчер занимается подбором ИВУ для решения поступающих задач, поэтому от него зависит эффективность работы системы в целом.
Как правило, эффективность работы диспетчера GRID оценивается исходя из уровня загрузки ИВУ системы, которая в свою очередь определяется коэффициентом полезной загрузки (КПЗ) ИВУ — отношением процессорного времени, потраченного ИВУ системы на решение полезных задач, поступающих в GRID, к общему времени их работы. В современных.
GRID значение КПЗ в высокой степени зависит от: 5.
1) оперативности нахождения исполнителей для поступающих задач;
2) интенсивности обменов данными между ИВУ в процессе решения задачи;
3) числа изменений параметров ИВУ или их отказов, требующих от диспетчера перемещения задач на другие ИВУ [6].
Эти обстоятельства определяют сферу применения большинства современных GRID — решение слабосвязных задач, не требующих интенсивных обменов данными между ИВУ.
В то же время существует широкий круг задач, которые не могут быть разбиты на множество отдельных не связанных друг с другом частей из-за необходимости обмена данными между ними. В дальнейшем такие задачи будем называть «связными задачами», а их отдельные части — подзадачами. Решение таких задач в GRID потребует интенсивного обмена данными между ИВУ системы.
В качестве одного из примеров таких задач можно привести задачу моделирования газотурбинных двигателей (ГТД). В настоящее время для этого используется так называемый метод структурного моделирования, когда общая модель ГТД строится в виде набора взаимосвязанных моделей его отдельных элементов. Данная модель, как правило, представляется в виде графа, вершинами которого являются модели отдельных элементов ГТД, а дугами — информационные связи между ними.
Как было сказано выше, основным отличием связных задач от несвязных является необходимость передачи данных между ИВУ, реализующих отдельные части (подзадачи) такой структурной модели. Это в свою очередь делает необходимым планирование последовательности решения подзадач, так как подзадачи не могут быть запущены без входных данных, которые в свою очередь будут получены только по итогам выполнения других подзадач. Процесс передачи данных между подзадачами таких задач является достаточно сложным, так как эти данные должны приниматься от одного из ИВУ, храниться до момента запуска подзадач, которым они необходимы, и передаваться другим ИВУ. Все это приводит к существенному снижению КПЗ GRID-системы.
Например, результаты исследований в области загрузки современных GRID [7] показывают, что в среднем КПЗ ИВУ GRID при решении несвязных задач на сегодняшний день колеблется от 75 до 90%. В то же время, при решении связных задач этот параметр оказывается существенно ниже — около 40% [8]. При этом процессы передачи данных между узлами GRID занимают порядка 30% времени работы, а более 20% времени работы ИВУ GRID простаивает.
На этапе своего становления GRID-системы строились в основном на базе оборудования, выделенного лицом, заинтересованным в решении своих задач, однако со временем за счет распространения локальных и глобальных сетей стали появляться системы, ориентированные на использование компьютеров, находящихся в частных руках [9] [10]. Низкая стоимость их организации и эксплуатации позволили появиться множеству проектов, использующих для своей работы удаленные вычислительные ресурсы ПК, предоставляемые владельцами бесплатно или за небольшие деньги. В качестве примера системы, строящейся таким образом, можно привести проект seti@home [10], основной целью которого является поиск внеземных сигналов искусственного происхождения за счет обработки данных, поступающих с радиотелескопа. Особенностью данного проекта является то, что пользователи добровольно предоставляют свои вычислительные ресурсы для работы в рамках системы seti@home. Таким образом, использование вычислительных ресурсов ПК, находящихся в руках частных пользователей — ИВУ-«фрилансеров» (по аналогии с фрилансерами, работающими удаленно), является наиболее экономически выгодным, и поэтому сегодня очень актуальна задача использования таких 7 вычислительных ресурсов. Однако большинство задач, решаемых в GRID, построенных на базе ИВУ-«фрилансеров», являются несвязными. При решении же связных задач в GRID, построенных на базе персональных компьютеров (ПК), находящихся в частных руках, возникает необходимость динамического изменения плана решения задачи в случае изменения параметров ИВУ в зависимости от действий его владельца (например, загрузка дополнительными задачами или отключение) [11]. Действительно, после составления плана решения задачи СВУ производительность какого-либо ИВУ может заметно сократиться (вплоть до полного отключения данного ИВУ), что приведет к увеличению времени решения его подзадач или даже к невозможности их решения. Это в свою очередь приведет к простоям других ИВУ, ожидающих решения его подзадач. Простои в работе оборудования приведут к тому, что время полезной работы ИВУ сократится, таким образом, эффективность их работы упадет. Поэтому КПЗ GRID-систем, построенных на базе ПК частных владельцев, при решении связных задач в общем случае будет еще ниже, чем КПЗ современных GRID.
Указанные недостатки могут быть частично устранены, если сделать процесс диспетчирования GRID более гибким и адаптивным, например, если учитывать особенности задачи при выборе ИВУ, делегировать ИВУ возможность прямого взаимодействия друг с другом, отслеживать и оперативно реагировать на изменения в параметрах ИВУ. Для того чтобы достичь этого предлагается переместить часть функций диспетчирования с.
СВУ GRID на множество ИВУ. Тогда за счет того, что множеству ИВУ будет доступно больше информации о вычислительной сети и задачах, станет возможным обмен данными между ИВУ напрямую. Кроме того, это позволит оперативно отслеживать изменения в параметрах ИВУ, что позволит строить более эффективные GRID на базе вычислительных ресурсов частных пользователей. Для этого предлагается на каждом ИВУ системы разместить проактивного представителя — программного агента 8 далее для краткости просто агента) [12] [13]. Тогда диспетчирование GRID будет осуществляться путем взаимодействия независимых агентов, каждый из которых представляет интересы своего ИВУ-«фрилансера». Для решения каждой из поступающих в GRID задач агенты должны объединяться в сообщество, ресурсов которого хватает для решения задачи за требуемое время [14]. Процессы распределения и решения задач внутри сообщества так же могут контролироваться таким мультиагентным диспетчером. При этом каждый из агентов должен осуществлять постоянный мониторинг параметров своего ИВУ, что позволит реагировать на любые изменения его параметров и оперативно учитывать эти изменения в процессе диспетчирования.
Потенциальными преимуществами такого подхода к диспетчированию GRID являются:
— возможность более эффективного решения связных задач за счет прямого взаимодействия ИВУвысокая эффективность работы в условиях динамически изменяющихся параметров исполнительных узлов за счет оперативного учета изменения параметров ИВУ и возможности эффективного распределения подзадач в сообществе агентов;
— простота масштабирования, так как нет необходимости добавлять в GRID-систему новые СВУ в случае увеличения количества ИВУ системы;
— более низкие требования к инфраструктуре, так как отсутствует необходимость содержания СВУ, необходимых для диспетчирования системы [15].
Таким образом, актуальной проблемой является разработка методов и средств децентрализованного диспетчирования ресурсов GRID-систем на базе мультиагентного подхода.
Цель работы. Целью работы является повышение коэффициента полезной загрузки GRID, построенных на базе ИВУ частных владельцев.
ИВУ-«фрилансеров»), при решении связных задач. 9.
Объект исследований. Объектом исследований являются методы и средства диспетчирования ресурсов в GRID.
Научная задача работы. Основная научная задача работы заключается в разработке методов и программных средств организации децентрализованного мультиагентного диспетчирования работы GRID в условиях динамически изменяющихся параметров ИВУ, позволяющих повысить коэффициент полезной загрузки GRID при решении связных задач при незначительном снижении процента решенных за отведенное время пользовательских задач.
В процессе решения основной научной задачи необходимо решить следующие частные задачи:
— провести анализ способов организации GRID-систем;
— разработать обобщенную модель GRID для оценки КПЗ системы;
— разработать метод децентрализованной мультиагентной организации диспетчера в GRID;
— разработать метод формирования пользовательской задачи в виде, подходящем для использования в децентрализованной GRID;
— разработать метод создания сообщества агентов для решения пользовательской задачи;
— разработать метод распределения подзадач в сообществе агентов;
— разработать структуру и алгоритмы работы программных средств мультиагентного диспетчера GRID;
— создать программную модель GRID с мультиагентным диспетчером;
— провести исследования эффективности разрабатываемых методов и средств мультиагентного диспетчирования на программной модели.
Методы исследования. Для достижения поставленной цели и решения сформулированных научных задач в ходе работы использовались методы теории множеств, теории графов и теории алгоритмов, теории коллективного принятия решений и теории построения мультиагентных систем (мультиагентности) [11][16]. Экспериментальные исследования осуществлялись с помощью многокритериального имитационного моделирования работы распределенной системы по специально разработанному плану.
Научная новизна работы. В диссертации разработаны и исследованы новые методы и средства децентрализованной организации диспетчирования работы GRID в условиях динамически изменяющихся параметров исполнительных узлов, в том числе:
1) метод децентрализованной мультиагентной организации диспетчера в GRID, отличающийся переносом функций диспетчирования на множество ИВУ GRID и использованием принципов мультиагентного взаимодействия между ними;
2) метод создания сообщества агентов для решения пользовательской задачи, отличающийся использованием оценки времени их решения с целью минимизации состава сообщества;
3) метод распределения подзадач в сообществе агентов, отличающийся возможностью учета текущих параметров исполнительных вычислительных узлов в процессе решения задачи;
4) комбинированный метод создания сообщества и распределения подзадач в нём, отличающийся предварительным планированием процесса решения задачи в целом, а так же адаптивным изменением плана решения задачи в случае, если в результате изменения параметров исполнительных вычислительных узлов предложенный ранее план решения становится невыполнимым;
Практическая значимость работы. Разработанные в диссертации методы и программные средства обеспечивают:
1) возможность создания GRID-систем на базе ПК частных владельцев, что существенно снижает стоимость вычислений за счет отсутствия необходимости затрат на содержание, обслуживание и замену ИВУ;
2) снижение стоимости вычислений за счет отсутствия в системе дорогостоящих служебных серверов и инфраструктуры по их обслуживанию;
3) повышение КПЗ GRID, построенных на базе ПК частных владельцев, при решении связных задач до 75%.
Реализация и внедрение результатов работы. Полученные в ходе работы над диссертацией практические и теоретические результаты были использованы при выполнении ряда НИР и ОКР. К наиболее значимым из них относятся:
— НИР «Разработка и исследование методов и средств повышения безопасности и эффективности функционирования распределенных информационно-управляющих систем сложных технических объектов» (шифр 2008;04−1.4−15−06−003) по государственному контракту № 02.514.11.4085 от 08.08.08 г., №ГР 1 200 852 907;
— СЧ ОКР «Разработка программных средств организации вычислительного процесса на базе мультиагентного диспетчера» (шифр «Премьер — ОВП ФПО») по договору № 593 220 с ОАО «Концерн радиостроения «ВЕГА»;
Грант РФФИ «Разработка методов и алгоритмов децентрализованного распределения ресурсов в GRID-структурах» (шифр «Поиск-2») № 08−07−249а;
— НИР «Разработка методов и алгоритмов повышения надежности и эффективности бортовых информационно-управляющих систем» (шифр «Агент 2»), №ГР 1 201 263 488;
— Грант РФФИ «Разработка адаптивных методов диспетчирования вычислений в децентрализованной вЯГО» (шифр «Поиск-3») № 11−07−463а, №ГР 1 201 164 292.
Результаты диссертации внедрены и нашли применение в:
— ОАО «Концерн радиостроения «ВЕГА» при создании алгоритма оптимизации распределения вычислительной загрузки, обеспечивающего организацию децентрализованного диспетчирования бортовой информационно-вычислительной системы изделия А-100 (Приложение 2);
— НИИ МВС ЮФУ при реализации алгоритмов распределенных вычислений в РИУС (Приложение 3).
Достоверность полученных результатов. Работоспособность разработанных методов и алгоритмов в различных режимах работы подтверждается непротиворечивостью математических выкладок, экспериментами, проведенными помощью программной модели, практическим внедрением результатов работы, экспертизами научных работ, прошедшими при получении грантов РФФИ и Фонда содействия развитию малых форм предприятий в научно-технической сфере, апробацией научных результатов на международных, всероссийских и региональных конференциях.
Апробация работы. Основные научные результаты работы докладывались и обсуждались на международных, всероссийских и региональных научных конференциях, в том числе:
1) региональные научно-технические конференции шестая, седьмая, восьмая ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН. (Ростов-на-Дону, Таганрог, 2010, 2011, 2012 гг.);
2) международная научно-техническая конференция «Экстремальная робототехника» (Санкт-Петербург, 2010 г.);
3) международные научно-технические конференции «Суперкомпьютерные технологии: разработка, программирование, применение» (СКТ-2010, СКТ-2012) (Дивноморское, 2010, 2012 гг.);
4) международные научные молодежные школы Высокопроизводительные вычислительные системы (Дивноморское, 2010, 2011,2012);
5) всероссийский научно-технический семинар «Управление в распределенных сетецентрических и мультиагентных системах» (Санкт-Петербург, 2010 г.);
6) международная научно-техническая конференция «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Уде, 2010 г.);
7) 4-я Всероссийская мультиконференция по проблемам управления (Дивноморск, 2011 г.);
8) международная конференция «High Performance Computing and Simulation» (Амстердам, 2012);
9) всероссийская конференция «Управление в технических, эргатических, организационных и сетевых системах» (Санкт-Петербург, 2012).
Публикации. По теме диссертации опубликовано 26 научных работ: 7 статей, из которых 3 — статьи в ведущих рецензируемых журналах и изданиях, рекомендуемых ВАК РФ для публикации результатов работ по диссертациям на соискание ученой степени, 17 материалов и тезисов научных конференций, 1 свидетельство об официальной регистрации программ для ЭВМ, а так же 7 отчетов о НИР.
Положение диссертации, выдвигаемое для защиты:
— мультиагентная организация диспетчера GRID позволяет повысить КПЗ ресурсов GRID при решении связных задач в условиях динамически изменяющихся параметров ИВУ при незначительном снижении процента решенных за отведенное время пользовательских задач.
Основные результаты диссертации, выдвигаемые для защиты.
— метод децентрализованной мультиагентной организации диспетчера в GRID;
— метод создания сообщества агентов для решения пользовательской задачи;
— метод распределения подзадач в сообществе агентов;
— комбинированный метод создания сообщества и распределения подзадач в нем.
Структура и объем диссертации
Диссертационная работа состоит из введения, трех глав, заключения, списка используемых литературных источников и трех приложений. Общий объем работы — 184 листа.
3.8. Выводы к главе 3.
1) Определены состав и структура программных средств GRID, достаточных для практической реализации предложенных методов и алгоритмов, и схема взаимодействия между различными элементами системы при решении поступающих задач,.
2) Предложены алгоритмы работы сайта и базы данных GRID, позволяющие пользователям и исполнителям присоединяться к GRID и хранить всю необходимую информацию, при этом не делают систему централизованной.
3) Разработаны схема и алгоритм работы оболочки пользователя GRID, позволяющие пользователю формировать и отправлять свою задачу на решение в виде, подходящем для решения в GRID.
4) Предложены схема и алгоритм работы доски объявлений GRID, позволяющие осуществлять взаимодействие между пользователями и исполнительными вычислительными узлами в рамках GRID.
5) Разработаны алгоритмы работы агента GRID в различных режимах, полностью регламентирующие процесс работы агента GRID на всех этапах его работы.
6) Разработана программная модель GRID, позволяющая проводить исследование виртуальных децентрализованных GRID для различных комбинаций параметров GRID-системы.
7) Предложена схема проведения исследования разработанных методов и алгоритмов с помощью программной модели, позволяющая сократить количество проводимых экспериментов для оценки влияния различных параметров системы и задач на эффективность работы GRID.
8) На базе разработанной программной модели проведено исследование эффективности предложенных методов и алгоритмов.
9) На основании проведенного исследования было показано, что средний КПЗ ИВУ при решении связных задач в большинстве исследованных режимов работы не опускается ниже 75%, что существенно выше (на 35%), чем у существующих GRID-систем.
ЗАКЛЮЧЕНИЕ
.
В настоящей работе решена научная задача разработки методов и алгоритмов мультиагентного диспетчирования ресурсов в GRID для решения связных задач в условиях динамически изменяющихся числа и параметров исполнительных вычислительных узлов. Предложенные в работе методы и алгоритмы позволяют строить GRID-системы на базе вычислительных ресурсов ИВУ, находящихся в частных руках, что позволяет заметно снизить стоимость вычислений в GRID, а также существенно повысить КПЗ ИВУ при решении связных задач, требующих интенсивных информационных обменов.
При проведении исследований и разработок по теме настоящей работы получены следующие теоретические и прикладные результаты, обладающие научной новизной:
1) Проведен анализ существующих в настоящее время GRID-систем. Предложена их модель GRID-системы, позволяющая оценить коэффициент полезной загрузки системы при решении пользовательских задач.
2) На основании предложенной модели сделан вывод, что КПЗ современных GRID-систем существенно снижается в случае решения связных задач, требующих интенсивных информационных обменов между подзадачами, а так же в случае организации GRID на базе ПК частных владельцев (ИВУ-«фрилансеров»), параметры которых могут динамически изменяться в процессе работы GRID.
3) Предложен метод мультиагентной децентрализованной организации диспетчера в GRID построенной на базе ИВУ-«фрилансеров», позволяющий повысить КПЗ GRID при решении связных задач.
4) Предложен метод создания сообщества агентов для решения пользовательской задачи, отличающийся оценкой времени решения задачи с целью уменьшения количества агентов, участвующих в её решении.
Предлагаемый метод позволяет создавать сообщества размера, достаточного для решения пользовательской задачи в требуемый срок.
5) Разработан метод распределения подзадач в сообществе агентов, отличающийся учетом текущих параметров исполнительных вычислительных узлов при назначении очередной подзадачи для решения на ИВУ. Предложенный метод позволяет оптимизировать распределение подзадач между узлами сообщества для уменьшения времени решения задачи.
6) Предложен комбинированный метод создания сообщества и распределения подзадач в нем, отличающийся предварительным планированием процесса решения задачи в целом, а так же адаптивным изменением плана решения задачи случае, если в результате изменения параметров исполнительных вычислительных узлов предложенный ранее план решения был невыполним. Данный метод позволяет сократить время решения задачи за счет распараллеливания процессов создания сообщества и распределения подзадач в нем.
7) Предложена методика проведения исследования разработанных методов и алгоритмов с помощью программной модели, позволяющая сократить количество проводимых экспериментов для оценки влияния различных параметров системы и задач на эффективность работы GRID.
8) На базе разработанной программной модели проведено исследование эффективности предложенных методов и алгоритмов.
9) На основании проведенного исследования было показано, что средний КПЗ ИВУ при решении связных задач в большинстве исследованных режимов работы не опускается ниже 75%, что существенно выше (на 35%), чем у существующих GRID-систем.
Основные научные результаты диссертационной работы опубликованы в работах [6][11][13−15][30][34−37][39−41][43−44][46−48][52−57].
Все научные результаты, полученные при решении научной задачи разработки методов и алгоритмов мультиагентного диспетчирования ресурсов в GRID получены автором лично.
Таким образом, в диссертации решена новая научная задача, которая является актуальной и имеет существенное научно-практическое значение.
