WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

В результате решения задачи определяется время старта задания и набор аллокаций ресурсов: A = {A1(rj,t0,t0 + T ),..., AK (rj,t0,t0 + T )}, K = 1, P, где rj 1 K i — ресурсы, используемые для аллокации такие, что: rj Rj,i = 1, K, i i rj + rj +... + rj = P, где rj — количество аллоцированных процессорных 1 2 K i узлов на ресурсе. Все аллокации начинаются в одно время и имеют одинаковую длительность. Кроме того, обеспечивается выполнение двух условий:

• характеристики исполнительных ресурсов отвечают требованиям компонент задания;

• исполнительные ресурсы в период [t0,t0 + T ] свободны, и политика разделения ресурсов не препятствует их выделению для задания.

Перечисленные выше свойства грида делают возможность построения точных аллокаций A1,..., AK, K = 1, P, в которых определяется множество исполнительных процессоров rj,..., rj и временной интервал [t0,t0 +T ], на 1 K который они отводятся этому заданию, проблематичной. Вместо этого во многих практических реализациях результатом планирования являются аллокации, в которых время начала и ресурсы точно не определены. Для параллельных заданий это влечёт за собой серьёзные дефекты при их обработке, такие как «зависание» заданий в очереди кластера.

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

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

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

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

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

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

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

Во второй части анализируются известные системы планирования параллельных заданий в гриде (KOALA, MSS, JSS, NWIRE, CCS). Особое внимание уделяется способу решения в них задачи коаллокации.

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

Рис. 1. Грид с неотчуждаемыми ресурсами.

В первой части рассматривается экономический подход к планированию в гриде для управления параллельными заданиями. Согласно этому подходу процесс распределения ресурсов организуется на базе модели рынка: владельцы ресурсов выступают в качестве продавцов, а пользователи — в качестве покупателей этих ресурсов. Реализуя такой подход, предлагаются два соглашения по разделению ресурсов и способы их поддержки при планировании. Первое соглашение касается разделения ресурсов между пользователями. Основное требование заключается в том, что пользователь должен иметь возможность управлять скоростью получения ресурсов при планировании. Для этого им устанавливается плата за выполнение каждого задания в рамках выделенного ему бюджета. При увеличении платы шансы быстрее выполнить задание повышаются, однако при этом ограничение бюджета не позволяет пользователю монополизировать весь ресурсный пул. Для разделения ресурсов между двумя потоками заданий, поступающих с локального и глобального уровней, предлагается второе соглашение о разделении ресурсов: глобальное задание может занять ресурсы при условии, что плата, назначенная пользователем за выполнение задания, не меньше их стоимости. Такое соглашение позволяет осуществлять динамическую балансировку потоков заданий, обеспечивая конкуренцию глобальных и локальных заданий, и является ключевым для грида с неотчуждаемыми ресурсами.

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

• можно синхронно выделить в количестве, необходимом заданию;

• удовлетворяют ресурсному запросу задания;

• подходят по стоимости.

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

Алгоритм рассчитан на следующие условия.

• Все компоненты параллельного задания имеют одни и те же требования к ресурсам компьютера, выраженные в ресурсном запросе.

• Плата за каждую компоненту задания составляет RC / P, где P — количество компонент, а RC — стоимость задания в целом. Таким образом, в соответствии с принципом разделения ресурсов, заданию могут быть выделены только те из них, которые имеют стоимость, меньшую RC / P.

Алгоритм подбирает слоты для одного задания в два этапа и основан на совместном использовании двух представлений расписания в виде списков Lи L2, в первом из которых слоты отсортированы по возрастанию времени начала, а во втором — по возрастанию времени конца. Эта сортировка выполняется один раз для всей очереди заданий перед началом работы алгоритма.

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

При переходе к новому слоту из списка L1, время начала аллокации t устанавливается равным началу этого слота. Осуществляется проверка, является ли слот подходящим для запуска задания. Если это так, то количество подходящих слотов увеличивается. После этого проходятся слоты второго списка, конец которых меньше t + T, и соответственно уменьшается количество подходящих слотов. Как только набирается необходимое количество подходящих слотов P, этот этап работы алгоритма завершается, и получается время t0 = t, начиная с которого для задания можно синхронно выделить требуемое количество слотов.

Если на первом этапе необходимое количество слотов найдено, то все слоты, лежащие на интервале [t0,t0 +T ] и являющиеся подходящими, могут быть использованы для его запуска. Для их отбора совершается ещё один проход по первому списку L1 (второй этап). Полученный набор слотов (или их частей) является искомым набором аллокаций.

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

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

В четвёртой главе рассматривается программная реализация прототипа системы диспетчеризации параллельных заданий, в основу которой положены разработанные в диссертационной работе метод и алгоритм. Система основывается на современном подходе к построению грид-систем — Открытой архитектуре грид-служб (OGSA), реализуемой с помощью концепции веб-служб (Web Service Architecture — WSA) и соответствующих стандартных протоколов. В основу реализации положено промежуточное программное обеспечение, признанное стандартом де-факто, — инструментарий Globus Toolkit 4. Особенностью системы является то, что для планирования диспетчер использует прогноз использования ресурсов на будущее, что позволяет эффективно распределять задания по ресурсам.

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

диспетчер, ресурсный агент и пользовательский интерфейс. На рис. 2 серым цветом выделены разработанные блоки, являющиеся частью системы, а компоненты, реализованные в виде веб-служб (WS-компоненты), заключены в жирную рамку. Каждой компоненте посвящён отдельный раздел.

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

Состав диспетчера включает:

• службу приёма команд от пользователей;

• службу приёма информации о ресурсах;

• базу данных планирования;

• службу планирования;

• службу управления запуском, включающую в себя менеджер резервирования, менеджер запуска и менеджер доставки данных.

Рис. 2. Архитектура системы диспетчеризации.

Работа службы планирования — основной компоненты диспетчера — является циклической: на каждом цикле строится план распределения заданий по ресурсам на основе информации, находящейся в базе данных планирования. Во время работы цикла все задания, поступающие от службы приёма заданий, и обновления кластерных расписаний, поставляемые ресурсными агентами, буферизуются средствами СУБД и не учитываются на текущем цикле. По окончанию цикла они актуализируются в базе данных для использования на следующих циклах. После построения плана определяется подмножество заданий, время начала аллокаций которых достаточно близко к моменту начала выполнения. Для этих заданий посредством службы предварительного резервирования выполняется резервирование ресурсов, гарантирующее их выделение в соответствии с построенными планировщиком аллокациями, и инициируется доставка заданий в кластеры средствами Globus Toolkit.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»