Содержание к диссертации
Введение
ГЛАВА 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. Система Х-СОМ
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. Методы распределения подзадач в сообществе агентов
2.3.1. Метод полного перебора 79
2.3.2. Метод градиентного спуска 80
2.3.3. Метод имитации отжига 81
2.3.4. Метод адаптивного распределения подзадач в сообществе агентов
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.!. Алгоритм работы в режиме «Инициализация» 134
3.5.2. Алгоритм работы в режиме «Выбор задачи» 135
3.5.3. Алгоритм работы в режиме «Ожидание» 136
3.5.4. Алгоритм работы в режиме «Вступление в сообщество» 137
3.5.5. Алгоритм работы в режиме «Выбор подзадачи» 139
3.5.6. Алгоритм работы в режиме «Выполнение подзадачи»
3.6. Программная модель grid с мультиагентным диспетчером 143
3.7. Исследование эффективности предложенных методов и алгоритмов мультиагентного диспетчирования grid 153
3.8. Выводы к главе 3 164
Заключение 166
Литература 169
Приложение
- Система Condor
- Метод создания сообщества агентов для решения пользовательской задачи
- Алгоритмы работы агента агент grid
- Программная модель grid с мультиагентным диспетчером
Введение к работе
Актуальность работы. В середине 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.
Результаты диссертации внедрены и нашли применение в:
- ОАО «Концерн радиостроения «ВЕГА» при создании алгоритма оптимизации распределения вычислительной загрузки, обеспечивающего организацию децентрализованного диспетчирования бортовой информационно-вычислительной системы изделия А-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 листа.
Система Condor
С самого начала компьютерной эры человечество использует вычислительную технику для решения сложных задач. Именно необходимость решения подобных задач подтолкнула человечество к автоматизации вычислений и созданию первых электронных вычислительных машин. Однако сложность задач росла и продолжает расти опережающими темпами. Изначально с такими вычислительными задачами могли справиться только суперкомпьютеры, громоздкие и дорогостоящие. Одним из первопроходцев в данной области стал Сеймур Крей со своим векторным суперкомпьютером «Сгау-1», который стал одним из самых востребованных суперкомпьютеров в истории. Затем ему на смену пришли параллельные векторные суперкомпьютеры, такие как «Cray Х-МР», «Сгау-2», а в 90-х появились и начали активно развиваться суперкомпьютеры с массовым параллелизмом, к которым можно отнести как Numerical Wind Tunnel от Fujitsu со 144 процессорами [17], так и суперкомпьютер ASCI Red, состоящий из нескольких тысяч процессоров, который первым преодолел рубеж пиковой производительности в 1 терафлоп в 1996 году [18]. При этом суперкомпьютер ASCI Red занимал площадь примерно в 150 квадратных метров и потреблял около 850 киловатт электроэнергии. Удельная стоимость вычислений в подобных машинах была предельно высока, и позволить себе использовать их могли только крупные государственные структуры и корпорации. Однако в 70-х годах 20-го века появились, и стали широко применяться относительно дешевые персональные компьютеры (ПК). Со временем ПК становились все доступнее и производительнее, и в определенный момент пришло осознание того, что сложные задачи, которые можно разделить на части, можно решать, используя множество персональных компьютеров за время, сравнимое со временем решения подобных задач на суперкомпьютере. Так появились первые распределенные вычислительные системы, представляющие собой локальные вычислительные сети, собранные на базе общедоступного оборудования. И хотя перечень задач, решаемых в подобных системах, был несколько уже, чем доступный суперкомпьютерам, стоимость построения и эксплуатации таких систем была намного ниже.
Первой системой, работающей подобным образом, стал «Беофульф» (Beowulf), созданный в 1994 году Томасом Стерлингом (Sterling) и Доном Беккером (Becker). Вычислительная система представляла собой 16-узловой кластер из процессоров Intel DX4, соединенных сетью 10 Мбит/с Ethernet с дублированием каналов. Кластер использовался в центре NASA Goddard Space Flight Center для поддержки необходимыми вычислительными ресурсами проекта Earth and Space Sciences. В последующие годы появилось множество программных комплексов, позволяющих создать вычислительный кластер на базе принципов, схожих с используемыми при построении системы «Beowul6 . В настоящее время под кластерной вычислительной системой, понимается вычислительный комплекс, состоящий из одного (реже более чем одного) серверного узла (который обычно называется головным), а также одного или нескольких подчиненных узлов, соединенных посредством выделенной компьютерной сети. В наши дни кластерные вычислительные системы обрели очень широкое распространение: среди суперкомпьютеров из списка Тор500 (top500.org) по информации на ноябрь 2011 года более 82% суперкомпьютеров являются кластерными вычислительными системами
Начавшееся в 90-х годах активное развитие телекоммуникационных технологий и компьютерных сетей позволило ускорить процесс доставки задач на географически уделенные ПК, что сделало возможным создание вычислительных систем, распределенных в пространстве. Это позволило создать кластерные вычислительных систем, компоненты которых могли быть удалены друг от друга: сначала в рамках вычислительных сетей ВУЗов и исследовательских центров, затем в масштабах городов и стран. Так же подобным подходом к организации кластерных вычислительных систем начали пользоваться многие крупные организации для построения своих собственных распределенных вычислительных сетей, однако в конце 90-х стало очевидно, что каждой организации нецелесообразно проектировать собственную вычислительную систему для решения своих задач, и тогда появилась идея создания универсальных GRID-систем.
В 1998 году основоположники GRID Ян Фостер и Карл Кессельман дали первое определение GRID. Они писали: "Компьютерная сеть (GRID) -это аппаратно-программная инфраструктура, которая обеспечивает надежный, устойчивый, повсеместный и недорогой доступ к высокопроизводительным компьютерным ресурсам" [4]. В следующей статье, "The Anatomy of the Grid" [2], написанной ими в соавторстве со Стивом Тьюке в 2000 году, данное определение было уточнено с учетом социальных и политических аспектов: GRID - это скоординированное разделение ресурсов и решение задач в динамически меняющихся виртуальных организациях со многими участниками. Ключевая концепция - это достижение договоренности о разделении ресурсов между поставщиками и потребителями и использование полученного пула ресурсов для различных целей.
Метод создания сообщества агентов для решения пользовательской задачи
Для того чтобы устранить указанные недостатки современных GRID, необходимо сделать процесс диспетчирования GRID более гибким и адаптивным: учитывать особенности задачи при выборе исполнителей, делегировать исполнителям возможность прямого взаимодействия друг с другом, отслеживать и оперативно реагировать на изменения параметров ИВУ. Для того чтобы сделать это предлагается переместить часть функций диспетчирования со служебного уровня на уровень исполнителей [37]. Тогда, за счет того, что уровню исполнителей будет доступно больше информации о вычислительной сети и задачах, станет возможным обмен данными между ИВУ напрямую, что в свою очередь позволит сократить время передачи данных между подзадачами. Кроме того размещение простейших диспетчеров на каждом ИВУ позволит им оперативно отслеживать изменения в параметрах этих вычислительных узлов, что даст возможность строить GRID на базе вычислительных ресурсов частных пользователей.
Таким образом, для того чтобы сделать возможным эффективное решение связных задач в GRID, построенной на базе ИВУ с динамически изменяемыми параметрами, предлагается разработать принципы децентрализованной мультиагентной организации диспетчера GRID, которые позволят перенести функции диспетчирования непосредственно на множество ИВУ GRID [38].
Мультиагентный подход к построению управляющей системы предполагает одновременную работу множества независимых друг от друга сущностей - агентов, которые в процессе взаимодействия приходят к определённым договоренностям, которые в свою очередь определяют в итоге эмергентное поведение системы. На сегодняшний день принципы мультиагентного взаимодействия успешно применяются при решении множества различных задач [12] [16].
В настоящее время в литературе существует множество различных определений понятия агент, поэтому необходимо привести определение, которое будет использоваться в данной работе. В дальнейшем автор предлагает под агентом понимать проактивную сущность, которая представляет интересы своего исполнительного вычислительного узла в процессе работы системы [39]. Одновременно в мультиагентной системе существует множество независимых друг от друга агентов, они взаимодействуют друг с другом, и каждый из них стремится максимально удовлетворить интерес своего владельца. При этом коллективное взаимодействие независимых агентов в рамках системы позволяет достичь глобальную цель системы в целом как совокупность локальных целей каждого из агентов. Именно это делает мультиагентную систему децентрализованной: каждый из агентов не контролируется извне, однако их группа решает общую задачу.
Мультиагентный подход может быть использован при организации децентрализованного диспетчера GRID. Основными взаимодействующими элементами системы целесообразно сделать агентов, которые выполняют функции как клиента GRID, так и диспетчера. Агенты физически располагаются на каждом ИВУ, и представляют их интересы в процессе работы мультиагентной GRID-системы.
При этом для решения каждой полученной системой задачи должна быть сформирована виртуальная организация множества агентов -сообщество. В данной работе предлагается под сообществом в дальнейшем понимать коллектив агентов, собравшихся вместе для решения одной и той же определенной задачи [39]. Основной целью создания сообщества является решение своей задачи к моменту времени, указанному владельцем задачи (пользователем GRID), при этом состав сообщества может изменяться в процессе решения задачи. Отказы оборудования ИВУ, изменение их производительности, снижение скорости передачи данных и другие изменения вычислительной сети, приводящие к увеличению времени решения пользовательской задачи, могут вызвать изменение состава сообщества.
В процессе формирования и работы сообщества части задачи, для решения которой сформировано данное сообщество, должны распределяться между агентами, включенными в состав сообщества. При этом в связи с неоднородностью оборудования в зависимости от полученного распределения частей задачи время решения задачи может варьироваться в широких пределах. Поэтому целесообразно производить оптимизацию размещения задач в сообществе с целью сокращения времени решения задачи. При этом для того, чтобы равномерно распределить нагрузку, процесс оптимизации должен быть распараллелен между всеми агентами сообщества.
Основным отличием такой схемы построения системы от существующих является то, что мультиагентная организация диспетчера GRID позволяет эффективно использовать вычислительные ресурсы ИВУ-«фрилансеров»: каждый из агентов может самостоятельно осуществлять мониторинг параметров своего ИВУ и, в случае их существенного изменения, инициировать перераспределение задач в сообществе или даже изменение состава сообщества. В то же время при такой организации ИВУ GRID будут обладать достаточным количеством информации о задаче и вычислительной сети для того, чтобы осуществлять передачу данных напрямую, без взаимодействия с узлами служебного уровня [40].
Однако подобная мультиагентная организация диспетчера системы накладывает определенные ограничения на взаимодействие пользователей и системы: так как GRID становится децентрализованной, пользователь не может взаимодействовать с системой через центральный диспетчер, как это происходит в классических GRID, а должен каким-либо образом передавать свою задачу множеству агентов. При этом можно предложить два различных способа взаимодействия пользователя с и ИВУ в рамках GRID с децентрализованным диспетчером:
Алгоритмы работы агента агент grid
На рисунке 2.9 подзадачи qi,q3 2Реш то есть Уже решены. Для обозначения этого окружности данных подзадач имеют заливку темно-серого цвета.
Для того чтобы найти для себя работу, агент Аг производит ту же самую процедуру поиска критического пути между вершиной подмножества QHeo6, имеющей наименьшее запланированное время начала Т„ (в данном случае это вершина \-j с временем начала Т„ = 9) и вершинами подмножества Qo6. При этом в данном случае время передачи данных Т„д от подзадачи qa к подзадаче ць может быть ненулевым, так как передача будет осуществляться между агентами Ai и Аг через сеть. При этом нужно учитывать следующее: скорость передачи данных через сеть будет ограничена наименьшей из пропускных способностей каналов данных пары передающих друг другу агентов.
В нашем случае пропускная способность канала данных для агента Ai равна К i=4, а для агента Аг равна К2=8, однако передача данных от одного агента другому будет осуществляться только на скорости Кп=4 , так как из пары пропускных способностей наименьшая равна 4. Допустим, что в приведенной в примере задаче количество данных, передаваемых от подзадачи qi к подзадаче q2 равно D]2=8, от q5 к q7 равно D57=4,. Тогда время передач этих данных между агентами будет составлять соответственно Т =2иТ =1.
Как только агент Аг находит критический путь, он ставит в соответствие каждой из подзадач qj критического пути планируемое время начала Т„ и окончания Т описанным выше образом с той лишь разницей, что время окончания Т предыдущей подзадачи критического пути будет равно разности времени начала следующей вершины Т и времени передачи
Как видно из рисунка 2.10, теперь подзадачи q2 и q5 решаются агентом Аг (на рисунке они обведены прерывистыми линиями. При этом стоит заметить, что агент Аг затратит на решение выбранного критического пути с учетом передач данных Т р = Т„ — Т = 9 — 2 = 7 единиц времени, таким образом время окончания решения выбранного им подмножества подзадач Q aKp будет равно Т лан=Т2+Т р=2+7=9, что удовлетворяет времени начала Т„ подзадачи q7, так же равному 9, так как Т Тплан. Таким образом, агент А.2 успевает выполнить подзадачи подмножества Фзакр ДО момента начала выполнения подзадачи q7 агентом Аь поэтому он вступает в сообщество для решения задачи и приступает к решению выбранных подзадач.
В ходе решения задачи в сообществе агентов может произойти случай, когда параметры одного из агентов изменяются или один из агентов сообщества отказывает (выходит из сообщества). Допустим что в момент времени Т2=2 производительность агента А і уменьшилась и стала равна Рі =80. Тогда время решения Tf агентом А] подзадач q (?закр будет составлять не рассчитанные им ранее Т = S4 / Pi = 400 / 100 = 4 единицы времени, а Т = S4 / Pi = 400 / 80 = 5 единиц времени. Не смотря на это, агент продолжит решение подзадач подмножества ?закр Рассмотрим пользовательскую задачу в момент времени Т3=7. В этот момент времени задача будет в следующем состоянии, показанном на рисунке 2.11.
Как видно из рисунка 2.11, в данный момент времени агент А] как раз закончил решение подзадачи q4, то есть q4G Qpem, а агент Аг находится в процессе решения подзадачи qs, то есть qsG Q3an.
Необходимо заметить, что не смотря на снизившуюся производительность, агент Аі все еще идет опережая график за счет запаса времени, который возник у него при выборе для решения подмножества (?закр- В то же время, не смотря на то, что агент Аг идет в соответствии со своим графиком, фактически он не успевает получить и передать необходимые агенту А і для решения подзадачи q данные к моменту времени Т, так как агент Аі выполнил все запланированные до вершины q7 подзадачи быстрее рассчитанного - к моменту времени Т3=7. Таким образом агент А і выясняет, что данных, необходимых для решения подзадачи qj в сообществе нет, поэтому он инициирует процедуру перераспределения подзадач. Процедура перераспределения подзадач в сообществе заключается в том, что все закрепленные за агентами подзадачи, кроме уже решенных и решаемых, помещаются в подмножество свободных подзадач, то есть QCBo6 = Q \ Qpem \ Q3an (в данном случае QcBo6={q6,q7,q8,q9}), а затем все агенты сообщества, начиная с самого производительного, определяют для себя подмножества Фзакр п0 описанной выше процедуре поиска критического пути.
В данном случае агент Аг является наиболее производительным агентом, поэтому он первым приступает к процедуре нахождения подмножества подзадач QaKp. После нахождения критического пути в обновленном подмножестве свободных вершин QCBO6 У него получается размещение, представленное на рисунке 2.12.
Как видно из рисунка 2.12, агент Аг берет на себя решение подмножества подзадач QaKp-{c{6, qs, q9}, но перед началом их решения, он должен завершить процесс решения подзадачи q5. Не смотря на это, суммарно он тратит на все это всего Т р=4 единицы времени. Так как T2=T3+Tgp=7+4=11, а решение задачи необходимо получить к моменту времени Тмах=12, то у него остается 1 единица времени про запас.
После этого агент А і так же ищет критический путь в подмножестве свободных вершин QcBo6={q?}- В качестве критического пути он выбирает для себя единственную подзадачу q7. Однако он не может взять на себя её решение, так как он не успеет осуществить все действия в необходимый срок (до момента Т„ = 11 запланированного начала решения подзадачи q9, так как он успеет передать данные для этой подзадачи агенту Аг только к моменту времени ТПЛан=Тк+Тпд=11.5+1=12.5, Тплан Тн). Поэтому он ПО передает полученные промежуточные результаты своих подзадач на ДО и выходит из состава сообщества.
Допустим, что в момент времени Т4=9 в сообщество вступил агент Аз с производительностью S3=200 и пропускной способностью канала данных Кз=8. Тогда после вступления данный агент выберет для себя подмножество подзадач (?акр, для этого он так же ищет критический путь в подмножестве свободных вершин QcBo6={q7}- В качестве критического пути он выбирает для себя единственную подзадачу qj как указано на рисунке 2.13.
На рисунке 2.13 подзадача цу, выбранная агентом Аз и соответствующие дуги выделены штрих-пунктирной линией. Не смотря на то, что агент Аз вступил в сообщество достаточно поздно, он успевает выполнить выбранную подзадачу и передать данные к моменту Т начала решения подзадачи q9, так как Т р = 2, Т„лан = Т4 + Т р = 9 + 2 = 11, Тплан Т . Таким образом, если в дальнейшем в сообществе не произойдет изменений, задача пользователя будет успешно решена, результаты работы последней подзадачи будут отправлены пользователю.
Программная модель grid с мультиагентным диспетчером
В представленной структуре программной модели GRID можно выделить следующие составные части: интерфейс программной модели - программная оболочка, позволяющая выбирать параметры и контролировать процесс моделирования; конфигурационный файл - файл, описывающий моделируемую систему: вычислительную сеть, поступающие задачи, а так же события, происходящие при моделировании (например, отказы оборудования); парсер конфигурационных файлов - блок, ответственный за получение информации из конфигурационного файла и создание списков переменных, описывающих моделируемую систему в соответствии с описанием в конфигурационном файле; блок генерации конфигураций эксперимента - блок, ответственный за полуавтоматическую генерацию конфигураций эксперимента для моделирования на основе данных, предоставляемых с помощью интерфейса программной модели; данные событий - список событий, которые должны быть смоделированы в процессе проведения эксперимента. Каждому событию в соответствие ставится момент, в который данное событие должно произойти, код, описывающий вид события, а так же информация о том, где событие должно произойти. В зависимости от кода событием может быть выход из строя или восстановление работоспособности определенных узлов моделируемой системы, изменение параметров каких-либо ИВУ; данные задач - список всех задач, запланированных для поступления в систему в процессе моделирования. Каждой задаче в соответствие ставится момент времени, в который данная задача попадает в систему, на какую из ДО данная задача должна попасть, а также сколько времени должно длиться решение данной задачи. Кроме того каждая из задач содержит информацию о подзадачах, их связях, сложностях и передаваемых между ними данных; блок имитации коммуникационной среды - часть программы, ответственная за взаимодействие узлов моделируемой системы. Позволяет осуществлять адресацию любого узла системы по его идентификатору, обладает очередью сообщений для каждого из узлов системы, реализует задержку передачи данных на время, зависящее от пропускных способностей каналов данных узлов; данные вычислительной сети - списки, содержащие информацию обо всех ИВУ и ДО моделируемой системы, такую как уникальный идентификатор, производительность, пропускная способность канала связи, состояние узла, выполняемые задача и подзадачи и т.д. При этом каждый из ИВУ и ДО системы может взаимодействовать с другими узлами только за счет обмена сообщениями через коммуникационную среду; блок имитации исполнительного вычислительного узла - блок, отвечающий за моделирование работы ИВУ GRID. Данный блок реализует алгоритмы работы агента GRID, предложенные в главе 3 данной работы, для ИВУ моделируемой системы; блок имитации доски объявлений - блок отвечающий за реализацию алгоритма работы доски объявлений GRID, предложенного в главе 3 данной работы; цикл имитации - часть программы, контролирующая непосредственно процесс моделирования GRID в последовательной вычислительной системе. Цикл имитации последовательно запускает на выполнение программы агентов и ДО системы, в необходимые моменты времени применяет события и добавляет активные задачи; блок расчета результатов эксперимента - блок, отвечающий за выбор из данных вычислительной сети и задач интересующей информации и получение на её основе значения параметров работы системы, измеряемых в ходе проведения эксперимента.
Согласно приведенной схеме программная модель работает следующим образом: Сначала с помощью интерфейса программной модели выбирается способ получений конфигурации эксперимента: загрузка информации из конфигурационного файла или полуавтоматическая генерация. В случае выбора загрузки информации из конфигурационного файла в дальнейшем необходимо в интерфейсе указать конфигурационный файл, из которого будет считываться информация. Далее выбранный файл попадает в парсер конфигурационных фалов, где из файла считывается конфигурация эксперимента, данные которой в после этого записываются в массивы данных задач, событий и вычислительной сети (агентов и ДО). В случае же выбора полуавтоматической генерации, в интерфейсе программной модели выставляется набор параметров, определяющих каким образом будет осуществляться генерация конфигурации эксперимента. После этого блок генерации конфигураций экспериментов, базируясь на выбранных ранее параметрах, осуществляет заполнение массивов данных задач, событий и вычислительной сети (агентов и ДО).
После заполнения массивов данных начинается процесс моделирования: обнуляется счетчик тактов и начинает свою работу цикл моделирования. Изначально в цикле моделирования проверяется, нет ли в системе событий, которые должны быть применены на данном такте. Если такие события есть, то осуществляются действия в соответствии с кодами событий и их параметрами. После этого в цикле моделирования проверяется, нет ли в массиве данных задач такой задачи, которая должна поступить в систему на данном такте. Если такие задачи есть, то осуществляется добавление их на ДО системы, указанные в параметрах задач.
Далее в цикле моделирования осуществляется имитация работы всех ИВУ системы: начиная с самого первого ИВУ и далее для каждого из ИВУ срабатывает блок имитации работы исполнительного вычислительного узла, в котором моделируется работа предложенных в главе 3 алгоритмов работы ИВУ GRID. В процессе моделирования работы алгоритмы имеют доступ к данным своего ИВУ в массиве данных вычислительной сети, для обмена данными с другими ИВУ или ДО системы в соответствии с предложенными алгоритмами осуществляется передача данных на другие узлы системы с помощью блока имитации работы коммуникационной среды. Для этого вызывается специальная функция, параметрами которой являются идентификатор узла-получателя и передаваемое сообщение. После вызова данной функции переданное сообщение помещается в очередь сообщений для узла с выбранным идентификатором. Для получения сообщений узел моделируемой GRID должен вызвать другую функцию, которая вернет первое из полученных данным узлом сообщений.
После завершения процесса работы всех ИВУ моделируемой системы осуществляется имитация работы всех ДО системы таким же образом: начиная с первого и далее для всех ДО моделируемой системы запускается блок имитации работы доски объявлений, который работает в соответствии с предложенным в 3 главе алгоритмом работы ДО в GRID. Как только все ДО системы закончат свою работу цикл имитации снова начинается с начала (с просмотра массива данных событий).
