Формирование стратегии вычислений


Планирование вычислений в грид

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

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

 

Рис. 1.2. Взаимодействие компонентов глобальной среды

 

Внешний планировщик в соответствии с некоторым алгоритмом определяет сайт, куда направляется поток заданий пользователя. Выбор сайта зависит от многих факторов: степени загруженности работами, наличия требуемых для вычислений данных и т.д. Эта информация может предоставляться локальными СПО. Для этого в них предусмотрена команда получения данных о текущем состоянии qstat. Однако информация, выдаваемая командой qstat, все-таки ориентирована на локальное управление ресурсами и, как правило, ее недостаточно для внешнего планирования. В преодолении этих трудностей может помочь механизм предварительного резервирования ресурсов, поддерживаемый рядом СПО. Сбор информации о состоянии локальных сайтов может опираться на информационную службу MDS системы Globus Toolkit. После того, как для задания выбран сайт, локальный планировщик (см. рис. 1.2) ставит это задание в очередь. Планировщик данных отвечает за доступ к данным на удаленных сайтах, перемещение и репликацию (тиражирование) данных. Репликация и перемещение данных в сочетании с внешним планированием является весьма действенным механизмом для управления заданиями в грид. В рассматриваемой модели (см. рис. 1.2) возможны различные сценарии взаимодействия пользователей, внешних планировщиков, локальных систем управления ресурсами и планировщиков данных. При этом эффективность планирования может оцениваться по совокупности критериев: использованию ресурсов, времени ответа на запросы пользователя и др.

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

Данные о распределенных ресурсах среды, особенностях приложения, пользовательских критериях производительности, моделях для оценки производительности и распределения ресурсов образуют так называемый информационный пул. Сбор информации о среде и прогнозирование загруженности ресурсов обеспечивается службой Network Weather Service. Четыре основные подсистемы агента, управляемые агентом-координатором, выполняют функции отбора той или иной комбинации ресурсов; планирования в соответствии с заданным пользователем критерием; взаимодействия с локальной системой управления ресурсами. Агент-координатор на основе оценки производительности отбирает лучший, с точки зрения пользователя, план и передает его через подсистему-исполнитель локальному планировщику в систему управления ресурсами.

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

 

 

Рис. 1.3. Структура агента-планировщика

 

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

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

 

2. Согласованное выделение ресурсов

2.1. Масштабируемая модель планирования

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

 

а б в

Рис. 2.1. Структуры заданий в моделях (а), (б), (в)

Переход от графа к графам осуществляется путем укрупнения задач и понижения уровня параллелизма. Граф задания параметризуется априорными оценками длительности выполнения задачи , , на ресурсе типа , относительных объемов вычислений на процессоре -го типа или передаваемых данных в коммуникационной подсистеме типа и т.п. Примеры параметров задач обработки для графов на четырех типах процессоров приведены в табл. 2.1. Длительность всех обменов данными для графа равна одной единице времени, в графах обмены и требуют двух, а обмен – четырех единиц времени. Полагается, что при укрупнении задач обработки значения соответствующих параметров составляющих подзадач такие суммируются.

 

Таблица 2.1

Длительность, Задачи обработки
объем вычислений

 

Параметризованный граф будем именовать моделью задания.

Распределение ресурсов между задачами из для соответствующей модели задания на отрезке времени зададим следующим образом:

,

(2.1.1)

где – параметр, определяющий назначение задачи на соответствующий ресурс; и – соответственно момент начала и длительность решения задачи на ресурсе, тип которого определяется назначением .

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

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

. (2.1.2)

Подчеркнем, что соотношения (2.1.1), (2.1.2) принципиально отличают масштабируемую модель планирования вычислений от традиционных моделей составления расписаний.

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

, , , (2.1.3)

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

План, соответствующий варианту допустимого, согласно (2.1.2), (2.1.3), распределения (2.1.1), в критерии эффективности использования вычислительных ресурсов представим вектором . Пусть – функции для оценки эффективности выполнения -й, -й задач на ресурсах, типы которых определяются назначениями , . Критерий представим следующим образом:

= . (2.1.4)

Эффективность распределения ресурсов (2.1.1) будем оценивать по вектору , где каждый из критериев , , можно записать в виде (2.1.4).

Пример критерия – функция стоимости завершения обработки:

, , (2.1.5)

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

Другой пример – коэффициент загрузки процессоров -го типа:

, (2.1.6)

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

Пусть – множество планов, каждый из которых соответствует допустимому распределению ресурсов (2.1.1) и своей модели задания. Для сравнения между собой различных планов на будем использовать понятие оптимальности по бинарному отношению , формируемому векторным критерием . Например, может быть отношением Парето, которое формируется критериями и , согласно (2.1.5) и (2.1.6). Пару будем называть моделью выбора, а множество , оптимальных по отношению планов в модели выбора , назовем -оптимальной стратегией распределения ресурсов.

Постановка задачи распределения ресурсов, согласованного со структурой выполняемого задания, представленного множеством моделей, заключается в отыскании -оптимальной стратегии допустимого в соответствии с (2.1.2), (2.1.3) распределения ресурсов (2.1.1), где формируется вектором критериев вида (2.1.4). Получаемая стратегия должна обеспечивать приемлемую аппроксимацию: совпадение ; включение ; совпадение с точностью до эквивалентности , где – квазипорядок, а – отношение эквивалентности на .

2.2. Формирование планов по частному критерию

Критической работой будем называть последовательность задач с наибольшей суммой априорных оценок длительности при использовании наилучшей комбинации ресурсов, которая содержит неназначенные задачи. Так, в графе (см. рис. 2.1) первой критической по длительности работе соответствует путь . Его априорная максиминная длительность равна 12 единицам времени (см. табл. 2.1). После назначения задач этой последовательности ресурсы должны распределяться для следующей работы , поскольку не назначены задачи и априорная длительность работы составляет 11 единиц. Распределение ресурсов для последовательности должно учитывать результаты назначения задач первой критической работы.

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

Пусть – функция для оценки эффективности выполнения -й работы по критерию , ; – число работ в задании; –план; – число задач; ; – соответственно длительность выполнения и назначение -й задачи, . С учетом свойства аддитивной сепарабельности (2.1.4) критерий можно представить в виде:

, (2.2.1)

где .

В соответствии с методом критических работ условный экстремум функции в (2.2.1) при заданном значении запаса по времени выполнения к моменту запуска -й задачи может быть получен из следующего функционального уравнения:

, (2.2.2)

где – условный оптимум функции при запасе по времени к моменту запуска -й задачи при наилучшей комбинации типов ресурсов.

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

, (2.2.3)

. (2.2.4)

В (2.2.3) – диапазон изменения длительности , зависящий от запаса по времени к моменту начала выполнения соответствующей задачи, а в (2.2.4) получается из (2.2.3)

Условно оптимальным является план следующего вида:

. (2.2.5)

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

, , (2.2.6)

где – подмножество задач, образующих -ю работу; – множество условно оптимальных планов (2.2.5), получаемых на шаге .

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

Пусть частный критерий формирует бинарное отношение:

, (2.2.7)

где – подмножество планов, являющееся одновременно внутренне и внешне устойчивым в модели выбора .

Будем называть в (2.2.7) стратегией, условно оптимальной по критерию .

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

Д о к а з а т е л ь с т в о т е о р е м ы 1. Пусть – условно оптимальная стратегия. Докажем, что каждая компонента плана является условно оптимальной.

Благодаря внешней устойчивости в модели выбора имеем: , . При этом , где определяется согласно (2.2.5).

Действительно, в (2.2.1) обладает свойством (2.1.4) и представляет собой монотонно-рекурсивный функционал, определенный на множестве последовательностей :

, , (2.2.8)

где – начало , а – сопряженное с ним окончание последовательности .

Рассмотрим наборы длительностей выполнения задач вида:

, .

Обозначим через , множества всех конечных отрезков допустимых последовательностей из множеств , соответственно, причем отрезки из , являются сопряженными с , . Множества , содержат наборы , для которых , являются начальными отрезками. Положим, . Ясно, что , поскольку входящие в эти множества последовательности определяются диапазонами и шагами изменения длительностей и вне зависимости от того, являются ли оптимальными их значения. В соответствии с обобщением принципа оптимальности динамического программирования последовательности из не могут быть условно оптимальными. Это означает, что условный экстремум функционала (2.2.8) согласно (2.2.2) имеет место лишь на последовательности вида (2.2.5). Следовательно, и условный экстремум , в силу (2.1.4), (2.2.1), достигается на . Поскольку внутренне и внешне устойчиво в модели выбора , то содержит все возможные условно оптимальные планы. Необходимость доказана.

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

Стратегию можно представить как упорядоченное семейство . В соответствии с функциональными уравнениями (2.2.2) - (2.2.4) получаем: , где бинарное отношение таково, что и , а – план, не являющийся условно оптимальным. Значит, . Поэтому и внутренне устойчиво в .

Следовательно, – условно оптимальная по стратегия. Теорема доказана.

2.3. Пример формирования планов

Предположим, необходимо построить условно оптимальную стратегию распределения процессоров по схеме (2.2.6) для задания, представленного информационным графом (см. рис. 2.1). Априорные оценки длительности задач обработки и относительных объемов вычислений для четырех типов базовых процессоров приведены в табл. 1, где ; . Число базовых процессоров каждого типа равно 1. Длительность всех обменов данными , равна одной единице времени. Задан срок завершения выполнения задания. Критерий эффективности использования ресурсов – функция стоимости вида (2.1.5). В (2.1.5) берется ближайшая к априорная оценка длительности , что и определяет тип используемого процессора.

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

, (2.3.1)

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

Необходимо построить условно минимальную по (2.1.5) стратегию для верхней и нижней границ максимального диапазона изменения длительности выполнения каждой задачи .

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

. (2.3.2)

В (2.3.2) – нижние границы, определяемые производительностью используемого процессора (см. табл. 2.1), а , , представляют запасы по времени к моменту начала выполнения задач .

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

; ;

; .

Для вышеперечисленных работ этот показатель соответственно равен 12, 11, 10 и 9 единицам времени. Выберем первую критическую работу и применим к ней функциональные уравнения (2.2.2)-(2.2.4) в рамках схемы (2.2.6). Введем следующие обозначения: – частные функции стоимости выполнения задач, входящие в критерий (2.1.5); – суммарная стоимость выполнения задач ; и соответственно. Максимумы диапазонов изменения длительности соответствующих задач по (2.3.2) равны: ; ; ; .

Чтобы найти условный минимум , необходимо в соответствии с (2.2.2) отыскать условно минимальные значения функций и в зависимости от запаса и к моменту запуска задачи и . Для , учитывая срок и длительность обменов, получаем: , . При имеем: , , условный минимум . Для условный минимум обеспечивается двумя парами значений и : 2, 10 и 10, 2. В значения входят лишь . Так, если , , то условный минимум , при этом . Для , имеет место: , причем, согласно (2.2.3), . Наконец, условные оптимумы достигаются тогда, когда , и , . При этом .

Назначения определяются по (2.2.4). Далее в соответствии со схемой (2.2.6) выполняется распределение ресурсов для последовательностей задач , и , входящих соответственно во вторую, третью и четвертую критические работы. Условно минимальная по стратегия представлена в табл. 2.2 планами 1, 2, 3.

 

Таблица 2.2

П Л А Н Длительность Назначение Критерии
 
0,35 0,10 0,15 0,50
0,35 0,65 0,50
0,35 0,10 0,15 0,50
0,85 0,10 0,15
0,85 0,15 0,50
0,85 0,10 0,55
0,85 0,10 0,15
0,30 0,65 0,55
0,35 0,75

Дата добавления: 2020-10-25; просмотров: 304;

Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.033 сек.