Введение к работе
Актуальность темы
Широкое распространение в науке, образовании и в решении прикладных задач приобрели сегодня высокопроизводительные вычислительные системы. Все чаще к таким многопользовательским и одновременно обслуживающим несколько вычислительных задач большого масштаба системам предъявляется требование по обеспечению качества обслуживания - гарантированному времени выполнения поступающих ресурсных запросов. В зависимости от назначения вычислительной системы предоставление ресурсов в ней может отвечать требованиям систем разделения времени или систем реального времени. Для целей настоящей работы требования систем разделения времени являются базовыми, а требования по гарантированному реагированию на недетерминированное количество внешних воздействий в ограниченное время, характерные для систем реального времени, не предъявляются. В настоящей работе рассматривается вопрос гарантированного обслуживания системой части поступающих ресурсных запросов, основанного на конкурентном доступе к разделяемым ресурсам и субъективной пользовательской оценке важности результатов выполнения задач. В качестве исходного условия принимается априорное превышение количества ресурсных запросов над возможностями обслуживающей системы.
Рассматриваемые в работе ресурсные запросы - параллельные задания пользователей (назовем их заданиями) помимо ограничений по времени обслуживания, выраженных в виде характеристических функций потери ценности решения, обладают случайным временем выполнения. Свойство «устаревания» результатов выполнения заданий, возможность индивидуальной оценки пользователями «важности», позволяет отнести рассматриваемые вычислительные системы и их объединения к системам «оперативного» времени. Выполнение заданий происходит в оперативном режиме - до момента потери ими актуальности. Если задание было распределено на выполнение, но не было завершено своевременно, оно не считается выполненным успешно при оценке эффективности работы вычислителя и в вычислительном смысле эквивалентно его простою. В качестве показателей эффективности функционирования рассматриваемых вычислительных систем используются целевые функции, характеризующие процесс обработки (время выполнения) заданий и пропускную способность системы (количество своевременно обслуженных заданий). Сведения о средней загруженности ВС при этом не используются для оценки качества распределения заданий, поскольку не дают представления об эффективности ее работы, что отличает системы данного класса от систем разделения времени.
Рассматривается объединенная вычислительная среда, предназначенная для обслуживания заданий, состоящая из разнородных вычислительных систем (ВС), администрируемых независимо друг от друга и предоставляющих неотчуждаемые ресурсы для общего пользования. Высокую
актуальность на сегодняшний день представляет задача обеспечения своевременного обслуживания заданий, характеризуемых невозрастающей функцией потери ценности решения и случайным временем выполнения при условии априорной нехватки вычислительных ресурсов в гетерогенной вычислительной среде.
Применительно к объединенной вычислительной среде, рассматриваемой в настоящей работе, возможно указать следующие основные свойства:
территориальная распределенность. Входящие в ее состав ВС распределены в открытой глобальной сетевой среде. Рассматриваемая модель вычислений (обслуживания заданий) позволяет принять коммуникационные издержки не влияющими на организацию вычислений;
автономность ресурсов. База вычислительных ресурсов среды формируется из независимых друг от друга ВС или отдельных компьютеров. Ресурсы обслуживаются и администрируются владельцами, которые имеют право реализовывать независимую политику доступа к ним;
коллективный режим работы с неотчуждаемыми ресурсами. Ресурсы используются в коллективном режиме, поэтому должно обеспечиваться гибкое и скоординированное их распределение между пользователями, решающими различные задачи. При этом остается возможность использования ресурсов ВС локально, без полного отчуждения ресурсов в объединенную вычислительную среду;
вариативность среды. Состав ресурсов, состав пользователей и их заданий динамично меняются.
В работе проведены исследования на тему своевременного обслуживания заданий, обладающих свойством потери актуальности решения, в многопользовательском опытном сегменте объединенной среды вычислений (ОВС), получившей название сетевой среды распределенных вычислений. Архитектурно опытный сегмент среды представляет собой объединение ряда ВС класса МВС-1000/15000 (разработка НИИ «КВАНТ» и ИПМ им. М. В. Келдыша РАН, головное предприятие - МСЦ РАН). Существующие в данной ОВС средства планирования заданий основаны на приоритетной схеме, не предусматривающей обеспечение своевременного обслуживания заданий, в силу чего требуется разработка как модели, так и программной реализации системы, устраняющий этот недостаток.
Разработана программная система планирования выполнения заданий для ОВС, позволяющая обеспечить требования по прогнозируемости времени их обслуживания заданий, основанная на условно-стоимостном исчислении и применении алгоритмов экономических моделей. Впервые термин и модель условно-стоимостного исчисления были предложены в конце 70-х годов для применения в мультипрограммных ЭВМ пакетной обработки (БЭСМ-6, ОС ДИСПАК) коллективом авторов ИПМ РАН (Н. Е. Балакирев, М. Г. Тонконогов, А. Е. Фирсов, И. А. Бахарев, В. И. Крюков).
Использование системы управления, основанной на указанных принципах, позволяет осуществлять назначение поступающих параллельных
заданий на выполнение в соответствии с пользовательскими оценками важности выполнения заданий и временем потери актуальности их решений.
Целью работы было создание алгоритмов и программных средств, предназначенных для планирования заданий и ресурсов в распределенной вычислительной среде. Задания характеризуются параллелизмом, случайным временем выполнения и описываются невозрастающей функцией полезности на интервале планирования (обслуживания). Дисциплина планирования заданий, основанная на условно-стоимостном исчислении, должна отвечать требованиям прогнозируемости времени их обслуживания.
Для достижения поставленной цели в работе были решены следующие задачи:
Определены вероятностные характеристики случайной величины, характеризующей время выполнения заданий, претендующих на разделяемые вычислительные ресурсы.
Выявлено взаимное влияние заданий на время выполнения при решении на разделяемых вычислительных ресурсах.
Сформирован универсальный подход определения очередности выполнения параллельных вычислительных заданий с прогнозируемым временем выполнения на узлах разнородных вычислительных систем.
Разработан способ оценки эффективности работы системы планирования, основанной на применении алгоритмов экономической модели.
Исследована применимость моделей условно-стоимостного исчисления для управления заданиями и ресурсами в распределенных вычислительных системах.
Создана система, реализующая способ управления заданиями в ОВС на основе условно-стоимостного подхода.
В качестве объектов исследования выступали механизмы управления ресурсами и заданиями в распределенных вычислительных системах, величины вероятностных характеристик случайного времени совместного выполнения заданий на разделяемых ресурсах, параллельные вычислительные задания, характеризуемые функцией потери ценности решения.
Научная новизна работы состоит в следующем:
Получены вероятностные характеристики случайной величины -минимального времени совместного выполнения параллельных заданий (в частности - для двух заданий), сохраняющих актуальность решения, на разделяемых ресурсах ВС.
Описан подход к распределению заданий в разнородной вычислительной среде, позволяющий максимизировать итоговую актуальность выполненных заданий на интервале планирования.
Предложен способ дифференциации заданий пользователей по важности (актуальности) на основе условно-стоимостного исчисления и алгоритм организации очередей заданий при индивидуальной оценке пользователями значимости заданий.
Реализован способ динамического перераспределения заданий в очереди, позволяющий сократить время простоя ресурсов при поступлении
внеочередных заданий и досрочном окончании выполнения запланированных заданий.
Практическая ценность исследования заключается в следующем:
Реализована децентрализованная система планирования заданий, использующая алгоритмы экономических моделей, предназначенная для планирования заданий в ВС и объединенной вычислительной среде, обеспечивающая прогнозируемое время выполнения заданий, характеризуемых невозрастающей функцией полезности.
Разработаны средства моделирования работы системы управления и подход к формированию модифицированного потока заданий для проведения имитационных экспериментов на основе реальной статистики работы ВС.
Обеспечена совместимость разработанной системы планирования заданий с существующей (систем семейства MB С, головные исполнители «НИИ «Квант» и ИПМ РАН). Предусмотрена ее работа в режиме действующей (приоритетной) системы планирования заданий.
Результаты, полученные в работе, использовались для выполнения государственного контракта № 26-2/2009 от 01 июня 2009 года «Разработка программного обеспечения автоматизированной системы, состоящей из удаленных вычислительных кластеров». Разработанные автором программные средства прошли государственную регистрацию [12] и являются базовыми для комплекса высокопроизводительных вычислителей, разработанного ЗАО «Закрытые технологии». Материалы диссертационной работы введены в учебный курс и используются в рамках лекционных и практических занятий по профилю кафедры 732 ИКСИ Академии ФСБ России.
Основные положения, выносимые на защиту:
Модель системы планирования очередности выполнения заданий на основе условно-стоимостного исчисления, обеспечивающая выполнение требований предсказуемого времени обслуживания в распределенной вычислительной среде.
Способ дифференциации заданий, основанный на пользовательской оценке значимости заданий, характеризуемых случайным временем выполнения и невозрастающей функцией актуальности (полезности).
Модель двухуровневой децентрализованной системы управления ресурсами объединенной вычислительной среды.
Апробация работы. Результаты диссертации прошли апробацию -обсуждались на научно-технической конференции ФГУП «НИИ «Квант» 10 февраля 2005 года и научной конференции МГУ им. М. В. Ломоносова 5 октября 2005 года; на международных конференциях «Распределённые вычисления и ГРИД-технологии в науке и образовании», проходивших 26-30 июня 2006 года и 30 июня - 4 июля 2008 года в ОИЯИ (г. Дубна); на международной конференции «Программные системы: теория и приложения», проходившей в ИСП РАН (г. Переславль-Залесский) в октябре 2006 года; на Всероссийских научных конференциях «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ», проходившей с 24 по 29 сентября 2007 года, и «Научный сервис в сети Интернет: масштабируемость,
параллельность, эффективность», проходившей с 21 по 26 сентября 2009 года в г. Новороссийске (пос. Абрау-Дюрсо), на научном семинаре, проходившем 27 февраля 2008 года в ИПМ им. М. В. Келдыша РАН.
Структура, объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 91 наименование. Общий объем диссертации составляет 106 страниц, включая 5 таблиц и 15 иллюстраций.
