В данной работе приводится пример использования возможностей OpenMP Application Programming Interface для ускорения расчетов матрицы первых производных векторфункции (матрицы Якоби) при решении задач о наименьших квадратах методом ЛевенбергаМарквардта. Вычисление матрицы Якоби производится с помощью методологии быстрого автоматического дифференцирования, при этом применяется пакет прикладного программного обеспечения Adept версии 1.0. Для ускорения расчетов использовано директивное многопоточное программирование c динамическим распределением вычислений между потоками и технология SIMD (Single Instruction Multiple Data) - принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. Вышеупомянутые технологии позволили в полной мере задействовать особенности архитектуры современных процессоров Intel, такие как многоядерность/многопоточность, расширение системы команд микропроцессоров Intel/AMD - Advanced Vector Extensions (AVX/AVX2), обрабатывающее данные в формате с плавающей запятой в группах длиной 256 бит, и FMA (Fused Multiply-Add) - технологию, предназначенную для выполнения совмещенной операции умножения-сложения. В результате, при минимальных трудозатратах, время вычисления матрицы первых производных вектор-функции на четырех ядерном процессоре удалось ускорить в 12 раз, по сравнению с вычислениями в однопоточном варианте.
of labor, the time for calculating the matrix of the first derivatives of the vector function on four core processors was 12 times faster, compared to calculations in a single-threaded version.
OpenMP; SIMD; the Jacobi matrix; the least-squares problem; the Levenberg-Marquardt method. +1 = + , = − .
+1 = + , ( + ) = − .
(
=1 ( ) ( ). Сделав получаем следующие итерационные схемы
методов. предположения о
том, что сла г(ае)мо(е )доминирует нда Q(x), где 0 < ≤ 1 – шаг метод а, - направление поиска, определяемое из решения системы уравнений направление поиска, определяемое
из решеснтиеямысиуравнений где I – единичная матрица , – некоторая неотрицательная константа, своя для каждог о - шага, развитием производные функций по вектоzриамu:
= i-е, -еj компоненты Предположим,
что компоненты
вектораu и виде: векторzоив u как , , , каждый предыдущи е , .
, = ве ктопраоследовательно выражается только через ет. 1≤j<i., тогда формулы-(9()8) можно записать в следующем Якоби) Здесь и ( , )∙ = 0, далее индTекосбозначает транспонирование, нижние индексы z, u обозначают
частные
(
= (z, u)+ ∑ Φ
( , )∙ . восстановления начальных данных для одномерного уравнения перено пассивной примеси в жидкости движущеойсстяоянсныпм значением скорости: соответствующее решени∗е( , )системы (12-()14), при Задачи, подобные этой, обычно решаются
численно с помощью некоторого метода спуска, к концентрацию ̅( , ), где ( , ∈ ).
примеси Ее
можно некоторых оптимальное экспериментальных
упралвение ∗( )= 1∗( ) и минимальное значение. Векторизация и многопоточность = ( , ), ̅ = ̅( 0 = 1 = = (
, ), = ℎ, = , ), 0 = 2 = 2( ), 0 ≤ ≤ , 0 ≤ ≤ . Архитектура универсальных микропросцоерсов постоянно развивается. Например, в процессоры
Intel, вслед (англ.
за single многопоточностью и многоядерностью последовательно были добавлены технологии
SI instruction, multiply – оdдaиtaночный поток команд, множественный поток данных), такие как MMX, SSE, SSE2, SSE3, SSSE3, SSE4.x, AVX, AVX2, AVX-512.
Не вдаваясь в подробности скажем, что
технология AVX2 (поддерживается c 2013 года в Intel
4 процессоров
C–orHeaswell) работает с 256 битными регистрами и позволяет орбабатывать
FMA3 (англ.
числа Fused с двойной точностью (или 8 чисел с одинарной точностью).
M-Auldtdip,ly умножени-есложение с однократным округлением). Вслед за изменением архитектуры микропроцессоров возникает необходимоситцьиромвоадтиьф программное обеспечение, с целью адаптации его для более эффективного использов Найти , решив Положить +1 = +
и −
k= 0,0 = 0.01, = 10−20 #pragma omp for – данная конструкция указывает компилятору на необходимость многопоточно исполнения цикла.
По умолчанию компилятор заранее разбивает n цстиактличенскаих групп и формирует n потоков исполнения, гnде– количество логических процессоров в системе (или число, указанное
пользователем). #pragma omp for schedule(dynamic) – разновидность предыдущей конструкции, указывающая что разбиение цикла будет происходить динамически, в процессе выполнения.
имеют скеунды и различное т.д., то время исполнения, на-пяриимтеерр,ац1и–я 1
секунда,-я 2 итерация 2 использование Если +1 < , 10. Если +1 < , +1 = 0.1 , = 11.
Если > 1020, +1; +1 то то то завершить работу.
положить + 1, и
перейти к шагу 3. завершить
работу. 12. Если +1 ≥ , то полож и ть+1 = 10 , и перейти к шагу 5. } Используя ключи компилятора -ftree-vectorizer-verbose=3 -fopt-info-vec-all=rezv.txt, можно увидеть, что векторизация данных циклов не производится. То есть преимущества современной архитектуры процессора не используются.
Заменим данные конструкции на а) if(flag_extra) for (int i = 0; i < n_extra; i++)
… else #pragma omp simd for (int i = 0; i < ADEPT_MULTIPASS_SIZE; i++)
… б) int n_non_zero = 0; if(flag_extra) for (int i = 0; i < n_extra; i++) { … if(a[i] != 0) n_non_zero = 1; } else #pragma omp simd reduction(|:n_non_zero) for (int i = 0; i < ADEPT_MULTIPASS_SIZE; i++) { … n_non_zero |= (a[i] != 0); } Здесь епременная цикла для большинства блоков изменяется от 0 до фиксированного знач ADEPT_MULTIPASS_SIZE, и включена принудительная векторизация директ#иpвrоaйgma omp simd. В случае б) необходимо, кроме этого, выполнять редукцию пnе_рnеoмnе_zнeнrоoй.
В рзеультате, после подбора парамеAтDрEаPT_MULTIPASS_SIZE (рис.1), получаем ускорение расчетов почти в 2 раза.
Таблица 5. Время вычислений при использовании SIMD
Шаг/Время сек
Вычисление функции
Вычисление матрицы Якоби
Вычисление коэффициентов системы уравнений
(
В работе не был затронут вопрос распараллеливания методов решения систем линейных урав Пути ускореиня могут быть следую–щиисепользование параллельных версий пакета LaPack, применение параллельных версий метода сопряженных градиентов. В ряде случаев будет эффективн использование двойственных постановок задач квадратичного программирования. Благодарности Работа выполнена при поддержке РФФИ, пр-0о7е-к0т045186.