Задача на данный момент не имеет общего эффективного решения Проблема



Скачать 32.93 Kb.
Pdf просмотр
Дата16.02.2017
Размер32.93 Kb.
Просмотров168
Скачиваний0
ТипЗадача

Разработка и реализация алгоритмов run-time оптимизации исполнения фрагментированных программ
Научный руководитель:
Перепёлкин В. А.
м.н.с., ИВМиМГ СО РАН
Дуплищев И. К.
4 курс ФИТ НГУ


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

Цель работы

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

Разработать и реализовать имитационную модель для тестирования алгоритмов балансировки

Разработать и реализовать алгоритмы динамической балансировки нагрузки на вычислительные узлы мультикомпьютера

Обзор

Mizan: Система динамической балансировки нагрузки для крупномасштабных графовых вычислений
(Z. Khayyat)

Статическая балансировка нагрузки для распределённой системы, основанная на кооперативных играх (D. Grosu)

Отображение параллельных программ на многоядерные компьютеры рекуррентными нейронными сетями (М. С. Тарков)

Диффузионная балансировка

Обзор
Обнаруженные недостатки:

Статическая балансировка

Частный случай модели вычислений (Bulk
Synchronous Parallel)

Централизованный подход и нелокальные коммуникации

Постановка задачи
Разработать и реализовать имитационную модель и алгоритмы динамической балансировки нагрузки
Требования для имитационной модели:

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

Возможность моделировать большие мультикомпьютеры на небольших вычислителях
Требования для балансировщика:

Децентрализованность

Масштабируемость

Локальность коммуникаций

Адаптация к задаче


Технология фрагментированного программирования - технология реализации на суперкомпьютерах больших задач численного моделирования

Исполняющаяся фрагментированная программа состоит из множества последовательных подзадач, связанных информационными зависимостями

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

Предлагаемая имитационная модель

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

Генерация задач без зависимостей

Последовательная реализация модели

Сохранение профиля работы фрагментированной программы

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

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

Алгоритмы динамической балансировки


Адаптивный алгоритм диффузионной балансировки на основе многослойного персептрона

Балансировка на основе прогнозирования сетью:

ESOINN (Enhanced Self-Organizing Incremental
Neural Network)

SOM (Self-Organized Map)

Многослойный персептрон

Гибридный вариант балансировки на основе прогнозирования и адаптивного алгоритма диффузионной балансировки
Алгоритмы динамической балансировки

Данные для обучения

Данные для обучения

Схема принятия решения для всей системы

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

Масштабируемость

Локальность коммуникаций

Децентрализованность

Адаптация к задаче
Соответствие представленных алгоритмов к требованиям динамического балансировщика

Параметры:

1000 вычислительных задач на 50 вычислительных узлов мультикомпьютера

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

эталон - алгоритм диффузионной балансировки

алгоритм2 - гибридный вариант балансировщика на основе прогнозирования многослойным персептроном

алгоритм3 - гибридный вариант балансировщика на основе прогнозирования ESOINN

алгоритм4 - гибридный вариант балансировщика на основе прогнозирования SOM
Тестирование

Тестирование

Тестирование

Тестирование

Тестирование показало:

Нейронные сети применимы для динамической балансировки нагрузки

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

Международная научная студенческая конференция 2014
“Студент и научно-технический прогресс” (название доклада -
“Применение нейронных сетей для динамической балансировки работы мультикомпьютера в системе фрагментированного программирования”)
Результаты работы

На защиту выносится:

Разработана и реализована имитационная модель исполнения фрагментированной программы на мультикомпьютере

Разработаны и реализованы алгоритмы динамической балансировки нагрузки на узлы мультикомпьютера на основе нейронных сетей

Произведено сравнительное тестирование предложенных алгоритмов на имитационной модели
Заключение


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

Интеграция разработанных алгоритмов в систему фрагментированного программирования
Дальнейшие планы


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал