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

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

Березовский Павел Сергеевич

УПРАВЛЕНИЕ ЗАДАНИЯМИ В ГРИДЕ С ^КЛАСТЕРИЗОВАННЫМИ РЕСУРСАМИ

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

1 9 МАЙ 2011

Москва —2011

4846760

Работа выполнена в Институте прикладной математики им. М.В. Келдыша Российской академии наук.

Научный руководитель: кандидат физико-математических наук

Коваленко Виктор Николаевич.

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

Лацис Алексей Оттович,

кандидат физико-математических наук Крюков Александр Павлович.

Ведущая организация: Объединённый институт ядерных исследований

(ОИЯИ, г. Дубна).

Защита состоится 14 июня 2011 г. в 11 часов на заседании диссертационного совета Д 002.024.01 в Институте прикладной математики им. М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН.

Автореферат разослан » апреля 2011 г.

Учёный секретарь диссертационного совета, доктор физико-математических наук

Т.А. Полилова

Общая характеристика работы

Актуальность темы

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

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

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

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

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

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

В таких условиях наиболее привлекательным выглядит применение масштабных одноуровневых гридов для выполнения серийных расчётов в виде набора независимых заданий, которые могут обрабатываться параллельно на разных ресурсах, не обмениваясь данными. В этом смысле их можно рассматривать как части одного слабо связанного параллельного задания. Приложения такого класса обрабатываются в проектах, созданных на платформе BOINC (SETI@Home, ClimatePrediction.net и др.).

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

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

4. Предоставление дистанционного доступа к приложениям. Понятие ресурса в гриде является очень широким и не ограничивается только

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

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

Цель и задачи работы

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

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

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

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

4. Программная реализация системы диспетчеризации для рассматриваемой формы грида.

Научная новизна

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

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

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

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

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

Практическая значимость

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

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

Апробация работы

Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

1. 1-я международная конференция «Распределённые вычисления и грид-технологии в науке и образовании». Доклад «Политика предоставления ресурсов в грид», Дубна, 29 июня-2 июля 2004 г.

2. Семинар МГУ им. М.В. Ломоносова «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н. В. А. Васенина. Доклад «Способы планирования в гриде и их реализация в грид-диспетчере», Москва, 12 апреля 2005 г.

3. Семинар группы разработчиков программного обеспечения для грид-инфраструктуры EGEE ARDA под руководством M. Lamanna. Доклад «KIAM in GT4 Evaluation Activity and Grid Research», CERN, Женева, 12 октября 2005 г.

4. 13-я Всероссийская научно-методическая конференция «Телематика-2006». Доклад «Создание прототипа центра базовых грид-сервисов нового поколения для интенсивных операций с распределёнными данными в федеральном масштабе», Санкт-Петербург, 5-8 июня 2006 г.

5. 2-я международная конференция «Распределённые вычисления и грид-технологии в науке и образовании». Доклад «Способ построения грид из некластеризованных ресурсов», Дубна, 26-30 июня 2006 г.

6. Научная конференция «Ломоносовские чтения», факультет ВМиК МГУ им. М.В. Ломоносова. Доклад «Способ построения грида из некластеризованных ресурсов», Москва, 16-24 апреля 2008 г.

7. 3-я международная конференция «Распределённые вычисления и грид-технологии в науке и образовании». Доклад «Механизмы управления разделяемыми компьютерами в гриде», Дубна, 29 июня-4 июля 2008 г.

8. 4-я международная конференция «Распределённые вычисления и грид-технологии в науке и образовании». Доклад «Применение грида с некластеризованными ресурсами для задач проектирования физических устройств», Дубна, 28 июня-3 июля 2010 г.

По материалам диссертации опубликовано 7 печатных работ [1], [2], [3], [4], [5], [6] и [7], в том числе, одна [4] — в журнале, рекомендованном ВАК для публикации основных результатов докторских и кандидатских диссертаций по вычислительной технике и информатике.

Структура и объём работы

Работа состоит из введения, пяти глав, заключения, списка литературы и двух приложений. Общий объём диссертации — 128 страниц. Список литературы содержит 60 наименований. В работе содержится 20 рисунков и одна таблица.

Содержание работы

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

Первая глава является обзорной и содержит анализ существующих решений для организации вычислительных инфраструктур из некластеризованных компьютеров. При рассмотрении наиболее развитых средств выделены четыре подхода: первый основан на создании проектов, направленных на решение отдельных задач; второй подход состоит в применении Р2Р-технологий и объединении исполнительных компьютеров в одноранговые сети; к третьему подходу отнесены системы с централизованным управлением; четвёртый подход представлен частными разработками корпоративных систем. Анализ систем, реализующих каждый из представленных подходов, показал, что ни одна из них не решает всей

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

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

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

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

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

• стандартизованность — соответствие общепринятым стандартам грида, обеспечивающее возможность функционирования соответствующих грид-инфраструктур как автономно, так и в составе объемлющего грида с любыми формами организации ресурсов;

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

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

Специфические особенности неотчуждаемых ресурсов определяют дополнительные требования:

• соблюдение приоритетов — выполнение задания грида на исполнительном компьютере не должно мешать работе владельца;

• автономность ресурсов — сохранение за владельцем полного контроля над своим компьютером и закрепление за ним права решать, кому, когда и сколько ресурсов он готов предоставить;

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

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

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

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

Рис. 1. Архитектура системы диспетчеризации

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

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

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

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

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

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

• информационная служба (осуществляет обработку непосредственно поставляемой в базу информации о загрузке ресурсов и агрегирует её для предоставления другим грид-системам);

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

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

запросу диспетчера агент снимает задание с выполнения. На протяжении всего времени выполнения агент посылает диспетчеру отчёты о своём состоянии и загрузке компьютера.

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

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

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

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

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

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

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

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

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

Далее в диссертационной работе даётся формальная постановка задачи планирования, а также приводится сравнение качества планирования алгоритмов FCFS (First Come First Serve) и его модификации ECP-FCFS (Effective Computer Power-FCFS). Критерием выступает число отказов по превышению предельного срока.

Задача планирования решается в следующих условиях.

• В грид поступает поток заданий.

• Алгоритм планирования выполняет распределение заданий по компьютерам в режиме on-line, то есть каждое задание распределяется независимо от других.

• Исходными данными для планирования являются время выполнения задания на эталонном компьютере, предельный срок выполнения задания и эффективная производительность компьютера.

Алгоритм FCFS.

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

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

Алгоритм ECP-FCFS.

В этом алгоритме на шаге 1 меняется способ выбора исполнительного компьютера:

1.1. Выбирается первое задание из очереди.

1.2. Задание распределяется только на тот компьютер, где оно может окончиться в срок. Если таких компьютеров нет, делается попытка распределить следующее задание из очереди.

Для оценки качества планирования по предложенному алгоритму ЕСР-FCFS используется моделирование работы алгоритмов FCFS и ECP-FCFS на синтетических входных данных, которые описывают поток заданий и характеристики компьютеров ресурсного пула.

Компьютеры в количестве Nc= 100 имеют эффективные производительности, генерируемые случайным образом по равномерному распределению из диапазона [0.1, 1.0]. Длины заданий и времена их поступления также задаются равномерным распределением. Диапазон длин заданий — [150, 750], задания поступают на временном отрезке [0, 75], где TS — минимально возможное время обработки потока, вычисляемое как отношение суммарной длины всех заданий к суммарной производительности компьютеров. Предельный срок выполнения заданий выбирается пропорционально их длине D,=a* fV,-, Коэффициент а, фактически определяет нижнюю границу эффективной производительности, при которой задание может выполниться в срок. Значения ai равномерно распределены в диапазоне [1.1, 5.0].

В результате моделирования обработки пакета заданий получено, что количество отказов алгоритма FCFS составляет 20.1% от общего числа заданий, в то время как количество отказов алгоритма ECP-FCFS — 3%. Улучшение, которое даёт учёт эффективной производительности, — значимое, но не слишком большое. Объясняется это тем, что компьютеры со слабой производительностью, на которых в основном и происходят отказы, вносят небольшой вклад в суммарную производительность грида. Если число таких компьютеров увеличивается, и соответственно растёт их вклад, преимущество ECP-FCFS становится весьма существенным. Это подтверждается моделированием, которое показывает, что при росте суммарной производительности пула компьютеров, в алгоритме FCFS число отказов линейно увеличивается, так как с большей вероятностью задания попадают на компьютеры с недостаточной производительностью. В то же время в алгоритме ECP-FCFS при недостаточной производительности компьютера для выполнения задания оно не распределяется на него, и число отказов остаётся постоянным.

Из-за неточности предсказания загрузки компьютера прогнозируемая производительность будет отличаться от получаемой заданием во время выполнения. Отдельная серия экспериментов была направлена на изучение влияния точности прогноза на число отказов. Относительное отклонение реально получаемой производительности Нг от прогнозируемой Я задаётся величиной R, Hr=H*(l+R). Значения R генерируются по нормальному распределению со средним значением 0 и стандартным отклонением а. Величина а является параметром исследования: при о= 0 время выполнения заданий совпадает с прогнозируемым, при больших а оно может значительно

отклоняться от прогноза. Моделирование показывает, что использование прогноза в алгоритме ECP-FCFS уменьшает число отказов в исследованном диапазоне 0 < а < 1. При добавлении в пул слабых компьютеров эффект становится ещё более заметным.

Последний раздел главы посвящен повышению эффективности использования пула неотчуждаемых компьютеров. Помимо уменьшения числа отказов учёт эффективной производительности даёт дополнительный эффект: при точном прогнозе (о=0) невозможность обработки задания в срок определяется в период его нахождения в очереди, так что не выполнимое в срок задание даже не распределяется на компьютер. Когда а Ф 0, возможны два вида отказов: по превышению времени ожидания в очереди и по превышению времени выполнения. Наличие прогноза позволяет, во-первых, заблаговременно информировать пользователей о невозможности обработки их заданий в срок и, во-вторых, не тратить ресурсы впустую. Для оценки того, насколько продуктивно используется мощность ресурсного пула, используется степень полезной загрузки ресурсов теми заданиями, которые завершаются в срок. Моделирование работы алгоритмов показало, что для пула компьютеров с равномерным распределением производительностей полезная загрузка составляет 40%. Когда к нему добавляются слабые компьютеры, суммарная мощность возрастает, но доля полезной загрузки уменьшается до 15%.

Причина того, что задания получают отказ в обслуживании, в то время как в системе имеются незанятые компьютеры, причём в любом количестве, состоит в том, что эти компьютеры имеют недостаточно высокую производительность для выполнения заданий в срок. Более полная загрузка ресурсов может быть достигнута с помощью известного способа запуска заданий в виде пакетов подзаданий (Bag-of-Tasks). Согласно этому способу задание разбивается на множество подзаданий, каждое из которых выполняет часть вычислений. Наибольший эффект такое разбиение даёт, если подзадания являются независимыми друг от друга и могут выполняться параллельно. Тогда можно обработать всю совокупность подзаданий в срок, определённый для исходного задания, но при меньших требованиях к производительности компьютеров. Таким образом, для обработки задания удаётся использовать большее число слабых компьютеров и увеличить степень полезной загрузки пула.

Четвёртая глава посвящена программной реализации системы диспетчеризации заданий для грида с некластеризованными ресурсами (SARD — StandAlone Resource Dispatcher), выполненной в соответствии с предложенной во второй главе архитектурой (рис. 1).

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

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

Рис. 2. Архитектура с интеграцией компонентов системы Condor

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

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

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

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

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

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

В пятой главе содержится описание прикладных задач, решённых с помощью разработанной системы. В Институте прикладной математики им. М.В. Келдыша РАН создана действующая экспериментальная вычислительная инфраструктура из ^кластеризованных ресурсов. В состав инфраструктуры входит диспетчер, расположенный на выделенном компьютере под управлением операционной системы Linux, а также десять исполнительных компьютеров под управлением операционной системы Windows различных версий производительностью от 200 до 700 мегафлопс.

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

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

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

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

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

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

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

Основные результаты

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

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

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

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

Список публикаций по теме диссертации

[1]. П.С. Березовский, В.Н. Коваленко. Политика предоставления ресурсов в грид // Распределённые вычисления и Грид-технологии в науке и образовании: Труды международной конференции. Дубна: ОИЯИ, 2004. С. 36-41.

[2]. Березовский П.С., Коваленко В.Н. Способ построения грид из некластеризованных ресурсов // Распределённые вычисления и Грид-технологии в науке и образовании: Труды 2-й международной конференции. Дубна: ОИЯИ, 2006. С. 216-226.

[3]. П.С. Березовский, В.Н. Коваленко. Состав и функции системы диспетчеризации заданий в гриде с некластеризованными ресурсами // Препринт № 67. Москва: ИПМ им. М.В.Келдыша РАН, 2007. 29 с.

[4]. П.С. Березовский, В.Н. Коваленко. Планирование в гриде с разделяемыми ресурсами на основе статистических данных // Программные продукты и системы. 2009. № 1(85). С. 3-6.

[5]. П.С. Березовский. Реализация системы диспетчеризации заданий SARD в одноуровневом гриде // Препринт № 49. Москва: ИПМ им. М.В.Келдыша РАН, 2010. 32 с.

[6]. П.С. Березовский, В.Н. Емельянов, В.Н. Коваленко, Э.С. Луховицкая Механизмы управления разделяемыми компьютерами в гриде // Распределённые вычисления и Грид-технологии в науке и образовании: Труды 3-й международной конференции. Дубна: ОИЯИ, 2008. С. 303306.

[7]. П.С. Березовский, A.C. Родин. Проведение оптимизационных расчётов для магнитного компрессора с использованием грида персональных компьютеров, управляемых системой SARD // Препринт № 7. Москва: ИПМ им. М.В.Келдыша РАН, 2011. 31 с.

Подписано в печать 14.04.2011. Формат 60x90/16. Усл. печ. л. 1,0. Тираж 70 экз. Заказ 7-30. ИПМ им.М.В.Келдыша РАН. 125047, Москва, Миусская пл., 4

Содержание.

Введение.

Грид с ^кластеризованными ресурсами.

Цель и задачи работы.10

Научная новизна.11

Практическая значимость.12

Апробация работы.13

Структура и объём работы.14

Краткое содержание работы.14

3.2.1.4. Выводы

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

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

3.2.2. Алгоритмы, использующие информацию о ресурсах и заданиях

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

3.2.2.1. Способы выбора очередного задания

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

Во время работы планировщику необходимо принять два основных решения — какое задание распределять следующим, и на какой исполнительный компьютер его направить. В предыдущем разделе был представлен случайный алгоритм который, не обладая информацией о компьютерах и заданиях, случайным образом определял очередное задание и таким же образом выбирал для задания исполнительный компьютер. В дальнейшем рассмотрении выделяется два возможных варианта для выбора очередного задания (самое короткое — Short, или самое длинное — Long) и четыре возможных варианта полноты информации о компьютерах (нет информации — Nolnfo, информация о производительности — Cpulnfo, информация о доступности — Availlnfo, наличие полной информации — Fulllnfo). Таким образом, в зависимости от имеющейся информации получается восемь возможных алгоритмов планирования.

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

3.2.2.2 Способы определения подходящего компьютера

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

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

3.2.3. Алгоритмы с пакетным распределением заданий

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

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

Обозначим величиной 1/Гу полезность выполнения задания / на компьютере у. Тогда построение решения заключается в поиске оптимального распределения заданий по исполнительным компьютерам в соответствии с полезностью каждого назначения и состоит в максимизации суммы *ХЦ, где Ху = 1 в том случае, если задание / выполняется на 7 компьютере у, и Хч = 0 в противном случае. 3.2.4. Выводы

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

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

3.3. Метод планирования, направленный на завершение заданий в заданный срок

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

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

3.3.1. Задача планирования в гриде с неотчуждаемыми ресурсами

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

Для планирования в гриде с неотчуждаемыми компьютерами наиболее важными являются характеристики, определяющие загрузку ресурсов и позволяющие её прогнозировать. Разработаны модели [40], [41], [44], которые предсказывают состояние ресурсов в пределах коротких отрезков времени (1-15 секунд). Эти модели служат основой для разработки механизмов разделения ресурсов компьютера.

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

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

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

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

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

3.3.2. Использование прогноза эффективной производительности

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

Сформулируем условия, в которых решается задача планирования. В грид поступает поток заданий {Jt, i~ 1,2,.}. Алгоритм планирования выполняет распределение заданий по компьютерам {Ск, к—\,.,Nc} в режиме on-line, то есть каждое задание распределяется независимо от других. Исходными данными планирования являются:

• характеристики заданий: длина (время выполнения на эталонном компьютере) W; и предельный срок выполнения Д-;

• характеристики компьютеров: эффективная производительность Щ.

Обычно для неотчуждаемых компьютеров используются алгоритмы планирования, которые опираются* лишь на характеристики заданий: рассмотренный ранее алгоритм WQ и его модификации, а также такие алгоритмы как First Come-First Serve (FCFS) и List Scheduling. Однако любой из этих алгоритмов может быть модифицирован для учёта эффективной производительности компьютеров. В следующих разделах проводится сравнение качества планирования алгоритмов FCFS и его модификации ЕСР-FCFS (Effective Computer Power-FCFS). Критерием выступает число отказов по превышению предельного срока.

Алгоритм FCFS.

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

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

Алгоритм ECP-FCFS.

В этом алгоритме на шаге 1 меняется способ выбора исполнительного компьютера:

1.1. Выбирается первое задание из очереди.

1.2. Задание распределяется только на тот компьютер, где оно может окончиться в срок. Если таких компьютеров нет, делается попытка распределить следующее задание из очереди.

3.3.3. Оценка качества планирования

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

Компьютеры в количестве 7Vc=100 имеют эффективные производительности, генерируемые случайным образом по равномерному распределению из диапазона [0.1, 1.0]. Длины заданий и времена их поступления также задаются равномерным распределением. Диапазон длин заданий — [150, 750], задания поступают на временном отрезке [0, 15], где TS — минимально возможное время обработки потока, вычисляемое как отношение суммарной длины всех заданий к суммарной производительности компьютеров. Предельный срок выполнения заданий выбирается пропорционально их длине Д—с^*^. Коэффициент а, фактически определяет нижнюю границу эффективной производительности, при которой задание может выполниться в срок, оц равномерно распределены- в диапазоне [1.1,5.0].

В результате моделирования обработки пакета из 1000 заданий получено, что количество отказов алгоритма БСРБ (201, то есть 20.1% от числа заданий) превосходит количество отказов алгоритма ЕСР-РСББ (30, то есть 3%). Улучшение, которое даёт учёт эффективной производительности, — значимое, но не слишком большое. Объясняется это тем, что компьютеры со слабой производительностью (Н<0.5), на которых в основном и происходят отказы, вносят небольшой вклад в суммарную» производительность грида. Если число таких компьютеров увеличивается, и соответственно растёт их вклад, преимущество ЕСР-РСР8 становится весьма существенным. Это иллюстрируется экспериментом, в котором к компьютерному пулу, описанному выше, добавляются дополнительные слабые (//=0.2) компьютеры. График зависимости количества отказов от числа добавленных компьютеров представлен на рис. 7. Хотя суммарная производительность растёт, в алгоритме РСБЗ число отказов линейно увеличивается, в то время как в ЕСР-РСРБ оно остаётся постоянным.

В реальности прогнозируемая производительность.будет отличаться от получаемой заданием во время выполнения. В следующем эксперименте изучалось влияние точности прогноза на число отказов: Относительное отклонение реально получаемой производительности Нг от прогнозируемой Н задаётся величиной Я, Нг—Н*(1+Я). Значения К генерируются по нормальному распределению со средним значением 0 и стандартным отклонением а. Величина а является» параметром исследования: при а=0 время выполнения заданий совпадает с прогнозируемым, при больших а оно может значительно отклоняться от прогноза.

10 0

I Т А * * *---^ * ^ * * -4

100 150 200 250 300 350 400 450 500 550 600

Количество узлов (100 + слабые узлы)

-■—ЯСРБ

А—ЕСР-РСРЭ

Рис. 7. Зависимость числа отказов от количества добавленных слабых компьютеров

Рисунок 8 соответствует условиям, когда производительности компьютеров и коэффициенты а, (определяющие предельные сроки заданий) распределены равномерно. Как видно из графика, использование прогноза в алгоритме БСР-БСРв уменьшает число отказов в исследованном диапазоне 0 <а< 1. При добавлении в пул слабых компьютеров (рис. 9) эффект становится ещё более заметным.

45 40

35 -30 -

5 0

О 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 а в—РСРБ —А—ЕСР-РСРЭ ь.

Рис. 8. Зависимость числа отказов от параметра а

Рис. 9. Зависимость числа отказов от параметра а (добавлено 100 слабых компьютеров)

3.3.4. Эффективное использование пула неотчуждаемых компьютеров

Помимо уменьшения числа отказов учёт эффективной производительности компьютеров даёт дополнительный эффект: при точном прогнозе (а=0) невозможность обработки задания в срок определяется в период его нахождения в очереди, так что задание даже не распределяется на компьютер. Когда а тФ возможны два вида отказов: по превышению времени ожидания в очереди и по превышению времени выполнения (рис. 10).

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

Суммирование в числителе отношения ведётся по всем заданиям, которые обработаны в срок, 5Т/ и ГТ; — время старта и завершения задания /, Н. — эффективная производительность компьютера во время выполнения задания. В выражении М8*НТ, стоящем в знаменателе, МБ обозначает время счёта пакета заданий, НТ = ^Нк , где Нк — эффективная производительность к компьютера за время М?, и суммирование ведётся по всем компьютерам ресурсного пула. по превышению времени ожидания в очереди I —а—по превышению времени выполнения

Рис. 10. Соотношение числа отказов по превышению времени ожидания в очереди и по превышению времени выполнения

Для исходного пула (с равномерным распределением производительностей) полезная загрузка составляет 40%. Когда к нему добавляются слабые компьютеры, суммарная мощность возрастает, но доля полезной загрузки уменьшается до 15% (рис. 11).

Количество компьютеров (100 + слабые)

Рис. 11. Полезная загрузка пула при добавлении слабых компьютеров

Причина того, что задания получают отказ в обслуживании, в то время как в системе имеются незанятые компьютеры, причём в любом количестве, состоит в том, что эти компьютеры имеют недостаточно высокую производительность для выполнения заданий в срок. Более полная загрузка ресурсов может быть достигнута с помощью известного способа запуска заданий в виде пакетов подзаданий (Ва§-о£-Та8кз) [46]. Согласно этому способу задание «/ разбивается на множество подзаданий {SJl,., каждое из которых выполняет часть вычислений. Наибольший эффект такое разбиение даёт, если подзадания являются независимыми друг от друга и могут выполняться параллельно. Тогда можно обработать всю совокупность подзаданий в срок, определённый для задания J, но при меньших требованиях к производительности компьютеров.

Время обработки задания J длины IV на компьютере с у ж производительностью Н составляет Т- — -\-Q-\-DV, здесь — — время н н выполнения, <2 — время ожидания в очереди, йУ— время доставки входных и выходных файлов. Тогда минимальная производительность компьютера, обеспечивающая выполнение задания за время ИЬ, оставшееся до

И7 наступления предельного срока, равна #тт = ——.

Если задание J разбито на М подзаданий &/}, которые отличаются

IV только входными данными, то время обработки каждого Т^ — л-^З^ЭУ,.

Н1

Всё множество подзаданий будет обработано за тот же предельный срок ИЬ, Ж что и исходное задание, если — + 01+ВУ,<ВЬ для всех 1=1,.,М.

Я,

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

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

Заключение

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

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

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

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

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

1. П.С. Березовский, В.Н. Коваленко. Состав и функции системы диспетчеризации заданий в гриде с ^кластеризованными ресурсами // Препринт №> 67. Москва: ИПМ им. М.В.Келдыша РАН, 2007. 29 с. http://gridclub.ru/library/publication.2008-10-20.3546711477

2. П.С. Березовский, В.Н. Коваленко. Планирование в гриде с разделяемыми ресурсами на основе статистических данных // Программные продукты и системы. 2009. № 1(85). С. 3-6.

3. П.С. Березовский. Реализация системы диспетчеризации заданий SARD в одноуровневом гриде // Препринт № 49. Москва: ИПМ им. М.В.Келдыша РАН, 2010. 32 с.

4. П.С. Березовский, В.Н. Емельянов, В.Н. Коваленко, Э.С. Луховицкая Механизмы управления разделяемыми компьютерами в гриде // Распределённые вычисления и Грид-технологии в науке и образовании:

5. Труды 3-й международной конференции. Дубна: ОИЯИ, 2008. С. 303306.

6. П.С. Березовский, А.С. Родин. Проведение оптимизационных расчётов для магнитного компрессора с использованием грида персональных компьютеров, управляемых системой SARD // Препринт № 7. Москва: ИПМ им. М.В.Келдыша РАН, 2011. 31 с.

7. Коваленко В.Н., Корягин Д.А. Организация ресурсов в грид // Препринт № 63. Москва: ИПМ им. М.В.Келдыша РАН, 2004. 25 с.

8. Инструментарий Globus Toolkit — http://www.globus.org

9. Проект gLite — http://glite.web.cern.ch

10. D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, D. Werthimer. SETI@home: An Experiment in Public-Resource Computing. Communications of the ACM, Vol. 45 No. 11, November 2002, pp. 56-61.

11. Проект SZTAKI Desktop Grid — http://szdg.lpds.sztaki.hu/szdg

12. Peer-to-Peer — http://www.openp2p.com

13. D. P. Anderson: BOINC: A System for Public-Resource Computing and Storage. 5th IEEE/ACM International Workshop on Grid Computing, November 2004, pp. 1-7.

14. СУБД MySQL — http://www.mysql.com

15. D. Zhou, V. Lo: Cluster Computing on the Fly: resource discovery in a cycle sharing peer-to-peer system. Fourth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'04), 2004, pp. 66-73.

16. W. Cirne, F. Brasileiro, N. Andrade, R. Santos, A. Andrade: Labs of the World, Unite!!! Journal of Grid Computing, Vol.4, No. 3, September 2006, pp. 225-246.

17. Монитор виртуальных машин Xen — http://www.xensource.com

18. С.И. Соболев. Управление заданиями в Виртуальном метакомпьютерном центре на основе технологий Х-Сот. // Распределённые вычисления и Грид-технологии в науке и образовании:

19. Труды 2-й международной конференции. Дубна: ОИЯИ, 2006. С. 401— 404.

20. Воеводин Вл.В., Жолудев Ю.А., Соболев С.И., Стефанов К.С. Эволюция системы метакомпьютинга Х-Сош // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. №4. 2009. С. 157-164.

21. R. Housley, W. Polk, W. Ford, D. Solo. Internet X.509 Public Key Infrastructure. Certificate and Certificate Revocation List (CRL) Profile.

22. O. Lodygensky, G. Fedak, F. Cappello, V. Neri, M. Livny, D. Thain. XtremWeb & Condor sharing resources between Internet connected Condor pools. CCGrid, pp.382, Third IEEE International Symposium on Cluster Computing and the Grid (CCGrid'03), 2003.

23. Система Entropía — http://www.entropia.com

24. Система Condor — http://www.cs.wisc.edu/condor

25. M. Solomon. The ClassAd Language Reference Manual, Version 2.4, 2004.

26. R. Raman, M. Livny, M. Solomon. Matchmaking: An extensible framework for distributed resource management, Springer Netherlands, 2004.

27. Служба управления заданиями GRAM http://www.globus.org/gridsoitware/computation/gram.php

28. Resource Specification Language. http://www.globus.Org/toolkit/docs/4.0/execution/wsgram/schemas/gramJo bdescription.html

29. A. Anjomshoaa, F. Brisard, M. Drescher, D. Fellows, A. Ly, A.S. McGough, D. Pulsipher, and A. Sawa. Job Submission Description Language (JSDL) specification, version 1.0. http://www.ogf.org/documents/GFD.56.pdf

30. I. Foster, C. Kesselman, J. Nick, S. Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. http://www.globus.org/reseach/papers/ogsa.pdf

31. E. Christensen, F. Curbera, G. Meredith, S. Weerawarana. Web Services Description Language (WSDL) 1.1.http://www.w3 .org/TR/wsdl

32. C. Kenyon, G. Cheliotis. Creating Services with Hard Guarantees from Cycle-Harvesting Systems. Third IEEE International Symposium on Cluster Computing and the Grid (CCGrid'03). pp.224. 2003.

33. D.P. Anderson, G. Fedak. The Computational and Storage Potential of Volunteer Computing. IEEE/ACM International Symposium on Cluster Computing and the Grid, Singapore, May 16-19, 2006.

34. P. Dinda, G. Memik, R. Dick, B. Lin, A. Mallik, A. Gupta, S. Rossoff. The User In Experimental Computer Systems Research, Proceedings of the Workshop on Experimental Computer Science (ExpCS 2007), June 2007.

35. K.D. Ryu, J.K. Hollingsworth. Resource Policing to Support Fine-Grain Cycle Stealing in Networks of Workstations. IEEE Transactions On Parallel And Distributed Systems, Vol. 15, No. 9, September 2004:

36. L. Eggert, J.D. Touch. Idletime Scheduling with Preemption Intervals.Proc. SOSP 005. http://www.isi.edu/touch/pubs/sosp2005.pdf

37. M. Canonico. Scheduling Algorithms for Bag-of-Tasks Applications on Fault-Prone Desktop Grids. Ph.D. dissertation, University of Turin, 2006.

38. Xiaojuan Ren, Seyong Lee, Rudolf Eigenmann, Saurabh Bagchi. Resource Availability Prediction in Fine-Grained Cycle Sharing Systems.

39. Dinda, P.A. The statistical properties of host load: Lecture Notes in Computer Science, Volume 1511, 1998, pp. 319-334. http://reports-archive.adm.cs.cmu.edU/anon/l 998/CMU-CS-98-143 .pdf

40. P. Dinda and D. O'Hallaron. Host load prediction using linear models. In The 8th IEEE Symposium on High Performance Distributed Computing, 1999.

41. DataGrid. DataGrid Accounting System.1 http://www.infh.it/workload-grid/docs/DataGrid-01 -TED-0126- 1 0.pdf

42. D.P. da Silva, W. Cirne, and F.V. Brasileiro. Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids. In Proc. of EuroPar 2003, volume 2790 of Lecture Notes in Computer Science, 2003.

43. J. Brevik, D. Nurmi, R. Wolski. Automatic Methods for Predicting Machine Availability in Desktop Grid and Peer-to-peer Systems, CCGrid 2004 GP2PC Workshop, 2004, Chicago, IL. http://pompone.cs.ucsb.edu/~nurmi/mypapers/ccgrid04.pdf

44. J. Brevik, D. Nurmi, and R. Wolski. Modeling machine availability in enterprise and wide-area distributed computing environments. Technical Report 37, Department of Computer Science, University of California, Santa Barbara, 2003.

45. M. Mutka. Considering deadline constraints when allocating the shared capacity of private workstations. Int. Journal in Computer Simulation, vol. 4, no. 1 pp.4163, 1994.

46. СУБД PostgreSQL — www.postgresql.org

47. GridFTP — http://www.globus:org/gridsoftware/data/gridftp.php

48. UNPACK — http://www.netlib.org/linpack/

49. J. Richter. Make Your Windows 2000 Processes Play Nice Together With Job Kernel Objects. Microsoft systems journal, 1999.

50. SOAP — http://www.w3.org/TR/soap/52. gSOAP — http://www.cs.fsu.edu/~engelen/soap.html

51. Утилита globusrun-ws —-http://www.globus.Org/toolkit/docs/4.0/execution/wsgram/rn0 IreO 1 .html

52. Delegation Service http://www.globus.org/toolkit/docs/latest-stable/security/delegation

53. Михайлов Г.А. Весовые методы Монте-Карло. Новосибирск: Изд-во СО РАН, 2000.

54. G-R. Jaenisch, С. Bellon, U. Samadurau, M. Zhukovskiy, S. Podoliako. Monte Carlo radiographic model with CAD-based geometry description. Insight, Vol. 48, No 10, October 2006, pp. 618-623.

55. M.E. Жуковский, C.B. Подоляко, M.B. Скачков, Г.-Р. Йениш. О моделировании экспериментов с проникающим излучением. Математическое моделирование, Т19, №5, 2007, с. 72-80.

56. Э.А. Азизов, С. Г. Алиханов, Е.П. Велихов, М.П. Галанин, В.А. Глухих, Е.В. Грабовский и др. Проект «Байкал». Отработка схемы генерации электрического импульса // Вопросы атомной науки и техники, серия Термоядерный синтез. 2001. №. 3. сс. 3-17.

57. М.П. Галанин, А.П. Потоцкий. Моделирование разгона и торможения лайнера в устройствах обострения мощности // Радиотехника и электроника. 2005. Т. 50. №2. сс. 256-264.

58. Щеглов И.А. Программа для триангуляции сложных двумерных областей Gridder2D // Препринт №60. Москва: ИПМ им. М.В. Келдыша РАН, 2008. 32 с.