Нижегородский государственный университет им. Н.И. Лобачевского

Abstract

Представлен новый подход к решению задач глобальной оптимизации, комбинирующий информационно-статистический алгоритм, разработанный в ННГУ им. Н.И. Лобачевского с блочной схемой редукции размерности. Предложен параллельный алгоритм, реализующий данный подход. Представлены синхронная и асинхронная схемы MPI-реализации указанного алгоритма. Приведены результаты сравнения схем, показывающие преимущество асинхронного варианта.

-

MPI-реализация блочной многошаговой схемы параллельного решения задач глобальной оптимизации* где (y) – действительная функция, a,bRN есть заданные векторы.

Численное решение задачи ( 1 ) состоит в отыскании оценки ( 3 ) (4)

Для снижения сложности алгоритмов глобальной оптимизации, формирующих неравномерное покрытие области поиска, широко используются различные схемы редукции размерности, которые позволяют свести решение многомерных оптимизационных задач к семейству задач одномерной оптимизации. Поэтому в качестве базовой задачи мы будет рассматривать одномерную задачу многоэкстремальной оптимизации  *  (x*)  min{ (x) : x [0,1]}, (5) в которой целевая функция (x) удовлетворяет условию Липшица.

Дадим краткое описание параллельного алгоритма глобального поиска (ПАГП), применяемого к решению задачи (5).

Пусть в нашем распоряжении имеется p  1 вычислительных элементов. Тогда на каждой итерации можно провести одновременно p испытаний и, следовательно, общее число испытаний, выполненных после n параллельных итераций, составит k  pn .

Предположим, что выполнено n  1 итераций метода (в качестве точек x1,...,x p первой итерации выбираются произвольные различные точки отрезка [0,1]). Тогда точки xk 1,...,xk  p текущей (n+1)-ой итерации определяются по правилам выбранного метода из класса характеристически представимых [3]. При этом характеристика интервала (xi1, xi ), 2  i  k рассматривается как некоторая мера вероятности нахождения в данном интервале точки глобального минимума, а испытания проводятся параллельно в первых p интервалах, имеющих наибольшие вероятности. Различные модификации одного из эффективных алгоритмов данного типа, информационно-статистического, и соответствующая теория сходимости представлены в [4]. 3. Блочная многошаговая схема редукции размерности

Один из подходов к решению многомерных задач глобальной оптимизации состоит в их сведении к одномерным и использовании для решения редуцированной задачи эффективных одномерных алгоритмов глобального поиска. При этом редукция может применяться как к области D из ( 1 ), взаимно однозначно отображая гиперпараллелепипед D на отрезок [0,1], так и к функции (y), минимизацию которой можно выполнять на основе рекурсивной схемы (см. [5]) min{ ( y) : y  D}  min min ... min  ( y) .

a1 y1b1 a2  y2 b2 aN  yN bN (6) В [3] подробно рассмотрены вопросы численного построения развертки на основе кривой Пеано y(x), однозначно отображающей отрезок вещественной оси [0,1] на n-мерный гиперкуб y  RN : 21  yi  21,1  i  N y(x) : 0  x  1.

Развертка является приближением к кривой Пеано с точностью порядка 2m , где m – параметр построения.

Использование подобного рода отображений позволяет свести многомерную задачу ( 1 ) к одномерной задаче

 ( y*)  ( y(x*))  min{ ( y(x)) : x [0,1]}.

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

Рассмотрим вектор y как вектор блочных переменных

y  ( y1, y2,...,yN )  (u1,u2,...,uM ) , где i-я блочная переменная ui представляет собой вектор размерности Ni из последовательно взятых компонент вектора y, т.е. u1  ( y1, y2,...,yN1 ) , uM  ( yNNM 1, yNNM 2,..., yN ) , причем N1  N2  ... NM  N .

С использованием новых переменных основное соотношение многошаговой схемы (6) может быть переписано в виде u2  ( yN1 1, yN1 2,..., yN1 N2 ) ,…, min ( y)  min min ... min  ( y) , yD u1D1 u2D2 uM DM где подобласти Di ,1  i  M , являются проекциями исходной области поиска D на подпространства, соответствующие переменным ui ,1  i  M .

При этом принципиальным отличием от исходной схемы является тот факт, что в блочной схеме вложенные подзадачи i (u1,...,ui ) 

min i1(u1,...,ui ,ui1) , 1 i  M 1 ui1Di1 являются многомерными, и для их решения может быть применен способ редукции размерности на основе кривых Пеано. 4. Параллельная блочная многошаговая схема

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

  (1, 2,, M ) , где  i , 1  i  M – число параллельно решаемых подзадач (i+1)-го уровня вложенности, возникающих в результате выполнения параллельных итераций на i-м уровне. Для M-го уровня число  M означает количество параллельных испытаний в процессе минимизации функции M (u1,,uM )  ( y1,, yN ) по переменной uM при фиксированных значениях u1,,uM 1 , т.е. количество параллельно вычисляемых значений целевой функции (y). В данной работе мы считаем, что компоненты вектора (9) не меняются в процессе решения задачи (7), а  M  1. Тогда общее число задействованных процессоров/ядер будет составлять На рисунке 1 приведена общая схема организации вычислений при M = 3.

2(u1, u2)

2(u1, u2) 3(u1,u2,u3) … 3(u1,u2,u3) 3(u1,u2,u3) …

3(u1,u2,u3)

M 1 i   1    j .

i1 j1 1(u1) … … Рис. 1. Схема организации параллельных вычислений (M = 3) 5. Синхронная MPI-версия блочной многошаговой схемы Соотношение (10) задает число MPI-процессов, которые должны быть созданы при запуске MPI-реализации блочной многошаговой схемы, а вектор (9) позволяет выстроить процессы в дерево, корневой процесс которого решает исходную задачу ( 1 ), процессы нижележащих уровней – подзадачи из (8), а процессы-листья кроме того вычисляют значения целевой функции (y). (7) (8) (9) (10) Простым вариантом взаимодействия процессов в дереве является синхронный, при котором каждый нетерминальный процесс раздает подчиненным процессам по одной подзадаче, дожидается, пока все пришлют найденные ими решения, после чего раздает им новые подзадачи.

Опишем общие схемы работы корневого процесса, нетерминальных и терминальных процессов в этом случае. 5.1. Схема работы корневого процесса u1,,ui1 .

брать произвольные  i точек). 1. Если N1 > 1 выполнить редукцию размерности, используя развертку Пеано, сведя задачу к одномерной. 2. Выбрать  1 точек в интервалах с наилучшими характеристиками (на первой итерации выбрать произвольные  1 точек). дому из  1 подчиненных процессов (далее потомков). 4. Дождаться решения порожденных подчиненными процессами подзадач, принять от каждого из них данные (оценку точки минимума, значение целевой функции). 5. Проверить условие остановки.

a. Если выполнено, СТОП. b. Если не выполнено, перейти к шагу 2.

Указанная схема соответствует шаблону взаимодействия процессов «мастер-рабочий». 5.2. Схема работы нетерминального процесса 0. Принять от процесса-мастера (далее родителя) точку с фиксированными координатами 1. Если Ni > 1 выполнить редукцию размерности, используя развертку Пеано, сведя задачу к одномерной. 2. Выбрать  i точек в интервалах с наилучшими характеристиками (на первой итерации вы3. Передать соответствующие зафиксированные координаты (u1,,ui ) каждому из  i потомков. 4. Дождаться решения порожденных потомками подзадач, принять от каждого из них данные (оценку точки минимума, значение целевой функции). 5. Проверить условие остановки.

a. Если выполнено, передать данные (оценку точки минимума, значение целевой функции) родителю. Перейти к шагу 0.

b. Если не выполнено, перейти к шагу 2. 5.3. Схема работы терминального процесса 0. Принять от родителя точку с фиксированными координатами u1,,uM 1 . 1. Если NM > 1 выполнить редукцию размерности, используя развертку Пеано, сведя задачу к одномерной. 2. Решить редуцированную задачу оптимизации. 3. Передать данные (оценку точки минимума, значение целевой функции) родителю. 4. Перейти к шагу 0. 6. Асинхронная MPI-версия блочной многошаговой схемы Синхронная версия блочной многошаговой схемы обладает существенным недостатком, связанным с возможными простоями всех узлов дерева процессов, кроме корневого. Простои могут возникать в том случае, если часть потомков некоторого процесса закончили решение своих подзадач и отправили данные родителю раньше остальных, поскольку родитель создаст для этих потомков новые подзадачи только после получения решений от всех своих потомков. С ростом числа уровней M в дереве процессов, указанные простои могут приводить к существенной потере эффективности, что подтверждается результатами экспериментов (раздел 7).

Для преодоления данной проблемы была разработана асинхронная версия блочной многошаговой схемы. Алгоритм работы терминальных процессов в этой схеме совпадает с алгоритмом в синхронном случае. Схемы для корневого и нетерминальных процессов представлены далее. 6.1. Схема работы корневого процесса 1. Если N1 > 1 выполнить редукцию размерности, используя развертку Пеано, сведя задачу к одномерной. 2. Выбрать  1 точек на отрезке [0,1]. 3. Передать зафиксированные координаты y1, y2,..., yN1 каждому из  1 потомков. 4. Дождаться решения порожденных подчиненными процессами подзадач, принять от каждого из них данные (оценку точки минимума, значение целевой функции). 5. Выбрать  1 точек в интервалах с наилучшими характеристиками. 6. Передать зафиксированные координаты y1, y2,..., yN1 каждому из  1 потомков. 7. Принять решение подзадачи от любого потомка, приславшего данные. 8. Проверить условие остановки. Если выполнено, СТОП. 9. Выбрать одну точку очередного испытания в интервале с наилучшей характеристикой. 10. Передать зафиксированные координаты y1, y2,..., yN тому потомку, от которого приняли 1 решение подзадачи на шаге 7. 11. Перейти к шагу 7.

Указанная схема соответствует шаблону взаимодействия процессов «мастер-рабочий». 6.2. Схема работы нетерминального процесса 0. Принять от родителя точку с фиксированными координатами u1,,ui1 . 1. Если Ni > 1 выполнить редукцию размерности, используя развертку Пеано, сведя задачу к одномерной. 2. Выбрать  i точек на отрезке [0,1]. 3. Передать зафиксированные координаты (u1,,ui ) каждому из  i потомков. 4. Дождаться решения порожденных потомками подзадач, принять от каждого из них данные (оценку точки минимума, значение целевой функции). 5. Выбрать  i точек в интервалах с наилучшими характеристиками. 6. Передать зафиксированные координаты (u1,,ui ) каждому из  i потомков. 7. Принять решение подзадачи от любого потомка, приславшего данные. 8. Проверить условие остановки. Если выполнено, передать данные (оценку точки минимума, значение целевой функции) родителю. Перейти к шагу 0. 9. Выбрать одну точку очередного испытания в интервале с наилучшей характеристикой. 10. Передать зафиксированные координаты (u1,,ui ) тому потомку, от которого приняли решение подзадачи на шаге 7. 11. Перейти к шагу 7. 7. Результаты вычислительных экспериментов

Вычислительные эксперименты проводились на суперкомпьютере «Лобачевский» (операционная система – CentOS 6.4, система управления – SLURM). Один узел суперкомпьютера располагает двумя процессорами Intel Sandy Bridge E5-2660 2.2 GHz (8 ядер в каждом), 64 Gb RAM, сеть InfiniBand. Использовался компилятор Intel C++ 14.0.2.

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

Функция Растригина

N  ( y1,..., yN )  10N   xi2 10 cos(2xi )

i1 Функция Розенброка  ( y1,..., yN )  N1 100xi1  xi2 2  (xi 1)2 

i1 Функция Ньюмайера

N N  ( y1,..., yN )   xi 12   xi xi1

i1 i2 Эксперименты направлены на сравнение синхронной и асинхронной схем, а также на выяснение того, каким образом распределение размерностей по уровням влияет на время работы программы. Результаты представлены в таблицах 1, 2, 3. Эксперименты проводились при числе уровней в дереве процессов M = 2 и M = 3. Использовались вектора  1  ( 3,1 ) и  2  ( 3,3,1 ) соответственно. Размерность задачи N и распределение параметров по уровням блочной схемы указаны в первом столбце таблиц.

Таблица 1. Сравнение синхронной и асинхронной версий, функция Растригина 0.994 2.725 1.460 1.009 3.771 10.105 0.962 5.416 13.848 5.103 1.732 5.594 12.745 14.096 1.360 ( 1, 1, 3 ) 15.900 14.588 33 25 ный алгоритм работает примерно так же, как синхронный. Также можно заметить, что корень дерева в асинхронной схеме делает меньше или столько же итераций, сколько в синхронной.

Что касается распределения числа параметров по уровням дерева, из таблиц 1-3 видно, что при M = 2 наилучший результат достигается при распределении вида (N–1, 1). При M = 3 этот эффект заметен не так явно, но в целом видна тенденция уменьшения времени при увеличении значений первых элементов в векторе (N1, N2, N3). 8. Заключение

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

В дальнейшем планируется дополнить разработанную схему возможностью использования множественных разверток при решении многомерных подзадач. Литература MPI implementation of dimension reduction multilevel scheme for parallel solving the global optimization problems Alexander Sysoyev, Konstantin Barkalov, Victor Gergel and Ilya Lebedev Keywords: global optimization, information-statistical algorithm, dimension reduction, multilevel scheme, synchronous scheme, asynchronous scheme, cluster The paper presents the new approach to solve the global optimization problems that combines the information-statistical algorithm developed in the University of Nizhni Novgorod with multilevel scheme of dimension reduction. A parallel algorithm that implements such approach is suggested and its synchronous and asynchronous MPI implementation is presented. The advantage of asynchronous scheme is shown by comparing with synchronous one.

References

3. Передать соответствующие зафиксированные N1 координат вектора y ( y1 , y2 ,..., yN1 ) каж - 33

1. K. Barkalov , V. Gergel . Multilevel scheme of dimensionality reduction for parallel global search algorithms // OPT-i 2014 . An International Conference on Engineering and Applied Sciences Optimization (Kos Island, Greece , 4 - 6 June 2014). 2014 . pp. 2111 - 2124 .

2. А.В. Сысоев, К.А. Баркалов, В.П. Гергель. Блочная многошаговая схема параллельного ре- шения задач многомерной глобальной оптимизации // Материалы XIV Международной конференции "Высокопроизводительные параллельные вычисления на кластерных систе- мах" . 10-12 ноября, ПНИПУ, Пермь. 2014 . С. 425 - 432 .

3. R.G. Strongin , Ya.D. Sergeyev, Global optimization with non-convex constraints. Sequential and parallel algorithms . Kluwer Academic Publishers, Dordrecht, 2000 .