Цель и задачи работы.10.
Научная новизна.11.
Практическая значимость.12.
Апробация работы.13.
Структура и объём работы.14.
Краткое содержание работы.14.
3.2.1.4. Выводы.
Случайный алгоритм не требует для планирования информации о характеристиках компьютеров или параметрах заданий, поэтому он может использоваться в системах, где такая информация недоступна, либо её получение сопряжено с трудностями. Рассмотренные модификации алгоритма позволяют увеличить его эффективность (увеличить долю выполненных заданий и сократить общее время их обработки) за счёт использования репликации и механизма контрольных точек. Однако, несмотря на увеличение числа выполненных заданий и уменьшение времени завершения, существенным недостатком этих модификаций является чрезмерное (в разы) использование процессорных ресурсов. Это связано с тем, что для каждого задания запускается несколько реплик, результат выполнения которых не представляет ценности для общего счёта.
В следующем разделе будет рассмотрен класс устойчивых к ошибкам алгоритмов, использующих для принятия решения информацию о состоянии исполнительных компьютеров и характеристики заданий. Такие алгоритмы эффективнее случайных, и позволяют более рационально использовать ресурсы исполнительных компьютеров.
3.2.2. Алгоритмы, использующие информацию о ресурсах и заданиях.
Как отмечалось ранее, алгоритмы планирования, не учитывающие при принятии решения информацию о заданиях и вычислительных компьютерах (случайные алгоритмы), обладают рядом недостатков. В качестве основного из них можно отметить нерациональное использование вычислительных ресурсов. В настоящем разделе будут рассмотрены методы распределения заданий, в которых учитывается информация об исполнительных компьютерах и заданиях. По предложенной выше классификации они могут быть отнесены к алгоритмам, которые используют для принятия решения информацию об исполнительных компьютерах и заданиях, работают в режиме онлайн, кроме того, в них могут использоваться различные средства повышения отказоустойчивости.
3.2.2.1. Способы выбора очередного задания.
В зависимости от имеющейся информации планировщик может принимать решение о распределении заданий, основываясь на характеристиках компьютеров, параметрах самих заданий, а также используя оба эти типа информации. В дальнейшем рассмотрении алгоритмов планирования предполагается, что для исполнительного компьютера могут быть получены данные о производительности и доступности (то есть моментах его отключения), а о задании известно, какое количество времени оно выполняется на эталонном компьютере, то есть на компьютере с производительностью Р= 1.
Во время работы планировщику необходимо принять два основных решения — какое задание распределять следующим, и на какой исполнительный компьютер его направить. В предыдущем разделе был представлен случайный алгоритм который, не обладая информацией о компьютерах и заданиях, случайным образом определял очередное задание и таким же образом выбирал для задания исполнительный компьютер. В дальнейшем рассмотрении выделяется два возможных варианта для выбора очередного задания (самое короткое — Short, или самое длинное — Long) и четыре возможных варианта полноты информации о компьютерах (нет информации — Nolnfo, информация о производительности — Cpulnfo, информация о доступности — Availlnfo, наличие полной информации — Fulllnfo). Таким образом, в зависимости от имеющейся информации получается восемь возможных алгоритмов планирования.
Имея информацию о времени выполнения задания, можно более рационально загружать вычислительные ресурсы в зависимости от того, какой эффект должен быть достигнут. Алгоритм Short позволяет выполнить как можно больше коротких заданий, чтобы затем на освободившихся компьютерах можно было запустить максимальное количество реплик длинных заданий, увеличивая тем самым вероятность успешного выполнения" всех заданий. В свою очередь, алгоритм Long направлен на то, чтобы сначала были завершены длинные задания, так как они наиболее требовательны к производительности компьютеров.
3.2.2.2 Способы определения подходящего компьютера.
В зависимости от имеющейся информации о компьютерах, выбор осуществляется следующим образом. Если о компьютере ничего не известно (Nolnfo), то выбирается любой из числа свободных. При наличии информации о производительности (Cpulnfo) выбирается компьютер с хмаксимальной производительностью. Это позволяет как можно быстрее выполнить задание и не допускать захвата слабых компьютеров (когда длинное задание попадает на слабый компьютер).
В том случае, когда планировщик может предсказать момент времени, в который компьютер будет недоступен (Availlnfo), выбирается самый надёжный — с самым поздним моментом отключения. При таком сценарии уменьшается вероятность возникновения ошибки во время выполнения задания, вследствие чего нет необходимости перезапускать задание на другом компьютере, также в этом случае может быть создана наиболее поздняя контрольная точка. Если же планировщик обладает информацией как о производительности, так и доступности компьютеров (Fulllnfo), он может определить, сколько по времени задание будет выполняться на каждом компьютере. В таком случае выбирается компьютер с максимальной производительностью, на котором задание успеет выполниться до момента отключения. Если ни на одном из свободных компьютеров задание не успевает выполниться до отключения, то выбирается наиболее мощный из них (как в Cpulnfo).
3.2.3. Алгоритмы с пакетным распределением заданий.
В разделах 3.2.1 и 3.2.2 были рассмотрены алгоритмы, распределяющие задания в режиме онлайн. Несмотря на то, что такие алгоритмы имеют важное преимущество — задания распределяются на исполнительные компьютеры как можно быстрее, а также выбирается наиболее мощный компьютер, такой способ не всегда походит для обработки интенсивного потока заданий и поддержки большого количества исполнительных компьютеров. В этом случае за время поиска наиболее подходящего компьютера может поступить некоторое количество новых заданий. Использование пакетного режима распределения позволяет рассматривать очередь заданий как единое целое и более эффективно использовать имеющиеся ресурсы для завершения всех заданий за минимальное время.
В случае пакетного распределения заданий планировщику необходимо рассмотреть все возможные варианты назначений заданий на различные ресурсы и выбрать наиболее подходящее назначение. Для оценки оптимальности вводится т.н. функция полезности (UF — utility function), выражающая в численном виде преимущество назначения задания на тот или иной компьютер. Функция полезности может быть выражена через самые различные характеристики, такие как цена задания, время выполнения задания, эффективная загрузка используемых компьютеров и т. п., а также через комбинации этих характеристик. В большинстве случаев функция полезности зависит от того, какой информацией о заданиях и компьютерах обладает планировщик.
Обозначим величиной 1/Гу полезность выполнения задания / на компьютере у. Тогда построение решения заключается в поиске оптимального распределения заданий по исполнительным компьютерам в соответствии с полезностью каждого назначения и состоит в максимизации суммы *ХЦ, где Ху = 1 в том случае, если задание / выполняется на 7 компьютере у, и Хч = 0 в противном случае. 3.2.4. Выводы.
В разделе 3.2 были рассмотрены различные сценарии работы планировщиков при распределении заданий в зависимости от условий и целей алгоритмов планирования. Отмечено, что при отсутствии информации об исполнительных компьютерах механизмы репликации и контрольных точек позволяют улучшить характеристики случайного алгоритма в отношении устойчивости к ошибкам и времени обработки множества заданий.
Несмотря на то, что получение полной информации о компьютерах и заданиях в распределённой среде является сложной задачей (необходимо определить состав собираемой информации, разработать механизмы её сбора и т. д.), некоторую информацию, такую, как производительность компьютера и длину задания, получить просто. Кроме того, центральный сервер диспетчеризации может фиксировать моменты отключения и включения компьютеров, которые используются для оценки их надёжности. Учёт такой информации позволяет улучшить качество планирования как по общему времени выполнения заданий, так и по количеству потерянного процессорного времени. Наконец, планирование сразу большого количества заданий из очереди позволяет сократить время выполнения множества заданий, однако использование пакетного распределения в случае неинтенсивного потока заданий не оправдано.
3.3. Метод планирования, направленный на завершение заданий в заданный срок.
Рассмотренные в предыдущем разделе алгоритмы планирования используются в распределённых системах, однако применить их для решения поставленной в работе задачи не представляется возможным, так как ни в одном из предложенных способов не учитывается свойство неотчуждаемости компьютеров. Планировщику остаётся принимать решение о размещении задания, основываясь лишь на характеристиках оборудования компьютеров и мгновенных показателях их загрузки: Учитывая условия одноуровневого грида, применение механизма миграции может приводить к постоянному перезапуску заданий на различных компьютерах, в результате чего большинство заданий так и не смогут выполниться. Ориентированность на наличие механизма контрольных точек не позволяет применять алгоритмы, использующие это средство, для запуска произвольных заданий (в том числе не поддерживающих контрольные точки).
В связи с этим разработка нового метода планирования заданий в гриде, направленного на обеспечение завершения заданий в заданный срок, является актуальным направлением деятельности, результаты которой позволят качественно улучшить распределение заданий. В настоящем разделе будет рассмотрен оригинальный метод, направленный на достижение поставленной цели.
3.3.1. Задача планирования в гриде с неотчуждаемыми ресурсами.
В связи с режимом использования компьютеров, когда их ресурсы разделяются между заданиями владельца и заданиями грида, возникает ситуацияпри которойдоля таких ресурсов, получаемая внешним заданием, меняется в зависимости от активности владельца компьютера. С точки зрения системы диспетчеризации такие ресурсы являются недетерминированными, так как невозможно точно предсказать время окончания задания, выполняющегося на неотчуждаемом компьютере. Это порождает проблему планирования процесса обработки, которое должно обеспечивать завершение выполнения каждого задания в заданный предельный срок. Для решения этой проблемы необходимо применять специальные меры, направленные на минимизацию нарушений задаваемого пользователем грида предельного времени выполнения задания.
Для планирования в гриде с неотчуждаемыми компьютерами наиболее важными являются характеристики, определяющие загрузку ресурсов и позволяющие её прогнозировать. Разработаны модели [40], [41], [44], которые предсказывают состояние ресурсов в пределах коротких отрезков времени (1−15 секунд). Эти модели служат основой для разработки механизмов разделения ресурсов компьютера.
В гриде обрабатываются задания с длительным временем выполнения (порядка нескольких часов), и для планирования их распределения между компьютерами более полезным выглядит использование статистических (усреднённых по большим интервалам времени) характеристик компьютеров. В контексте работ по созданию системы управления заданиями в гриде с неотчуждаемыми некластеризованными компьютерами проведено исследование возможностей улучшения стандартных методов планирования путём построения прогноза загрузки ресурсов на основе статистических характеристик.
В качестве основного показателя, который характеризует функционирование компьютера с точки зрения его работы на грид, введём понятие эффективной производительности. Эффективная производительность компьютера на некотором интервале времени Т определяется как средняя величина процессорной мощности, которая остаётся неиспользованной при работе владельца компьютера и может быть получена внешним заданием. Она задаётся в условных единицах по отношению к производительности эталонного компьютера, принимаемой за единицу. Если задание (рассматриваются счётные задания) на эталонном компьютере выполняется за время Т, то на компьютере с эффективной производительностью Н оно выполнится за время Т/Н.
В системе диспетчеризации сбор данных, по которым вычисляется эффективная производительность, производится отдельно для каждого' компьютера. Для этого в составе агента, управляющего обработкой внешних заданий на компьютере, реализуется программа, которая, получает от операционной системы значения текущей загрузки процессора [3] и периодически посылает их в информационную базу планировщика.
По собранным данным составляется прогноз эффективной производительности. Предлагаемый способ получения прогноза основан на предположении, что деятельность владельца компьютера в основном регулярна: мало изменяется день ото дня, но в течение суток могут быть перерывы в работе, а в конце рабочего дня компьютер, как правило, отключается. В связи с этим прогноз эффективной производительности представляется набором значений Н, относящихся к временным интервалам, на которые разбиваются сутки. Для вычисления Н на одном интервале производится усреднение полученных от компьютера значений текущей загрузки процессора. Кроме того, производится усреднение методом скользящего окна значений Н, относящихся к нескольким предыдущим суткам.
Следует отметить, что существуют нерегулярные факторы, например, отпускные дни, в которые компьютер может быть выключен в течение длительного времени. Учесть их трудно, и следует исходить из того, что прогноз не является точным.
3.3.2. Использование прогноза эффективной производительности.
В получивших известность и описанных в первой главе системах управления неотчуждаемыми компьютерами не учитывается, что их производительность не совпадает с эффективной производительностью. В соответствии с ведущейся на компьютерах основной деятельностью эффективная производительность меняется во времени. Вследствие этого возникают ситуации, когда задание, распределённое на некоторый, компьютер, не успевает завершиться в заданный пользователем предельный срок (deadline). Прогноз эффективной производительности позволяет дать оценку времени завершения задания и использовать её как дополнительный критерий при выборе компьютера. Как будет показано далее, таким способом можно уменьшить число отказов — превышений предельного срока — даже при неточном предсказании.
Сформулируем условия, в которых решается задача планирования. В грид поступает поток заданий {Jt, i~ 1,2,.}. Алгоритм планирования выполняет распределение заданий по компьютерам {Ск, к—,., Nc} в режиме on-line, то есть каждое задание распределяется независимо от других. Исходными данными планирования являются:
• характеристики заданий: длина (время выполнения на эталонном компьютере) Wи предельный срок выполнения Д—.
• характеристики компьютеров: эффективная производительность Щ.
Обычно для неотчуждаемых компьютеров используются алгоритмы планирования, которые опираются* лишь на характеристики заданий: рассмотренный ранее алгоритм WQ и его модификации, а также такие алгоритмы как First Come-First Serve (FCFS) и List Scheduling. Однако любой из этих алгоритмов может быть модифицирован для учёта эффективной производительности компьютеров. В следующих разделах проводится сравнение качества планирования алгоритмов FCFS и его модификации ЕСР-FCFS (Effective Computer Power-FCFS). Критерием выступает число отказов по превышению предельного срока.
Алгоритм FCFS.
1. Если очередь не пуста, и имеются свободные компьютеры, то выбирается случайный компьютер и на него распределяется первое задание из очереди.
2. В противном случае ожидаются события поступления задания или освобождение компьютера.
Алгоритм ECP-FCFS.
В этом алгоритме на шаге 1 меняется способ выбора исполнительного компьютера:
1.1. Выбирается первое задание из очереди.
1.2. Задание распределяется только на тот компьютер, где оно может окончиться в срок. Если таких компьютеров нет, делается попытка распределить следующее задание из очереди.
3.3.3. Оценка качества планирования.
Сравнение алгоритмов FCFS и ECP-FCFS выполнено путём моделирования их работы на синтетических входных данных, которые описывают поток заданий и характеристики компьютеров ресурсного пула.
Компьютеры в количестве 7Vc=100 имеют эффективные производительности, генерируемые случайным образом по равномерному распределению из диапазона [0.1, 1.0]. Длины заданий и времена их поступления также задаются равномерным распределением. Диапазон длин заданий — [150, 750], задания поступают на временном отрезке [0, 15], где TS — минимально возможное время обработки потока, вычисляемое как отношение суммарной длины всех заданий к суммарной производительности компьютеров. Предельный срок выполнения заданий выбирается пропорционально их длине Д—с^*^. Коэффициент а, фактически определяет нижнюю границу эффективной производительности, при которой задание может выполниться в срок, оц равномерно распределеныв диапазоне [1.1,5.0].
В результате моделирования обработки пакета из 1000 заданий получено, что количество отказов алгоритма БСРБ (201, то есть 20.1% от числа заданий) превосходит количество отказов алгоритма ЕСР-РСББ (30, то есть 3%). Улучшение, которое даёт учёт эффективной производительности, — значимое, но не слишком большое. Объясняется это тем, что компьютеры со слабой производительностью (Н<0.5), на которых в основном и происходят отказы, вносят небольшой вклад в суммарную" производительность грида. Если число таких компьютеров увеличивается, и соответственно растёт их вклад, преимущество ЕСР-РСР8 становится весьма существенным. Это иллюстрируется экспериментом, в котором к компьютерному пулу, описанному выше, добавляются дополнительные слабые (//=0.2) компьютеры. График зависимости количества отказов от числа добавленных компьютеров представлен на рис. 7. Хотя суммарная производительность растёт, в алгоритме РСБЗ число отказов линейно увеличивается, в то время как в ЕСР-РСРБ оно остаётся постоянным.
В реальности прогнозируемая производительность. будет отличаться от получаемой заданием во время выполнения. В следующем эксперименте изучалось влияние точности прогноза на число отказов: Относительное отклонение реально получаемой производительности Нг от прогнозируемой Н задаётся величиной Я, Нг—Н*(1+Я). Значения К генерируются по нормальному распределению со средним значением 0 и стандартным отклонением а. Величина, а является" параметром исследования: при а=0 время выполнения заданий совпадает с прогнозируемым, при больших, а оно может значительно отклоняться от прогноза.
10 0.
I Т, А * * *—-^ * ^ * * -4.
100 150 200 250 300 350 400 450 500 550 600.
Количество узлов (100 + слабые узлы).
-¦—ЯСРБ.
А—ЕСР-РСРЭ.
Рис. 7. Зависимость числа отказов от количества добавленных слабых компьютеров.
Рисунок 8 соответствует условиям, когда производительности компьютеров и коэффициенты а, (определяющие предельные сроки заданий) распределены равномерно. Как видно из графика, использование прогноза в алгоритме БСР-БСРв уменьшает число отказов в исследованном диапазоне 0 <а< 1. При добавлении в пул слабых компьютеров (рис. 9) эффект становится ещё более заметным.
45 40.
35 -30 ;
5 0.
О 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 а в—РСРБ —А—ЕСР-РСРЭ ь.
Рис. 8. Зависимость числа отказов от параметра а.
Рис. 9. Зависимость числа отказов от параметра, а (добавлено 100 слабых компьютеров).
3.3.4. Эффективное использование пула неотчуждаемых компьютеров.
Помимо уменьшения числа отказов учёт эффективной производительности компьютеров даёт дополнительный эффект: при точном прогнозе (а=0) невозможность обработки задания в срок определяется в период его нахождения в очереди, так что задание даже не распределяется на компьютер. Когда, а тФ возможны два вида отказов: по превышению времени ожидания в очереди и по превышению времени выполнения (рис. 10).
Наличие прогноза позволяет, во-первых, заблаговременно информировать владельцев заданий о невозможности их обработки в срок и, во-вторых, не тратить ресурсы впустую. Для оценки того, насколько продуктивно задействуются мощности ресурсного пула, будем использовать степень полезной загрузки ресурсов и теми заданиями, которые завершаются в срок: и = ' м^нт.
Суммирование в числителе отношения ведётся по всем заданиям, которые обработаны в срок, 5Т/ и ГТ- — время старта и завершения задания /, Н. — эффективная производительность компьютера во время выполнения задания. В выражении М8*НТ, стоящем в знаменателе, МБ обозначает время счёта пакета заданий, НТ =Нк, где Нк — эффективная производительность к компьютера за время М?, и суммирование ведётся по всем компьютерам ресурсного пула. по превышению времени ожидания в очереди I —а—по превышению времени выполнения.
Рис. 10. Соотношение числа отказов по превышению времени ожидания в очереди и по превышению времени выполнения.
Для исходного пула (с равномерным распределением производительностей) полезная загрузка составляет 40%. Когда к нему добавляются слабые компьютеры, суммарная мощность возрастает, но доля полезной загрузки уменьшается до 15% (рис. 11).
Количество компьютеров (100 + слабые).
Рис. 11. Полезная загрузка пула при добавлении слабых компьютеров.
Причина того, что задания получают отказ в обслуживании, в то время как в системе имеются незанятые компьютеры, причём в любом количестве, состоит в том, что эти компьютеры имеют недостаточно высокую производительность для выполнения заданий в срок. Более полная загрузка ресурсов может быть достигнута с помощью известного способа запуска заданий в виде пакетов подзаданий (Ва§-о?-Та8кз) [46]. Согласно этому способу задание «/ разбивается на множество подзаданий {SJl,., каждое из которых выполняет часть вычислений. Наибольший эффект такое разбиение даёт, если подзадания являются независимыми друг от друга и могут выполняться параллельно. Тогда можно обработать всю совокупность подзаданий в срок, определённый для задания J, но при меньших требованиях к производительности компьютеров.
Время обработки задания J длины IV на компьютере с у ж производительностью Н составляет Т- — —Q—DV, здесь — — время н н выполнения, <2 — время ожидания в очереди, йУ— время доставки входных и выходных файлов. Тогда минимальная производительность компьютера, обеспечивающая выполнение задания за время ИЬ, оставшееся до.
И7 наступления предельного срока, равна #тт = ——.
Если задание J разбито на М подзаданий &/}, которые отличаются.
IV только входными данными, то время обработки каждого Т^ — л-^З^ЭУ,.
Н1.
Всё множество подзаданий будет обработано за тот же предельный срок ИЬ, Ж что и исходное задание, если — + 01+ВУ,<�ВЬ для всех 1=1,., М.
Я,.
Предполагая, что длительность выполнения всех подзаданий и время V доставки файлов примерно одинаковые и равны соответственно —, М —, можно дать следующую оценку минимальнои производительности М цг компьютеров: ншщ — —• При условии, что время доставки файлов каждого подзадаиия много меньше его выполнения, требования к производительности компьютеров снижаются в Мраз.
Эффективность декомпозиции и параллельного выполнения заданий иллюстрирует таблица 1. В первой строке приведены данные по обработке исходного пакета заданий, во второй — пакета, который получается из исходного путём разбиения заданий на подзадания одинаковой длины. Количество подзаданий выбирается таким образом, чтобы каждое могло выполниться на компьютерах с минимальной производительностью (в данном случае 0.2). Приводятся стандартные показатели планирования — время счёта пакета заданий и степень загрузки ресурсов, а также количество отказов. Как видно из этих данных, пакет с разбиением на подзадания" обрабатывается с существенно меньшим числом отказов за меньшее время (оно близко к минимальному). Эффект объясняется более высокой степенью загрузки ресурсов. Выигрыш будет ещё более ощутим для пула, который содержит большое количество слабых компьютеров.
Заключение
.
В рамках диссертационной работы получены следующие результаты.
1. Разработан новый подход, позволяющий создавать вычислительные инфраструктуры из компьютеров, которые используются в режиме разделения с их владельцами. Предложены сценарии применения таких инфраструктур для массовой обработки вычислительных заданий.
2. Предложена архитектура системы управления инфраструктурой из некластеризованных компьютеров. Архитектура согласована с принципами и стандартами грида, в ней введены функции, необходимые для условий неотчуждаемых компьютеров. Предложенная архитектура допускает использование некластеризованных ресурсов в составе объемлющих грид-инфраструктур с любой формой организации ресурсов.
3. Разработан новый метод планирования распределения заданий, направленный на обеспечение завершения заданий в заданный срок. Путём моделирования показано, что использование прогноза эффективной производительности исполнительных компьютеров существенно повышает качество планирования и позволяет увеличить степень полезной загрузки пула неотчуждаемых компьютеров.
4. На основе предложенных решений выполнена программная реализация системы диспетчеризации, создана вычислительная инфраструктура, на которой проведены расчёты прикладных задач.
