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

Параллельные вычисления являются одной из современных областей вычислительных наук [1]. Ее постоянное развитие следует из актуальной потребности в больших вычислительных ресурсах для решения прикладных задач и моделирования процессов, и предельности последовательных архитектур и схем вычислений.

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

исследовать предметную область;

провести анализ средств распараллеливания приложений;

выбрать программные средства для реализации задачи;

разработать собственный алгоритм и программное решение поставленной задачи;

проанализировать результаты

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

Минимизируя среднеквадратическую ошибку исходной выборки, получаем:

где n – количество исследуемых точек.

Все опыты проводились многократно, с усреднением полученных результатов. Использовалась вычислительная машина, содержащая 64-х разрядную ОС Windows 7, 4 Гб ОЗУ и 4 ядра, процессор: Intel® CORE™ i5-3550 (CPU @ 3.30 GHz 3.70 GHz).

В качестве инструментов для решения задачи было решено использовать среду разработки Matlab 2016a (Version 9.0) [2], содержащую обширную библиотеку функций оптимизации с поддержкой параллельных вычислений; библиотеку Intel MKL, оптимизированную для работы на конкретном аппаратном обеспечении, и стандарт для организации многопоточных приложений на многопроцессорных системах с общей памятью OpenMP, позволяющий реализовать собственное решение задачи.

В качестве первой среды разработки был выбран Matlab [3,4]. Он позволяет реализовать решение задачи двумя способами: последовательный и параллельный режим. Среда содержит удобный инструмент Profiler Matlab, который позволяет оценить время, затраченное на выполнение каждой строки кода функции или скрипта.

Результаты по времени выполнения задачи представлены в таблице (Табл. 1):

Таблица 1. Результаты времени выполнения задачи

	Последовательная реализация	Параллельная реализация
Кол-во итераций	Время выполнения функции fminunc, сек.	Время выполнения функции fminunc, сек.Время работы всей программы, сек.
32	0,58	5,0432,354

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

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

Рис. 1. Зависимость изменения скорости выполнения решения задачи от количества переменных и количества потоков (Matlab)

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

Следующим инструментом для решения задачи была выбрана библиотека Intel MKL [5,6]. Intel® Math Kernel Library (Intel® MKL) – библиотека математических вычислений, которая содержит хорошо оптимизированные многопоточные реализации математических операций и алгоритмов. Может использоваться для параллельной обработки данных в таких областях как экономика, химия, вычислительная математика, физика, биология, медицина и пр. Содержит ScaLAPACK, LAPACK, быстрое преобразование Фурье, BLAS, Solver-ы для разреженных систем и т.д. Библиотека многоплатформенная, но в Mac OS* X ScaLAPACK не поддерживается. Поддерживаются языки C и Fortran. Входит в состав таких пакетов, как IntelR Parallel Studio XE, IntelR Composer XE, IntelR Cluster Studio XE, IntelR C++ Studio XE, IntelR Fortran Composer XE, IntelR C++ Composer XE.

Результаты по времени выполнения представлены в таблице (Табл. 2) и на графике (Рис. 2).

Таблица 2. Результаты времени выполнения задачи

Рис. 2. Зависимость времени работы функции поиска минимума от количества переменных при использовании Intel MKL

Как видно, гораздо лучше по времени, чем Matlab, но хуже по количеству итераций алгоритма. Объяснить это можно тем, что MKL ориентирован на конкретную реализацию процессора Intel, а в опытах используется процессор Intel CORE i5. При увеличении количества переменных в функции время выполнения минимизации функции возрастает. Прямой зависимости от количества итераций не наблюдается.

Следующий инструмент – OpenMP – выбран за возможность написания собственного, проблемноориентированного решения в последовательном варианте выполнения и дальнейшей его модификации для возможности параллельной работы [7].

В среде Microsoft Visual Studio 2010 была написана последовательная программа, реализующая поиск минимума функции исходной задачи методом сходящегося итерационного процесса. В дальнейшем, эта программа была модифицирована с помощью директив стандарта OpenMP.

По итогам работы, среднее время выполнения программы последовательного выполнения составило порядка 0,33 секунды при заданных параметрах. А при использовании OpenMP время сократилось до 0.06 секунды (Табл. 3).

Таблица 3. Сравнительная таблица результатов решения задачи при различных подходах

	Matlab	Intel MKL	OpenMP
Время выполнения на 4 потоках, сек.	5,04	0,07	0,06
Количество итераций	32	381	30

Таким образом, время решения задачи минимизации с помощью инструмента OpenMP меньше в 5 раз, чем время решения с помощью последовательной программы, и близко к времени выполнения решения задачи с использованием библиотеки Intel MKL. Выигрыш во времени очевиден. Количество итераций – 30, что является наилучшим результатом по всем опытам.

1. Шпаковский Г.И. Реализация параллельных вычислений: кластеры, многоядерные процессоры, грид, квантовые компьютеры. – Минск, БГУ, 2010 г., 155 с.
2. Васильева М.В., Хестанова А.Ф. Исследование особенностей параллельной реализации задач минимизации… // Современные научные исследования и инновации. 2016. № 5 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2016/05/68851 (дата обращения: 16.06.2016).
3. Г.В. Жиба, А.С. Миронов. Исследование эффективности использования Matlab при распределенных вычислениях. Электронное научное издание «Ученые заметки ТОГУ». 2015, Том 6, № 4, С. 460 – 464.
4. Parallel Computing Toolbox. Mathworks. URL: http://uk.mathworks.com/products/parallel-computing/ (дата обращения 23.02.2016).
5. Академия Intel: Оптимизация приложений с использованием библиотеки Intel MKL. URL: http://www.intuit.ru/studies/courses/663/519/info (дата обращения 25.02.2016).
6. Лупин С.А, Посыпкин М.А. Технологии параллельного программирования. – М.: ИД «ФОРУМ»: ИНФРА-М, 2011, С. 119-146.
7. Введение в оптимизацию приложений с использованием библиотеки Intel MKL.  Национальный открытый университет ИНТУИТ. URL: http://www.intuit.ru/studies/professional_skill_improvements/5276/info (дата обращения 14.02.2016).

Все статьи автора «Васильева Мария Валерьевна»