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

На правах рукописи

Голосов Павел Евгеньевич

ПЛАНИРОВАНИЕ ЗАДАНИЙ С ВРЕМЕННОЙ ФУНКЦИЕЙ ПОТЕРИ ЦЕННОСТИ РЕШЕНИЯ В СЕТЕВОЙ СРЕДЕ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ

Специальность 05.13.01 - системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2010

2 9 ДПР 2010

004601395

Работа выполнена в Институте криптографии, связи и информатики Академии ФСБ России

Научный руководитель: кандидат технических наук, доцент

А. В. Киселев

Официальные оппоненты: доктор технических наук, профессор

И. Л. Шеремет

кандидат технических наук, доцент А. Б. Ермолаева

Ведущая организация: ОАО «Институт точной механики и

вычислительной техники им. С. А, Лебедева»

Защита состоится « 2Г » 2010 г. в /"6 часов на

заседании диссертационного совета Д212Л33.01 Московского государственного института электроники и математики (МИЭМ) по адресу: 109028, г. Москва, Б. Трехсвятительский пер., д. 3.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики.

Автореферат разослан« » СЬи^л-е^*-? 2010 г.

Ученый секретарь

диссертационного совета /У

кандидат технических наук, доцент С. Е. Бузников

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

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

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

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

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

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

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

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

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

В работе проведены исследования на тему своевременного обслуживания заданий, обладающих свойством потери актуальности решения, в многопользовательском опытном сегменте объединенной среды вычислений (ОВС), получившей название сетевой среды распределенных вычислений. Архитектурно опытный сегмент среды представляет собой объединение ряда ВС класса МВС-1000/15000 (разработка НИИ «КВАНТ» и ИПМ им. М. В. Келдыша РАН, головное предприятие - МСЦ РАН). Существующие в данной ОВС средства планирования заданий основаны на приоритетной схеме, не предусматривающей обеспечение своевременного обслуживания заданий, в силу чего требуется разработка как модели, так и программной реализации системы, устраняющий этот недостаток.

Разработана программная система планирования выполнения заданий для ОВС, позволяющая обеспечить требования по прогнозируемое™ времени их обслуживания заданий, основанная на условно-стоимостном исчислении и применении алгоритмов экономических моделей. Впервые термин и модель условно-стоимостного исчисления были предложены в конце 70-х годов для применения в мультипрограммных ЭВМ пакетной обработки (БЭСМ-6, ОС ДИСПАК) коллективом авторов ИПМ РАН (Н. Е. Балакирев, М. Г. Тонконогов, А. Е. Фирсов, И. А. Бахарев, В. И. Крюков).

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

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

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

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

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

2. Выявлено взаимное влияние заданий на время выполнения при решении на разделяемых вычислительных ресурсах.

3. Сформирован универсальный подход определения очередности выполнения параллельных вычислительных заданий с прогнозируемым временем выполнения на узлах разнородных вычислительных систем.

4. Разработан способ оценки эффективности работы системы планирования, основанной на применении алгоритмов экономической модели.

5. Исследована применимость моделей условно-стоимостного исчисления для управления заданиями и ресурсами в распределенных вычислительных системах.

6. Создана система, реализующая способ управления заданиями в ОВС на основе условно-стоимостного подхода.

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

Научная новизна работы состоит в следующем:

1. Получены вероятностные характеристики случайной величины -минимального времени совместного выполнения параллельных заданий (в частности - для двух заданий), сохраняющих актуальность решения, на разделяемых ресурсах ВС.

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

3. Предложен способ дифференциации заданий пользователей по важности (актуальности) на основе условно-стоимостного исчисления и алгоритм организации очередей заданий при индивидуальной оценке пользователями значимости заданий.

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

внеочередных заданий и досрочном окончании выполнения запланированных заданий.

Практическая ценность исследования заключается в следующем:

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

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

3. Обеспечена совместимость разработанной системы планирования заданий с существующей (систем семейства МВС, головные исполнители «НИИ «Квант» и ИПМ РАН). Предусмотрена ее работа в режиме действующей (приоритетной) системы планирования заданий.

Результаты, полученные в работе, использовались для выполнения государственного контракта № 26-2/2009 от 01 июня 2009 года «Разработка программного обеспечения автоматизированной системы, состоящей из удаленных вычислительных кластеров». Разработанные автором программные средства прошли государственную регистрацию [12] и являются базовыми для комплекса высокопроизводительных вычислителей, разработанного ЗАО «Закрытые технологии». Материалы диссертационной работы введены в учебный курс и используются в рамках лекционных и практических занятий по профилю кафедры 732 ИКСИ Академии ФСБ России.

Основные положения, выносимые на защиту:

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

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

3. Модель двухуровневой децентрализованной системы управления ресурсами объединенной вычислительной среды.

Апробация работы. Результаты диссертации прошли апробацию -обсуждались на научно-технической конференции ФГУП «НИИ «Квант» 10 февраля 2005 года и научной конференции МГУ им. М.В.Ломоносова 5 октября 2005 года; на международных конференциях «Распределённые вычисления и ГРИД-технологии в науке и образовании», проходивших 26-30 июня 2006 года и 30 июня - 4 июля 2008 года в ОИЯИ (г. Дубна); на международной конференции «Программные системы: теория и приложения», проходившей в ИСП РАН (г. Переславль-Залесский) в октябре 2006 года; на Всероссийских научных конференциях «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ», проходившей с 24 по 29 сентября 2007 года, и «Научный сервис в сети Интернет: масштабируемость,

параллельность, эффективность», проходившей с 21 по 26 сентября 2009 года в г. Новороссийске (пос. Абрау-Дюрсо), на научном семинаре, проходившем 27 февраля 2008 года в ИПМ им. М. В. Келдыша РАН.

Структура, объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 91 наименование. Общий объем диссертации составляет 106 страниц, включая 5 таблиц и 15 иллюстраций.

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

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

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

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

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

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

Таблица 1.

Сравнение систем управления ресурсами и заданиями в ОВС,

использующих методы экономических моделей

№ Наименование системы Поддержка качества обслуживания Возможность локального/ глобального планирования Децентрализация глобаль-I ного I управления Оптимизация времени выполнения заданий Страна разработки

1. GRAS + +/+ - - Россия

2. REXEC - +/- - - США

3. MAUI - +/+ - США

4. SGI (групп, зад.) + + + - США

5.1 Nimrocj-G - -/+ - + Австрл.

5.2 Libra RMS + +/- - + Австрл.

6. Система управления ОВС1 + + + + Россия

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

- децентрализация управления заданиями в ОВС, состоящей из разнородных ВС;

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

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

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

1 Требования, предъявляемые к системе планирования заданий объединенной вычислительной срсды

8

- наличие средств, позволяющих обеспечить работу пользователей в «замкнутом» режиме - режим ограниченности (в рамках отчетного периода) как объема доступных вычислительных ресурсов (и, как следствие, ограниченность объема доступных бюджетных средств), так и числа пользователей, допущенных к использованию ресурсов системы;

- целевая функция работы ВС состоит в максимизации количества своевременно обслуженных заданий;

- перепланирование очереди заданий при досрочном высвобождении ресурсов;

- возможность работы системы планирования заданий в режиме имитации обработки потока заданий;

- преемственность в способе постановки заданий на обслуживание с существующей приоритетной системой управления ОВС.

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

Работа системы планирования в ВС построена на взаимодействии двух основных компонент - сервера очередей, обрабатывающего поступающие в виде «паспортов заданий» ресурсные запросы и организующего локальную очередь заданий на выполнение и непосредственно планировщика, обеспечивающего выделение требуемого числа ресурсов для ветвей параллельных заданий. Относительно существующей схемы планирования (см. рис. 1), построенной на основе приоритетной системы управления прохождением заданий (СУПЗ), обеспечена взаимозаменяемость этих модулей, что делает возможным работу ВС как в режиме «экономического», так и приоритетного планирования.

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

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

Рис. 1. Архитектура системы планирования задании ВС на основе

приоритетов и с применением алгоритмов экономической модели

Общий порядок распределения заданий в ОВС возможно представить в виде следующей последовательности шагов:

Шаг 1. В момент начального распределения все узлы ОВС свободны;

Шаг 2. Происходит назначение пользовательских квот, определение пользователями множества распределяемых заданий и их функций актуальности;

Шаг 3. Осуществляется выбор ВС для распределения существующего множества заданий. Формируется множества нераспределенных заданий для каждой ВС и отправка соответствующих ресурсных запросов на вышележащий уровень;

Шаг 4. Задания из перечня для выполнения в ВС попарно упорядочиваются на основании процедуры ценового ранжирования. Далее для каждого из пары заданий определяется порядок выполнения и количество выделяемых ресурсов локальных ВС. Производится уменьшение пользовательских квот на величину планируемой занятости ресурсов;

Шаг 5. При досрочном окончании выполнения заданий производится переупорядочение очередей и возврат пользователям неиспользованных квот;

Шаг 6. Итеративный шаг - определение заданий из множества поступающих/нераспределенных для выполнения в ВС с применением «окна планирования» и процедуры ценового ранжирования заданий. Обновление пользовательских квот в соответствии с параметрами «окна планирования».

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

Для обслуживания заданий трудоемкости! (назовем это типом задания) Аь А?,... применяется совокупность распределенных разнородных вычислительных ресурсов типов И], Яг,--., объединенных в единую систему. Относительно независимые пользователи 11), иг,..., начиная с некоторого момента времени ^=0, обращаются к администратору системы с запросами на выполнение имеющихся у них наборов заданий:

= = (1) где через (К,!0 обозначим \'-й запрос пользователя и,. Тип этого задания обозначим через л!'1.

Особенности заданий таковы, что объем вычислений в них является случайным и не зависит от интересов пользователя и типа используемого вычислительного ресурса. Это означает следующее. Каждое задание представляет собой конечный набор элементарных фрагментов (ЭФ). Очередность выполнения ЭФ указывает пользователь, но количество ЭФ, необходимых для выполнения всего задания, является случайной величиной вероятностное распределение которой соответствует его типу - А,. Такая постановка вопроса не исключает случая, когда случайная величина ^ принимает одно фиксированное значение.

Характерным свойством рассматриваемых заданий является возможность распараллеливания их выполнения. При этом ветви выполняемого параллельного задания зависимы по данным. Максимальную степень распараллеливания задания типа А) (максимальное количество одновременно выполняемых ветвей задания) обозначим как щ.

Ресурсоемкость задания с трудоемкостью (типом) А) жестко связана с алгоритмом его решения, потенциально ориентированном на конкретный ресурс 11„, поэтому в качестве ее количественной характеристики рассмотрим вектор, количество координат которого соответствует числу различных типов ресурсов (при единственной ненулевой компоненте приходим к рассмотрению проблемы планирования для одиночной ВС):

п=(г»,г12,..), (2)

в котором гл- это количество элементарных фрагментов задания типа А;, выполняемых на ресурсе Т^ за время Т (отчетный период, интервал планирования). Время Т выбирается единым для всех типов задач.

В свою очередь векторы (2) определяют интегральную характеристику ресурсов всей системы за время Т в виде матрицы, составленной из векторов >', для всех типов заданий:

*=Ы> <3>

размеры которой определяются числом типов заданий и числом различных видов вычислительных ресурсов распределенной системы. Здесь и далее полагаем, что мощности множеств А = {А1,А1,...} и Л = конечны и

равны, соответственно, И = а и |й| = Ь.

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

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

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

Ожидаемая ценность (получаемая выгода) деятельности пользователей системы позволяет лицу, принимающему решения (администратор ВС), на основе анализа матрицы (3), выделить квоты каждому пользователю на каждое необходимое для обеспечения его деятельности задание типа А^

Эта квота представима в виде следующего вектора:

(■'. 'Г ......). (4)

в котором и и ~ это количество элементарных заданий, выделенных пользователю V, для решения задания типа Aj на время Т. Понятно, что элементы матрицы квот составлены из строк и,:

и = р9\, (5)

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

Х<-'-X'-,. (6)

I 8

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

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

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

Функцию актуальности у-го задания 1-го пользователя на временном интервале [0,Т], численно выражающую степень заинтересованности пользователя в решении данного задания, обозначим как:

^">(0. (7)

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

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

- наборы заданий пользователей (1);

- матрица ресурсов системы (3);

- матрица квот пользователей (4);

- функции старения пользовательских заданий (7).

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

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

(8)

I V

где суммирование ведется по всем невыполненным заданиям всех пользователей. В данном выражении г (№[!'') - есть оставшееся время выполнения задания >Си является случайной величиной.

Для практических расчетов значения случайных величин в (8) заменяют на их математические ожидания. Таким образом, основная функция администратора состоит в распределении заданий и указании такого допустимого распараллеливания их выполнения, которые максимизируют функционал (8) при ограничениях (6).

Каждое задание А] состоит из конечного набора пу элементарных фрагментов, очередность выполнения которых указывает пользователь. Количество элементарных фрагментов, требуемых для решения задания А], является случайной величиной с,. Далее будем предполагать, что имеет равномерное распределение на множестве {1,...,пу}. Трудоемкость элементарных фрагментов, относящихся к разным типам заданий, является сравнимой. Все пу элементарных фрагментов на N процессорах вычислительной системы выполняются не более чем за время Ту. Будем считать, что время их выполнения (отыскание первого подходящего решения) является случайным, обозначается как ту, причем туе[0, Ту]

Каждая из случайных величин £ равномерно распределена на интервале

= , где М - степень параллелизма задания (количество ветвей ее параллельного выполнения), величины независимы.

В системе имеется всего N процессоров, на которые можно распределить элементарные фрагменты выделив заданию г, - ^процессоров.

м

N = ^N„N,>1.

ы

Распределение времени выполнения элементарного фрагмента 21 на Л', процессорах описывается тем, что инициализируются /^случайных величин 4!л, ) = I, Л',, одна из которых распределена равномерно на интервале

т.

о,-

N.

Т.

а остальные сосредоточены в точке ~. Тогда случайная величина

7/0) = будет равномерно распределена на

оД

N.

, где / = 1, М.

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

■!) гЛ °2 0 1 ^ 1 1 1 7 1 V 1 1

Е[пл +?;'*')=-\—п. +—и, Ц +-------и, +--------и, Д----О:,

и ' б(д ' О, г) ' [2 Д 6 Д 2 Д 6 Д -) - 2 £),Д

где при заданных Ть Т2, Ы, N1, N2 (Т^-НК^М) вычисляется значение удельного

т

ожидаемого времени решения (трудоемкости вычислений) 1)а = ,

N

коэффициента использования заданием вычислительного ресурса где

а=1, 2; Б0 = тт{Оь 02}.

Минимум величины £(?/0) + £;/12>)при заданных Ть Т2, N определяется подбором параметра N1 (1< М|< N-1). В указанном выражении:

- г)(|>, л<2) - случайные величины, характеризующие минимальное время выполнения параллельных заданий с соответствующими индексами;

- Ть Т2 - для каждого из заданий - ожидаемое время решения для наихудшего случая (максимальной трудоемкости);

- N - общее количество ресурсов в вычислительной системе;

- N1, - количество ресурсов, выделяемых заданиям с соответствующими индексами.

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

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

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

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

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

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

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

Интерпретация экспериментов серии 1. В силу построения эксперименты серии (№№ 1-6) различались характеристиками потока заданий, предназначенных для обслуживания в ВС. При этом все пользователи, размещающие запросы на обслуживание заданий, предъявляли эквивалентные требования по «срочности» их обслуживания (наихудший случай - «всем нужно одинаково срочно»), С увеличением номера эксперимента ослаблялись требования пользователей к срочности обслуживания заданий. Так, если в эксперименте № 1 заданию требовалось не более 60 минут на выполнение, то пользователем на его обслуживание выделялось не более 66 минут, в эксперименте № 3 на обслуживание такого задания пользователем отводилось уже 120 минут.

Таблица 2.

Результаты экспериментов серии 1_

№ Наименование эксперимента Количество заданий, выполненных с соблюдением установленного времени обслуживания, % Среднее значение загруженности ресурсов, % Среднее приведенное значение времени ожидания обслуживания (Кт)

1. 10nopt 69 56 0,1

2. 10opt 70 58 0,094

3. lOOnopt 70 64 0,69

4. 10Oopt 81,3 69 0,61

5. 250opt 93 74 1,9

6. uni 100 80 -

7. Существующая схема 100 80 3,0

Кроме того, в экспериментах №1 и №3 не производилось перепланирование очереди при досрочном выполнении заданий. Ослабление требований по срочности обслуживания позволило увеличить число своевременно обслуженных заданий, улучшение значения данной характеристики стало возможным благодаря перепланированию очереди (эксперименты №№ 2, 4). В эксперименте № 6 (uni) ограничения по времени обслуживания заданий были сняты, что позволило обеспечить как количество обслуженных заданий, так и загрузку вычислительных узлов ВС на уровне существующей. Проведение данной серии экспериментов позволило оценить долю заданий, отклоненных по причине невозможности своевременного обслуживания при различных начальных условиях. В данной главе также приводится оценка приведенного среднего времени обслуживания заданий (Кт) для результатов экспериментов серии 1. Величина Ку вычисляется следующим образом:

где - время ожидания ¡-го задания в очереди, ^вып - время выполнения ¡-го задания, М - общее количество заданий.

Очевидно, что чем меньше значение величины Кт, тем для пользователя выше качество обслуживание заданий системой, поскольку сокращается время ожидания результатов выполнения. Как видно из таблицы 2, с уменьшением номера эксперимента сокращается среднее время обслуживания задания и, соответственно (набор заданий в экспериментах неизменен), величина Кт. Это означает, что для обслуженных заданий многократно сокращается время ожидания обслуживания по сравнению с существующей схемой планирования (в 1,5 раза для эксперимента №5 и в 30 раз для эксперимента № 2). Своеобразной «платой» за своевременное выполнение части заданий является отказ от обслуживания некоторого их количества, зависящего (при достаточности квоты) от указанной пользователем их «срочности».

В серии экспериментов 2 исследовалось количество обслуживаемых заданий ресурсами ОВС, объединяющей две эквивалентные ВС, при их совместном использовании. Было показано, что при планировании заданий на основе условно-стоимостного подхода совместное использование ресурсов в рамках ОВС, а также динамическое перераспределение заданий локальных очередей ВС позволяют увеличить общее количество выполняемых заданий с соблюдением пользовательских требований к качеству обслуживания заданий по сравнению с использованием ресурсов ВС под управлением СПЭА без объединения в единую среду вычислений.

Проведенные имитационные эксперименты позволили сделать следующие выводы:

- выбранная модель и целевая функция работы СПЭА при планировании заданий в ОВС позволяют обеспечить требование по качеству обслуживания заданий в аспекте прогнозируемое™ времени обслуживания при условии превышения объема ресурсных запросов над возможностями системы;

- величина средней загруженности ресурсов ВС не является информативной оценкой качества работы СПЭА. Для оценки ее эффективности следует использовать величины количества своевременно обслуженных заданий и приведенного среднего времени обслуживания заданий (Кт);

- при планировании заданий с использованием СПЭА возможно достижение многократного сокращения времени обслуживания заданий при условии возможного уменьшения количества своевременно обслуженных заданий;

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

- совместная работа ВС в составе объединения позволяет обеспечить общую производительность, превышающую суммарную для независимых ВС.

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

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

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

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

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

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

Направлениями дальнейших исследований являются:

1. Формирование процедур и автоматизированного способа определения трудоемкости заданий для каждого из видов ресурсов в ОВС, в том числе для случая совместного решения заданий на ресурсах различных ВС.

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

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

Публикации по теме диссертации:

1. Корнеев В., Киселёв А., Голосов П. Планирование заданий в грид на основе экономической модели. «Distributed Computing and Grid-technologies in Science and Education» Proceedings of Second International Conference (Dubna, June 26 -30, 2006) Dubna: JINR, 2006, D11-2006-167, 419 p., ISBN 5-9530-0138-X. -C. 335-342.

2. Голосов П. E. Планирование заданий и ресурсов в сетевой среде распределенных вычислений на основе экономических моделей. // Труды международной конференции «Программные системы: теория и приложения» / Под редакцией С. М. Абрамова - М.: Физматлит, 2006 т. 1, - С. 297-305 -ISBN 5-94052-128-1.

3. Корнеев В. В., Киселев А. В., Голосов П. Е. Реализация системы планирования заданий в сетевой среде распределенных вычислений на основе экономической модели. // Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ: Труды Всероссийской научной конференции. - М.: Изд-во МГУ, 2007., - С. 70-73.

4. Киселёв А.В., Голосов П. Е. Система планирования заданий в сетевой среде распределенных вычислений на основе экономической

модели // Распределенные вычисления и грид-технологии в науке и образовании: Труды 3-й междунар. конф. (Дубна, 30 июня - 4 июля, 2008 г.). ISBN-979-5-9530-0198-4. - Дубна: ОИЯИ, 2008. - С. 310-314.

5. П. Е. Голосов. Об одной модели распределения заданий для обеспечения комплексной безопасности вычислений в грид-среде // Безопасность информационных технологий - 2009, выпуск 4. М.: МИФИ - С. 90-93.

6. Голосов П. Е., Кравченко И. А. Технология распределения заданий со случайным временем выполнения и обладающих функцией потери ценности решения в распределенной разнородной вычислительной среде. Радиоэлектронная промышленность России - М.: ООО «ИД «Военный Парад», 2010., 652 е.; ISBN 978-5-904578-01-5, С. 239-245.

Тезисы докладов

7. Голосов П. Е. Управление ресурсами сетевой среды распределенных вычислений на основе экономических моделей // Методы и средства обработки информации. Труды второй Всероссийской научной конференции / Под ред. Л. Н. Королева. — Москва: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова, 2005, С. 148-153.

8. Корнеев В. В., Киселев А. В., Голосов П. Е. Планирование заданий в грид на основе экономической модели // Распределенные вычисления и Грид-технологии в науке и образовании: Тезисы докладов 2-й международной конференции (Дубна, 26-30 июня 2006 г.). - Дубна, ОИЯИ, 2006. - С. 80.

9. Корнеев В. В., Киселев А. В., Баранов А. В., Семенов Д. В., Кузнецов А. В., Голосов П. Е. Развитие системного программного обеспечения компьютеров на базе многопроцессорных кристаллов. // Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ: Труды Всероссийской научной конференции. - М.: Изд-во МГУ, 2007. - С. 52-54.

10. Семенов Д.В., Корнеев В.В., Киселев A.B., Баранов A.B., Кузнецов A.B., Голосов П.Е. Опыт практической реализации сетевой среды распределённых вычислений // Сборник тезисов докладов Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», 18-23 сентября 2006 г., г. Абрау-Дюрсо. - С. 68-74.

11. Голосов П.Е. Технология распределения типовых заданий со случайным временем выполнения и убывающей функцией потери ценности решения в распределенной разнородной вычислительной среде. // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г. Новороссийск) - М.: Изд-во МГУ, 2009. - С. 114-116.

Авторское свидетельство

12. Свидетельство о государственной регистрации программы для ЭВМ № 2010611523 «Система планирования заданий с временной функцией потери ценности решения в сетевой среде распределенных вычислений». Правообладатель, автор: Голосов П. Е. Зарегистрировано в Реестре программ для ЭВМ 24 февраля 2010 г.

Подписано в печать 14 апреля 2010 г. Объем 1,0 п.л. Тираж 100 экз. Заказ № 320 Отпечатано в Центре оперативной полиграфии ООО «Ол Би Принт» Москва, Ленинский пр-т, д.37

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ РАЗРАБОТОК В ОБЛАСТИ СИСТЕМ ПЛАНИРОВАНИЯ В РАСПРЕДЕЛЕННЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.

1.1. Основные понятия.

1.2. Организация управления заданиями и ресурсами в ОВС.

1.2.1. Система управления ресурсами ОВС централизованного типа.

1.2.2. Иерархическое построение системы управления ОВС.

1.2.3. Децентрализованная система управления ресурсами ОВС

1.2.4. Средства промежуточного программного обеспечения для ОВС.

1.3. Проблема качества обслуживания заданий в ОВС.

1.3.1. Анализ способов построения очереди заданий в распределенных ВС.

1.3.2. Административный подход к регулированию потока заданий.

1.3.3. Распределение заданий на основе общей целевой функции.

1.3.4. Распределение заданий с использованием алгоритмов экономических моделей.

1.3.4.1. Программный комплекс GrAS.

1.3.4.2. Система планирования REXEC.

1.3.4.3. Система планирования PBS, Maui scheduler.

1.3.4.4. Система управления SGE—Enterprise Edition (ЕЕ).

1.3.4.5. Система управления Nimrod-G Grid resource broker.

1.3.4.6. Система управления Libra RMS.

1.3.5. Управление ресурсами на основе условно-стоимостного исчисления в ОВС.

1.4. Теоретические основы применения экономических моделей для организации управления в распределенных вычислительных средах.

1.5. Выводы по главе 1.

ГЛАВА 2. РАЗРАБОТКА СИСТЕМЫ ПЛАНИРОВАНИЯ

ЗАДАНИЙ В ОВС НА ОСНОВЕ УСЛОВНО-СТОИМОСТНОГО ИСЧИСЛЕНИЯ.

2.1. Модель планирования заданий в ВС и ОВС.

2.1.1. Распределение заданий для выполнения в объединении ВС.

2.1.2. Построение очереди заданий в ВС.

2.1.3. Ценовое ранжирование заданий.

2.2. Реализация планирования заданий в ОВС.

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

2.2.2. Двухуровневая организация планирования заданий.

2.2.3. Внеочередное планирование.

2.2.4. Оптимизация расходования пользовательских квот.

2.2.5. Работа системы планирования заданий в режиме моделирования.

2.3. выводы по главе 2.

ГЛАВА 3. ОЦЕНКА ЭФФЕКТИВНОСТИ РАБОТЫ СИСТЕМЫ

ПЛАНИРОВАНИЯ ЗАДАНИЙ.

3.1. Обеспечение надежного распределения заданий в ОВС.

3.2. Оценка эффективности работы СПЭА.

3.2.1. Эксперименты по оценке количества обслуживаемых заданий и загруженности ресурсов для ВС (эксперименты серии 1).:.

3.2.2. Результаты экспериментов серии

3.2.3. Дополнительные оценки экспериментов серии 1 (оценка качества обслуживания заданий).

3.2.4. Оценка результатов экспериментов серии 1.

3.2.5. Эксперимент по оценке количества обслуживаемых заданий и загруженности ресурсов для ОВС (эксперименты серии 2)

3.2.6. Оценка результатов эксперимента серии 2.

3.3. Выводы по главе 3.

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

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

Характер рассматриваемых задач, предназначенных для решения в рамках объединенной вычислительной среды, позволяет отнести такие вычислительные объединения к системам «оперативного» времени. Для целей настоящей работы требования систем разделения времени являются базовыми, а требования по гарантированному реагированию на недетерминированное количество внешних воздействий в ограниченное время, характерные для систем реального времени, не предъявляются. Решение задачи представляет собой процесс выполнения параллельной программы на некотором множестве вычислительных узлов одной или нескольких ВС. Будем называть такие параллельные программы вычислительными заданиями или заданиями. Свойством заданий является ограниченное время актуальности результатов их выполнения, характеризуемое для каждого из них функцией полезности (актуальности).

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

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

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

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

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

• вариативность среды. Состав ресурсов, состав пользователей и их заданий динамично меняются.

На сегодняшний день в ряде стран, в том числе в России и странах СНГ, уже созданы и используются объединенные вычислительные среды, организованные, в том числе, и в виде грид-систем [74,75,76], предназначенные для решения различных классов задач [62,82,87-90]. В США, помимо решения научных и образовательных задач (компьютерная сеть национального фонда научных исследований - NSF Сотр. Grid), грид-технологии активно используются в специальных и военных целях -информационная сеть поддержки НАСА (NASA Information Power Grid), глобальная информационная сеть министерства обороны (DOD GI Grid).

В настоящей работе проведены исследования на тему своевременного обслуживания заданий, обладающих свойством потери актуальности решения, в многопользовательском опытном сегменте объединенной вычислительной среды (ОВС). Архитектурно рассматриваемый опытный сегмент ОВС представляет собой объединение ряда ВС класса МВС-1000/15000 и имеет наименование сетевой среды распределенных вычислений (разработка НИИ «КВАНТ» и ИПМ им. М. В. Келдыша РАН, головное предприятие - МСЦ РАН). Существующие в ОВС средства планирования заданий [6,12,20,21,23-30] основаны на приоритетной схеме, не предусматривающей обеспечения своевременного обслуживания заданий, в силу чего требуется разработка как модели, так и программной реализации системы, устраняющий этот недостаток. Особенностью используемой сегодня в ОВС приоритетной схемы планирования является и то, что для каждой ВС, входящей в ее состав, шкала приоритетов пользователей и их заданий, в соответствии с которыми происходит определение очередности выполнения заданий, является уникальной. Это делает невозможной организацию взаимодействия ВС для перераспределения заданий между ними.

К организации вычислений в объединенной вычислительной среде предъявляются следующие общие требования, еще называемые требованиями к качеству обслуживания поступающих заданий (QoS - Quality of Service):

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

• надежность и постоянная доступность ресурсов;

• приемлемое для использования и предсказуемое время выполнения заданий.

В работах [20-23,25,26] рассматриваются решения, позволяющие организовать процесс обработки заданий в ОВС, отвечающий предъявляемым требованиям по безопасности объединяемых ресурсов и выполняющихся заданий, а также обеспечивающие постоянную доступность и надежность вычислительных ресурсов. Разрабатываемая в настоящей работе система планирования заданий и распределения ресурсов ориентирована на обеспечение приемлемого для использования и прогнозируемого времени обслуживания параллельных заданий пользователей при их назначении на вычислительные ресурсы ОВС.

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

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

Предложенный в настоящей работе вариант планирования заданий и ресурсов в ОВС основан на условно-стоимостном исчислении и позволяет пользователям производить индивидуальную оценку информационной важности задания, выражая ее в условных единицах, определяющих доступность вычислительных ресурсов. Для исключения возникновения «узкого места», характерного для централизованной организации системы управления распределенными ресурсами [1,79,40-43], и обеспечения масштабируемости предложена система планирования заданий объединенной вычислительной среды децентрализованного типа.

Исследования по организации управления заданиями на ЭВМ на основе условно-стоимостного исчисления проводились в конце семидесятых - начале восьмидесятых годов в Институте прикладной математики им. М. В. Келдыша РАН. Коллективом авторов, в числе которых Н. Е. Балакирев, М. Г. Тонконогов, А. Е. Фирсов. Были получены результаты, позволившие заложить основу для качественного повышения эффективности использования ресурсов вычислительных систем и автоматизации управления прохождением заданий мультипроцессорных ЭВМ. Результаты исследований позднее получили отражение в работах И. А. Бахарева и В. И. Крюкова [2]. Актуальность подтверждается также тем, что работы в данном направлении активно ведутся как зарубежными [33-40,80,85], так и отечественными производственными и научно-исследовательскими организациями (ИПМ РАН, ФГУП «НИИ «КВАНТ»).

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

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

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

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

Для достижения цели исследования были сформулированы следующие задачи:

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

2. Исследовать взаимное влияние заданий на время выполнения при решении на разделяемых вычислительных ресурсах.

3. Сформировать универсальный подход к определению очередности выполнения параллельных вычислительных заданий с прогнозируемым временем выполнения на узлах разнородных вычислительных систем.

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

5. Оценить применимость моделей условно-стоимостного исчисления для управления в распределенных вычислительных системах.

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

При решении поставленных задач применялись объектно-ориентированные методы и экспериментальные методы и методы анализа. В частности в работе использовались:

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

2. Объектно-ориентированные методы проектирования систем и программирования.

3. Аналитические и вероятностные математические методы.

4. Экспериментальные методы оценки качества систем. Диссертация состоит из введения, трех глав, заключения, списка

3.3. Выводы по главе 3

В данной главе определены основные требования по обеспечению гарантированного распределения заданий при работе СПЭА в ВС и ОВС. На основании статистических сведений о работе существующего сегмента ОВС (на основе систем класса МВС) с приоритетным управлением предложен подход к оценке эффективности работы ОВС под управлением СПЭА ' " ' '

Для ВС и ОВС с функционирующей СПЭА произведена оценка и сравнение с аналогичными характеристиками приоритетной схемы планирования таких параметров как:

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

- среднего значения загруженности ресурсов; - приведенного .среднего значения времени обслуживания заданий.

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

На основании проведенных экспериментов сделаны следующие общие выводы:

- выбранная модель и целевая функция работы СПЭА при планировании заданий в ВС и ОВС позволяют обеспечить требования по качеству обслуживания заданий в аспекте прогнозируемости времени обслуживания;

- величина средней загруженности ресурсов ВС не является информативной оценкой качества работы СПЭА. Для оценки ее эффективности следует использовать величины количества своевременно обслуженных заданий и величины приведенное среднее время обслуживания заданий (Кт);

- при планировании заданий с использованием СПЭА возможно достижение многократного ускорения обслуживания заданий пользователей при условии возможного сокращения количества своевременно обслуженных заданий. Степень ускорения обслуживания заданий определяется пользовательскими оценками их срочности и величиной выделяемой квоты. Таким образом, пользователь при постановке запроса о выполнении задания производит субъективную оценку важности его результатов, для которой обеспечивается сравнимость с аналогичными оценками других пользователей ВС и ОВС;

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

ЗАКЛЮЧЕНИЕ

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

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

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

Оценка работы СПЭА была проведена на основании статистических сведений о работе опытного сегмента ОВС и результатов экспериментов по моделированию работы для различных начальных условий в соответствии с критериями количества своевременно обслуженных заданий и приведенного среднего времени обслуживания заданий для ВС и

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

Направлениями дальнейших исследований являются:

1. Формирование процедур и автоматизированного способа определения трудоемкости заданий для каждого из видов ресурсов в ОВС, в том числе для случая совместного решения заданий на ресурсах различных ВС.

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

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

1. Баранов А.В., Лацис А.О., Храмцов М.Ю., Шарф С.В. Руководство системного программиста (администратора) системы управления прохождением задач МВС-5000. —Москва: ИПМ им. М. В. Келдыша РАН. Отдел ИВС и ЛС, сектор эксплуатации МВС, 2001, 65 с.

2. Бахарев И.А., Крюков В.А., Управление прохождением задач на ЭВМ, препринт Института прикладной математики им. М. В. Келдыша АН СССР, 1981, № 149, 24 с.

3. Коваленко В.Н., Корягин Д.А. Вычислительная инфраструктура будущего // Открытые системы. 1999. №11-12. С. 45-52.

4. Коваленко В.Н., Коваленко Е.И., Корягин Д.А., Любимский Э.З. Метод опережающего планирования для Грид. Препринт ИПМ им. М.В.Келдыша РАН, 2005, №112.

5. Корнай Я. Дефицит. М., 1990.к

6. Корнеев В.В, Киселёв А.В., Семёнов Д.В., Сахаров И.Е. Управление метакомпьютерными системами. // Журнал «Открытые системы» №2, 2005 г.

7. Ларичев О. И. Теория и методы принятия решений. М.: Логос, 2000, С.296, ISBN: 5-88439-046-7,

8. Лэйард Р. Макроэкономика. М., 1994.

9. Мюллер-Армак А. Принципы социального рыночного хозяйстваУ/Социальное рыночное хозяйство. СПб., 1999.

10. Самуэльсон П. Экономика в 2-х томах. Москва: МГП «Алгон» ВНИИСИ, 1992.

11. П. Е. Голосов. Об одной модели распределения заданий для обеспечения комплексной безопасности вычислений в грид-среде // Безопасность информационных технологий 2009, выпуск 4. М.: МИФИ -С. 90-93.

12. Корнеев В. В., Киселев А. В., Голосов П. Е. Планирование заданий в грид на основе экономической модели // Распределенные вычисления и

13. Грид-технологии в науке и образовании: Тез. докл. 2-й междунар. Конф. (Дубна, 26-30 июня 2006 г.). Дубна ОИЯИ, 2006, - С. 80.

14. Киселев А.В., Корнеев В.В., Баранов А.В., Зверев Е.Л., Подзоров

15. Корнеев В.В., Киселёв А.В., Семёнов Д.В., Сахаров И.Е.I

16. Семенов Д.В. Исследование моделей организации внешней памяти кластеров, включающей-локальные диски ВМ, файл-серверы кластера ифайл-серверы сетевой среды распределённых вычислений // Научный отчет, ЦНТК РАН, 2003. С. 68-74.

17. R. Buyya, D. Abramson, and J. Giddy, Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid, HPC ASIA'2000, China, IEEE CS Press, USA, 2000.

18. M. Stonebraker, R. Devine, M. Kornacker, W. Litwin, A. Pfeffer, A. Sah, C; Staelin, An Economic Paradigm for Query Processing and Data

19. Migration in Mariposa, Proceedings of 3rd International Conference on Parallel ' and Distributed Information Systems, Austin, TX, USA, 28-30 Sept. 1994. Los Alamitos, CA, USA: IEEE Computer Society Press, 1994.

20. C. Waldspurger, T. Hogg, B. Huberman, J. Kephart, and W. Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, Vol. 18, No. 2, Feb. 1992.

21. N. Nisan, S. London, O. Regev, N. Camiel, Globally Distributed computation over the Internet The POPCORN project, International Conference on Distributed Computing Systems (ICDCS'98), 1998.

22. В. Chun and D. Culler, Market-based proportional resource sharing for clusters, Technical report, University of California, Berkeley, September 1999.

23. G. Heiser, F. Lam, and S. Russell, Resource Management in the Mungi Single-Address-Space Operating System, Proceedings of Australasian Computer Science Conference, Perth Australia, Feb. 1998, Springer-Verlag, Singapore, 1998.

24. Y. Amir, B. Awerbuch., A. Barak A., S. Borgstrom, and A. Keren, An Opportunity Cost Approach for Job ; Assignment in a Scalable Computing Cluster, IEEE Tran. Parallel and Distributed Systems, Vol. 11, No. 7, July 2000.

25. D. Abramson, J. Giddy, and L. Kotler, High Performance Parametric Modeling with Nimrod/G:-Killer Application for the Global Grid?, IPDPS'2000, Mexico, IEEE CS Press, USA, 2000.

26. LoadLeveler for AIX 5L Version 3.2 Using and Administering, SA22-7881-01, IBM, Oct. 2003.

27. LSF Version 4.1 Administrator's Guide, Platform Computing, 2001.

28. OpenPBS Release 2.3 Administrator Guide, Altair Grid Technologies, Aug. 2000.

29. Sun ONE Grid Engine, Administration and User's Guide, Sun Microsystems, Oct. 2002.

30. Beiriger, J., Johnson, W., Bivens, H., Humphreys, S. and Rhea, R., Constructing the ASCI Grid. In Proc. 9th IEEE Symposium on High Performance Distributed Computing, 2000, IEEE Press.

31. Bolcer, G.A. and Kaiser, G. SWAP: Leveraging the Web To Manage Workflow. IEEE Internet Computing,: 85-88. 1999.

32. Grimshaw, A. and Wulf, W., Legion A View from 50,000 Feet. In Proc. 5th IEEE Symposium on High Performance Distributed Computing, 1996, IEEE Press, 89-99.

33. Nakada, H., Sato, M. and Sekiguchi, S. Design and Implementations of Ninf: towards a Global Computing Infrastructure. Future Generation Computing Systems, 1999.

34. I. Foster, C. Kesselman. Computational Grids. Chapter 2 of "The Grid: Blueprint for a New Computing Infrastructure", Morgan-Kaufman, 1999.

35. H. H. Mohamed and D. H. J. Epema. Experiences with the koala co-allocating scheduler in multiclusters. In CCGrid, pages 784-791. IEEE CS, 2005.

36. P. Saiz, P. Buncic, and A. J. Peters. AliEn resource brokers. In Computing in High Energy and Nuclear Physics, 2003. Also available as CoRR cs.DC/0306068.

37. N. Capit et al. A batch scheduler with high level components. In

38. CCGrid, pages 776-783, 2005. .- i

39. P. Buncic, A. J. Peters, P.Saiz. The AliEn system, status and perspectives. Computing in High Energy and Nuclear Physics, 24-28 March 2003, La Jolla, California.

40. A. Reinefeld et al. Managing clusters of geographically distributed high-performance computers. CP&E, 11(15):887-911, 1999.

41. Cluster Resources Inc. Moab workload manager administrator's guide. Tech. Doc. v.5.0, Jan 2007.

42. M. Ellert et al. Advanced Resource Connector middleware for lightweight computational grids. FGCS, 23(2):219-240, 2007.

43. D. Epema, M. Livny, R. Dantzig, X. Evers, and J. Pruyne. A worldwide flock of Condors: Load sharing among workstation clusters. FGCS, 12:53-65.

44. U. Schwiegelshohn and R. Yahyapour. Resource allocation and scheduling in metasystems. In DCM, volume 1593 of LNCS, "pages 851-860, 1999.

45. N. Andrade et al. OurGrid: An approach to easily assemble grids with equitable resource sharing. In JSSPP, volume 2862 of LNCS, pages 61-86, 2003.

46. M. Siddiqui, A. Villaz'on, and T. Fahringer. Grid allocation and reservation grid capacity planning with negotiation-based advance reservation for optimized qos. In SC, page 103, 2006.

47. D. Thain, T. Tannenbaum, and M. Livny. Distributed computing in practice: the condor experience. CP&E, 17(2-4):323-356, 2005.

48. K. Czajkowski et al. A resource management architecture for metacomputing systems. In IPPS/SPDP, pages 62-82, 1998.

49. The NorduGrid architecture and tools. P. Eerola et al. Computing in High Energy and Nuclear Physics, 24-28 March 2003, La Jolla, California.

50. R. Buyya, T. Cortes, and H. Jin, "Single System Image," The International Journal of High Perfoimance Computing Applications, vol. 15, no. 2, pp. 124-135, Summer 2001.

51. Foster, A. Roy, V. Sander, L. Winkler. End-to-End Quality of Service for High-End Applications. Technical Report, 1999.

52. S. Chapin, J. Karpovich, A. Grimshaw, The Legion Resource Management System, Proceedings.of the, 5th Workshop on Job Scheduling Strategies for Parallel Processing, April 1999.

53. M. Litzkow, M. Livny, and M. Mutka, Condor A Hunter of Idle Workstations, Proceedings-of-the-8th International Conference of Distributed Computing Systems, June 1988.

54. F. Berman and R. Wolski, The AppLeS Project: A Status Report, Proceedings of the 8th NEC Research Symposium, Berlin, Germany, May 1997.

55. H. Casanova and J. Dongarra, NetSolve: A Network Server for Solving Computational Science Problems, Intl. Journal of Supercomputing Applications and High Performance Computing, Vol. 11, Number 3, 1997.

56. N. Kapadia and J. Fortes, PUNCH: An Architecture for Web-Enabled Wide-Area Network-Computing, Cluster Computing: The Journal of Networks, Software Tools and Applications, September 1999.

57. B. N. Chun and D. E. Culler, "User-centric Performance Analysis of Market-based Cluster Batch Schedulers," in Proc. of 2nd IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2002), Berlin, Germany, May 2002.

58. Kindleberger Ch.P. Economic Development. N. Y., 1958.1. Электронные ресурсы

59. Российский грид для интенсивных вычислений. Петербургский институт ядерной физики им. Б. П. Константинова Электронный ресурс., http://egee.pnpi.nw.ru/cgi/index.cgi?Il=5&12=2 (проверено 24.11.2009).

60. Суперкомпьютерная программа «СКИФ-ГРИД» Электронный ресурс., http://skif.pereslavl.ru/psi-info/rcms-skif/index.ru.html (проверено 13.01.2010).

61. Российский грид для интенсивных операций с данными Russian Data Intensive Grid, RDIG, // Информационный ресурс в сети Интернет Электронный ресурс., www.egee-rdig.ru (проверено 01.03.2010).

62. Condor Version 6.7.1 Manual, University of Wisconsin-Madison, 2004. Электронный ресурс., http://www.cs.wisc.edu/condor/manual/v6.7 (проверено 24.11.2009).

63. Mojo Nation June 2001. Электронный , ресурс., http://www.oreillynet.eom/pub/d/262 (проверено 01.03.2010).

64. Workload Management System. Электронный ресурс., http://egee-jral-wm.mi.infn.it/egee-jral-wm/wms.shtml (проверено 01.03.2010).

65. Enabling Grids for E-sciencE (EGEE) Электронный ресурс., http://eu-egee.org (проверено 01.03.2010).

66. The EGEE grid infrastructure Электронный ресурс., http://egeena4.lal.in2p3.fr (проверено 01.03.2010).

67. XtremWeb: the Open Source Platform for Desktop Grids Электронный ресурс., http://www.xtremweb.net/ (проверено 01.03.2010).

68. SETI@Home Электронный ресурс., http://setiathome. ssl.berkeley.edu/ (проверено 01.03.2010).

69. Maui Scheduler Version 3.2 Administrator's Guide, Supercluster Research and Development Group ^ Электронный ресурс., http://www. supercluster.org/mauidocs/mauiadmin.shtml (проверено 01.03.2010).

70. The Grid3 collaboration Электронный ресурс., http://www.grid.org.il/?CategoryID=287 (проверено 01.03.2010).

71. TeraGrid open scientific discovery infrastructure Электронный ресурс., www.teragrid.org (проверено 01.03.2010).1. О (Ь>п

72. Global Ring Network for Advanced Applications Development (GLORIAD) Электронный ресурс., http://www.gloriad.org/gloriaddrupal (проверено 01.03.2010).

73. The GEANT Collaboration Электронный ресурс., http://www.geant.net/ (проверено 01.03.2010).

74. Inter-Operating Grids through Delegated MatchMaking. A. Iosup, D.H.J. Epema, T. Tannenbaum, M. Farrellee, M. Livny Электронный ресурс., www.cs.wisc.edu/condor/doc/SC07-Iosup.pdf (проверено 01.03.2010).4 .