В роботі розглядаються алгоритми методів розв'язання систем нелінійних рівнянь (СНР) і задач Коші для систем звичайних диференціальних рівнянь (СЗДР) для багатоядерних комп'ютерів з процесорами Intel Xeon Phi. Наведено часи розв'язування СНУ і СЗДР різних порядків, обраховані коефіцієнти прискорення і ефективності використання запропонованих методів. Ключові слова: багатоядерні комп'ютери, системи нелінійних рівнянь, задачі Коші для систем звичайних диференціальних рівнянь. В работе рассматриваются алгоритмы методов решения систем нелинейных уравнений (СНУ) и задач Коши для систем обыкновенных дифференциальных уравнений (СОДУ) для многоядерных компьютеров с процессорами Intel Xeon Phi. Приведены времена решения СНУ и СОДУ разных порядков, вычислены коэффициенты ускорения и эффективности использования предложенных методов. Ключевые слова: многоядерные компьютеры, системы нелинейных уравнений, задачи Коши для систем обыкновенных дифференциальных уравнений. The paper deals with algorithms of methods for the solving both of non-linear systems (NLS) and initial-value problems for systems of ordinary differential equations (SODE) on multi-core computers. Times required for the solving of various order SNE and SODE are given; acceleration and performance coefficients characterizing the employment of methods being proposed are evaluated, as well.
Задача Коші для системи звичайних диференціальних рівнянь. Нехай дано систему n звичайних диференціальних рівнянь. Задачу з початковими умовами (задачу Коші) для СЗДР n-го порядку на інтервалі [t0, T ] розглядатимемо у вигляді де v v1,v2 ,,vn T шуканий вектор, а права частина системи – n-вимірна неперервна вектор-функція t,v 1t,v,2 t,v,, n t,vT .
При моделюванні реальних процесів на комп'ютері за допомогою СЗДР виникає ряд труднощів, зокрема, потреба мати справу з задачами з наближеними даними. Тому на практиці, як правило, замість задачі (3), (4) маємо задачу з наближеними даними: де ( i = 0, 1, 2, … )
k1 hi f (ti , y(i) ), k2 hi f (ti hi / 2, y(i) 0,5k1), k3 hi f (ti hi / 2, y(i) 0,5k2),
k4 hi f (ti hi , y(i) 0,5k3) . де y y1, y2,, yn T , y (0) v(0) , f t, y f1t, y, f2 t, y,, fn t, yT , причому t, w f t, w t, w, t, w для довільної функції w(t ) . Методи розв’язування СНР та задач Коші для СЗДР
fi Метод Ньютона. Якщо H x j i, j1 n
матриця Якобі системи (1) (або деяке наближення до неї), то
H k wk f xk ітераційний процес методу Ньютона знаходження розв’язку при заданому початковому наближенні записується у вигляді де wk xk 1 xk поправка, k = 0, 1, ... – номер ітерації, а xk 1 xk wk . Як видно з формули (7), на кожній ітерації необхідно обчислювати значення вектор-функції і матрицю Якобі та розв’язувати систему лінійних алгебраїчних рівнянь (СЛАР).
Метод Рунге – Кутта 4-го порядку точності. Одним із широко вживаних методів, що застосовується для чисельного інтегрування задач з початковими умовами для СЗДР, є метод Рунге – Кутта 4-го порядку. Класичний метод Рунге – Кутта 4-го порядку реалізується за формулами: y(i1) y(i) (k1 2k2 2k3 k4) / 6, dv dt
(t,v) , v(t0) v(0), dy dt
f (t, y), y(t0 ) y(0) , (7) (9) оцінки головного члена похибки, який визначає вибір кроку інтегрування, доводиться, частіше за все, тричі застосовувати метод Рунге – Кутта. Паралельні алгоритми розв’язування СНР та задач Коші для СЗДР Розпаралелювання алгоритмів проводилось, виходячи з архітектури комп’ютера з багатоядерними процесорами Intel Xeon Phi. Кожний процесор Intel Xeon Phi має від 64 до 72 ядер, кожне з яких має два VPU (векторних процесорних пристроїв). Така архітектура процесора дає можливість мати декілька рівнів паралелізму.
Вищий рівень паралелізму передбачає використання середовища MPI, що дає можливість проводити обчислення у вигляді паралельних процесів на p ядрах, забезпечує синхронізацію обчислень та обмін інформацією між ядрами. На нижчому рівні кожний з таких процесів розпаралелюється між деякою кількістю потоків на вільних ядрах. Для розпаралелювання на цьому рівні доцільно використовувати програмні модулі математичної бібліотеки Intel МКL, які застосовуються для обчислення матричновекторних операцій.
При розв’язуванні СНР та інтегруванні СЗДР будь-яким методом значна частина арифметичних операцій припадає на обчислення значень вектор-функції f x . Тому на комп’ютерах з паралельною організацією обчислень необхідно в першу чергу проводити розпаралелювання обчислення значень вектор-функції, яке дозволить автоматично розпаралелити обчислення наближення до матриці Якобі і розв’язування відповідної СЛАР та інтегрування СЗДР методом Рунге – Кутта за формулами (8), (9).
Автоматичний розподіл обчислення значень компонент деякої n-вимірної вектор-функції на p блоків (p – кількість процесів верхнього рівня паралелізму, що використовуються) виконується, виходячи з рівномірного завантаження процесів [1, 2].
Паралельний алгоритм методу Ньютона. На кожній ітерації алгоритму методу Ньютона виконуються наступні макрооперації:
1) обчислення кожним MPI-процесом частини компонент вектор-функції, що відповідають його логічному номеру; 2)
обчислення кожним MPI-процесом відповідної кількості рядків матриці Якобі H x(k 1) ; 3) розв’язування отриманої СЛАР (7), використовуючи відповідний (до структури матриці Якобі) паралельний алгоритм, наприклад, паралельний алгоритм методу Гауса [3]; 4)
використовуючи отриманий розв’язок СЛАР, обчислення кожним MPI-процесом відповідних його логічному номеру компонент наступного наближення до розв’язку СНР x(k 1) x(k) w(k) ; 5) перевірка умов закінчення ітераційного процесу за формулою f x(k 1)
H (k 1) 1 , 1) 2) 3) 4) кроком hi ; яка є оцінкою якості наближеного розв’язку, що забезпечує виконання нерівності x(k 1) x , де x – точний розв’язок СНР [4].
Зазначимо, що обчислення пунктів 2) – 5) проводиться з використанням функцій бібліотеки Intel МКL. Паралельний алгоритм методу Рунге – Кутта 4-го порядку. Кожний і-й крок алгоритму реалізується за наступною схемою:
обчислення кожним MPI-процесом у відповідності з його логічним номером компонент векторів k1 , k2 , k3 , k4 та вектора y(i1) y(i) 6 , де k1 2k2 2k3 k4 ; номером частину компонент yi1 , використовуючи двократне чисельне інтегрування СЗДР з кроком hi 2 ; за схемою першого пункту обчислення кожним MPI-процесом у відповідності з його логічним логічним номером частину компонент yi1 , використовуючи однократне чисельне інтегрування СЗДР з за схемою першого пункту обчислення кожним MPI-процесом у відповідності з його обчислення кожним MPI-процесом у відповідності з його логічним номером частину компонент вектора похибки апроксимації системи i1 1mjaxn yji1 yji1 ;
5) обчислення кожним MPI-процесом при виконанні умов досягнення заданої точності уточненої довжини кроку інтегрування; 6) перевірка кожним MPI-процесом умов досягнення на наступному кроці інтегрування точки виводу розв’язку або кінцевої точки інтервалу інтегрування T та коригування при необхідності довжини кроку інтегрування.
Після обчислення розв’язку в точці виводу запам'ятовуються вектор розв’язку, константа Ліпшиця та оцінка похибки розв’язку [5].
Зазначимо, що обчислення пунктів 1) – 5) проводиться з використанням функцій бібліотеки Intel МКL. Експериментальне дослідження паралельних алгоритмів
Обчислювальні експерименти по розв’язуванню СНР та задач Коші для СЗДР проводилися на одновузловому (однопроцесорному) комп’ютері з процесором Intel Xeon Phi х200, який використовує 64 ядра.
Експериментальне дослідження паралельного алгоритму методу Ньютона. Методом Ньютона розв’язувалась система нелінійних рівнянь: i i 2 0 , i=1, 2, , n n x j 0.53n 1 2xi2 21 2 j1 n n (10) при заданому початковому наближенні x0 1
, в області D 1000 xi 1000, i 0,1,2,, n 1 . Наведемо деякі з отриманих результатів. В табл. 1 представлені часи розв’язування СНР (10) в залежності від її порядку.
Коефіцієнти прискорення S p T1 Tp , де T1 та Tp часи розв’язування СНР відповідно на одному та p ядрах (рис. 1); та коефіцієнт ефективності Ep S p p (рис. 2) для СНР (10) порядку n = 5 000 показані на вказаних рисунках. Рис. 1. Коефіцієнт прискорення Результати, наведені на рис. 1, свідчать, що розроблений паралельний алгоритм забезпечує нормальну масштабованість, тобто час виконання задачі пропорційно зменшується з ростом кількості обчислювальних пристроїв. Найбільше прискорення досягається при використанні 64 процесів.
На наступному рисунку представлено значення коефіцієнту ефективності у відсотках, отриманого при розв’язуванні наведеної СНР п’ятитисячного порядку, з використанням паралельного алгоритму метода Ньютона. Рис. 2. Коефіцієнт ефективності Наведені результати демонструють, що найбільша ефективність розв’язування системи п’ятитисячного порядку досягається при використанні 16 процесів.
Експериментальне дослідження алгоритму методу Рунге – Кутта 4-го порядку. Методом Рунге – Кутта 4-го порядку розв’язувалась задача Коші для системи звичайних диференціальних рівнянь: j0 n1 dui u j ui n1 t 2 t dt з початковими умовами ui 0 1 i 0,1,2,,n 1, на інтервалі [0,0; 0,4].
Наведемо деякі з отриманих результатів. В табл. 2 представлені часи розв’язування наведеної СЗДР в залежності від її порядку. Рис. 4. Коефіцієнт ефективності Отримані результати демонструють, що найбільша ефективність при розв’язуванні зазначеної СЗДР досягається при використанні 16 процесів. Отриманий коефіцієнт ефективності, який перевищує 100 %, свідчить, що паралельний алгоритм створено при правильному врахуванні особливостей архітектури комп’ютера. Висновки
Розроблені алгоритми розв’язування СНР та СЗДР великої розмірності призводять до значного скорочення часу їх розв’язання на комп’ютерах з процесорами Intel Xeon Phi. Отримані результати досягнуті за рахунок врахування архітектури процесора, яка дає можливість мати декілька рівнів паралелізму. Зауважимо, що розроблені програми призначено для однопроцесорного комп’ютера з процесорами Intel Xeon Phi, можна використовувати для багатопроцесорних комп’ютерів за умови розпаралелювання засобами MPI. Яковлев М.Ф., Герасимова Т.О., Нестеренко А.Н. Особливості розв’язування систем нелінійних та диференціальних рівнянь на паралельних комп’ютерах. Питання оптимізації обчислень (ПОО – XXXV). Праці міжнародного симпозіуму. Київ: Інститут кібернетики імені В.М. Глушкова НАН України, 2009. Т. 2. С. 435–439. Яковлев М.Ф., Нестеренко А.Н., Бруснікін В.М. Проблеми ефективного розв’язування систем нелінійних рівнянь на багатопроцесорних комп’ютерах MIMD-архітектури. Науково-теоретичний журнал "Математичні машини і системи" Київ. 2014. № 4. С. 12–17. Химич А.Н., Молчанов И.Н., Попов А.В, Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной математики. К.: Наукова думка, 2008. 248 с. Нестеренко А.Н., Химич А.Н., Яковлев М.Ф. Некоторые вопросы решения систем нелинейных уравнений на многопроцессорных вычислительных системах с распределенной памятью. Вестник компьютерных и информационных технологий. М.: 2006. № 10. С. 54–56. Химич А.Н., Яковлев М.Ф., Герасимова Т.А. Некоторые вопросы решения систем обыкновенных дифференциальных уравнений на MIMD-компьютерах. Кибернетика и системный анализ. 2007. № 2. С. 175–182.
Yakovlev, M.F. & Gerasymova, T.O. & Nesterenko, A.N. (2009) Characteristic features of the solving both of non-linear systems and systems of ordinary differential equations on parallel computers. In Proceedings of international symposium “Optimization problems of computations” (OPC – XXXV). Kyiv: V.M. Glushkov Institute of cybernetics of NAS of Ukraine, 2009. Kyiv: Vol. 2. P. 435–439.
Yakovlev, MV.F. & Nesterenko, A.N. & Brusnikin, V.N. (2014) Problems of the efficient solving of non-linear systems on multi-processor MIMD-architecture computers. Mathematical machines and systems. (4). P. 12–17.
Khimich, A.N. et al. (2008) Parallel algorithms for the solving of computational mathematics problems. Kiev: Naukova Dumka. Nesterenko, A.N. & Khimich, A.N. & Yakovlev, M.F. (2006) To the problem of solving of non-linear systems on multi-processor distributed memory computing system. Gerald of computer and information technologies. 10. P. 54–56.
Khimich, A.N. & Yakovlev, M.F. & Gerasymova T.O. (2007) Some questions related to the solving of systems of ordinary differential equations on MIMD computers. Cybernetics and system analysis. (2). P. 175–182.