Методы и средства децентрализованного диспетчирования ресурсов GRID для решения связных задач тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Каляев, Анатолий Игоревич

• Каляев, Анатолий Игоревич
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Каляев, Анатолий Игоревич

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПРИНЦИПЫ ОРГАНИЗАЦИИ ДЕЦЕНТРАЛИЗОВАННОГО ДИСПЕТЧИРОВАНИЯ В GRID

1.1. Анализ существующих способов организации работы GRID

1.1.1 Система Globus

1.1.2. Система Condor

1.1.3. Система AppLeS

1.1.4. Система Х-СОМ

1.2. Обобщенная модель современной GRID-системы

1.3. Проблемы современных GRID-систем

1.4. Принципы децентрализованной мультиагентной организация диспетчера GRID

1.5. Метод децентрализованной мультиагентной организации диспетчера в GRID

1.6. Выводы к главе 1

ГЛАВА 2. МЕТОДЫ ОРГАНИЗАЦИИ МУЛЬТИАГЕНТНОГО ВЗАИМОДЕЙСТВИЯ ПРИ ДИСПЕТЧИРОВАНИИ GRID

2.1. Метод формирования пользовательской задачи

2.2. Метод создания сообщества агентов для решения пользовательской задачи

2.3. Методы распределения подзадач в сообществе агентов

2.3.1. Метод полного перебора

2.3.2. Метод градиентного спуска

2.3.3. Метод имитации отжига

2.3.4. Метод адаптивного распределения подзадач в сообществе агентов

2.4. Комбинированный метод создания сообщества и распределения подзадач в нём

2.5. Выводы к главе 2

ГЛАВА 3. ПРОГРАММНЫЕ СРЕДСТВА МУЛЬТИАГЕНТНОГО ДИСПЕТЧЕРА GRID

3.1. Структура программных средств

3.2. Сайт и база данных

3.3. Оболочка пользователя

3.4. Доска объявлений

3.5. Алгоритмы работы агента Агент GRID

3.5.1. Алгоритм работы в режиме «Инициализация»

3.5.2. Алгоритм работы в режиме «Выбор задачи»

3.5.3. Алгоритм работы в режиме «Ожидание»

3.5.4. Алгоритм работы в режиме «Вступление в сообщество»

3.5.5. Алгоритм работы в режиме «Выбор подзадачи»

3.5.6. Алгоритм работы в режиме «Выполнение подзадачи»

3.6. Программная модель GRID с мультиагентным диспетчером

3.7. Исследование эффективности предложенных методов и алгоритмов мультиагентного диспетчирования GRID

3.8. Выводы к главе 3

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

ПРИЛОЖЕНИЕ 3

Введение диссертации (часть автореферата) на тему «Методы и средства децентрализованного диспетчирования ресурсов GRID для решения связных задач»

ВВЕДЕНИЕ

Актуальность работы. Еще в 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 г., №ГР 01200852907;

- СЧ ОКР «Разработка программных средств организации вычислительного процесса на базе мультиагентного диспетчера» (шифр «Премьер - ОВП ФПО») по договору №593220 с ОАО «Концерн радиостроения «ВЕГА»;

Грант РФФИ «Разработка методов и алгоритмов децентрализованного распределения ресурсов в GRID-структурах» (шифр «Поиск-2») №08-07-00249а;

- НИР «Разработка методов и алгоритмов повышения надежности и эффективности бортовых информационно-управляющих систем» (шифр «Агент 2»), №ГР 01201263488;

- Грант РФФИ «Разработка адаптивных методов диспетчирования вычислений в децентрализованной вЯГО» (шифр «Поиск-3») №11-07-00463а, №ГР 01201164292.

Результаты диссертации внедрены и нашли применение в:

- ОАО «Концерн радиостроения «ВЕГА» при создании алгоритма оптимизации распределения вычислительной загрузки, обеспечивающего организацию децентрализованного диспетчирования бортовой информационно-вычислительной системы изделия А-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 получены автором лично.

Таким образом, в диссертации решена новая научная задача, которая является актуальной и имеет существенное научно-практическое значение.

Список литературы диссертационного исследования кандидат технических наук Каляев, Анатолий Игоревич, 2013 год

ЛИТЕРАТУРА

1. I. Foster, С. Kesselman, eds., The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Francisco, 1999.

2. Foster, C. Kesselman, S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. / International I. Supercomputer Applications, 15(3), 2001.

3. Николай Виноградов Анализ современного состояния ГРИД проектов в мире //let Info online - информационный бюллетень компании "Инфосистемы Джет" URL:

http://www.jetinfo.ru/stati/?nid=0161 d223cb9ed29f66470cbf7931 ае22 (Дата обращения: 23.02.2012).

4. Foster, С. Kesselman, J. Nick, S. Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. / Open Grid Service Infrastructure WG, Global Grid Forum, June 22, 2002

5. Коваленко B.H., Коваленко Е.И., Корягин Д.А., Любимский Э.З., Хухлаев Е.В., Шорин О.Н. Грид-диспетчер: реализация службы диспетчеризации заданий в грид / Труды международной конференции "Распределенные вычисления и Грид-технологии в науке и образовании" (Дубна, 29 июня-2 июля 2004 г.). - Дубна: 11-2004-205, ОИЯИ, 2004, сс. 133-139.

6. Каляев А.И., Герасименко И.С. Об одном подходе к мониторингу и управлению вычислительным процессом в децентрализованных информационно-управляющих системах / Тезисы докладов Пятой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. -С.133 134.

7. Полежаев Петр Николаевич Экспериментальное исследование алгоритмов планирования задач для грид-систем с использованием симулятора / Материалы Международная конференция «Высокопроизводительные вычисления» HPC-UA'2012 (Украина, Киев, 810 октября 2012 года)

8. Ивашко Е.Е., Головин А.С. Вычислительная эффективность BOINC-GRID / Материалы Международная конференция «Высокопроизводительные вычисления» HPC-UA'2012 (Украина, Киев, 810 октября 2012 года) С187-193

9. Distributed Computing Technologies, Inc. URL: Distributed.net (Дата обращения: 25.02.2012).

10. Search for ExtraTerrestrial Intelligence at home. Поиск Внеземного Разума на дому URL: http://setiathome.ssl.berkeley.edu (Дата обращения: 25.11.2011).

11. Каляев А.И. Разработка и исследование новых децентрализованных методов организации вычислительного процесса в информационно-управляющих системах / Тезисы докладов Четвертой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2008. - С. 101 102.

12. Michael Wooldridge, An Introduction to MultiAgent Systems, John Wiley & Sons Ltd, 2002, paperback, 366 pages, ISBN 0-471-49691-Х.

13. Каляев А.И., Мельник Э.В. Об одном способе децентрализованной организации вычислений в GRID - About one way of the decentralized organization of calculations in grid / Экстремальная робототехника. // Труды международной конференции с элементами научной школы для молодежи. - СПб: Изд-во «Политехника-сервис» 2010.- С. 73-75

14. Каляев А.И. Об одном способе децентрализованного

построения GRID-системы / Высокопроизводительные вычислительные

170

системы // Материалы Седьмой Международной научной молодежной школы. - Таганрог: Изд-во ТТИ ЮФУ, 2010. - С.263-267

15. Каляев А.И., Мельник Э.В. Об одном способе децентрализованной организации вычислений в GRID / Материалы научно-технического семинара «Управление в распределенных сетецентрических и мультиагентных системах». - СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2010. - С.71-74

16. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям. Эдиториал УРСС, М., 2002.

17. N. Hirose and М. Fukuda (1997). "Numerical Wind Tunnel (NWT) and CFD Research at National Aerospace Laboratory". Proceedings of HPC-Asia '97. IEEE Computer Society. doi:10.1109/HPC.1997.592130.

18. Timothy G. Mattson An Overview of the Intel TFLOPS Supercomputer // MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) URL:

http://www.ai.mit.edu/projects/aries/course/notes/ascii_red.pdf (Дата обращения: 25.11.2012).

19. The TOP500 statistics // The TOP500 project URL: http://i.top500.org/stats (Дата обращения: 02.09.2012).

20. Great Internet Mersenne Prime Search GIMPS URL: http://www.mersenne.org/ (Дата обращения: 26.11.2012).

21. NEESgrid URL: http://www.neesgrid.org (Дата обращения: 29.09.2011).

22. AccessGrid.org URL: http://www.accessgrid.org (Дата обращения: 29.09.2011).

23. Butterfly.net project URL: http://Butterfly.net (Дата обращения: 29.09.2011).

24. HP DETAILS StorageWorks GRID STRATEGY // DSStar URL: http://www.taborcommunications.com/dsstar/04/Q921/109032.html (Дата обращения: 29.09.2011).

25. Grid MP Overview URL: http://www.univa.com/products/grid-mp (Дата обращения: 29.09.2011).

26. GLOBUS Toolkit URL: http://www.globus.org/toolkit/ (Дата обращения: 12.11.2011).

27. Computing with HTCondor // The Department of Computer Sciences at the University of Wisconsin-Madison URL: http://www.cs.wisc.edu/condor/downloads (Дата обращения: 12.11.2012).

28. Francine Berman Adaptive Computing on the Grid Using AppLeS URL: http://walfredo.dsc.ufcg.edu.br/papers/10369.pdf (Дата обращения: 19.12.2012).

29. С.И. Соболев. Архитектура нового поколения системы метакомпьютинга Х-Сот // Распределенные вычисления и Грид-технологии в науке и образовании. Труды третьей международной конференции. Дубна, 30 июня - 4 июля 2008 г. С. 123-126.

30. Каляев А.И., Мельник Э.В. Об одном способе децентрализованной организации вычислений в GRID / Материалы научно-технического семинара «Управление в распределенных сетецентрических и мультиагентных системах». - СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2010. - С.71-74

31. В. А. Васильев, М. В. Крапошин, А.Ю. Ницкий, А. В. Юскин ПРИМЕНЕНИЕ НРС-ТЕХНОЛОГИЙ ДЛЯ РЕШЕНИЯ ПРОСТРАНСТВЕННЫХ ЗАДАЧ МУЛЬТИФИЗИКИ / Вычислительные методы и программирование. 2011. Т. 12 С160-169

32. И.М. ГОРЮНОВ СТРУКТУРНО-ПАРАМЕТРИЧЕСКИЙ СИНТЕЗ И АНАЛИЗ ГТД И ЭУ Вестник УГАТУ Т. 11, №2 (29). С. 30-38

33. И. А. КРИВОШЕЕВ, Д. А. АХМЕДЗЯНОВ, А. Е. КИШАЛОВ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ РАБОТЫ АВИАЦИОННЫХ ГТД С ЭЛЕМЕНТАМИ СИСТЕМ УПРАВЛЕНИЯ // Вестник УГАТУ Т. 11, №2(29). С. 3-11

34. Каляев А.И. Методы адаптивного распределения вычислительной нагрузки в децентрализованной GRID / VII ежегодная научная конференция студентов и аспирантов базовых кафедр Южного научного центра РАН: Тезисы докладов - Ростов н/Д: Изд-во ЮНЦ РАН, 2011. - С.124-125

35. Каляев А.И. Мультиагентная организация облачных вычислений на базе сети компьютеров частных пользователей / «Высокопроизводительные вычислительные системы» Труды молодых ученых ЮФУ и ЮНЦ РАН, Таганрог: Изд-во ЮФУ, 2012, С68-72

36. Каляев А.И. Об одном способе снижения стоимости GRID-вычислений за счет децентрализации функций диспетчирования / Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010) // Материалы международной научно-технической конференции. Т. 2. - Таганрог: Изд-во ТТИ ЮФУ, 2010. -С. 45-49

37. Каляев А.И., Мельник Э.В. Об одном способе децентрализованной организации GRID-вычислений / Инфокоммуникационные и вычислительные технологии и системы: материалы III Международной конференции. - Улан-Уде: Издательство Бурятского госуниверситета, 2010. - С.160-162

38. И.А. Каляев, Э.В. Мельник Децентрализованные системы компьютерного управления - Ростов н/Д: Издательство ЮНЦ РАН, 2011г.

39. Каляев А.И. Децентрализованная организация диспетчера GRID на базе сообществ агентов / Известия ЮФУ. Технические науки. №8, 2011г.- Таганрог: Изд-во ТТИ ЮФУ.- С. 230-238.

40. Каляев А.И. Метод и алгоритмы адаптивной организации распределенных вычислений в децентрализованной GRID / Вестник компьютерных и информационных технологий. №4, 2012г.- Москва: Изд-во "СПЕКТР".- С. 28-33.

41. Kalyaev A.I. Method and algorithms of the adaptive organization of the distributed computations in a decentralized GRID / International Young Scientists Conference High Performance Computing and Simulation 2012. Book of abstracts. - C.55-56

42. Peter Biddle, Paul England, Marcus Peinado, and Bryan Willman The Darknet and the Future of Content Distribution URL:

http://msl 1 .mit.edu/ESD 10/docs/darknet5.pdf (Дата обращения: 19.01.2013).

43. Каляев А.И. Об одном подходе к снижению стоимости GRID-вычислений / Тезисы докладов Шестой ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. -Ростов-на-Дону: Изд-во ЮНЦ РАН, 2010. - С. 102 103

44. Каляев А.И. Мультиагентный диспетчер для организации распределенных вычислений в GRID / Материалы 4 Всероссийской мультиконференции по проблемам управления-Таганрог: Изд-во ТТИ ЮФУ, 2011.-С. 301-302.

45. И. Е. Федотов Модели параллельного программирования Изд-во: "Солон-Пресс", 2012, 384 стр.

46. Каляев А.И. Метод децентрализованной организации облачных сервисов для решения сложных задач / VIII ежегодная научная конференция студентов и аспирантов базовых кафедр Южного научного центра РАН: Тезисы докладов - Ростов н/Д: Изд-во ЮНЦ РАН, 2012.-С.126-127.

47. Каляев А.И. Разработка и использование программной модели распределенной вычислительной системы в обучении / Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT09". Научное издание в 4-х томах. - М.: Физматлит, 2009, Т.З. - С. 119-123

48. Каляев А.И. Применение адаптивных методов при

диспетчировании децентрализованной GRID / 4-я Всероссийская

мультиконференция //Материалы 4 Всероссийской мультиконференции

174

по проблемам управления-Таганрог: Изд-во ТТИ ЮФУ, 2012. - С. 303304.

49. JI.A. Растригин. Статистические методы поиска.- М.:Наука,

1968.

50. Костенко В.А. Проблемы разработки итерационных алгоритмов для построения расписаний с одновременным нахождением необходимого количества ресурсов и их характеристик // Искусственный интеллект (Донецк), 2002. No 2, С. 141-150.

51. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

52. Каляев А.И. Методы адаптивного распределения вычислительной нагрузки в децентрализованной GRID / ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ Труды молодых ученых Южного федерального университета и Южного научного центра РАН -Таганрог: Изд-во ТТИ ЮФУ, 2012. - С. 84-91.

53. Каляев А.И. Разработка алгоритма взаимодействия между подзадачами в отказоустойчивых распределенных информационно-управляющих системах / Материалы Международной научно-технической конференции Высокопроизводительные вычислительные системы - 2008 (ВПВС-2008) -Таганрог: Изд-во ТТИ ЮФУ, 2008. -С.408 409.

54. Каляев А.И. Об одном методе размещения задач в коллективе вычислителей, основанном на планировании времени решения задачи / Материалы 2-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии», Изд-во: Издательство Южного федерального университета, Ростов н/Д, 2012, С294-297

55. Блуишвили И.В., Радченко С.А., Каляев А.И. Программная модель мультиагентной конфигурации / Материалы Международной научно-технической конференции Многопроцессорные вычислительные

и управляющие системы (МВУС-2007). -Таганрог: Изд-во ТТИ ЮФУ, 2007.-С. 315-316.

56. Горелова Г.В., Мельник Э.В., Радченко С.А, Каляев А.И. Планирование эксперимента при исследовании новых методов и алгоритмов организации распределенных вычислений / Вестник информационных и компьютерных технологий - М.: Машиностроение, 2007, №10,2007г. - С.49-56

57. Семенистый С.А., Мельник Э.В., Каляев А.И. Имитатор программных средств организации вычислительного процесса в децентрализованной отказоустойчивой вычислительной системе. Свидетельство о государственной регистрации программы для ЭВМ №20088614265 от 05.09.2008 г.

КОД ХМЬ-ФАЙЛА ДЕСКРИПТОРА СИШ С ДЕЦЕНТРАЛИЗОВАННЫМ ДИСПЕТЧЕРОМ

Каляев Анатолий Игоревич

МЕТОДЫ И СРЕДСТВА ДЕЦЕНТРАЛИЗОВАННОЙ ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ В GR.ro

Специальность: 05.13.11 - Вычислительные машины, комплексы и

компьютерные сети

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата технических наук

Научный руководитель: доктор технических наук Капустин Сергей Григорьевич

П1. КОД XML-ФАИЛА ДЕСКРИПТОРА GRID С ДЕЦЕНТРАЛИЗОВАННЫМ ДИСПЕТЧЕРОМ

Код xml-файла дескриптора, сгенерированного оболочкой пользователя:

<?xml version="l.О" encoding="UTF-8" ?> <task id="12345"> - идентификатор задачи <owner>123</owner> - идентификатор пользователя задачи <price>2000</price> - стоимость решения задачи < complexity >1000</ complexity > - сложность задачи <gain>2</gain> - выгодность задачи

<parallelism>2</parallelism> - степень

распараллеливаемости

<time>123453523345345</time> - момент времени в секундах, к которому должна быть решена задача

<subtasks number="5"> - раздел поддазач

<subtask id="l"> - подзадача 1, идентификатор

подзадачи

<exefile>taskl.exe</exefile> - исполняемый файл <complexity>200</complexity> - сложность <datain>0</datain> - идентификаторы входных

данных

<dataout>l,2</dataout> </subtask>

<subtask id="2"> - подзадача 2

<exefile>task2.exe</exefile>

< complexity >300</ complexity > <datain>l</datain> <dataout>3</dataout>

</subtask>

<subtask id="3"> - подзадача 3

<exefile>task3.exe</exefile>

< complexity >100</ complexity > <datain>2</datain> <dataout>4</dataout>

ид-ры исходящих данных

</subtask>

<subtask id="4"> - подзадача 4

<exefile>task4.exe</exefile>

< complexity >200</ complexity > <datain>3</datain> <dataout>5</dataout>

</subtask>

<subtask id="5"> - подзадача 5

<exefile>task5.exe</exefile>

< complexity >200</ complexity > <datain>4,5</datain> <dataout>6</dataout>

</subtask> </subtasks>

<datafiles> - раздел файлов данных

<datafile id="0" size="l">fileO.jpg</datafile> - файл данных

<datafile id="l" size="l">filel.jpg</datafile> <datafile id="2" size="2">file2.jpg</datafile> <datafile id="3" size="l">file3.jpg</datafile> <datafile id="4" size="3">file4.jpg</datafile> <datafile id="5" size="l">file5.jpg</datafile> <datafile id="6" size="l">file6.jpg</datafile> </datafiles>

<graph> - граф задачи в виде таблицы смежности 0,1,0,2,0; 0,0,3,0,0; 0,0,0,0,4; 0,0,0,0,5; 0,0,0,0,0; </graph>

<layers> - распределение подзадач по ярусам графа 1;

2,3; 4;

5;

</layers> </task>

АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ

РАБОТЫ

Каляев Анатолий Игоревич

МЕТОДЫ И СРЕДСТВА ДЕЦЕНТРАЛИЗОВАННОЙ ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ В GRID

Специальность: 05.13.11 - Вычислительные машины, комплексы и

компьютерные сети

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата технических наук

Научный руководитель: доктор технических наук Капустян Сергей Григорьевич

^«ЩЕРЖДАЮ» по .науке f у QAÖ «КЩерн «Вега», ft- ^4%нсАфессор

Ж-f А.Т. Силкин

2013 г.

АКТ

о внедрении результатов диссертационной работы

Каляева Анатолия Игоревича «Методы и средства мультиагентного диене[чирования ресурсов GRID для решения связных задач», представляемой на соискание ученой степени кандидата технических наук.

Комиссия в составе: A.B. Васильев - главный конструктор изделия А-100, к.т.н., председатель, К.Н. Иванов - первый замес! и гель главного конструктора изделия А-100, Ю.В. Данчаков - заместитель главного конструктора изделия А-100 составила настоящий акт в том, что результаты диссертационной работы Каляева Анатолия Игоревича «Методы и средства мультиагентного диспетчирования ресурсов GRID для решения связных задач», представляемой на соискание ученой степени кандидат гехнических наук, внедрены ОАО «Концерн «Вега» в изделие А-100 в составе программных средств, разработанных в рамках СЧ ОКР «Разработка программного средства организации вычислительного процесса на базе мультиа! ен июго управления вычислительными ресурсами».

Разработанный в рамках диссертационного исследования Каляева А.И. метод распределения подзадач в сообщесч ве агентов был использован с целью реализации алгоритма оптимизации распределения вычислительной нагрузки, обеспечивающего организацию децентрализованного диспетчирования бортовой информационно-вычислительной системы изделия А-100.

Применение разработанного Каляевым А.И. метода позволило значительно сократить время отклика бортовой информационно-управляющей системы.

Председатель комиссии: ^^А.В.Васильев

4j></- & ' с

Члены комиссии: vi?.г/? К.Н.Иванов

' — Ю.В. Данчаков

АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ

РАБОТЫ

Каляев Анатолий Игоревич

МЕТОДЫ И СРЕДСТВА ДЕЦЕНТРАЛИЗОВАННОЙ ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ В вЯГО

Специальность: 05.13.11 - Вычислительные машины, комплексы и

компьютерные сети

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата технических наук

Научный руководитель: доктор технических наук Капустян Сергей Григорьевич

г

МИНИСТЕРСТВО ОЬРАЗОПАНИЯ И НАУКИ РОГ< ИЙГКОН ФЕДЕРАЦИИ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ VHHBEPCm ET

Научно-исследовательский нистигут многопроцессорных вычислительных систем имени академика A.B. Каляева федерального государственного автономною образовательной о учреждения высшего профессионально» о образования «Южный федеральный университет» __НИИ многопроцессорных вычислительных систем ЮФУ_

ул.Чехова,2, ГСП-284. ¡.Таганрог. Ростовская область,Россия,347928 Тел. [phone], Fax [phone], 615-459 e-mail: [e-mail] littp://www.mvs.sfMu.ru Получатель: ИНН-6163027810 КПП-б 15431008 р/с-405038101(Ш1ХЮ003022 в Филиале Jin 5 ОАО КБ «Центр-инвест», г. Таганрог к/с 30101810700000000943 в РКЦ. г. Таганрога БИК 046013993 ОКНО 02070157, ОКВЭД 73.10, '4J0, ОКОГУ 13240, ОКЛТО 6043^000000, ОКФГ 12, ОКОПФ 90

19 QU №i2> дг 60¿.fí OS-¿S/í

Hd№

> ч' -Утверждаю Замл;дирекП'ора':ЦИИ MBC ЮФУ ,Н. Котов

АКТ ^J^

о внедрении ре!ультатов диссертационной работы

Каляева Анатолия Игоревича «Методы и средства мультнагсшною диспетчировапия ресурсом GRID для решеиия святых задач», представляемой на соискание ученой ыепени кандидата технических наук по специальности 05.1J.11 «Магсы;иическое и программное обеспечение вычислительных машин, комплексов и компьютерных cctcíi».

Комиссия в составе зам директора НИИ МВС ЮФУ д.т н Левин Илья Израилевич, председатель, зав лабораторией ПИИ МВС ЮФУ к г.н Мельник Эдуард Всеволодович, с н.с. НИИ МВС ЮФУ к.тн Поюрелов Констанши Владимирович составила настоящий ata о том, что результаты диссертационном риСнмы Каляева Анатолия Игоревича «Ме годы и срсдсца чультиа! ей inoro диспстчирования ресурсов GRID для решения связных задач», представляемой на соискание ученой степени кандидата технически наук по специальности 05 13.11, внедрены в Научно-исс 1едовательскоч инсштуте МП01 опроцессорных нычислительных систем имени академика Д.В Каляева федеральною госудлрс!венного автономного образовательного учреждения высшего профессионального образования «Южный Федеральный Университет» при выполнении НИР «Разрабо1ка методов и средств повышения безопасности и эффективности функционирования распределенных информационно-управляющих систем сложных техногенных обьекюв» (шифр «Деиентрализация-3») ГК 02.514.11 4085 oí 08 08 2008

В указанной НИР при реализации алгоритмов распределенных вычислений в РИУС быт внедрен препложенный в дисссрыции Каляева Л И. метод распределения подзадач в сообществе агеншв Это подтверждается мспериалами. представленными в отчете по НИР за 2009 год (peí истрационный номер 01200852907, инвен гарный номер 02200954490)

Исследования, проведенные с использованием разработанных в ходе НИР программных средств, показали, что применение предложенных Каляевым А.И методов позволило сни$игь время отклика инфорчациинно-управляющих систем, построенных на базе персональных компьютеров, до двух раз.

Председатель комиссии:

Члены комиссии

SFedU Acad Kalyaev Scientific Research Institute of Multiprocessor Computer Systems

2 Chekhov il GSP-284, 1 agmirog 347928 Ruwia Plwnc, +7 S<>3 \) f ax (-■> 8631) jbOJifi 61 ->-4:9

F mjil mys^im1, itcdu ru hup tivntv, .rvs slcjj ru

Левин И И

Мельник O.B

-у Погорелов К В.