Планирование задач в распределённых вычислительных системах на основе метаданных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Голубев, Иван Алексеевич

• Голубев, Иван Алексеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Голубев, Иван Алексеевич

Содержание

Введение

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

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

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

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

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

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

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

1.2.1. Система HTCondor

1.2.2. Система DIET

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

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

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

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

1.3. Выводы

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

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

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

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

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

2.5. Выводы

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

в РСОД

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

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

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

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

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

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

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

3.5. Выводы

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

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

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

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

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

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

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

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

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

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

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

4.4. Выводы

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Планирование задач в распределённых вычислительных системах на основе метаданных»

Введение

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

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

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

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) - модель, в которой клиент предоставляется возможность управлять виртуальными ресурсами - виртуальными машинами, виртуальными сетями, а также балансировкой нагрузки, межсетевыми экранами и пр. Поставщик услуги предоставляет гибкие механизмы доступа к пулу ресурсов, а также хранения и перенастройки заранее сконфигурированных виртуальных машин.

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

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

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

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

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

Значительное число исследований [6] показало, что современные вычислительные нагрузки высокоизменчивы, и характеризуются особым распределением: множество небольших задач (или запросов) с малыми ресурсными требованиями и сравнительно небольшое множество крупных задач с непропорционально высокими требованиями к потребляемым ресурсам. Интеллектуальное планирование распределением задач по узлам обработки, обеспечивающее эффективное использование ресурсов становится чрезвычайно актуальным при таких характеристиках задач.

С учётом данных особенностей в настоящей работе основное внимание уделяется анализу, математическому моделированию и улучшению методов планирования задач в условиях и с учётом:

1. Разнородности задач;

2. Гетерогенности узлов РСОД;

3. Метаданных задач;

4. Истории выполнения задач.

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

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

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

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

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

Проблема планирования задач обработки состоит из выделения ресурсов (узлов обработки) для задач и установления порядка в котором задачи из входной очереди будут выполняться на этих ресурсах [7].

Класс систем, в которых осуществляется централизованное управление ресурсами получил название системы управления ресурсами [8], который, как правило тесно интегрируется с системой планирования задач или планировщи-

а

о н о Я со Р й

И

№

и 43

<т>

Й

задание п

•--- _

__*

задание 2

задача 1

т

задача задача

2 3

задача 4

Ж

задача 5

\

з:

задача 6

задание 1

задание

планировщик заданий/ задач

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

Рисунок 1.2. Состав потока входных данных для систем планирования ком задач [9].

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

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

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

(планирования) задачами и ресурсами.

Метод или политика планирования задач (task scheduling policy) представляет собой набор правил, которые используются для определения когда и как выбирать новую задачу (процесс) на обработку [10]. В основе выбора задачи на исполнение лежит процедура сортировки задач в соответствии с их приоритетами.

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

Дисциплины обслуживания без априорных знаний [6]:

1. First in First Out, FIFO, - задачи обрабатываются в порядке поступления.

2. Last in First Out, LIFO, - задачи обрабатываются в обратном порядке.

3. Random Selection for Service (RSS), - задача выбирается случайным образом.

4. Time Sharing, с разделением времени - квант времени выделяется каждой задаче поочерёдно.

5. Least Attained Service - выбирается задача, получившая наименьшее время обслуживания.

К недостаткам приведённых дисциплин обслуживания можно отнести следующее:

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

2. Решают другую задачу: какую задачу из очереди выбрать первой для обработки в соответствии с приоритетом или другими критериями;

3. Предполагают однотипность задач в плане ресурсных требований (вычислительной и пространственной трудоёмкости);

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

При использовании данных подходов ресурсы используются неэффективно в случаях, когда:

1. Узлы РСОД различаются по мощности (гетерогенность РСОД);

2. Задачи разнородны по вычислительной и пространственной (по памяти) сложности, и, следовательно имеют сильно отличающиеся ресурсные требования;

3. Узлы РСОД могут исполнять параллельно несколько задач.

Если ресурсные требования заданы заранее, то могут применяться следующие дисциплины обслуживания [6]:

1. Shortest Job First (SJF), - выбирается задача с наименьшими ресурсными требованиями.

2. Shortest Remaining processing time, - выбирается задача, для которой оценённое время обслуживания минимально.

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

Другой аспект приведённых методов планирования задач - поддержка сохранения состояния выполнения задач, что позволяет прерывать выполнение текущей задачи и переключаться на выполнение другой (например более приоритетной). Такие методы как Time Sharing, Least Attained Service, Shortest Remaining Processing Time относятся к данному классу методов планирования задач, за счёт чего на каждом вычислительном узле могут находиться несколько задач на разных стадиях выполнения.

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

исследования настоящей диссертации.

Следующий этап планирования - для каждой выбранной задачи применяется метод выбора узла (node allocation policy), который определяет оптимальный набор ресурсов для выделения на задачу обработки данных. Методы управления ресурсами строятся с учётом состояния каждого узла/ресурса распределённой среды, а также в соответствии с заранее установленными требованиями приложений [8].

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

1. Наименее использованный узел (Least Recently Used Node/Server) , - выбрать наименее загруженный или неиспользуемый узел.

2. Случайный выбор (Random Selection), - узел-обработчик выбирается случайным образом.

3. На основе теории массового обслуживания (Queue metrics based), - выбрать узел с наименьшей длиной очереди или средним временем ожидания обработки.

4. Оценка оставшегося времени выполнения (Elapsed-time prédiction), - выбрать узел с наименьшим прогнозируемым временем выполнения.

5. Прогнозирование ресурсопотребления (Resource consumption prédiction), -выбрать узел, наиболее соответствующий прогнозу потребления ресурсов.

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

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

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

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

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

Time Sharing, Least Attained Service

FIFO, LIFO Random Service Selection

Shortest Job First

Shortest Remaining Processing Time

Методы планирования

задач с з ависимостями

Рисунок 1.3. Область исследования

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

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

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

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

Традиционные требования, которые предъявляются со стороны приложений:

1. Сетевые требования (пропускная способность и задержка);

Список литературы диссертационного исследования кандидат наук Голубев, Иван Алексеевич, 2014 год

Литература

1. Tanenbaum A. S., Steen M. v. Distributed Systems: Principles and Paradigms (2nd Edition). Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 2006. ISBN: 0132392275.

2. Prahbu C. Grid and Cluster Computing. PHI Learning Private Limited, 2013. P. 253.

3. Воеводин В.В., Воеводин Вл.В. Паралельные вычисления. СПб: БХВ-Петер-бург, 2002. С. 608.

4. The NIST Definition of Cloud Computing. No. Special Publication 800-145. National Institute of Standards and Technology, 2011. P. 7.

5. Casal D. Cloud Computing for Programmers. Amazon Digital Services, Inc., 2013. P. 59.

6. Broberg J. A. Effective task assignment strategies for distributed systems under highly variable workloads: Ph. D. thesis / School of Computer Science and Information Technology, Science, Engineering, and Technology Portfolio, RMIT University, Melbourne, Victoria, Australia. 2006.

7. Barbosa J. M. G., Moreira B. D. R. Dynamic Job Scheduling on Heterogeneous Clusters // Proceedings of the 2009 Eighth International Symposium on Parallel and Distributed Computing. ISPDC '09. Washington, DC, USA: IEEE Computer Society, 2009. P. 3-10. URL: http: //dx. doi. org/10.1109/ISPDC. 2009.19.

8. Endo P., Palhares A. D. A., Pereira N. et al. Resource allocation for distributed cloud: concepts and research challenges // Ieee Network. 2011. Vol. 25, no. 4. P. 42-46.

9. Chtepen M., Claeys F., Dhoedt B. etal. Performance evaluation and optimization of an adaptive scheduling approach for dependent grid jobs with unknown execution time // 18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation, Proceedings / edited byR. Anderssen, R. Braddock, L. Newham. Modelling and Simulation Society of Australia and

New Zealand ; International Association for Mathematics and Computers in Simulation, 2009. P. 1003-1009. URL: http://www.mssanz.org.au/modsim09/ C5/chtepen.pdf.

10. Bovet D., Cesati M. Understanding The Linux Kernel. Oreilly & Associates Inc, 2005. ISBN: 0596005652.

11. Imam M. T., Miskhat S. F., Rahman R. M., Amin M. A. Neural Network and Regression Based Processor Load Prediction for Efficient Scaling of Grid and Cloud Resources // 14th International Conference on Computer and Information Technology (ICCIT). IEEE, 2011.

12. Kwok Y.-K., Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors // ACM Comput. Surv. 1999. Vol. 31, no. 4. P. 406-471. URL: http://doi.acm.org/10.1145/344588.344618.

13. Kim J.-K., Shivle S., Siegel H. J. et al. Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment //J. Parallel Distrib. Comput. 2007. Vol. 67, no. 2. P. 154-169. URL: http://dx.doi.org/10. 1016/j.jpdc.2006.06.005.

14. Sun W., Zhang Y., Inoguchi Y. Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy // IEICE - Trans. Inf. Syst. 2007. Vol. E90-D, no. 4. P. 736-744. URL: http://dx.doi.org/10. 1093/ietisy/e90-d.4.736.

15. Maheswaran M., Ali S., Siegel H. J. et al. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems //J. Parallel Distrib. Comput. 1999. Vol. 59, no. 2. P. 107-131. URL: http://dx.doi.org/10. 1006/jpdc.1999.1581.

16. Caniou Y., Jeannot E. Experimental Study of Multi-criteria Scheduling Heuristics for GridRPC Systems // Euro-Par. 2004. P. 1048-1055.

17. Xue S., Chen L., Liu G. Resource state prediction in the grid based on neural network // Proceedings of the 5th international conference on Natural computation. ICNC'09. Piscataway, NJ, USA: IEEE Press, 2009. P. 294-298. URL:

http://dl.acm.org/citation.cfm?id=1797096.1797156.

18. HTCondor Version 8.0.0 Manual. University of Wisconsin-Madison: Center for High Throughput Computing, 2013. P. 1053.

19. Abdelkader A., Caniou Y., Caron E. et al. DIET 2.8 user's manual. Inria, ENS-Lyon, UCBL, SysFera, 2011.

20. Amedro B., Bodnartchouk V., Baduel L. et al. ProActive Scheduling v.3.3.2 user's manual. INRIA, University of Nice-Sophia Antipolis, ActiveEon, 2013. P. 152.

21. Torque v.4.2.4 Administrator Guide. Adaptive Computing Enterprises, 2013. P. 314.

22. Moab Workload Manager v.7.2.4 Administrator Guide. Adaptive Computing Enterprises, 2013. P. 1136.

23. Maui v.3.2 Administrator's Guide. Adaptive Computing Enterprises, 2011. P. 287.

24. Metadata registries. ISO/IEC 11179-1 International Standard. ISO/IEC, 2004. P. 32.

25. Qin X., Jiang H., Manzanares A. et al. Dynamic Load Balancing for I/O-intensive Applications on Clusters // Trans. Storage. 2009. Vol. 5, no. 3. P. 9:1-9:38. URL: http://doi.acm.org/10.1145/1629075.1629078.

26. Harchol-Balter M., Downey A. B. Exploiting Process Lifetime Distributions for Dynamic Load Balancing // SIGOPS Oper. Syst. Rev. 1995. Vol. 29, no. 5. P. 236- URL: http://doi.acm.org/10.1145/224057.225838.

27. Hui C.-C., Chanson S. T. Improved Strategies for Dynamic Load Balancing // IEEE Concurrency. 1999. Vol. 7, no. 3. P. 58-67. URL: http://dx.doi.org/ 10.1109/4434.788780.

28. Acharya A., Setia S. Availability and Utility of Idle Memory in Workstation Clusters // SIGMETRICS Perform. Eval. Rev. 1999. Vol. 27, no. 1. P. 35-46. URL: http: //doi . acm. org/10.1145/301464.301478.

29. Voelker G. M., Jamrozik H. A., Vernon M. K. et al. Managing Server Load in

Global Memory Systems // SIGMETRICS Perform. Eval. Rev. 1997. Vol. 25, no. 1. P. 127-138. URL: http://doi.acm.org/10.1145/258623.258682.

30. Zhang X., Qu Y., Xiao L. Improving Distributed Workload Performance by Sharing both CPU and Memory Resources // ICDCS. IEEE Computer Society, 2000. P. 233-241.

31. Aha D. W., Kibler D., Albert M. K. Instance-based learning algorithms // Machine Learning. 1991. P. 37-66.

32. Wettschereck D., Aha D. W., Mohri T. A Review and Empirical Evaluation of Feature Weighting Methods for aClass of Lazy Learning Algorithms // Artif. Intell. Rev. 1997. Vol. 11, no. 1-5. P. 273-314. URL: http://dx.doi.org/10. 1023/A:1006593614256.

33. Wu M., Scholkopf B. A local learning approach for clustering //In Avances Neural Information Processing Systems. 2006.

34. Bottou E., Vapnik V. Local Learning Algorithms // Neural Computation. 1992. Vol. 4. P. 888-900.

35. Varun C., Shyam B., Vipin K. Similarity Measures for Categorical Data - A Comparative Study // Technical Report TR 07-022. 2007. URL: http://www. cs.umn.edu/tech_reports_upload/tr2007/07-022.pdf.

36. Hall M. A. Correlation-based feature selection for machine learning: Ph. D. thesis / The University of Waikato, Hamilton, NewZealand. 1999.

37. Langley P., Sage S. Oblivious Decision Trees and Abstract Cases. 1994.

38. Kelly J. D., Davis L. A Hybrid Genetic Algorithm for Classification // Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 2. IJCAI'91. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1991. P. 645-650. URL: http://dl.acm.org/citation.cfm?id=1631552.1631558.

39. Aha D. W. Tolerating Noisy, Irrelevant and Novel Attributes in Instance-based Learning Algorithms // Int. J. Man-Mach. Stud. 1992. Vol. 36, no. 2. P. 267-287. URL: http: //dx. doi. org/10.1016/0020-7373 (92) 90018-G.

40. Wettschereck D. A Study of Distance-based Machine Learning Algorithms:

Ph.D. thesis. Corvallis, OR, USA: Oregon State University, 1994. AAI9507711.

41. Kohavi R., John G. H. Wrappers for Feature Subset Selection // Artif. I11-tell. 1997. Vol. 97, no. 1-2. P. 273-324. URL: http://dx.doi.org/10.1016/ S0004-3702(97)00043-X.

42. Mitchell T. M. The Need for Biases in Learning Generalizations // Readings in Machine Learning / Ed. by J. W. Shavlik, T. G. Dietterich. Morgan Kauffman, 1980. P. 184-191. Book published in 1990. URL: http://www.cs.nott.ac. uk/~bsl/G52HPA/articles/Mitchell:80a.pdf.

43. Guyon I., Elisseeff A. An Introduction to Variable and Feature Selection //J. Mach. Learn. Res. 2003. Vol. 3. P. 1157-1182. URL: http://dl.acm.org/ citation.cfm?id=944919.944968.

44. Ventura D., Martinez T. R. An Empirical Comparison of Discretization Models // Proceedings of the 10th International Symposium on Computer and Information Sciences. 1995. P. 443-450.

45. Wilson D. R., Martinez T. R. Improved Heterogeneous Distance Functions // J. Artif. Int. Res. 1997. Vol. 6, no. 1. P. 1-34. URL: http://dl.acm.org/ citation.cfm?id=1622767.1622768.

46. Quinlan J. R. Unknown Attribute Values in Induction // Proceedings of the Sixth International Workshop on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1989. P. 164-168. URL: http://dl.acm. org/citation.cfm?id=102118.102173.

47. Janert P. K. Data Analysis with Open Source Tools - a Hands-on Guide for Programmers and Data Scientists. O Reilly, 2011. ISBN: 978-0-596-80235-6.

48. Nassif L. N., Nogueira J. M., Ahmed M. et al. Job Completion Prediction in Grid Using Distributed Case-based Reasoning // 2012 IEEE 21st International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises. 2005. P. 249-254.

49. Burkard R., Dell'Amico M., Martello S. Assignment Problems. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2009. ISBN: 0898716632,

9780898716634.

50. Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2. P. 83-97.

51. Hopcroft J., Karp R. An n. 5/2 algorithm for maximum matchings in bipartite graphs // SIAM Journal on Computing. 1973. Vol. 2. P. 225-231.

52. Munkres J. Algorithms for the assignment and transportation problems // Journal of the Society for Industrial and Applied Mathematics. 1957. Vol. 5, no. 1. P. 32-38.

53. Mary-Huard T., Robin S. Tailored Aggregation for Classification // IEEE Trans. Pattern Anal. Mach. Intell. 2009. Vol. 31, no. 11. P. 2098-2105. URL: http: //dx.doi.org/10.1109/TPAMI.2009.55.

54. Yuan Z.-W., Wang Y.-H. Research on K Nearest Neighbor Non-parametric Regression Algorithm Based on KD-Trec and Clustering Analysis // Proceedings of the 2012 Fourth International Conference on Computational and Information Sciences. ICCIS '12. Washington, DC, USA: IEEE Computer Society, 2012. P. 298-301. URL: http://dx.doi.org/10.1109/ICCIS.2012.246.

55. Fu A. W.-c., Chan P. M.-s., Cheung Y.-L., Moon Y. S. Dynamic Vp-tree Indexing for N-nearest Neighbor Search Given Pair-wise Distances // The VLDB Journal. 2000. Vol. 9, no. 2. P. 154-173. URL: http://dx.doi.org/10.1007/ PL00010672.

56. Lu J., Lu Y., Cong G.'Reverse Spatial and Textual K Nearest Neighbor Search // Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. SIGMOD '11. New York, NY, USA: ACM, 2011. P. 349-360. URL: http: //doi . acm. org/10.1145/1989323.1989361.

57. Gionis A., Indyk P., Motwani R. Similarity Search in High Dimensions via Hashing // Proceedings of the 25th International Conference on Very Large Data Bases. VLDB '99. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1999. P. 518-529. URL: http://dl.acm.org/citation.cfm?id=645925. 671516.

58. Datar M., Immorlica N., Indyk P., Mirrokni V. S. Locality-sensitive Hashing Scheme Based on P-stable Distributions // Proceedings of the Twentieth Annual Symposium on Computational Geometry. SCG '04. New York, NY, USA: ACM, 2004. P. 253-262. URL: http://doi.acm.org/10.1145/997817.997857.

59. Wang H., Cao J., Shu L., Rafiei D. Locality Sensitive Hashing Revisited: Filling the Gap Between Theory and Algorithm Analysis // Proceedings of the 22Nd ACM International Conference on Conference on Information Knowledge Management. CIKM '13. New York, NY, USA: ACM, 2013. P. 1969-1978. URL: http://doi.acm.org/10.1145/2505515.2505765.

60. Dasgupta A., Kumar R., Sarlos T. Fast Locality-sensitive Hashing // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '11. New York, NY, USA: ACM, 2011. P. 1073-1081. URL: http: //doi . acm. org/10.1145/2020408.2020578.

61. Yang Z., Ooi W. Т., Sun Q. Hierarchical, non-uniform locality sensitive hashing and its application to video identification. 2004. P. 743-746.

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

63. Cormen Т. Н., Stein С., Rivest R. L., Leiserson С. Е. Introduction to Algorithms. 2nd edition. McGraw-Hill Higher Education, 2001. ISBN: 0070131511.

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

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

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

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

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

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

70. 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.

71. 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.

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

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

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

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

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

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

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

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

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

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

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