Модели и методы планирования сложноструктурированных заданий в распределённых вычислениях тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Целищев, Алексей Сергеевич

• Целищев, Алексей Сергеевич
• кандидат технических наук
• 2011

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

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

Вопросы, связанные с распределением трудоемких, вычислений, поднимаются уже не один десяток лет. Современные требования и научный прогресс влияют как на-объёмы обрабатываемых данных, так и на способы их обработки. Сегодня уже невозможно справиться с тем потоком информации, с которым необходимо работать различным организациям, имея под рукой лишь персональный компьютер, а в некоторых случаях даже целый вычислительный центр. Будь то петабайты данных, получаемых физиками на Большом Адронном Коллайдере [1], или огромное число комбинаций при поиске лекарства от тяжелой болезни [2] - современные реалии таковы, что не позволяют осуществить выполнение поставленных задач в рамках одной, сколь угодно большой или влиятельной организации, и требуют совершенно иного подхода к их решению.

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

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

Объектом исследований в представленной диссертации являются распределенные вычислительные среды, а предметом исследований — модели и методы планирования распределённых вычислений.

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

Для достижения поставленной цели в диссертации решены следующие основные задачи:

Исследованы существующие методы и алгоритмы планирования вычислений в распределенных средах

Предложена концепция решения задачи оптимального планирования вычислений на уровне приложений и потоков заданий

• Совмещение методов планирования уровня потоков заданий и методов планирования уровня приложений;

• Использование экономических критериев и модели планирования;

• Распределение ресурсов в два этапа: выбор домена вычислительных узлов и оптимизация выполнения задания.

Предложенная модель впервые позволяет одновременно соблюдать интересы пользователей Грид-систем, администраторов вычислительных узлов и организаторов Грид-систем и совмещать преимущества различных методик планирования: Budget- и Deadline-constrained (ограничения на бюджет и на время) планирования, а также Best-effort планирования:

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

• Разработаны алгоритмы- генерации' заданий в виде информационных графов, а• также алгоритмы анализа их структуры;

• Разработан обобщённый метод критических работ, основанный на переходе от концепции типов ресурсов к детерминированному домену узлов, предложен механизм обратной связи с узлами;

• Разработан ряд эвристик для разрешения коллизий между фрагментами заданий, для осуществления динамического выбора ресурсов в модифицированном методе критических работ и др.

Проведённый с помощью разработанной среды имитационного моделирования экспериментальный анализ предложенных методов показал их эффективность при работе с широким спектром заданий.

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

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

В четвертой главе работы приведено описание статистических экспериментов, проведенных с помощью разработанной среды имитационного моделирования М1МАРК и направленных на выявление закономерностей и подтверждение эффективности выдвинутой рабочей гипотезы об эффективности предложенных методов и алгоритмов. Также

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

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

Практическая значимость работы заключается в том, что на основе среды имитационного моделирования были разработаны программные модули, оптимизированные с точки зрения производительности, которые возможно положить в основу реализации реальной системы управления ресурсами Грид-системы. Программное обеспечение зарегистрировано в государственном реестре программ для ЭВМ: свидетельство № 2011611541 от 10.03.2011 г. ([119]). Результаты исследования нашли применение в учебном процессе кафедры ВТ ФГБОУ ВПО «НИУ МЭИ» и были использованы при подготовке лекционных курсов «Вычислительная техника», о чём имеются соответствующие акты.

На различных этапах проведения исследований работа автора была поддержана различными грантами:

• «Разработка моделей и методов согласованного выделения ресурсов для организации распределенных вычислений на основе опорных планов» РФФИ № 06-01-00027;

• «Стратегии диспетчеризации потоков заданий в виртуальных организациях распределенных вычислительных сред» РФФИ № 0901-00095);

• «Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред», Совет по грантам Президента Российской Федерации для поддержки ведущих научных школ НШ-7239.2010.9

• «Стратегии организации и поддержки крупномасштабных вычислений в распределенных средах» проекты 2.1.2/6718 и 2.1.2/13283 аналитической ведомственной целевой программы Министерства Образования и Науки РФ "Развитие научного потенциала высшей школы (2009-2010 годы)"

• "Программные модели и системы планирования распределённых вычислений", государственные контракты № П2227, 16.740.11.0038 федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы

• Именная премия первой степени комитета поддержки развития отечественных автоматизированных систем^ управления имени академика, Семенихина (2008г).

По теме диссертации было опубликовано 27 печатных работ (в том числе 7 в зарубежных изданиях), из них 4 в периодических научных изданиях, одна глава в монографии в соавторстве и одна в издании, рекомендованном ВАК ([82],[84],[87],[89],[91-97],[108-109],[117-130]). Результаты исследований были апробированы на многочисленных российских и зарубежных научных конференциях в период с 2007 по 2011гг. Во время выполнения исследований автор прошёл стажировку в Европейской Организации по Ядерным Исследованиям CERN (Швейцария) и ознакомился с принципами организации вычислений в крупнейшем на сегодняшний день проекте распределенных вычислений в мире - LHC Computing Grid.

Автор выражает благодарность своему научному руководителю В.В. Топоркову, своим коллегам A.B. Бобченкову и Д.М. Емельянову за помощь и сотрудничество в проведении исследований.

12

Заключение диссертации по теме «Вычислительные машины и системы», Целищев, Алексей Сергеевич

3.2 Результаты работы имитационной модели

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

Исходные данные'.

1. Сложноструктурированное задание, представленное ориентированным ациклическим взвешенным информационным графом G, состоящим из 11 вершин и 13 ребер, определяющих подзадачи и информационные зависимости между ними (рис. 3.3). Для каждой из вершин задан соответствующий её подзадаче условный объём вычислений в условных единицах. Граф сгенерирован с помощью функции среды моделирования Generate (см. приложения С и D).

2. Набор из 6 вычислительных узлов - процессоров рг0,.,рг5 разной производительности. Для каждой вершины графа указана априорная оценка времени выполнения соответствующей ей подзадаче на каждом из вычислительных узлов в условных единицах времени.

Условные объёмы вычислений для подзадач: рО V:21 pi V:27 р2 V:ll рЗ V:19 р4 V:19 р5 V:12 рб V:25 р7 V:22 р8 V:18 Р9 V:21 plO V:16 в списке работ, представленном ниже, нет повторяющихся элементов. Подобная фильтрация делается заранее, чтобы минимизировать объём s вычислений для модуля планировщика. Действительно, если какая-либо вершина или ребро присутствуют в более длинной критической работе, процесс последовательной обработки критических работ исключит эти i вершины из рассмотрения как уже распределенные. В результате работы* алгоритма, предложенного в подразделе 2.3.2., получены следующие данные, готовые к подаче в модуль планировщика:

Job 1: р0-рб-р5, суммарное время 7,=72+60+72+5+5=214 ед.вр. (здесь и далее обозначение ед.вр. соответствует условным единицам времени)

Job 2: (р0-р6)-р8. Вторая по длительности критическая работа для заданного графа полностью выглядит как р0-р6-р8, 7,=72+60+60+5+5=209 ед.вр., однако вершины рО и рб с соединяющим их ребром уже присутствуют в работе Job 1. Таким образом, в планировщик работа поступает как р8 и инцидентное ей входящее ребро. Принятая нотация — в скобках указываются вершины и рёбра, встреченные ранее и не подаваемые планировщику.

Job 3: р9-(рб-р8). Т=60+60+67+5+5=197 ед.вр.

Job 4: (р9)-р7-(р5). Т=60+54+72+5+5=196 ед.вр.

Job 5: р4-(р7-р5). Т=60+54+72+5+5=196 ед.вр.

Job 6: pl-(p7-p5). Т=57+54+72+5+5=193 ед.вр.

Job 7: (р9-р7)-(р8). Т=60+54+67+5+5=191 ед.вр. (для планировщика эта работа будет состоять лишь из одного ребра р7-р8)

Job 8: (р9-р7)-р10. Т=60+54+62+5+5=186 ед.вр.

Job 9: р2-(р8). Т=73+67+5=145 ед.вр.

Job 10: (pl)-(p5). Т=57+72+5=134 ед.вр.

Job 11: (pl)-(p8). Т=57+67+5=129 ед.вр.

Job 12: рЗ Т=54 ед.вр. (работа состоит из одной изолированной вершины)

Легко проверить, что в этом списке вершины и ребра встречаются вне скобок всего лишь один раз, то есть сам список включает в себя все t 110 компоненты графа. По полученным значениям длительностей выполнения критических работ на основе закона Амдала можно сделать вывод, что отрезок планирования для всего графа не может быть меньше, чем длительность работы Job 1 (см. рис. 3.3 — р0-р6-р5), равной 214 ед.вр. Работа Job 1 - не что иное как наиболее длительный последовательный участок графа, не подлежащий распараллеливанию.

Если бы заданный пользователем вычислительной среды, временной отрезок был бы меньше 214 ед.вр., то имитационная модель уже перед планированием сигнализировала бы о том, что за данный, промежуток времени данное задание на заданном наборе ресурсов выполнить невозможно.

3.2.2. Масштабирование

На втором этапе решения задачи происходит получение планов по стратегии, заданной в условии задачи, а именно планирование подзадач критических работ и определение выделенных каждой подзадаче времен таким образом, чтобы максимизировать среднюю загрузку всех вычислительных узлов. Планирование начинается после запуска процедуры Distribute (подробное описание всех компонентов и методов модели см. в приложениях С и D) с предварительным указанием значения в 300 ед.вр. в параметре Timespan и номера критериальной функции 1 в параметре Criterion. После окончания работы планировщик выдаст результаты и информацию о ходе распределения в файле Log.html. Рассмотрим их подробнее.

В данном примере механизм прямого и обратного прохода по критическим работам (см. подразделы 2.2.4 и 2.3.3) будет применён только для критической работы Job 1, так как только она с точки зрения планировщика содержит более одной нераспределённой вершины. Процесс проходов иллюстрируется планировщиком следующим образом:

Первая строка таблицы Layer 1-290 заполняется возможными временами выполнения первой подзадачи работы рО при условии соблюдения ограничения на запас по времени (если оставшегося запаса времени после выделения времени первой подзадаче не хватает на выполнение оставшихся подзадач на самых быстрых процессорах, подобные назначения не рассматриваются). Как показали эксперименты, подтверждающие гипотезу, предложенную в подразделе 2.2.4, эффективно» проводить поиск, рассматривая времена, соответствующие оценкам времени выполнения подзадачи на каждом их процессоров. Промежуточные значения не вносят в результирующий список стратегий новые планы. Таким образом, на процессоре ргО подзадача рО будет выполнена за 72 ед.вр., на prl — за 78 ед.вр., и так далее. Последний столбец соответствует максимально возможному времени, которое можно отвести на выполнение рО (время рассчитывается как разность между запасом и суммой времен выполнения, остальных подзадач рб и р5 на самых быстрых процессорах Z=290-72-60=l>58 ед.вр.). Повторим, что выделять и рассматривать другие времена, для выполнения рО не имеет большого смысла, так как они в итоге будут сводиться к выбору одного из представленных семи вариантов. При желании модуль планировщика можно модифицировать и соблюдать другую дисциплину выбора времен. Подробнее об этом в приложении В.

Вторая строка Layer 1-290 определяет запасы по времени для вершин дерева следующего яруса, которые будут соответствовать разным вариантам распределений операции рО. Z2(p6)=T-tl(p0)=290-72=218 ед.вр. для ргО, Т=212 ед.вр. для prl и так далее. Индекс у Z2 соответствует ярусу запаса, индекс у tl — рассматриваемому ярусу. Число ярусов дерева возможных распределений равно числу подзадач, входящих в критическую работу с точки зрения планировщика. Таблицы для последнего яруса не строятся, так как для последней вершины выделенное время однозначно определяется запасом, оставшимся с предыдущего

113 корректности работы алгоритма, что является одним из важнейших результатов диссертационных исследований. На данном этапе получено распределение, которое одновременно удовлетворяет условию, поставленному пользователем системы распределённых вычислений (ограничение по времени), а также критериям, определённым владельцами вычислительных ресурсов (обеспечение максимальной загрузки). Как уже было отмечено в главе 1, существующие на данный момент планировщики не позволяют получать подобные распределения.

3.2.3. Составление расписания и разрешение коллизий

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

Процесс масштабирования в среде имитационного моделирования происходит после загрузки графа и запуска процедуры Distribute. По окончании работы модуля планировщика итоговые планы будут

Связность ¿/=15

Объемы вычислений v, £ [100,300] Время выполнения гг е [50 ед. вр. ,100 ед. вр.] Время информационных передач 5 = 5 ед.вр. Число процессоров /=10 Число экспериментов Е = 2000 Масштабирование: по времени Критерий: максимизация средней загрузки узлов Отрезок масштабирования Ь= 1.5*/.

В 93.44% случаев коллизии при таком переназначении были успешно разрешены, причем среднее значение средней загрузки вычислительных узлов ухудшилось с 36.96% до 35.45%, что является неплохим результатом (для сравнения эффективности такого подхода по другому критерию см. эксперимент Эффективность эвристик коллизий). В оставшихся 6.56% случаев коллизии разрешить не удалось, причем в таких ситуациях наблюдались два варианта:

• Нехватка узлов ~ ситуация, в которой уровень имеющихся ресурсов недостаточен для того, чтобы переназначить какую-либо из подзадач, проигравшую коллизию. При этом процессор, быстродействие которого учитывалось планировщиком при составлении распределения, занят выполнением подзадачи, которая не вступает в коллизию. Подобные ситуации составляют 5.33% случаев.

• «Любимый процессор» - ситуация, при которой выделенное планировщиком время может обеспечиваться одним и только одним процессором, на который подзадача и была назначена, но после чего проиграла коллизию за этот процессор. Таким образом, возникает исключительный случай, и алгоритм приостанавливает работу.

Подобные ситуации возникают в 1.23% случаев.

148

При оптимизации расписаний по критерию максимизации стоимости расписания очевидно объяснение выбора самого дорогого (а в принятой модели одновременно самого быстродействующего) вычислительного узла. Именно подобная ситуация критически влияет на разрешение коллизий при невозможности ввода дополнительных ресурсов подобного типа. При этом статистика успехов разрешения коллизий выглядит удручающе - лишь в 21.7% случаев на выходе были получены оптимальные или близкие к оптимальным планы. При этом в 70.2% случаев невозможность составления плана возникала по причине наличия любимого процессора. При учете предложенной эвристики, когда самый быстродействующий узел выводился из пула процессоров перед процедурой масштабирования, статистика кардинально менялась - не встречалось ни одного случая любимого процессора, а число успешных составлений расписаний составило 76.0% случаев. Данный эксперимент показал высокую, чувствительность метода к внешним параметрам, но также и гибкость настройки, которая позволяет адаптировать его к практически любым ограничениям и условиям конкретных вычислительных сред, а также принятых стратегий и политик.

Последним экспериментом при условии невозможности ввода дополнительных экземпляров определенного типа ресурсов является эксперимент по оценке отклонения от полученного на этапе масштабирования значения критерия.

Эффективность эвристик коллизий

Число ярусов графа N=5

Максимальное число вершин в ярусе М= 5

Связность d= 15

Объемы вычислений v, £ [100,300]

Время выполнения г,- £ [50 ед. вр. Д00 ед. вр. ]

150

Время информационных передач 5 = 5 ед.вр. Число процессоров ./= 17 Число экспериментов Е = 1000 Масштабирование: по времени Критерий: максимизация стоимости Отрезок масштабирования Ь= 1.3*/.

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

4.1.3. Эксперименты с величиной интервала масштабирования

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

Возможные временные диапазоны (здесь и далее речь идет о масштабировании по времени, однако выкладки для масштабирования по стоимости будут аналогичны), в рамках которых можно составить расписание для задания сложной структуры, можно определить как где ТК1т.п — минимальное время выполнения самой длинной (по сумме весов вершин и рёбер графа) критической работы на определённом наборе ресурсов, а £у - сумма времён выполнения всех подзадач и информационных обменов. Иными словами, при отсутствии параллелизма время выполнения всего сценария равно сумме времён выполнения каждой из подзадач и обменов (верхняя граница), а при максимально возможном параллелизме время выполнения сценария ограничено длиной максимальной критической работы (нижняя граница), то есть самым длинным последовательным участком графа. Проблема выбора интервала планирования объясняется тем, что для случайно генерируемых сценариев сложно дать оценку необходимого времени планирования' ввиду абстрактности самого сценария, тогда как в реальной ситуации это прерогатива пользователя, инициирующего задание. Однако, предложенный' критерий сразу позволит отклонить запросы пользователей с заведомо некорректными требованиями к интервалу выполнения сценария (в том случае, когда предлагаемый интервал будет короче [0; Тштт]), а также дать вероятностную оценку успеха распределения ещё до его начала. Рассмотрим следующий эксперимент: меняя длину отрезка масштабирования, оценим долю успешно составленных планов. В данном случае абсолютные значения не так важны (эксперименты, касающиеся показателей успеха, были рассмотрены в предыдущих подразделах), обратим внимание на тенденции, проглядывающиеся в ходе осуществления процесса планирования.

Анализ графика, изображённого на рис. 4.3 показывает, что увеличение длины отрезка масштабирования относительно времени выполнения самой длинной критической работы на самом быстром процессоре сопровождается существенным ростом числа успешно распределённых заданий. Данная зависимость явно проявляется для критерия максимизации средней загрузки вычислительных узлов, а в общем случае обусловлена приоритетами выбора узлов той или иной производительности. Подробнее о влиянии типов и количества ресурсов см. эксперименты подразделов 4.1.4 и 4.1.5. Очевидно, что не для каждого сценария возможно' составить близкое к оптимальному расписание и обеспечить его выполнение, однако предлагаемые подходы позволяют вплотную подойти к решению этой задачи, а также дать априорные оценки вероятности успешного распределения.

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

Зависимость количества успешных составлений планов от длины отрезка масштабирования

Число ярусов графа N=6 Максимальное число вершин в ярусе М= 5 Связность й= 15

Объемы вычислений V, £ [100,300]

Время выполнения г, 6 [20 ед. вр. ,200 ед. вр. ]

Время информационных передач е [5 ед. вр. Д 5 ед. вр. ]

Число процессоров15

Число экспериментов Е = 9 прогонов по 200 заданий)

Масштабирование: по времени

Критерий: максимизация средней загрузки узлов

Отрезок масштабирования Ь= 1*1г, 1г=1.2.6 с шагом 0.2

154 предлагаемой иерархической модели планирования (см. рис. 2.1) необходимо было в первую очередь привести доказательства эффективности методов планирования на уровне приложений, а также обеспечить выполнение необходимых требований, предъявляемых к компонентам модели на уровне приложений. В главах 2 и 3, а также предыдущих разделах главы 4 были получены результаты, позволяющие говорить о том, что предложенные схемы и методы обеспечивают решение задачи планирования сценария распределенных вычислений' с одновременным соблюдением следующих требований (в общем случае противоречивых и преследующих различные цели):

• Требования пользователей распределённых вычислительных сред к срокам и/или стоимости выполнения подаваемых ими заданий

• Требования владельцев вычислительных ресурсов среды к загрузке конечных узлов1 и/или требования к соблюдению их экономических интересов.

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

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

168

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

Основным практическим результатом диссертационных исследований является построение и реализация сложной имитационной модели уровня приложений ([84], [120]), которая позволяет получать планы выполнения распределённых вычислений на уровне приложений с оптимизацией заданных критериев и соблюдением различных требований. Новизна полученных результатов заключается в том, что реализованная модель впервые позволяет обеспечить совмещение требований и экономических интересов участников вычислений и> дополнительных ограничений- при составлении планов и расписаний, являющихся важнейшими компонентами реальных систем распределённых вычислений. В диссертации последовательно рассмотрены все этапы получения планов выполнения заданий по заданным стратегиям, функционал и параметры имитационной модели, проведены многочисленные эксперименты, доказывающие эффективность разработанных методов. Исследование результатов работы модели, которые показывают, что разработанные методы позволяют получать оптимальные или близкие к оптимальным планы для случайных заданий, подтвердило приемлемость применения предложенной концепции в реальных системах.

В процессе работы над диссертацией автору удалось показать, что разработанная модель планирования на уровне приложений годится для интеграции в предложенную комплексную иерархическую концепцию планирования, так как позволяет получать планы выполнения широкого спектра сценариев распределённых вычислений при различных стратегиях организации вычислений. Несмотря на то, что представленные исследования методов планирования являются- завершённой' научным работой, разработанные методы и модель уровня приложений1 может использоваться в дальнейшем для исследований' по следующим^ направлениям:

Исследование методик интеграции модели. Разработанные на основе результатов работы имитационной модели оптимизированные приложения могут быть интегрированы в реальные системы Грид-вычислений, что в совокупности с использованием методов уровня планирования потоков заданий (исследования с участием автора [118], [121], [122], [123] и [126]) позволит повысить эффективность использования ресурсов- в Грид-системах.

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

175

Построение комплексной модели уровня потоков заданий и уровня приложений. Интеграция разработанной модели на уровне потоков заданий позволит провести моделирование и получить оценки качества обслуживания всех участников распределённых вычислений, а также значения интегральных характеристик потока (на примере эксперимента, приведённого в разделе 4.3). Исследования в данном направлении позволят проработать дополнительные аспекты комплексной концепции и, тем самым, вплотную подойти к возможности её реализации в-реальных системах распределённых вычислений. Принимая-участие в параллельных исследованиях методов планирования на уровне потоков заданий, автор учитывал, их результаты» при разработке представленных алгоритмов, что позволило создать модель, готовую к сопряжению с алгоритмами более высокого уровня.

Применение методов планирования распределённых вычислений в других областях науки и промышленности. Изучая различные подходы- к планированию распределённых вычислений, автор- обнаружил необходимость решения задачи составления1 расписаний- и в других областях, напрямую не относящихся к объекту диссертационных исследований. Так теория планирования и организации бизнес-процессов в экономике включает в себя задачу составления оптимального расписания выполнения» определённого задания группой исполнителей, которая, при определённых допущениях может быть спроецирована на задачи; решаемые в. диссертации ([110]). Также существует ряд промышленных, и экономических отраслей, где получение оптимального расписания выполнения какой-либо задачи может существенно влиять на итоговые показатели (например, [115], [112], [81] и др.). Использование полученных в диссертационном исследовании результатов и методов планирования может позволить рассмотреть встречающиеся задачи на качественно ином уровне и обеспечить показатели, достичь которых имеющимися на сегодняшний день методами невозможно.

176

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

1. I. Bird, L. Robertson, J. Shiers, "Deploying the LHC computing grid the LCG service challenges" // International Symposium on Mass Storage Systems and Technology, pp. 160165, 2005 IEEE International Symposium on Mass Storage Systems and Technology, 2005

2. Оф. сайт проекта DrugDiscovery@Home http://boinc.drugdiscoveryathome.com/

3. Топорков В.В. Модели распределённых вычислений. М.: ФИЗМАТЛИТ, 2004. 320с.

4. Ben-Ari, М. Principles of Concurrent and Distributed Programming (2nd ed.) Addison-Wesley. ISBN 978-0-321-31283-9.

5. Hansen P.B. Model programs for computational science: a programming methodology for multicomputers // Concurrency: Practice and Experience. 1993/ - V. 5. - P. 407-423

6. Andrews, Gregory R. (2000), Foundations of Multithreaded, Parallel, and Distributed Programming, Addison-Wesley, ISBN 0-201-35752-6

7. Yeng-Ting Lee; Kuan-Ta Chen, "Is Server Consolidation Beneficial to MMORPG? A Case Study of World of Warcraft," // Cloud Computing (CLOUD), 2010 IEEE 3rd International Conference on , vol., no., pp.435-442, 5-10 July 2010

8. K. S. Narendra, S. Mukhopadhyay Intelligent Control Using Neural Networks // Neuro-Control Systems: Theory and Applications. A Selected Reprinted Volume., Eds. M. M. Gupta and D. H. Rao. IEEE Press, 1994

9. Hatcher, P.; Reno, M; Antoniu, G.; Bouge, L.\ "Cluster computing with Java," // Computing in Science & Engineering , vol.7, no.2, pp. 34- 39, March-April 2005 doi: 10.1109/MCSE.2005.28

10. Korpela, E.; Werthimer, D.; Anderson, D., Cobb, J.; Leboisky, M; , "SETI@home-massively distributed computing for SETI," // Computing in Science & Engineering , vol.3, no. 1, pp.78-83, Jan/Feb 2001

11. Оф. сайт проекта PrimeGrid http://www.primegrid.com/

12. Оф. сайт проекта ABC@Home http://www.abcathome.com/

13. Stainforth, D.; Kettleborough, J.; Allen, M.; Collins, M.; Heaps, A.; Murphy, J.; , "Distributed computing for public-interest climate modeling research" // Computing in Science & Engineering , vol.4, no.3, pp.82-89, May/Jun 2002

14. Оф. сайт проекта MindModeling@Home http://www.mindmodeling.org

15. Оф. сайт проекта Chess960@Home http://www.chess960athome.org/

16. Оф. Сайт сообщества World Community Grid http://www.worldcommunitygrid.org/

17. Bird, /.; Jones, В.; Kee, K.F.; "The Organization and Management of Grid Infrastructures," // Computer, vol.42, no.l, pp.36-46, Jan. 2009

18. Kurdi, H.; Li, M.; Al-Raweshidy, H; , "A Classification of Emerging and Traditional Grid Systems," // Distributed Systems Online, IEEE , vol.9, no.3, pp.1, March 2008

19. Nash, H.; Blair, D.; Grefenstette, J.; "Comparing algorithms for large-scale sequence analysis," // Bioinformatics and Bioengineering Conference, 2001. Proceedings of the IEEE 2nd International Symposium on , vol., no., pp.89-96, 4-6 Nov 2001

20. Xhafa, Fatos; Abraham, Ajith (Eds.) Metaheuristics for Scheduling in Distributed Computing Environments // Studies in Computational Intelligence, V 146, Springer-Verlag Berlin Heidelberg, 2008

21. Brian J.S. Chee, Curtis Franklin Jr., "Cloud Computing: Technologies and Strategies of the Ubiquitous Data Center" // CRC Press, 2010, ISBN: 1439806128, 288 p.

22. Sciaba, A. et al. gLite 3.1 user guide // CERN 2009 CERN-LCG-GDEIS-722398

23. Kretsis, A.; Kokkinos, P.; Varvarigos, E.; "Developing Scheduling Policies in gLite Middleware," // Cluster Computing and the Grid, 2009. CCGRID '09. 9th IEEE/ACM International Symposium on , vol., no., pp.20-27, 18-21 May 2009

24. Frey J., Foster I., Livny M. et al. Condor-G: a Computation Management Agent for Multi-institutional Grids // Proc. of the 10th International Symposium on High-Performance Distributed Computing. New York: IEEE Press, 2001. - P. 55-66.

25. Gropp W., Lask E. Beowulf Cluster Computing with Linux, 2nd Edition // The MIT Press 2003, 660p 978-0-262-69292-2

26. Silva V. Grid Computing For Developers // Charles River Media, 2006 576p.

27. Romberg, M. \ "The UNICORE architecture: seamless access to distributed resources // High Performance Distributed Computing, 1999. Proceedings. The Eighth International Symposium on , vol., no., pp.287-293, 1999

28. Berman F. et al. Adaptive Computing on the Grid Using AppLeS // IEEE Transactions on parallel and distributed systems, vol. 14, no. 4, April 2003

29. Коффмап Э.Г. Теория расписаний и вычислительные машины М.:Наука, 1984 -334с

30. Taillard, Е. (January 1993). "Benchmarks for basic scheduling problems" // European Journal of Operational Research 64 (2): 278-285. doi: 10.1016/0377-2217(93)90182-M.

31. Muller-Merbach H. Ein Verfahren zur Planung des optimalen Betriebsmetteleinsatzes bei der Terminierung von Grossprojekten II Zeitschrift fuer Wirtschaftliche Fertigung. 1967 N62 83-88

32. Lawler E.L., Wood D.E. Branch and bound methods: a survey II Operations Research. 1966. N14(4). 699-719

33. Wieczorek, M„ Prodan, R., Fahringer, T.\ Scheduling of Scientific Workflows in the ASKALON Grid Enviornment. ACM SIGMOD Record 34(3), 56-62 (2005)

34. Berman, F., et al.: New Grid Scheduling and Rescheduling Methods in the GrADS Project. International Journal of Parallel Programming (IJPP) 33(2-3), 209-229 (2005)

35. Blythe, J., et al.: Task Scheduling Strategies for Workflow-based Applications in Grids. In: IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2005) (2005)

36. Topcuoglu, H., Hariri, S., Wn, M.Y.: Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing // IEEE Transactions on Parallel and Distributed Systems 13(3), 260-274 (2002)

37. Blaha, P., et al. : WIEN2k: An Augmented Plane Waveplus Local Orbitals Program for Calculating Crystal Properties. Institute of Physical and Theoretical Chemistry, Vienna University of Technology (2001)

38. Оф. сайт продукта MOAB cluster suitehttp://www.clusterresources.com/products/moab-cluster-suite/workload-manager.php

39. Шаповалов T.C., Пересветов B.B. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем // Вычислительные методы и программирование. М.: МГУ, 2009. Том 10, №1.

40. Yu, J., Buyya, R.\ Scheduling Scientific Workflow Applications with Deadline and Budget Constraints using Genetic Algorithms //Scient. Programming 14(3-4), 217—230 (2006)

41. Топорков B.B. Поведенческий синтез систем. -М.: Издательство МЭИ. — 2001. 192с

42. Thain D„ Tannenbaum Т., and Livny М. Distributed Computing in Practice: the Condor Experience // Concurrency and'Computation: Practice and Experience. 2004. - Vol. 17. -No. 2-4. - P. 323-356.

43. Аветисян A.K, Гайсарян C.C., Гришин Д.А. и др. Эвристики распределения задач для брокера ресурсов Grid // Труды Института системного программирования РАН. 2004. Т. 5. С. 41-62.

44. Berman F. High-performance Schedulers II In: I. Foster and С. Kesselman (eds.), The Grid: Blueprint for a New Computing Infrastructure. San Francisco: Morgan Kaufmann,1999. P. 279-309.

45. Yang Y., Raadt K:, and Casanova H. Multiround Algorithms for Scheduling Divisible Loads // IEEE Transactions on Parallel and Distributed Systems. 2005. - Vol. 16. - No. 8. -P. 1092-1102.

46. Beiriger J., Johnson W., Bivens H. et al. Constructing the ASCI Grid // Proc. of the 9th IEEE Symposium on High Performance Distributed Computing. New York: IEEE Press,2000.-P. 193-200.

47. Abramson D., Giddy J., and Kotler L. High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid? // Proc. of the International Parallel and Distributed Processing Symposium. New York: IEEE Press, 2000. - P. 520-528.

48. Воеводин Вл.В. Решение больших задач в распределенных вычислительных средах // Автоматика и телемеханика. 2007. - № 5. - С. 32-45.

49. Zhang Y, Franke Н., Morreira J.E. et al. An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration // IEEE Trans, on Parallel and Distributed Systems. 2003. 14 (3). P. 236-247.

50. Ioarmidou M.A., Karatza H.D. Multi-site scheduling with multiple job reservations and forecasting methods // In: Guo, M. et al. (eds): ISPA 2006. Lecture Notes in Computer Science, Vol. 4330. Springer-Verlag Berlin Heidelberg. 2006. P. 894-903.

51. Ranganathan к1 and Foster I. Decoupling Computation and Data Scheduling in Distributed Data-intensive Applications // Proc. of the 11th IEEE International Symposium on High Performance Distributed Computing, New York: IEEE Press, 2002. P. 376-381.

52. M. Tang, B.S. Lee, X. Tang, et al.: The Impact of Data Replication on Job Scheduling Performance in the Data Grid, Future Generation Computing Systems, 2006, Vol. 22, No. 3. P. 254-268.

53. N.N. Dang, S.B. Lim, and C.K. Yeo: Combination of Replication and Scheduling in Data Grids, Int. J. of Computer Science and Network Security, 2007, Vol. 7, No. 3. P. 304 308.

54. William H.B. et al. Optor Sim A Grid Simulator for Studying Dynamic Data Replication Strategies // Int. J. on HPC Appl., 2003, Vol. 17, No. 4. P. 403-416.

55. Foster I., Kesselman C., and Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // Int. J. of High Performance Computing Applications. 2001. - Vol. 15.-No. 3,-P. 200-222.

56. Garg S.K., Buyya R., Siegel H. J. Scheduling Parallel Applications on Utility Grids: Time and Cost Trade-off Management // Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009), Wellington, New Zealand. 2009. P. 151-159.

57. Degabriele J.P., Рут D. Economic Aspects of a Utility Computing Service, Trusted Systems Laboratory HP Laboratories Bristol HPL-2007-101 // Technical Report, July 3, 2007.-P. 1-23.

58. Ailamaki A., Dash D., Kantere V. Economic Aspects of Cloud Computing // Flash Informatique, Special HPC, 27 October 2009. P. 45-47.

59. Bredin J., Kotz D., Rus D. Economic Markets as a Means of Open Mobile-Agent Systems // Proceedings of the Workshop "Mobile Agents in the Context of Competition and Cooperation (MAC3)". 1999. P. 43-49.

60. Buyya R., Abramson D., Giddy J. et al. Economic Models for Resource Management and Scheduling in Grid Computing // J. of Concurrency and Computation: Practice and Experience. 2002. - Vol. 14. - No. 5. - P. 1507-1542.

61. Ernemann C., Hamscher V., Yahyapour R. Economic scheduling in Grid computing // Proc. of the 8th Int. JSSPP Workshop. LNCS. Vol. 2537. 2002. P. 129-152.

62. Коваленко B.H., Коваленко Е.И., Корягин Д.А. и др. Управление параллельными заданиями в гриде с неотчуждаемыми ресурсами. Препринт № 63. М.: ИПМ им. М.В. Келдыша РАН, 2007. - 28 с.

63. Киселев А., Корнеев В., Семенов Д., Сахаров И. Управление метакомпьютерными системами // Открытые системы. 2005. - №2. - С. 11-16.

64. Отчёт о проведении патентных исследований по 1 этапу Государственного контракта № 16,740,11,0038 от 01 сентября 2010 г. Под рук. В.В. Топоркова

65. Toporkov V. Multicriteria Scheduling Strategies in Scalable Computing Systems // Proc. of the 9th International Conference on Parallel Computing Technologies, LNCS. Vol. 4671. - Heidelberg: Springer, 2007. - P. 313-317.

66. Toporkov V.V., Tselishchev A. Safety Strategies of Scheduling and Resource Co-allocation in Distributed Computing // Proc. of the 3rd International Conference on Dependability of Computer Systems. Los Alamitos: IEEE CS Press, 2008. - P. 152-159.

67. Научно-технический отчёт о выполнении 1 этапа Государственного контракта № 16.740.11.0038 от 01 сентября 2010г. под рук. В.В. Топоркова

68. Toporkov V.V. Job and Application-Level Scheduling in Distributed Computing // Ubiquitous Computing and Communication (UbiCC) Journal. Special Issue on ICIT 2009 Conference Applied Computing. 2009. Vol. 4. No. 3. P. 559 - 570.

69. Kharitonov V. У. A Consistency Model for Distributed Virtual Reality Systems // Proc. of the 4th International Conference on Dependability of Computer Systems. Los Alamitos: IEEE CS Press, 2009. P. 271-278.

70. А.Б. Барский Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. - 256с.

71. Мнхалевич B.C., КуксаА.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. — М.:Наука, 1983. — 208с

72. Топорков В.В. Конспект лекций по курсу «Модели и методы анализа проектных решений» 2006

73. Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton Univ. Press, 1962.

74. Jin Y. Yen. "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Quart. Appl. Math., 27, 1970, 526-530.

75. Оф. сайт платформы Java http://java.oracle.com

76. Оф. сайт проекта Mono http://www.mono-project.com

77. Bilo, К; Flammini, M; Moscardelli, L.\ , "Pareto approximations for the bicriteria scheduling problem," // Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, vol., no., pp. 83, 26-30 April 2004

78. Оф. сайт корпорации Intel: описание процессора Intel® Core™2 Duo E6850 http://ark.mtel.com/Product.aspx?id=30785

79. Hay D.C. Requirement Analysis: From business views to architecture // Pearson Education, Inc., Prentice Hall, New Jersey, 2003

80. Anderson D.P. and Fedak G. The Computational and Storage Potential of Volunteer Computing // Proc. of the IEEE/ACM International Symposium on Cluster Computing and Grid, New York: IEEE Press, 2006. P. 73-80.

81. Fischer K., Midler J.P., Pischel M, Schier D. A Model For Cooperative Transportation Scheduling // Proceedings of the First International Conference on Multiagent Systems, AAAI, 1995.

82. Fruchterman, Т. M. J. and Reingold, E. M. (1991), Graph drawing by force-directed placement. Software: Practice and Experience, 21:1129-1164. doi: 10.1002/spe.4380211102

83. Karatza, H.D.\ , "A simulation-based performance analysis of gang scheduling in a distributed system," Simulation Symposium, 1999. Proceedings. 32nd Annual , vol., no., pp.26-33,1999

84. Арютов Б.Л., Важенин A.H., Пасин A.B. «Методы повышения эффективности механизированных производственных процессов по условиям их функционирования в растениеводстве: Учебное пособие» Издательство "Академия Естествознания", 2010

85. А.В. Бобченков «Разработка модели и методов управления ресурсами в виртуальных организациях распределенных вычислительных сред», Дис. канд. технических наук, Москва 2011, -156с.

86. Toporkov V.V., Tselishchev A. Safety Scheduling Strategies in Distributed Computing // Int. J. Critical Computer-Based Systems, Vol. 1, No. 1/2/3, 2010. P. 41-58.

87. Топорков В.В., Целищев А.С. Метод критических работ как перспектива эффективной организации распределённых вычислений // Информационные технологии, 2011, №6, с. 13-17

88. Tselishchev A., Toporkov V.V. Compound job scheduling and job-flows management in distributed computing // Proc. of the 54 Int. Colloquium, Ilmenau, Germany, 2009. P. 21 —26.

89. Целищев А. С. Цифровые сертификаты как средство аутентификации в Грид-компьютинге // Труды XVI международной научно-технической конференции "Информационные средства и технологии". В 3 томах. Т. 1. М.: Издательский дом МЭИ, 2008. - 237 с.

90. Tselishchev A. CERN Certification Authority: Evolution Труды XIV международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», изд. МЭИ, 2008

91. Листинг A.l: Интервалы распределения работ из примера подраздела 3.2.2.1. Critical job 3

92. Scaling interval: 99 time units.1. Critical job tasks: p9p6 distributed

93. Only one task is not distributed, no tree to build. Critical job 4

94. Scaling interval: 103 time units.

95. Critical job tasks: p9 distributed P7p5 distributed

96. Only one task is not distributed, no tree to build. Critical job 5

97. Scaling interval: 99 time units.1. Critical job tasks: P4p7- distributed

98. Only one task is not distributed, no tree to build. Critical job 6

99. Scaling interval: 99 time units.1. Critical job tasks: Pip7 distributed

100. Only one task is not distributed, no tree to build. Critical job 7

101. Scaling interval: 5 time units.

102. Critical job tasks: p7 distributed p8 - distributed

103. Only one transfer in job, no tree to build. Critical job 8

104. Scaling interval: 108 time units.

105. Critical job tasks: p7 distributed plO

106. Only one task is not distributed, no tree to build.1. Critical job 9

107. Scaling interval: 197 time units.1. Critical job tasks: p2p8 distributed

108. Only one task is not distributed, no tree to build. Critical job 10

109. Scaling interval: 103 time units.

110. Critical job tasks: pi distributed p5 - distributed

111. Only one transfer in job, no tree to build. Critical job 11

112. Scaling interval: 103 time units.

113. Critical job tasks: pi distributed p8 - distributed

114. Only one transfer in job, no tree to build. Critical job 12

115. Scaling interval: 300 time units.1. Critical job tasks: p3

116. Only isolated task in job, no tree to build.