Введение

Рассмотрим задачу многомерной многоэкстремальной оптимизации в виде }. Как известно, вычислительные затраты на решение задачи (1) растут экспоненциально с ростом размерности, что делает актуальным распараллеливание процесса поиска оценки (2). В данной работе рассматривается подход, в котором схема распараллеливания основана на одновременном проведении нескольких испытаний в выбранных по некоторому правилу точках.

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

Базовый параллельный алгоритм глобального поиска

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

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

в которой целевая функция (x) удовлетворяет условию Липшица.

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

Пусть в нашем распоряжении имеется

k i x x i i    2 ), ,( 1 рассматри

вается как некоторая мера вероятности нахождения в данном интервале точки глобального минимума, а испытания проводятся параллельно в первых p интервалах, имеющих наибольшие вероятности. Различные модификации одного из эффективных алгоритмов данного типа, информационно-статистического, и соответствующая теория сходимости представлены в [4].

Блочная многошаговая схема редукции размерности

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

) ( min ... min min } : ) ( min{ 2 2 2 1 1 1 y D y y N N N b y a b y a b y a           .(6)

В [3] подробно рассмотрены вопросы численного построения развертки на основе кривой Пеано y(x), однозначно отображающей отрезок вещественной оси [0,1] на n-мерный гиперкуб

    1 0 : ) ( 1 , 2 2 : 1 1            x x y N i y R y i N .

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

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

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

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

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

2 1 2 1 M N u u u y y y y   , где i-я блочная переменная u i представляет собой вектор размерности i N из последовательно взятых компонент вектора y, т.е. ) ,..., , ( 1 2 1 1 N y y y u  , ) ,..., , ( 2 1 1 1 2 1 2 N N N N y y y u     ,…, ) ,..., , ( 2 1 N N N N N M y y y u M M      , причем N N N N M     ...2 1 .

С использованием новых переменных основное соотношение многошаговой схемы (6) может быть переписано в виде

) ( min ... min min ) ( min 2 2 1 1 y y M M D u D u D u D y        , (7) где подобласти M i D i   1 , , являются проекциями исходной области поиска D на подпро- странства, соответствующие переменным M i u i   1 ,

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

1 1 1 1 1 1       i i i D u i i u u u u u i i   , 1 1    M i (8)

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

Параллельная блочная многошаговая схема

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

2 1 M       ,(9)

где

M i i   1 ,  -число параллельно решаемых подзадач (i+1)-го уровня вложенности, возни- кающих в результате выполнения параллельных итераций на i-м уровне. Для M-го уровня чис- ло M  означает количество параллельных испытаний в процессе минимизации функции ) , ,( ) , , ( 1 1N M M y y u u      по переменной M u при фиксированных значениях 1 1 , ,  M u u  , т.е.

количество параллельно вычисляемых значений целевой функции (y). В данной работе мы считаем, что компоненты вектора (9) не меняются в процессе решения задачи (7), а 1

 M  . Тогда общее число задействованных процессоров/ядер будет составлять        1 1 1 1 M i i j j  . (10)

На рисунке 1 приведена общая схема организации вычислений при M = 3.

Рис. 1. Схема организации параллельных вычислений (M = 3)

Синхронная MPI-версия блочной многошаговой схемы

Соотношение (10) задает число MPI-процессов, которые должны быть созданы при запуске MPI-реализации блочной многошаговой схемы, а вектор (9) позволяет выстроить процессы в дерево, корневой процесс которого решает исходную задачу (1), процессы нижележащих уровней -подзадачи из (8), а процессы-листья кроме того вычисляют значения целевой функции

(y).  1 (u 1 )  2 (u 1 , u 2 )  2 (u 1 , u 2 )  3 (u 1 ,u 2 ,u 3 )  3 (u 1 ,u 2 ,u 3 )  3 (u 1 ,u 2 ,u 3 )  3 (u 1 ,u 2 ,u 3 ) … … … …

Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Простым вариантом взаимодействия процессов в дереве является синхронный, при котором каждый нетерминальный процесс раздает подчиненным процессам по одной подзадаче, дожидается, пока все пришлют найденные ими решения, после чего раздает им новые подзадачи.

Опишем общие схемы работы корневого процесса, нетерминальных и терминальных процессов в этом случае. Указанная схема соответствует шаблону взаимодействия процессов «мастер-рабочий».

Схема работы корневого процесса

Схема работы нетерминального процесса

0. Принять от процесса-мастера (далее родителя) точку с фиксированными координатами

Схема работы терминального процесса

Асинхронная MPI-версия блочной многошаговой схемы

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

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

Схема работы корневого процесса

Результаты вычислительных экспериментов

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

В качестве тестовых задач были выбраны функции Растригина, Розенброка и Ньюмайера. Формульное задание функций представлено ниже. Что касается распределения числа параметров по уровням дерева, из таблиц 1-3 видно, что при M = 2 наилучший результат достигается при распределении вида (N-1, 1). При M = 3 этот эффект заметен не так явно, но в целом видна тенденция уменьшения времени при увеличении значений первых элементов в векторе (N 1 , N 2 , N 3 ).

Функция Растригина        N i i i N x x N y y 1 2 1 ) 2 cos( 10 10 ) ,..., (   Функция Розенброка             1 1 2 2 2 1 1 ) 1 ( 100 ) ,..., ( N i i i i N x x x y y  Функция Ньюмайера           N i N i i i i N x x x y y

Заключение

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

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

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.