Презентация по меттоду оптимизасия на тему “ Параллельные алгоритмы поиска глобально-оптимальных решений”

Параллельные алгоритмы поиска
глобально-оптимальных решений
Программная система параллельных вычислений в задачах выбора глобально-оптимальных решений “Абсолют Эксперт”

Содержание
Описание предметной области
1.1.Постановка задачи
1.2.Методы решения задач оптимизации
1.3.Индексный метод с одной разверткой
Использование чисел расширенной точности
2.1.Необходимость использования чисел расширенной точности
2.2.Особенности использования чисел расширенной точности
Распараллеливание алгоритмов глобально поиска
3.1.Необходимость параллельных реализаций
3.2.Распараллеливание индексного метода с одной разверткой
3.3.Параллельный алгоритм Стронгина
3.4.Пересылка точек испытаний поиска
3.5.Распараллеливание индексного метода с множественной разверткой
Планы на будущее

1.1. Описание предметной области
Одна из типичных моделей процессов принятия решений – модель в виде задачи оптимизации



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

1.2. Методы решения задач оптимизации
Типичный способ решения сложных задач оптимизации – различные итерационные процедуры
Итерация:
выбор очередной точки xi в области поиска


вычислении входящих в задачу функционалов в точке xi

Процесс останавливается либо по числу итераций, либо по некоторому специальному условию
y0
y1
y2
yk
yk+1
yn-1
yn
yn+1

1.2. Методы решения задач оптимизации
Простейший метод решения – «полный перебор»







С увеличением размерности задачи экспоненциально растет число точек

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

1.2. Используемые сокращения
ISE - индексный метод с одной разверткой
ISEP - индексный метод с одной разверткой (параллельный)
ISEMC - модифицированный индексный метод с одной разверткой
GGSA - алгоритм Стронгина
GGSAP - алгоритм Стронгина (параллельный)
IME - индексный метод с множественной разверткой
IMEP - индексный метод с множественной разверткой (параллельный)

2.1. Необходимость использования чисел расширенной точности
Проблема:
для достижения точности ε = (½)m в RN на отрезке [0, 1] требуется точность (½)m·N
при использовании типа double максимально возможная точность ограничена условием Nm < 52
при m = 10 ограничение на размерность решаемых задач N = 5
Выход:
использование чисел расширенной точности для представления точек на отрезке [0, 1]

2.2. Особенности использования чисел расширенной точности
В работе были проанализированы некоторые библиотеки, в которых реализованы числа расширенной точности: GMP, MAPM, WinNTL
Предпринята попытка написания собственной библиотеки
Общий недостаток всех библиотек – уменьшение скорости выполнения простейших арифметических операций на 2-3 порядка

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

2.2. Особенности использования чисел расширенной точности
В индексном методе широко используется и занимает существенное временя следующая операция
нахождение расстояния между точками в многомерном пространстве через возведение в степень 1/N расстояния между двумя точками из отрезка [0, 1]




Зададимся вопросом, насколько значение res1 отличается от res2?
Пусть Ext – тип данных с расширенной точностью.

Ext m = 0.999999999999999999999;

double d, res1, res2;
res1 = m.pow(1.0 / 10.0).toDouble();
res2 = pow(m.toDouble(), 1.0 / 10.0);

2.2. Результаты использования чисел расширенной точности
Удалось сократить замедление c 500 до 10 раз
Ограничение Nm < 52  2Nm < 10308,
т.е. Nm < 1000
Проведены эксперименты на задачах с
N = 10 – 12

2.3. Результаты численных экспериментов
Функция Растригина


Размерность D=9.
область [-1.5,1.5].
Алгоритм: ISEP
m = 15, L = 0, r = 2
Максимальное число итераций 3e6
Глобальный минимум F=0.
Найденное приближение:
С использованием чисел расширенной точности
F*= 1.995057903858124
(остановка по причине нехватки оперативной памяти)
Без использования чисел расширенной точности
F*= 6.221869174733854 (остановка по причине нехватки точности)

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

3.1. Две схемы распараллеливания
Распараллеливание индексного метода с одной разверткой
Деление набора интервалов с максимальными характеристиками на каждой итерации. 1 процесс -1 интервал
Распараллеливание индексного метода с множественной разверткой
«Равномерное» разделение интервала поиска [0,..,L+1] между процессами

3.2. Распараллеливание индексного метода с одной разверткой
Построение набора интервалов с максимальными характеристиками




Каждый процесс работает с тем интервалом, индекс которого соответствует его рангу в параллельной схеме

Процесс 0
Процесс 1
Процесс N

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

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

Передача данных между процессами происходит синхронным образом

3.2. Модификация последовательного индексного метода с одной разверткой
Реализация ISE (исходный последовательный алгоритм)
на каждой итерации выбирается интервал с максимальной характеристикой и делится;
Реализация ISEMC (модифицированный последовательный алгоритм)
на итерации выбирается сразу серия интервалов с максимальными характеристиками и делится;
В отличие от параллельной версии процесс сам вычисляет индексы и значение функций во всех точках.

3.3. Параллельный алгоритм Стронгина
Схема реализации GGSAP
Использование подхода, примененного в ISEP
Отличие заключается в узкой сфере его применимости, обусловленной следующим фактом
алгоритм Стронгина позволяет решать только задачи без ограничений с одним критерием

3.4. Что пересылают друг другу процессоры?
В состав отправляемой и получаемой информации входит:
Дробная часть координаты точки;
Номер развертки;
Номер итерации, на которой вычислена точка;
Значение последней вычисленной функции в точке;
Индекс точки;
Расстояние до следующей точки;
Эта информация из переменных различных типов упаковывается в структуру

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

3.4. Пересылка чисел расширенной точности
Схема пересылки чисел расширенной точности





Необходимость формирования специальной структуры для отправки содержимого объекта класса числа расширенной точности
Число X
Структура
Процесс 0
Число X
Структура
Процесс 1
MPI

3.5. Распараллеливание индексного метода с множественной разверткой

Основана на равном разделении интервала поиска [0, L + 1] между вычислительными процессами
Каждый процесс на итерации выбирает интервал с максимальной характеристикой в своем интервале поиска
Использованы неблокирующие посылки MPI. Схема обмена данными между процессами асинхронная

3.5. Распараллеливание индексного метода с множественной разверткой
Матрица состояния поиска разделена на части, которые хранится на различных процессах
Пересылка только точек множественной итерации
Посылка точки 2 раза:
В виде заблокированной (без вычисленного значения функционала)
В виде разблокированной (с вычисленным значением функционала и индексом)

3.5. Реализация неблокирующих приемов
Первый прием?
Вызов MPI_Test для всех вызванных ранее попыток неблокирующего приема
Сохранение всех принятых точек во временную структуру
В случае если на итерации принято число точек равное числу неблокирующих запросов, то увеличить число запросов на итерации на 1
Вызов серии MPI_Irecv неблокирующих запросов на прием установленного количества точек
НЕТ
ДА
Установить число принятых на итерации точек равное 0
Установить число неблокирующих запросов равное числу процессов

3.2. IMEP V.S. IME
Результаты сравнительных экспериментов параллельного и модифицированного последовательного алгоритма.
Функция Растригина, размерности 5, 1000 итераций

4. Планы на будущее

Реализация приложения визуализирующего:
поэтапно схему межпроцессорного взаимодействия по собранной трассе
ход вычислений на каждом процессе для учебных целей
Реализация OpenMP версии алгоритмов
Реализация смешанной MPI-OpenMP схемы алгоритмов
Cluster and PDA – ideal friends