В.В. Топорков, Д.М. Емельянов

В.В. Топорков, Д.М. Емельянов

 

ПЛАНИРОВАНИЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ

 

 

УЧЕБНОЕ ПОСОБИЕ

по курсу

«Вычислительные системы»

для студентов, обучающихся по направлению

«Информатика и вычислительная техника»

 

Москва

Издательство МЭИ

2018

УДК 621.398

ББК 32.97

Т 584

Утверждено учебным управлением МЭИ

Подготовлено на кафедре вычислительной техники

Рецензенты:,

докт. техн. наук, проф. В.П. Климанов

докт. техн. наук, проф. И.В. Огнев

Топорков, В.В.

Т 584    Планирование распределенных вычислений:учебное пособие / В.В. Топорков, Д.М. Емельянов. — М.: Издательство МЭИ, 2018. — 84 с.

ISBN-978-5-7046-1870-6

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

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

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

——————

Учебное издание

Топорков Виктор Васильевич

Емельянов Дмитрий Михайлович

ПЛАНИРОВАНИЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ

Учебное пособие

по курсу «Вычислительные системы»

для студентов, обучающихся по направлению

«Информатика и вычислительная техника»

 

Редактор Издательства ***.

Компьютерная верстка ***.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

Темплан издания МЭИ 2018, учебн.                                       Подписано в печать

Печать офсетная        Формат 60×84/16                             Физ. печ. л. 5,0

Тираж 200 экз.           Изд. № 14у-066                                Заказ

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

Оригинал-макет подготовлен в Издательстве МЭИ, 111250, г. Москва,
ул. Красноказарменная, д. 14

Отпечатано в типографии Издательства МЭИ, 111250, г. Москва,
ул. Красноказарменная, д. 13

ISBN-978-5-7046-1870-6                               Ó Национальный исследовательский

университет «МЭИ», 2018

ВВЕДЕНИЕ

Организация вычислений в распределенных системах и средах, в отличие от составления расписаний в рамках известных моделей, обогащается таким важнейшим компонентом как управление ресурсами. Часто сложные наборы взаимосвязанных задач (задания) требуют согласованного выделения ресурсов (коаллокации) на нескольких вычислительных узлах. Каждый из узлов может находиться в автономном административном домене, представлять собой многомашинный или многопроцессорный комплекс, прохождением заданий в котором управляет своя локальная система пакетной обработки (СПО). Задание (исполняемые, входные и выходные файлы) часто принимается за единицу обработки в грид и замкнутых конфигурациях. Однако при этом его структура, как правило, не учитывается. Одно из немногих исключений применительно к параллельным вычислениям – планировщик в СПО Moab Cluster Suite, который допускает, что задание может состоять из параллельных задач, причем все задачи считаются однотипными в смысле требуемого вычислительного ресурса. В общем случае при согласованном выделении ресурсов необходимо учитывать и структуру задания, и разнотипность составляющих его задач.

Методы и средства для согласованного распределения ресурсов при организации параллельных вычислений в замкнутых конфигурациях, например, в кластерах и архитектурах с распределенной разделяемой памятью, хорошо известны. Так, системы LL и СУППЗ реализуют назначение многопроцессорных заданий на множество однотипных процессоров; NQE и PBS допускают согласованное выделение процессоров и памяти; CODINE и LSF позволяют управлять ресурсами или выбирать их конфигурацию в неоднородных распределенных средах. В замкнутых конфигурациях предполагается полный контроль над всеми ресурсами, что не осуществимо в грид. Эффективное управление заданиями может быть реализовано на основе стратегий – комбинации различных алгоритмов и эвристик планирования с учетом многочисленных факторов и критериев: политики предоставления и администрирования ресурсов, динамичности состава, разнородности узлов и т.д. К факторам, влияющим на выбор стратегии согласованного распределения ресурсов, относятся степень загруженности узлов и наличие необходимых для вычислений данных, заставляющие использовать гибкую политику репликации и перемещения данных в среде, их упреждающее кэширование. Это и необходимость использования многокритериальных моделей, учитывающих интересы пользователей, владельцев ресурсов и политику предоставления ресурсов, принятую в той или иной виртуальной организации грид, а также механизмы ее реализации (экономические принципы или квоты). Выбор состава ресурсов зависит также от прогнозируемого времени выполнения пользовательской программы либо наличия контрольных сроков, обусловленных фактором реального времени. Таким образом, приходится рассматривать совокупность возможных сценариев в организации вычислений, а за их планированием в глобальной среде должно стоять нечто большее, чем один, пусть и очень совершенный алгоритм работы программы-планировщика.

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

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

Учебное пособие содержит введение, четыре раздела, перечень контрольных вопросов и список литературы.

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

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

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

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

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

 

 

1. Управление ресурсами в распределенных средах

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

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

Рассмотрим принципы глобального планирования на основе следующей модели (рис. 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	3	1	2	1	2
	4	6	2	4	2	4
	6	9	3	6	3	6
	8	12	4	8	4	8
	20	30	10	20	10	20

 

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

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

,

(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)

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

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

, .

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