Введение 4
Постановка задачи 6
Глава 1. Теоретические основы. Обзор литературы 7
1.1 Балансировка нагрузки 8
1.2 Топологические методы анализа данных 11
1.3 Применение методов анализа данных в задачах балансировки нагрузки 14
Выводы по главе 16
Глава 2. Предлагаемые подходы и вычислительные эксперименты 17
2.1 Подготовка данных 17
2.2 Кластеризация методом k-средних 20
2.3 Кластеризация с помощью смеси гауссиан 22
2.4 Выявление различных типов задач с помощью устойчивых гомологий 23
2.5 Алгоритм Mapper 25
Выводы по главе 25
Глава 3. Реализация и результаты 27
3.1 Подготовка данных 27
3.2 Реализация алгоритма кластеризации k-средних, подбор параметров и
результаты 32
3.3 Анализ данных с использованием смеси гауссиан с процессом Дирихле 38
3.4 Реализация выявления типов задач с помощью устойчивых гомологий 41
3.5 Поиск компонент сильной связности в облаке данных с помощью алгоритма
Mapper 43
Выводы по главе 47
Заключение 49
Список литературы 50
Приложение
За довольно непродолжительное время количество данных, генерируемых человечеством в единицу времени, невероятно возросло. Буквально каждую минуту генерируется информация сравнимая по объёму с информацией, на создание которой в прошлом требовались десятки лет. Одной из причин такого роста является развитие технологий, в частности, развитие интернета и вычислительных сетей.
Интернет можно рассматривать как совокупностью информационных систем, каждая из которых осуществляет обработку информации. При увеличении объёма данных, которые обрабатывает информационная система, производительности, которую может обеспечить одна вычислительная машина становится недостаточно, что послужило причиной объединения вычислительных машин в вычислительные сети, обеспечивающие работу информационных систем.
Становление вычислительных сетей в качестве основы для работы информационных систем привело к увеличению вычислительных возможностей, доступных к использованию в рамках информационной системы. Однако переход к распределенной архитектуре сопровождается рядом новых проблем и задач, с которыми не приходится сталкиваться в рамках нераспределённой архитектуры. К таким задачам можно отнести: обеспечение согласованности данных в рамках вычислительной сети, обнаружение завершения выполнения задачи, необходимость коммутации пакетов в рамках вычислительной сети и балансировка нагрузки в рамках информационной системы.
Есть основания полагать, что в будущем количество данных, генерируемых человечеством, будет продолжать быстро расти. Этому будут способствовать и многие нововведения из мира информационных технологий, в качестве примера можно указать набирающие всё большую популярность устройства, относящиеся к классу интернета вещей. Очевидно, что при увеличении количества таких устройств, информационная нагрузка, как на частные локальные сети, так и на вычислительные сети информационных систем, обеспечивающие работу таких устройств, будет возрастать. В условиях увеличивающейся нагрузки работа информационных систем, в том числе и алгоритмы обеспечивающие внутреннюю работу вычислительной сети, должны совершенствоваться и работать более эффективно.
Одним из аспектов требующих наиболее эффективной работы программного комплекса вычислительной сети является пост-обработка и анализ результатов выполнения вычислительной сетью входящих задач. Данная работа нацелена на решение именно этой задачи, а именно на анализ набора данных, описывающих работу вычислительного комплекса, с целью выявления типов выполненных операция для последующей выработки стратегии балансировки нагрузки.
Целью данной работы была проверка гипотезы о том, что применение топологических методов анализа данных позволит выбирать более эффективные стратегии балансировки нагрузки в вычислительной сети, за счёт выявления дополнительных особенностей, не выявляемых традиционными методами анализа данных.
Был проанализирован набор данных описывающих месяц работы вычислительных кластеров Google.
Были реализованы и применены несколько методик выявления особенностей задач, выполняемых вычислительным кластером Google.
Результаты работы топологических и традиционных методов анализа данных были рассмотрены и проанализированы. На основе проведённого анализа были сделаны выводы о применимости топологического анализа данных и конкретных аспектах его применения в задаче балансировки нагрузки в вычислительной сети.
