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

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

Голубев Иван Алексеевич

Планирование задач в распределённых вычислительных системах на основе метаданных

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

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

2 2 МАЙ 2014

005548839

Санкт-Петербург - 2014

005548839

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» на кафедре вычислительной техники

Официальные оппоненты:

доктор технических наук, профессор, Воробьёв Владимир Иванович, «Санкт-Петербургский институт информатики и автоматизации РАН»

кандидат технических наук, Курносов Михаил Георгиевич,

«Сибирский государственный университет телекоммуникаций и информатики»,

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

Ведущая организация: ОАО «Информационные телекоммуникационные

Защита состоится «30» июня 2014 г. в 15 часов 30 минут на заседании диссертационного совета Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Профессора Попова, дом 5.

С диссертацией можно ознакомиться в библиотеке университета и на сайте www.eltech.ru.

Автореферат разослан «25» апреля 2014 г. Ученый секретарь

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

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

доктор технических наук, профессор Куприянов Михаил Степанович

технологии» (ОАО «Интелтех»)

Д 212.238.01, к.т.н.

Щеголева Н.Л.

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

Актуальность темы исследования

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

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

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

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

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

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

Объектом исследования являются системы планирования задач в РСОД.

Предметом исследования выступают методы планирования задач, которые используются в системах планирования для РСОД.

Целью диссертационной работы является сокращение временных затрат на выполнение задач в РСОД в условиях неполноты информации о ресурсных требованиях.

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

1. Анализ существующих методов планирования задач обработки данных в РСОД.

2. Разработка математической модели планирования задач в РСОД.

3. Разработка метода планирования задач в РСОД.

4. Решение проблемы поиска ближайших задач с учётом разнородности атрибутов и их значимости для ресурсопотребления.

5. Разработка методики планирования задач в РСОД.

6. Проведение экспериментов по распределению задач обработки данных по ресурсам РСОД на основе предложенного метода.

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

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

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

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

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

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

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

Методология и методы исследования

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

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

1. Математическая модель планирования задач в РСОД.

2. Метод планирования задач в РСОД.

3. Модификация алгоритма поиска ближайших соседей.

Степень достоверности и апробация результатов

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

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

Внедрение результатов:

Полученные научные и практические результаты использовались при выполнении следующих работ:

1. НИР «Разработка теоретических основ проектирования сервисно-ориентированной информационно-аналитической системы анализа данных на базе технологии облачных вычислений». СПб ТЭТУ. Проект №2.1.2/12448. Сроки: 2011.

2. НИР «Создание высокопроизводительных вычислительных технологий для интеллектуальных систем оперативной обработки и визуализации гидроакустической информации». СПб ТЭТУ. Сроки: 2012-2013.

3. НИР «Разработка математического аппарата априорной оценки работы алгоритмов интеллектуального анализа в гетерогенной распределенной среде». СПб ТЭТУ. Проект №01201155585. Сроки: 2011-2013.

4. НИР «Организация производства систем гидроакустического мониторин-

га акватории на базе покровных антенн в местах размещения нефте- и газодобывающих платформ в районе Арктического шельфа». СПб ГЭТУ. Проект M3.G25.31.0054. Сроки: 2010-2012.

Публикации

Основные теоретические и практические результаты диссертации опубликованы в 20 печатных работах, среди которых 4 статьи в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 раздела в 2-х монографиях, 5 работ - в материалах международных научно-технических конференций, 9 свидетельств о регистрации программ для ЭВМ1.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и библиографии. Общий объем диссертации 136 страниц, из них 127 страниц текста, включая 29 рисунков и 8 таблиц. Библиография включает 82 наименования на 9 страницах. Основное содержание работы

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

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

Проведённый анализ основных методов и систем планирования в РСОД (Slurm, Torque, Moab, Maui, HTCondor и DIET) показал следующее:

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

1Часть программных свидетельств получена до смены фамилии. Свидетельство о перемене имени с Громов И.А. на Голубев II.A. I-AK № 539834.

теля.

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

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

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

Проведённый анализ позволил сделать следующие выводы:

1. Каждая из задач обработки данных характеризуется одновременно:

• множеством характеристик данных,

• множеством ресурсных требований,

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

• метриками загрузки вычислительных ресурсов.

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

3. Оценка ресурсных требований новых задач может быть выполнена посред-

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

Р = (Т,А,К,Я, М,/,С, IV)

где:

Т - множество задач\

А - множество атрибутов данных (метаданных), связанных с задачами; К - множество узлов-обработчиков; Я - множество характеристик узлов;

М - множество метрик загрузки ресурсов вычислительных узлов; / - отображение множества Т на множество К;

С - оценки вычислительных затрат выполнения задач из множества Т на узлах-обработчиках из множества К;

У/ - коэффициенты назначения задач из множества Т на узлы-обработчики из множества К.

В процессе обработки данных в РСОД происходит назначение поступивших задач на узлы обработки в соответствии с некоторым методом планирования /:

/ : («,*:) ш,

где:

í € Т - задача из очереди ожидания, к Е К - вычислительный узел-обработчик,

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

С каждым единичным назначением (£, к) связана некоторая оценка ресурсных затрат с, а метод планирования / строит матрицу ресурсных затрат С и

матрицу назначения W:

С

Си Си ■ • С21 С22 • '

\

Cln С2п

ycni

Сп 2

V

Ш21 1^22 W„1 ™n2

V

ад.

0 если задание г не назначено на узел ]

1 если задание г назначено на узел ]

<

где г £ [1,та];^ £ [1,т];п = |Т|;ш = При этом выполняется условие:

= 1, i,j £ iV.

г=1

- то есть каждое задание назначается на выполнение только на одном вычислительном узле.

Цель метода планирования состоит в том, чтобы решить задачу о назначениях, подобрав коэффициенты Wij £ {0,1}, с целью сокращения суммарных ресурсных затрат:

п т

min.

п т

CijWij — sum

i=1 j=l

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

Метод планирования задач в РСОД на основе метаданных и ресурсных метрик представляет собой последовательность применения функций на этапе сбора предыстории выполнения:

fhist = fhist.2 ° fhist Л j

и на этапе прогнозирования:

f — /assign ^ fcost.estimation 0 fnearestt

который позволяет получить коэффициент назначения w для каждой пары (задача, вычислительный узел).

I. На этапе сбора данных предыстории применяются следующие функции:

1.1. Функция fhist. 1 : (i, к) м- (ть т2, • • • тт) G Mhist, г £ N

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

t 6 ThiSt - задача обработки данных, к 6 Khist - узел-обработчик, Mhist - множество кортежей метрик загрузки ресурсов, полученных в результате выполнения.

1.2. Функция fhiSt.2 : (шь m2, • • • mr) м- с

- задаёт способ получения оценок вычислительных затрат с Е Chist для задач предыстории.

В результате строится множество троек (t,k,c) £ Ghist, где: с - оценка вычислительных затрат выполнения задачи t на узле к. Эти данные используются для прогнозирования затрат выполнения новых задач. II. На этапе прогнозирования применяются следующие функции:

11.1. ФунКЦИЯ /nearest Т X К ^ Ghist,nearest

- задаёт способ получения ближайших к новой паре (t, к)

троек (thist, khist,с) е Ghist.nearest С Ghist из предыстории, для которых известны оценки вычислительных затрат с.

11.2. Функция fcost.estimation -Т X К X Chist.nearest ^ С ~ Задаёт способ ПОлучения оценок вычислительных затрат на выполнение новых задач на доступных вычислительных узлах, где:

Chist.nearest = {ci, с2, • • • с„}, для некоторого п£ N - оценки вычислительных затрат ИЗ полученного множества Ghist.nearest ■

11.3. Функция /assign С ^ W

- задаёт способ получения коэффициентов назначения на основе полученных оценок, где:

с € С - коэффициент оценки вычислительных затрат выполнения

задач из очереди ожидания;

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

1. Основной проблемой такого рода поиска является его высокая размерность. Для каждого сочетания (узел, задача) необходимо вычислить расстояние до всех п задач из предыстории выполнения, где асимптотическая сложность единичного запроса равна 0(п).

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

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

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

Модификация алгоритма поиска ближайших соседей на основе метода локализованного хэширования: I. Выбор атрибутов для хэширования:

1.1. Разделить множество атрибутов на категориальные и численные.

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

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

II. Построение хэш-таблицы на основе обучающей выборки: для каждого объ-

екта данных:

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

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

11.3. Сохранить идентификатор объекта по полученному адресу в хэш таблицу.

III. Поиск к ближайших соседей для нового объекта:

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

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

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

111.4. Отсортировать полученный вектор расстояний.

111.5. Выбрать к объектов с наименьшим расстоянием.

Для применения описанного метода планирования задач в РСОД на практике, была сформулирована методика планирования задач на основе метаданных и ресурсных метрик (Рисунок 1).

(1.1. Задать

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

X

(^1.2. Задать процедуры получения и сохранения метрик загрузки ресурсов

_I_

^11.1. Запустить задания обработки данных)

[Нет] Г

(П.2. Выбрать задание^-

_ Г _

_ У_

(п.З. Получить метрики загрузки ресурсов^

_I_

(н.4. Вычислить оценку ресурсных затрат)

(п.5.Сохранить кортеж (метаданные, оценка затрат))

Данных достаточно для

прогнозирования?

[Да]

(ш.1. Выбрать пакет новых заданий из входной очереди)

(111.2. Выбрать задание) _ ^ _

(1н.З. Найти множество близких заданий из предыстории)

_Г2_

(ш.4. Загрузить вектор оценок ресурсных затрат близких заданий)

^ I

Гш.5. Вычислить оценку затрат для данного задания)

[Нет]

Пакет заданий обработан?

[Нет]

Ща]

(ш.6. Решить задачу о назначениях на основе матрицы ресурсных затрат)

_ц_

(III.7. Назначить ресурсы в соответствии с полученной матрицей назначения))

(1~У. Дообучение (сбор метрик, оценка затрат)

Входная очередь заданий пуста?

-Иа]-

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

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

Проведён цикл экспериментов по планированию задач, результаты которых приведены на Рисунках 2 и 3.

% Относительное суммарное время выполнения

40

Е Загрузка

Рисунок 2. Изменение временных затрат выполнения задач для метода Meta_Sched по сравнению с методом FIFO LLF

50

Относительное время ожидания

71 2 67.0 72 2 719

59.1

34.1

14.0

-50

Jigbtx

-9.1

-41.9

medium

-35.1

Е Загрузка

Рисунок 3. Изменение среднего времени ожидания в очереди для метода Ме1а_8сЬес1 по сравнению с методом Р1РО_ЬЬР

Эксперименты проводились при различных условиях распределения трудоёмкости задач (равномерное, гауссово, постоянное, случайное) и интенсив-

ности вычислительной нагрузки (легкая - до 6 задач/мин, средняя - от 6 до 19 задач/мин и высокая - 86 задач/мин и выше) с использованием предлагаемого метода планирования (Meta_Sched) и метода FIFO/Least Loaded First (FIFO_LLF). Оба метода принадлежат к классу методов, которые не требуют указания ресурсных требований.

Анализ результатов эксперимента (Рисунки 2 и 3) показывает следующее:

1. Суммарное время нахождения заявок в системе при использовании метода планирования на основе метаданных сокращается на 20% по сравнению с методом FIFO_LLF при высокой интенсивности поступления задач в систему, но возрастает на 4.5% при средней интенсивности и на 10.7% при слабой интенсивности.

2. Среднее время ожидания обработки заявок при использовании метода планирования на основе метаданных сокращается на 7.58% по сравнению с методом FIFO_LLF при высокой интенсивности поступления задач в систему, но возрастает на 10.55% при средней интенсивности и на 70.6% при слабой интенсивности (что объясняется значительной долей накладных расходов в этом случае).

3. Увеличение интенсивности поступления заявок также увеличивает объём данных предыстории, что приводит к повышению качества прогнозирования.

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

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

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

3. Предложена модификация алгоритма поиска ближайших соседей на ос-

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

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

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

6. Проведён цикл экспериментов по планированию задач декодирования видео, который показал в среднем 20% сокращение временных затрат выполнения задач при высокой интенсивности поступления заявок.

7. Сочетание предложенного метода с известными, например ИГО_ЬЬГ, позволяет обеспечить сокращение временных затрат при различных ин-тенсивностях поступления заявок.

8. Метод планирования на основе метаданных был апробирован на задаче обработки гидрографических данных и позволил сократить время выполнения задач в среднем на 10%.

Публикации в журналах перечня ВАК

1. Голубев И. А. Развертывание распределенной системы интеллектуального анализа данных в облачной среде // Известия ЛЭТИ. 2011. № 9. С. 36-43.

2. Голубев И. А., Губарев Н. В. Генерация трёхмерных карт на основе гидрографических данных стандарта Б-57 // Известия ЛЭТИ. 2013. № 5. С. 61-64.

3. Каршиев 3. А., Голубев И. А., Прохоренко К. А. Оценка ускорения и эффективности параллельного выполнения алгоритмов интеллектуального анализа данных // Известия ЛЭТИ. 2012. № 10. С. 46-52.

4. Куприянов М. С., Голубев И. А. Система восстановления моделей информационных бизнес-процессов в унаследованных ИТ-системах // Известия ЛЭТИ. 2011. № 10. С. 31-38.

Разделы монографий

5. Холод И. И., Куприянов М. С., Голубев И. А. и др. Интеллектуальный анализ распределенных данных на базе облачных вычислений. СПб: Изд-во СПбГЭТУ ЛЭТИ, 2011. С. 148. ISBN: 978-5-7629-1176-4.

6. Холод И. И., Куприянов М. С., Голубев И. А. и др. Интеллектуальный анализ данных в распределенных системах. СПб: Изд-во СПбГЭТУ ЛЭТИ, 2012. С. 101. ISBN: 978-5-7629-1228-0.

Материалы конференций

7. Golubev I. A., Smirnov А. N. Clustering and Classification Tasks Adaptation to Cloud Environment // IEEE RNW Section Proceedings. Vol. 2. IEEE, 2011.

8. Голубев И. А. Уровни оптимизации загрузки арендуемых виртуальных ресурсов // Proceedings of XV International Conference on Soft Computing and Measurements, (SCM'2012). 2012. C. 241-244.

9. Голубев И. А. Распределение задач обработки в вычислительных кластерах на основе метаданных // Proceedings of XVI International Conference on Soft Computing and Measurements (SCM'2013). Т. 1. 2013. C. 162-164.

10. Golubev I. A., Kupryianov M. S. Metadata-driven task scheduling in computer clusters // Proceedings of 9th International Conference on Computer Science and Information Technologies (CSIT 2013), Yerevan, Armenia. 2013. P. 249-252.

11. Golubev I. A., Kupryianov M. S. Cloud-based distributed data mining systems // Proceedings of 9th International Conference on Computer Science and Information Technologies (CSIT 2011), Yerevan, Armenia. 2011. P. 183-186.

Программные свидетельства

12. Холод И. И., Куприянов М. С., Громов И. А. и др. Программа кластеризации текстов на основе лексической информации, Свидетельство о гос. регистрации программы для ЭВМ №2010615374, 20.08.2010.

13. Холод И. И., Куприянов М. С., Громов И. А. и др. Программа автоматического сравнения слабоструктурированных текстовых документов, Свидетельство о гос. регистрации программы для ЭВМ №2010615389, 20.08.2010.

14. Холод И. И., Куприянов М. С., Громов И. А. и др. Программа автоматического построения модели бизнес процесса на основе последовательности кадров мейнфреймов, Свидетельство о гос. регистрации программы для ЭВМ №2010615373, 20.08.2010.

15. Холод И. И., Куприянов М. С., Громов И. А. и др. Программа автоматического анализа структурированной текстовой информации, Свидетельство о гос. регистрации программы для ЭВМ №20106111456, 19.02.2010.

16. Холод И. П., Серебрянский Д. А., Голубев И. А. Программа генерации графовых моделей на основе подграфов, Свидетельство о гос. регистрации программы для ЭВМ №2012610928, 20.01.2012.

17. Голубев И. А. Программа для распределённого анализа данных, Свидетельство о гос. регистрации программы для ЭВМ №2012610984, 23.01.2012.

18. Афанасьев А. Н., Голубев И. А., Губарев Н. В. и др. Модуль построения карт высот в системе гидроакустического мониторинга акватории для карт стандарта 3-57, Свидетельство о гос. регистрации программы для ЭВМ № 2013611677, 30.01.2013.

19. Афанасьев А. Н., Голубев И. А., Губарев Н. В. и др. Модуль визуализации карт высот для систем гидроакустического мониторинга акватории, Свидетельство о гос. регистрации программы для ЭВМ № 2013611630, 30.01.2013.

20. Афанасьев А. Н., Голубев И. А., Губарев Н. В. и др. Модуль визуализации тактической подводной обстановки для систем гидроакустического мониторинга акватории, Свидетельство о гос. регистрации программы для ЭВМ № 2013611675, 30.01.2013.

Подписано в печать 24.04.14. Формат 60*84 1/16. Бумага офсетная. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 40.

Отпечатано с готового оригинал-макета в типографии издательства СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)»

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

04201459533

Голубев Иван Алексеевич

Планирование задач в распределённых вычислительных системах на основе метаданных

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель

доктор технических наук, профессор

Куприянов Михаил Степанович

Санкт-Петербург - 2014

Содержание

Введение 4

Глава 1. Особенности построения современных систем планирования задач в распределённых системах 8

1.1. Анализ предметной области и обзор научных публикаций..........8

1.1.1. Основные типы распределённых систем обработки..........8

1.1.2. Системы управления ресурсами и планировщики заданий . 14

1.1.3. Свойства задач и ресурсов в распределённых системах . . 20

1.1.4. Методы планирования использования ресурсов и выполнения задач........................................................21

1.2. Анализ распространённых промышленных планировщиков заданий и систем управления ресурсами..................................27

1.2.1. Система HTCondor..............................................27

1.2.2. Система DIET ..................................................30

1.2.3. Программный стек ProActive..................................32

1.2.4. Системы управления ресурсами Slurrn и Torque ............34

1.2.5. Планировщик Moab............................................35

1.2.6. Планировщик Maui..............................................38

1.3. Выводы..................................................................41

Глава 2. Использование метаданных для планирования в РСОД 42

2.1. Классификация метаданных ..........................................42

2.2. Создание и хранение мультимедийных метаданных................44

2.3. Связь между метаданными и ресурсными требованиями ..........48

2.4. Поиск близких задач....................................................52

2.5. Выводы..................................................................58

Глава 3. Разработка теоретических основ планирования задач

в РСОД 59

3.1. Математическая модель планирования задач в РСОД..............60

3.2. Метод планирования задач в РСОД па основе метаданных и ресурсных метрик............................. 65

3.2.1. Вычисление ресурсных затрат выполнения на основе ресурсных метрик......................... 67

3.2.2. Оценка ресурсных затрат на выполнение на основе метаданных .............................. 69

3.2.3. Вычисление матрицы назначения............... 71

3.3. Модификация алгоритма поиска ближайших соседей на основе метода локализованного хэширования................ 72

3.4. Методика планирования задач на основе метаданных и ресурсных метрик.................................. 76

3.5. Выводы................................. 80

Глава 4. Экспериментальная оценка эффективности предложенного метода 81

4.1. Архитектура программной системы..................................81

4.2. Задача декодирования видео данных..................................87

4.2.1. Описание задачи................................................87

4.2.2. Инфраструктура и метаданные................................88

4.2.3. Жизненный цикл метаданных................................93

4.2.4. Оценка вычислительных затрат ..............................96

4.2.5. Обработка результатов эксперимента ........................99

4.3. Задача обработки гидрографических данных............114

4.3.1. Задача построения карт высот................114

4.3.2. Планирование задач обработки гидрографических данных 116

4.4. Выводы.................................123

Заключение 125

Литература 127

Введение

Актуальность темы исследования

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

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

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

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

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

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

Объектом исследования являются системы планирования задач в РСОД.

Предметом исследования выступают методы планирования задач, которые используются в системах планирования для РСОД.

Целью диссертационной работы является сокращение временных затрат на выполнение задач в РСОД в условиях неполноты информации о ресурсных требованиях.

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

1. Анализ существующих методов планирования задач обработки данных в РСОД.

2. Разработка математической модели планирования задач в РСОД.

3. Разработка метода планирования задач в РСОД.

4. Решение проблемы поиска ближайших задач с учётом разнородности атрибутов и их значимости для ресурсопотребления.

5. Разработка методики планирования задач в РСОД.

6. Проведение экспериментов по распределению задач обработки данных по ресурсам РСОД на основе предложенного метода.

Методология и методы исследования

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

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

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

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

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

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

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

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

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

1. Математическая модель планирования задач в РСОД.

2. Метод планирования задач в РСОД.

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

Основные положения и результаты диссертационной работы докладывались и обсуждались на 5 международных научно-технических конференциях. Внедрение результатов:

Полученные научные и практические результаты использовались при выполнении следующих работ:

1. НИР «Разработка теоретических основ проектирования сервисно-ориентированной информационно-аналитической системы анализа данных на базе технологии облачных вычислений». СПб ТЭТУ. Проект №2.1.2/12448. Сроки: 2011.

2. НИР «Создание высокопроизводительных вычислительных технологий для интеллектуальных систем оперативной обработки и визуализации гидроакустической информации». СПб ТЭТУ. Сроки: 2012-2013.

3. НИР «Разработка математического аппарата априорной оценки работы алгоритмов интеллектуального анализа в гетерогенной распределенной среде». СПб ТЭТУ. Проект №01201155585. Сроки: 2011-2013.

4. НИР «Организация производства систем гидроакустического мониторин-

га акватории на базе покровных антенн в местах размещения нефте- и газодобывающих платформ в районе Арктического шельфа». СПб ТЭТУ. Проект JM3.G25.31.0054. Сроки: 2010-2012.

Публикации

Основные теоретические и практические результаты диссертации опубликованы в 20 печатных работах, среди которых 4 статьи в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 раздела в 2-х монографиях, 5 работ - в материалах международных научно-технических конференций, 9 свидетельств о регистрации программ для ЭВМ1.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и библиографии. Общий объем диссертации 135 страниц, из них 126 страниц текста, включая 30 рисунков и 8 таблиц. Библиография включает 82 наименования на 9 страницах.

1 Часть программных свидетельств получена до смены фамилии. Свидетельство о перемене имени с Громов И.А. на Голубев И.А. 1-АК № 539834.

Глава 1

Особенности построения современных систем планирования задач в распределённых системах

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

1.1. Анализ предметной области и обзор научных публикаций

1.1.1. Основные типы распределённых систем обработки

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

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

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

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

Приведём определения указанных систем обработки данных.

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

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

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

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

Задачи обработки данных

Распределённая система обработки данных

Система планирования задач

i^y^jy ииУя fSLi

входная очередь

-И

Узлы-обработчики

Рисунок 1.1. Высокоуровневое представление кластерной РСОД

деле.

Под грид системой (от англ. grid - сетка) или метакомпыотером понимают сеть гетерогенных вычислительных ресурсов, географически распределённых, используемых для параллельной обработки вычислительных задач [1]. Грид представляет собой программно-аппаратную инфраструктуру для разделяемого использования вычислительных узлов, сетей, баз данных и других ресурсов, которые находятся в юрисдикции различных географически распределённых организаций [2]. Для управления ресурсами используется промежуточное ПО, причём управление как правило - децентрализованное.

Отличительными свойствами грид систем являются [3]:

1. Распределённость компонентов - узлы системы могут находиться в географически удалённых друг от друга регионах, что сказывается на оперативности взаимодействия;

2. Метакомпыотер может динамически менять конфигурацию - система поддержки прозрачно для пользователя производит распределение задач по компонентам системы с учётом динамического подключения/отключения удалённых ресурсов;

3. Неоднородность системы - в состав грид системы могут входить узлы с различным составом программно-аппаратных ресурсов;

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

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

Облачные вычисления - общий термин для целого ряда сетевых сервисов, предоставляемых по требованию, для которых наиболее характерными являются следующие свойства [4]:

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

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

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

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

5. Оплата услуг выполняется исходя из учёта затраченных ресурсов.

Облачные сервисы могут предоставляться в соответствии со следующими моделями обслуживания [5]:

1. Программное обеспечение как услуга (SaaS, англ. Software-as-a-Service) -модель в которой пользователь абстрагируется от всех деталей поддержки приложения: аппаратного обеспечения, распределённости данных, используемых программных средств и др., - и получает в качестве услуги готовое к использованию программное обеспечение, предоставляемое по сети. Наиболее характерным примером таких услуг могут выступать сервисы предоставления или обработки данных, которые доступны как SOAP или REST веб-сервисы, и могут использоваться программным способом.

2. Платформа как услуга (PaaS, англ. Platform-as-a-Service) - модель, в которой пользователь абстрагируется от аппаратной части поддержки приложения и получает возможность управлять заранее подготовленным набором информационно-технологических платформ: операционными системами, базами данных, средствами разработки и тестирования и др., - и имеет возможность устанавливать и использовать собственное прикладное программное обеспечение.

3. Инфраструктура как услуга (IaaS, англ. IaaS or Infrastructure-as-a-Service) - модель, в которой клиент предоставляется возможность управлять виртуальными ресурсами - виртуальными машинами, виртуальными сетями, а также балансировкой нагрузки, межсетевыми экранами и п�