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

 Тогда возможный способ описания априорных предположений о минимизируемой функции  состоит в задании плотности  распределения вероятностей на пространстве .

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

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

Алгоритм

Шаг 0: y(0)=a, y(1)=b, n=1

Шаг 1: вычисляем m оценку константы Липшица

гдеr параметр метода r>1

Шаг 2: для всех отрезков вычисляем характеристику  и находим максимум

Шаг 3: находим новую точку разбиения на интервале максимальной характеристики

Шаг 4: проверяем критерий останова (останов по точности) если выполняется, то алгоритм завершается. Результат работы алгоритма min = иначе упорядочиваем массив y(i) по возрастанию и переходим на Шаг 1.

Метод Пиявского

 Данный метод предполагает, что минимизируемая функция одного аргумента f(y) удовлетворяет на отрезке [a,b] условию Липшица с константой L>0, т.е.f ( y)Lip[a,b] .

 Идея метода геометрически проста: предлагается проводить очередное испытание в точке минимума кусочно-линейной миноранты , что реализует принцип одношаговой оптимальности.

Алгоритм

Шаг 0: y(0)=a, y(1)=b, n=1

Шаг 1: вычисляем m оценку константы Липшица

где r параметр метода r>1

Шаг 2: для всех отрезков вычисляем характеристику  и находим максимум

Шаг 3: находим новую точку разбиения на интервале максимальной характеристики

Шаг 4: проверяем критерий останова (останов по точности) если выполняется, то алгоритм завершается. Результат работы алгоритма min = иначе упорядочиваем массив y(i) по возрастанию и переходим на Шаг 1.

Реализация методов, основные пути распараллеливания

Требования, накладываемые алгоритмом

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

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

Требования, связанные со спецификой MPI

 Прежде всего следует отметить что Message Passing Interface (MPI, интерфейс передачи сообщений) — программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан для запуска процессов, совместно выполняющих некоторую задачу и рассчитан на системы с разделенной памятью. Следовательно, основными моментами, на которые следует обращать внимание при написании алгоритмов параллельных MPI программ является проблема обмена данными. Каждый процесс хранит свою локальную копию всех данных. Возникает проблема оптимизации количества пересылок данных между процессами(операция пересылки по сети — является трудоемкой операцией).

 Так как с программной точки зрения алгоритмы Пиявского и Стронгина отличаются только  формулами вычисления характеристики, далее будем рассматривать только алгоритм Стронгина.

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

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

 Структура сегмент имеет 2 поля начальную и конечную точку отрезка, где yj < yi.

struct segment

{

double yi;

double yj;

};

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

separator = 0.5*(segments[T].yi+segments[T].yj)- (f(segments[T].yi)-f(segments[T].yj))/(2*m);

segments[N+1].yi = segments[T].yi;

segments[T].yi = separator;

segments[N+1].yj = separator;

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

 В случае вычисления M, оценки константы Липшица, вызов функции имеет вид

MPI_Allreduce(&_M,&Mr,1,MPI_DOUBLE,MPI_MAX,MPI_COMM_WORLD);

где _M содержит локально-вычисленное максимальное значение для данного процесса, а Mr — переменная, куда будет разослан результат операции   MPI_MAX(взятие максимума  из всех полученных от процессов значений)

 В случае вычисления R, характеристики сегмента, вызов функции имеет вид

MPI_Allreduce(&_in,&out,1,MPI_DOUBLE_INT, MPI_MAXLOC,MPI_COMM_WORLD);

где _in содержит локально-вычисленное максимальное значение характеристики для данного процесса а так же номер сегмента на котором оно вычислено, а _out — переменная, куда будет разослан результат операции  MPI_MAXLOC(взятие максимума  из всех полученных от процессов значений по переменной типа double) а далее в _out рассылается каждому процессу структура, соответствующая этому значению

 _out и _in имеют тип mpiArtefact

struct mpiArtefact{

double R;

int T;

};

Следует обратить внимание, что для корректной пересылки сообщений необходимо что бы каждый вычислительный узел имел свою копию _out и _in, _M и Mr.

Пусть последовательная версия алгоритма сошлась за n шагов, m- число запущенных процессов,i-шаг алгоритма, тогда последовательная версия выполнит на первом шаге одно вычисление, на втором 2, на третьем 3 и тд. За вычисление считаем операцию подсчета константы Липшица и подсчета характеристики сегмента.
Получаем
Рассмотрим параллельный случай. На каждом шаге каждый процесс вычисляет минимум [i/m]элементов, остаток [i-i/m]
последняя скобка показывает число вычислений которые добавляются в результате не целого деления и исключаем те шаги на которых i/m делится нацело
Преобразуем
Найдем отношение общего числа вычислений производимых 1 процессом к числу вычислений на один процесс при условии что вычисления производится m процессами.

Предположим что число процессов m = 2, получаем Что в пределе дает 2
Следовательно данная реализация в пределе дает максимальную эффективность.

Тестовая функция sqrt(x)*sin(x) Стандартные параметры методов r=2.0, e = 0.0001, a = 1.0, b = 8.0
Таблица результатов для тестовой функции со стандартными настройками.

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

Проверим эффективность распараллеливания для более сложной функции на большем отрезке. Тестовая функция sqrt(1+3*cos(x)^2)+cos(10*x) Сс параметрами r=2.0, e = 0.00001, a = 1.0, b = 50.0

методы	сходится, шагов	1 процесс, с	2 процесса, с	ускорение, раз	4 процесса, с	ускорение, раз
Стронгина	5350	13.81639917	10.12693594	1.364	8.28853031	1.666
Пиявского	7934	6.49823946	4.46015380	1.456	3.14978404	2.063

Хотя прирост производительности наблюдается, теоретическая оценка эффективности не достигается что связано с накладными расходами на параллелизм. (Для теста использовались 2 двух ядерных ноутбука с процессорами intel core, соединенные wifi сетью.)

Следует отметить что наибольший прирост производительности параллельный алгоритм показывает на функциях, близких к константе, т.к. алгоритму необходимо сделать достаточно большое число шагов, чтобы обеспечить сходимость.
Далее приведены результаты экспериментов для функции 100+cos(10*x) с параметрами r=2.0, e = 0.00001, a = 1.0, b = 10.0

методы	сходится, шагов	1 процесс, с	2 процесса, с	ускорение, раз	4 процесса, с	ускорение, раз
Стронгина	4804	2.55342372	1.71274949	1,492	1.28456212	1.987
Пиявского	6693	4.65466386	2.94497056	1.583	2.12037880	2.195

Прирост производительности для метода Стронгина для 2 процессов примерно 1,49 раз. Прирост производительности для метода Пиявского для 2 процессов примерно 1,58 раз.
Теоретическая оценка эффективности не достигается, что обьясняется большими накладными расходами на параллелизм, по сравнению с вычислительной нагрузкой. Наиболее Эффективно распараллеливание в случае если функция является близкой к константе.