автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства децентрализованного диспетчирования ресурсов GRID для решения связных задач

На правах рукописи

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

Методы и средства мультиагентного диспетчировання ресурсов вИШ для решения связных задач

Специальность: 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата технических наук

Таганрог - 2013

005531980

005531980

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» (ЮФУ) на кафедре «Интеллектуальные и многопроцессорные системы» (ИМС) и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика А.В. Каляева федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» (НИИ МВС ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук

Капустян Сергей Григорьевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ

Крукиер Лев Абрамович, доктор физико-математических наук, профессор, Южно-Российский региональный центр информатизации, директор

ВЕДУЩАЯ ОРГАНИЗАЦИЯ

Мельников Андрей Кимович, кандидат технических наук, в.ч. 33949, ведущий советник

Федеральное государственное автономное научное учреждение НИИ «Спецвузавтоматика»

Защита диссертации состоится «28» июня 2013 годав 14.20 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корпус «И», комната 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «Ш> мая 2013.

Просим Вас прислать 347928, г. Таганрог, ГСП Южного федерального диссертационного совета

Ученый секретарь диссертационного совета

ечатью учреждения, по адресу: ехнологический институт ому секретарю Павловичу.

А.П. Кухаренко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В середине 1990-х годов Ян Фостер и Карл Кессельман предложили термин, который стал символом новой эпохи компьютерных технологий - GRID. Основной идеей GRID-компыотинга является объединение и предоставление путем удаленного доступа заинтересованным пользователям разнообразных вычислительных ресурсов. С момента появления GRID было создано множество различных GRID-систем, однако принципы организации подобных систем практически не изменились. Современные GRID строятся, как правило, по иерархической схеме: имеется некоторое количество (от одного и более) выделенных служебных вычислительных узлов (СВУ) - серверов, реализующих функции управления работой GRID, а также множество исполнительных вычислительных узлов (ИВУ) - компьютеров, выполняющих непосредственно вычисления. Основным управляющим элементом системы при этом является диспетчер GRID - набор программных средств, отвечающих за распределение вычислительных ресурсов GRID при решении поступающих пользовательских задач. От того, каким образом организована работа диспетчера GRID, во многом зависит эффективность работы системы в целом. При этом эффективность работы GRID, как правило, оценивается, исходя из уровня загрузки ИВУ системы, и может быть определена с помощью коэффициента полезной загрузки (КПЗ) ИВУ, который рассчитывается как отношение процессорного времени, потраченного ИВУ системы на решение полезных задач, поступающих в GRID, к общему времени их работы.

В современных GRID диспетчер, как правило, реализуется с помощью специально выделенных СВУ, полностью контролирующих работу системы, что существенно усложняет процедуры взаимодействия между ИВУ. Поэтому высокая эффективность работы в таких GRID достигается в основном при решении задач, которые могут быть разбиты на отдельные информационно несвязанные подзадачи, в то время как при решении связных задач, требующих интенсивных информационных обменов между подзадачами, их КПЗ резко снижается. В качестве примера таких связных задач можно привести задачи структурного моделирования сложных мехатронных объектов, например газотурбинного двигателя. Результаты исследований в области загрузки современных GRID показывают, что в среднем КПЗ ИВУ GRID при решении несвязных задач колеблется в пределах от 75 до 90%, в то время как при решении связных задач этот параметр оказывается существенно ниже - менее 40%. При этом процессы передачи данных между узлами GRID занимают порядка 30% времени работы, а около 20% времени ИВУ GRID простаивает.

На этапе своего становления GRID-системы строились в основном на базе оборудования, выделенного лицом, заинтересованным в решении своих задач, однако со временем за счет распространения и развития локальных и глобальных сетей стали появляться системы, ориентированные на использование компьютеров, находящихся в частных руках, т.е. ИВУ-«фрилансеров» (по аналогии с фрилансерами, работающими удаленно). Использование таких ресурсов является экономически выгодным, т.к. резко

снижаются затраты на их содержание и обслуживание. Однако, с другой стороны, использование таких ресурсов существенно усложняет процесс диспетчирования GRID, так как параметры ИВУ-«фрилансеров» могут непредсказуемо изменяться в процессе решения задачи по воле их владельцев. Поэтому, при решении связных задач в GRID, построенных на базе таких ИВУ-«фрилансеров», составленный диспетчером план решения задачи может в любой момент потерять свою актуальность в случае изменении параметров ИВУ, задействованных в ее решении, а это в свою очередь вызовет дополнительные простои оборудования, что еще сильнее снизит КПЗ системы.

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

Цель работы. Целью работы является повышение коэффициента полезной загрузки GRID, построенных на базе ИВУ частных владельцев (ИВУ-«фрилансеров»), при решении связных задач.

Объект исследований. Объектом исследований являются методы и средства диспетчирования ресурсов в GRID.

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

В процессе решения основной научной задачи необходимо было решить следующие частные задачи:

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

- разработать метод децентрализованного мультиагентного диспетчирования ресурсов GRID;

- разработать метод представления пользовательской задачи в виде, удобном для использования в децентрализованной GRID; \ '

- разработать метод создания сообщества агентов для решения пользовательской задачи;

- разработать метод распределения подзадач в сообществе агентов;

- разработать алгоритмы работы агента ИВУ в различных режимах;

- разработать алгоритмы работы программных средств децентрализованной

GRID;

- создать программную модель GRID с мультиагентным диспетчером;

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

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

Научная новизна работы. В диссертации разработаны и исследованы методы и средства децентрализованной мультиагентной организации диспетчера 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; Грант РФФИ «Разработка адаптивных методов диспетчирования вычислений в децентрализованной GRID» (шифр «Поиск-3») №11-07-00463а, №ГР 01201164292.

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

- ОАО «Концерн радиостроения «ВЕГА» при создании алгоритма оптимизации распределения вычислительной загрузки, обеспечивающего организацию деце1ггрализованного диспетчирования бортовой информационно-вычислительной системы изделия А-100 (акт о внедрении от 12 апреля 2013г.);

- НИИ МВС ЮФУ при реализации алгоритмов распределенных вычислений в РИУС (акт о внедрении от 29 апреля 2013г.).

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

Апробация работы. Основные научные результаты работы докладывались и обсуждались на международных, всероссийских и региональных научных конференциях, в том числе: региональные научно-технические конференции шестая, седьмая, восьмая ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН. (Ростов-на-Дону, Таганрог, 2010, 2011, 2012 гг.); международная научно-техническая конференция «Экстремальная робототехника» (Санкт-Петербург, 2010 г.); международные научно-технические конференции «Суперкомпьютёрные технологии: разработка, программирование, применение» (СКТ-2010, СКТ-2012) (Дивноморское, 2010, 2012 гг.); международные научные молодежные школы Высокопроизводительные вычислительные системы (Дивноморское, 2010, 2011, 2012); всероссийский научно-технический семинар «Управление в распределенных сетецентрических и мультиагентных. системах» (Санкт-Петербург, 2010 г.); международная научно-техническая конференция «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Уде, 2010 г.); 4-я Всероссийская мультиконференция по проблемам управления (Дивноморск, 2011 г.); международная конференция «High Performance Computing and Simulation» (Амстердам, 2012);

всероссийская конфренция «Управление в технических, эргатических, организационных и сетевых системах» (Санкт-Петербург, 2012).

Публикации. По теме диссертации опубликовано 26 научных работ: 7 статей, из которых 3 - статьи в ведущих рецензируемых журналах и изданиях, рекомендуемых ВАК РФ для публикации результатов работ по диссертациям на соискание ученой степени, 18 материалов и тезисов научных конференций, 1 свидетельство об официальной регистрации программ для ЭВМ, а так же 7 отчетов о НИР.

Положение диссертации, выносимое на защиту:

- мультиагентная организация диспетчера GRID позволяет повысить КПЗ ресурсов GRID при решении связных задач в условиях динамически изменяющихся параметров ИВУ при незначительном снижении процента решенных за отведенное время пользовательских задач.

Основные результаты диссертации, выносимые на защиту:

- метод мультиагентного диспетчирования ресурсов в GRID;

- метод создания сообщества агентов для решения пользовательской задачи;

- метод распределения подзадач в сообществе агентов GRID;

- комбинированный метод создания сообщества и распределения подзадач в

нем;

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации посвящена разработке принципов "и метода мультиагентного диспетчирования ресурсов в GRID.

В начале главы проведен анализ ряда современных GRID-систем и предложена их обобщенная модель, позволяющая оценить коэффициент полезной загрузки (КПЗ) системы при решении пользовательских задач. С помощью данной модели показано, что КПЗ современных GRID-систем существенно снижается в случае решения связных задач, требующих интенсивных информационных обменов между подзадачами, а так же в случае организации GRID на базе ПК частных владельцев (ИВУ-«фрилансеров»), параметры которых могут динамически изменяться в процессе работы GRID.

Для того, чтобы повысить КПЗ GRID, построенной на базе ИВУ-«фрилансеров», при решении связных задач, предложено переместить большую часть функций диспетчирования со служебного уровня СВУ непосредственно на уровень исполнителей - ИВУ-фрилансеров. При этом основными взаимодействующими

элементами системы становятся реализуемые на ИВУ программные агенты, представляющие интересы владельцев ИВУ-фрилансеров в процессе работы GRID. Основными отличиями предложенной схемы построения GRID-системы от существующих является то, что диспетчирование работы GRID будет осуществляться за счет прямого взаимодействия агентов друг с другом, что, в свою очередь, позволяет снизить непродуктивные потери времени при организации информационных обменов между ИВУ и, как следствие, повысить КПЗ. Кроме того, каждый из агентов может самостоятельно осуществлять мониторинг параметров своего ИВУ и оперативно учитывать все эти изменения в процессе диспетчирования.

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

На основе приведенных соображений разработаны принципы децентрализованного мультиагентного диспетчирования ресурсов в GRID (см. рисунок 1). Пользователь GRID у себя на ПК формирует задачу для решения, задает требования по времени ее решения в GRID и предлагаемую оплату, которую он готов заплатить за ее решение. После этого он отправляет эту информацию на ДО. Агенты GRID, не занятые решением каких-либо задач, с некоторой периодичностью опрашивают ДО на предмет наличия нерешенных пользовательских задач. Если такая задача обнаруживается, то для ее решения создается сообщество агентов, причем агенты включаются в сообщество до тех пор, пока оценочное время решения задачи сообществом не станет меньше времени, указанного пользователем. Когда в сообществе набирается количество агентов, достаточное для решения задачи в указанный пользователем срок, расширение сообщества прекращается. В созданном таким образом сообществе агенты совместно производят распределение подзадач между их ИВУ, при этом распределение осуществляется таким образом, чтобы минимизировать общее время решения пользовательской задачи. Как только подзадачи размещены по ИВУ, агенты запускают процесс их решения. При этом агенты производят постоянный мониторинг параметров своих ИВУ (производительность, скорость доступа к сети и т.п.). В случае если параметры какого-либо ИВУ сообщества существенно изменяются, то его агент оповещает остальных членов сообщества об этом, и сообщество может перераспределить подзадачи с учетом этих изменений, либо вообще изменить свой состав в случае необходимости, например, добавить новых агентов. Как только задача полностью решена, результат ее решения отправляется на ДО и далее пользователю, а агенты получают часть баллов, предложенных пользователем за решение задачи пропорционально их вкладу (объему произведенных вычислений), после чего сообщество распускается.

Пол ьзовател ьский уровень

Формирование , задачи

!— Отправка задачи [на выполнение

Пользовательский интерфейс

Служебный уровень ■

- Обмен |

Информацией о ¡задачах

© Q О

Исполнительный

уровень

- - Создание сообщества

- Мониторинг параметров ИВУ

- Распределение частей задачи в сообществе

- Решение задачи

- Передача данных между ИВУ

- Отправка результатов

Рисунок 1 - Схема GRID-системы с децентрализованным мультиагентным

диспетчером.

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

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

Прежде чем передать задачу для решения на доску объявлений пользователь GRID должен представить её в виде, понятном системе. Для этого в диссертации предложена представлять пользовательскую задачу в виде графа G(Q,X), каждой вершине q;6Q которого ставится в соответствие исполняемый модуль 1-й подзадачи, а так же значение S;, определяющее ее вычислительную сложность, а каждой дуге x(qi,qj)6X приписывается объем данных Dij, передаваемый между подзадачами qi и qj и соответствующий файл данных. Далее полученный таким образом граф G(Q,X) представляется в ярусно-параллельной форме, указывается последовательность решения подзадач, а также определяется степень распараплеливаемости задачи М как наибольшее количество подзадач в ярусе. Кроме того, пользователь должен указать к

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

Для решения пользовательской задачи в вычислительной сети GRID должно быть сформировано сообщество агентов, способных решить задачу за отведенное пользователем время, т.е. ТреЦ|епш1<Т0СТ, где Тост - оставшееся для решения задачи время, а Трешки, - время решения задачи сообществом, причем Трешешм= Трп + Твп + Тсс, где Тсс - время создания сообщества, Трп - время распределения подзадач, Твп - время выполнения подзадач, а Тосг=Тмах-Т*, где Т* - текущий момент времени, Тмах - время решения задачи, указанное пользователем. Для этого свободные агенты должны периодически опрашивать ДО для поиска «неполных» задач, причем, поскольку количество агентов в системе в общем случае может быть намного больше, чем количество ДО, то для того, чтобы избежать перегрузки канала связи ДО целесообразно сделать так, чтобы агенты имели возможность опрашивать ДО только с определенным временным интервалом Тожиданм. С другой стороны, если агенты будут обращаться к ДО с большой временной задержкой, то время решения задачи создания сообщества в системе может существенно увеличиться. Чтобы избежать этого, предлагается использовать принцип приглашения агентов в сообщество другими агентами, уже участвующими в сообществе по решению пользовательской задачи.

Далее в главе дана формальная постановка задачи создания сообщества агентов для решения пользовательской задачи: найти такой минимальный набор ИВУ { С}, который будет удовлетворять следующим условиям :

- Трп + Твп < Го,-,., где 7*о*ст~Тмах-Т*- Тсс - время, оставшееся после завершения процесса создания сообщества;

- N<M, где N =[С|. - количество агентов в сообществе, M - степень распараллеливаемости пользовательской задачи.

Перед вступлением в сообщество, агент должен первым делом оценить целесообразность своего участия в решении данной задачи. Такую оценку агент может осуществить на основе двух параметров задачи - ее общей трудоемкости S-и ее стоимости О. На основании отношения 0/S, агент может оценить относительную выгодность V решения данной задачи. Если для выбранной задачи значение V= O/S выше установленной владельцем агента минимальной величины Уш1п, то агент принимает решение о вступлении в сообщество для решения данной задачи.

Поскольку в общем виде значения Трп и Твп зависят от состава сообщества и распределения подзадач в нем, и заранее определить их не представляется возможным, предложено использовать их оценочные значения Торп«Трп и Т0В[1~ТВП. Если Товп+ Торт^о'ст» гае F,,*,-,. = Тмах -Т* (где Т* - время, прошедшее с момента поступления задачи на ДО, а Тмах- общее время, отведенное пользователем для решения задачи), то можно сделать вывод о том, что число агентов в сообществе достаточно для решения пользовательской задачи за указанное пользователем время. В этом случае задача

помечается на ДО как «полная», а другие агенты не предпринимают попыток войти в сообщество для ее решения.

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

Агент Aj ищет задачи, помеченные как

___________неполные на ДО.___

£

Агент Aj ранжирует обнаруженные задачи по соотношению их стоимости к

... Е—.трудоёмкости. 0/S ............

/ Агент Aj выбирает очередную задачу \

из обнаруженных начиная с самых V-\ __«выгодных» _ /

"ет __-—ВЫГОДНОСТЬ—

—<Сзадачи удовлетворяетусловиям^'.:.

-ала.дельца^--- ' ___

Агент А} вступает в сообщеаво для [ ______решения в_ь1б^анной задачи

Агент А, отправляет другим агентам. ■ ______сообщества данные о себе______

Агент вступил в сообщество

Агенты сообщества осуществляют оценку времени распределения Торп и выполнения подзадач Товп и находят

• лс^вщвеся;:^я^решения время Т*ост_ .

Торп+Товп<=Т* ост;

Йет '

Режим ожидания в течении времени

. —;---------:-----Igfttyutm^.___

Да

Да

N=M

Нет

Агент с наименьшей производительностью исключается из сообщества

Агент высылает приглашения известным агентам

Г

• Агенты ожидают завершения создания __сообщества _

Агенты переходят в режим распределения подзадач

Рисунок 2 - Схема работы метода создания сообщества агентов.

Следующим этапом решения пользовательской задачи в GRID является этап распределения подзадач между агентами, вступившими в сообщество для её (задачи) решения. При этом задача распределения формулируется следующим образом:

необходимо найти такое распределение вершин графа 0((2,Х) в сообществе, состоящем из N ИВУ с производительностью Р|(1=1,ЛГ) и пропускной способностью канала данных К$=1,Л0, для которого выполняются условия:

- Твп<Г0*ст, где Твп - время выполнения подзадач, Т^ - время, которое останется до указанного пользователем момента решения задачи, после завершения процесса распределения подзадач;

- ТрП < , где Тр*п - оценочное среднее время распределения подзадач, .1 -

средняя частота изменений параметров ИВУ, приводящих к необходимости перераспределения подзадач.

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

При использования такого подхода в условиях динамически изменяющихся параметров ИВУ агенты должны периодически оценивать производительность своих ИВУ для того, чтобы более точно определять временные потери при выборе очередной подзадачи для решения. Если же параметры какого-либо ИВУ сообщества изменились настолько существенно, что время решения пользовательской задачи в сообществе выходит за отведенные пользователем пределы Тмах, то агент должен инициировать перераспределение подзадач в сообществе. Если же в результате перераспределения подзадач в сообществе условие Твп<Г0"ст все равно не выполняется, то запускается процедура создания нового сообщества.

На рисунке 3 приведена схема работы метода распределения подзадач в сообществе агентов для произвольного агента А^где С>я - множество не решенных агентами подзадач, для которых имеются все входящие данные; ДТЯ=Т^П- Тт1„ -потенциальные временные потери при решении агентом Aj подзадачи qR, т.е. разница между полученным агентом временем решения подзадачи и найденным другими агентами минимальным временем решения; — подзадача, для которой выполняется условие АТс=гтп(ДТя).

Агент А;

..

п...

Найти множество Од

;::.::: г*

\

/ Для каждой из \ , подзадач^,, V

\ множества 0« /

Для каждого ИВУ \ сообщества А,

1x1..N

\

Рассчитать время ТК| решения подзадачи я агентом А,-

"Среди Та на ити~......

минимальное время решения д^ ;

Найти разницу &Тя

гг

Выбрать минимальное ДТС и подзадачу яс

Отправить информацию о том, что выбрана

. _.....;

! Считать исполняемый модуль и входящие данные

1С

Выполнить выбранную подзадачу дс

Отправить всем, что подзадача яс является «выполненной.»

Да

Последняя подзадача

Определить свою текущую производительность

Отправить результат : решения задачи на ДО

£ообидеств'а \ Нет

достаточно для >-

' решения в ср.сж ,-т-

Да

Агенты переходят в 1 режим создания сообщества

.. Имеются —г'«свободные» задачи...

Да

/

^ Конец

Рисунок 3 - Схема работы метода распределения подзадач в сообществе агентов.

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

То6щ= Ы*Талг_те+ Талг_рп**[ + твп,

где Тш а - время работы алгоритма создания сообщества, Тшг рп - время работы алгоритма распределения подзадач в сообществе, Твп - время выполнения

подзадач, I - частота изменения производительности агентов сообщества, N -количество агентов в сообществе, Ъ - количество подзадач в задаче.

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

Схема работы разработанного комбинированного метода создания сообщества и распределения подзадач в нём приведена на рисунке 4.

Рисунок 4 - Схема работы комбинированного метода создания сообщества и

распределения в нём подзадач

При этом использованы следующие обозначения: (?/акр - подмножество подзадач, запланированных для решения агентом А^ ?аакр=2 <34кр -подмножество всех подзадач, запланированных для будущего решения агентами сообщества; ()сво6 -

подмножество подзадач, еще не запланированных для решения, то есть не закрепленных ни за одним из агентов сообщества; <?необ £ Q3aKp - подмножество подзадач, закрепленных за агентами сообщества, которые согласно плану решения задачи пока не обеспечены входными данными, то есть если q„6 QHea6, то она связана хотя бы одной входящей дугой с вершиной qs£ <?сво6; Qo6 с <?закр _ подмножество подзадач, закрепленных за агентами сообщества, которые согласно плану решения задачи обеспечены всеми входными данными, то есть если q0e Qo6, то она связана всеми входящими дугами с вершинами, принадлежащими подмножеству <?закр, причем Соб = (?закр/(?необ; (?зап £ <?закр - подмножество подзадач, находящихся в процессе решения одним из агентов; Q3an = U;<?|an> где (¡¡ап - подзадача, решаемая агентом Aj в настоящий момент времени; Qpem с Q3aKp _ подмножество подзадач, решение которых успешно завершено.

В главе также разработан и подробно описан алгоритм поиска критического пути в графе G(Q,X) при составлении агентом плана решения.

Общее время решения пользовательской задачи при использовании комбинированного метода можно оценить как: Тобщком= TKn*J*TBn *N + Твп. Полученное значение меньше оценочного времени решения задачи при использовании предложенных ранее алгоритмов создания сообщества и распределения подзадач в сообществе на величину ДТ = N*TMr_cc + Тв„* J*N (Z* TMr_pn - Ткп).

Третья глава диссертации посвящена разработке и исследованию программных средств GRID с мультиагентным диспетчером.

Структура программных средств GRID показана на рисунке 5. В общем виде описанные программные средства GRID работают следующим образом:

1. Администратор системы вносит в базу данных актуальную информацию о работающих в рамках системы досках;

2. Пользователь GRID регистрируется на сайте, где получает уникальный идентификатор;

3. Для каждого лица, принимающего участие в работе GRID, в базе данных создается собственная запись и открывается виртуальный счет, который содержит количество виртуальной валюты (аналога заработанных баллов);

4. Пользователь формирует с помощью программной оболочки пользователя дескриптор для своей задачи, вносит на свой счет количество виртуальной валюты, необходимое для решения задачи, затем задача отправляется оболочкой пользователя на ДО системы;

5. Владельцы вычислительных ресурсов (ИВУ-фрилансеров) определяют необходимый минимальный порог относительной выгодности задач для решения, а затем запускают на своих компьютерах программное обеспечение агентов;

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

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

8. Как только задача решена, её результат отправляется сообществом агентов на доску объявлений, на которой хранится задача, доска объявлений пересылает результат пользователю и отправляет в базу данных запрос на перевод средств. При этом каждый из ИВУ-«фрилансеров» сообщества получает часть обещанных за решения задачи средств в соответствии с суммарной вычислительной сложностью решенных им подзадач.

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

Для исследования эффективности предложенных в диссертации методов и алгоритмов, была разработана программная модель GRID с мультиагентным диспетчером. Эффективность работы GRID было предложено оценивать с помощью двух критериев. Первым критерием является среднее значение КПЗ всех ИВУ системы, то есть отношение количества процессорного времени, потраченного на решение полезных задач всеми ИВУ к суммарному процессорному времени,

затраченному всеми ИВУ в процессе работы системы. Этот критерий определяет эффективность работы с точки зрения владельцев ИВУ-фрилансеров, поскольку, чем больше будет значение КПЗ, тем больше баллов они получат за выполненную работу. Для пользователя эффективность работы GRID будет зависеть от того, будут ли задачи, отправленные им на решение в GRID, решены за указанное им время. Поэтому вторым критерием является процентное соотношение количества задач, решенных за требуемое время, к общему количеству задач, поступившему на решение. Определен перечень наиболее важных параметров GRID, оказывающих наиболее существенное влияние на значение указанных выше критериев и на их основе предложена методика проведения экспериментов: рассмотрены различные потенциальные сферы применения разрабатываемой системы и выбраны соответствующие им значения параметров для исследования. Всего в процессе исследования проведено 12 серий по 48 экспериментов в каждой при различных значениях следующих параметров: количество ИВУ в GRID, производительность ИВУ, пропускная способность канала связи ИВУ, частота поступления задач, трудоемкость задач, объемы данных, передаваемые между задачами, оплата за решение задачи, количество подзадач в задаче, ограничение на время решения задачи. Результаты экспериментов показали, что средний КПЗ ИВУ системы при решении связных задач практически не опускается ниже 75%, что существенно превышает аналогичный показатель для современных GRID. При этом процент решенных за отведенное пользователем время задач в среднем составил 97%.

Основной научный результат диссертации заключается в решении актуальной задачи разработки методов и алгоритмов мультиагентного диспетчирования ресурсов в GRID для решения связных задач в условиях динамически изменяющихся числа и параметров исполнительных вычислительных узлов. В ходе работы показано, что мультиагентная организация диспетчера GRID позволяет повысить КПЗ ресурсов GRID при решении связных задач в условиях динамически изменяющихся параметров ИВУ при незначительном снижении процента решенных пользовательских задач за отведенное время. Предложенные в работе методы и алгоритмы позволяют строить GRID-системы на базе вычислительных ресурсов ИВУ, находящихся в частных руках, что позволяет заметно снизить стоимость вычислений в GRID, а также существенно повысить КПЗ ИВУ при решении связных задач, требующих интенсивных информационных обменов.

Все научные результаты, представленные в диссертации, получены автором

лично.

Основные публикации по теме диссертации

1-.Каляев А.И. Децентрализованная организация диспетчера GRID на базе сообществ агентов / Известия ЮФУ. Технические науки. №8, 2011г.- Таганрог: Изд-во ТТИ ЮФУ,- С. 230-238 (ведущий рецензируемый журнал, входит в перечень ВАК);

2. Каляев А.И. Метод и алгоритмы адаптивной организации распределенных вычислений в децентрализованной GRID / Вестник компьютерных и информационных технологий. №4, 2012г.- С. 28-33 (ведущий рецензируемый журнал, входит в перечень ВАК);

3. 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 - C.55-56;

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

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

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

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

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

9. Каляев А.И. Об одном методе организации облачных вычислений на основе взаимодействия исполнителей-фрилансеров / Материалы конференции «Управление в технических, организационных и сетевых системах» - СПб.: ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор», 2012 - С.140-143;

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

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

В совместных работах приведенного списка автором получены следующие результаты: в работе [4] разработан метод создания сообщества агентов для решения пользовательской задачи; в работе [5] разработан метод автоматизации проведения экспериментов с помощью программной модели распределенной вычислительной системы; в работе [7] предложен метод децентрализованной организации диспетчера GRID.

ЛР №020565 от 23 июня 1997г. Подписано к печати 22.05.2013 г. Формат 60х84Шб. Бумага офсетная. Печать офсетная. Усл. п.л. - 1,4. Уч.-изд.л. - 1,1.

Заказ № МЧ. Тираж 110 экз.

ГСП 17А, Таганрог, 347928, Некрасовский, 44. Типография Технологического института Южного федерального университета в г. Таганроге

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

УДК 004.75 правах рукописи

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

МЕТОДЫ И СРЕДСТВА ДЕЦЕНТРАЛИЗОВАННОГО ДИСПЕТЧИРОВАНИЯ РЕСУРСОВ GRID ДЛЯ РЕШЕНИЯ СВЯЗНЫХ

ЗАДАЧ

Специальность: 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

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

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

ТАГАНРОГ - 2013

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ...............................................................................................................................2

ВВЕДЕНИЕ......................................................................................................................................4

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

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

1.1.1 Система Globus................................................................................................................20

1.1.2. Система Condor...............................................................................................................22

1.1.3. Система AppLeS..............................................................................................................25

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.................................................................................................................................166

ЛИТЕРАТУРА..................................................................................................................................169

ПРИЛОЖЕНИЕ 1.......................................................................................................................177

ПРИЛОЖЕНИЕ 2.......................................................................................................................181

ПРИЛОЖЕНИЕ 3.......................................................................................................................183

ВВЕДЕНИЕ

Актуальность работы. Еще в 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 с мультиагентным диспетчером;

- пров