Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком
Розроблено і досліджено гібридний алгоритм методу Рунге-Кутта 4-го порядку розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь (СЗДР). Розглянуто питання програмної реалізації алгоритму на комп’ютерах з графічними процесорами. Наведені результати апробації алгорит...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2015
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/113562 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком / М.Ф. Яковлев, Т.О. Герасимова, В.М. Бруснікін // Математичні машини і системи. — 2015. — № 2. — С. 20-27. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-113562 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1135622017-02-11T03:02:54Z Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком Яковлев, М.Ф. Герасимова, Т.О. Бруснікін, В.М. Обчислювальні системи Розроблено і досліджено гібридний алгоритм методу Рунге-Кутта 4-го порядку розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь (СЗДР). Розглянуто питання програмної реалізації алгоритму на комп’ютерах з графічними процесорами. Наведені результати апробації алгоритму на багатоядерному комп’ютері з графічними прискорювачами Інпарком, коефіцієнти прискорення та ефективності використання запропонованого алгоритму. Разработан и исследован гибридный алгоритм метода Рунге-Кутта 4-го порядка для решения задач с начальными условиями для систем обыкновенных дифференциальных уравнений (СОДУ). Рассмотрены вопросы программной реализации алгоритма на компьютерах с графическими процессорами. Приведены результаты апробации алгоритма на многоядерном компьютере с графическими ускорителями Инпарком, коэффициенты ускорения и эффективности использования предложенного алгоритма. A hybrid algorithm of the Runge-Kutta 4-th order method intended for the solving of initial-value problems in systems of ordinary differential equations (SODE) has been developed and investigated. The paper deals with problems related to program implementation of algorithm on multi-core computers with graphic accelerators. The results gained during program implementation and testing of algorithm on multi-core computer with graphic accelerators Inparcom are presented; acceleration and efficiency coefficients for the proposed algorithm are determined as well. 2015 Article Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком / М.Ф. Яковлев, Т.О. Герасимова, В.М. Бруснікін // Математичні машини і системи. — 2015. — № 2. — С. 20-27. — Бібліогр.: 5 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/113562 519.6 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Обчислювальні системи Обчислювальні системи |
| spellingShingle |
Обчислювальні системи Обчислювальні системи Яковлев, М.Ф. Герасимова, Т.О. Бруснікін, В.М. Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком Математичні машини і системи |
| description |
Розроблено і досліджено гібридний алгоритм методу Рунге-Кутта 4-го порядку розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь (СЗДР). Розглянуто питання програмної реалізації алгоритму на комп’ютерах з графічними процесорами. Наведені результати апробації алгоритму на багатоядерному комп’ютері з графічними прискорювачами Інпарком, коефіцієнти прискорення та ефективності використання запропонованого алгоритму. |
| format |
Article |
| author |
Яковлев, М.Ф. Герасимова, Т.О. Бруснікін, В.М. |
| author_facet |
Яковлев, М.Ф. Герасимова, Т.О. Бруснікін, В.М. |
| author_sort |
Яковлев, М.Ф. |
| title |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком |
| title_short |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком |
| title_full |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком |
| title_fullStr |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком |
| title_full_unstemmed |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком |
| title_sort |
розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами інпарком |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2015 |
| topic_facet |
Обчислювальні системи |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/113562 |
| citation_txt |
Розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь на багатоядерному комп’ютері з графічними прискорювачами Інпарком / М.Ф. Яковлев, Т.О. Герасимова, В.М. Бруснікін // Математичні машини і системи. — 2015. — № 2. — С. 20-27. — Бібліогр.: 5 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT âkovlevmf rozvâzuvannâzadačzpočatkovimiumovamidlâsistemzvičajnihdiferencíalʹnihrívnânʹnabagatoâdernomukompûterízgrafíčnimipriskorûvačamiínparkom AT gerasimovato rozvâzuvannâzadačzpočatkovimiumovamidlâsistemzvičajnihdiferencíalʹnihrívnânʹnabagatoâdernomukompûterízgrafíčnimipriskorûvačamiínparkom AT brusníkínvm rozvâzuvannâzadačzpočatkovimiumovamidlâsistemzvičajnihdiferencíalʹnihrívnânʹnabagatoâdernomukompûterízgrafíčnimipriskorûvačamiínparkom |
| first_indexed |
2025-07-08T05:59:35Z |
| last_indexed |
2025-07-08T05:59:35Z |
| _version_ |
1837057312267698176 |
| fulltext |
20 © Яковлев М.Ф., Герасимова Т.О., Бруснікін В.М., 2015
ISSN 1028-9763. Математичні машини і системи, 2015, № 2
УДК 519.6
М.Ф. ЯКОВЛЕВ*, Т.О. ГЕРАСИМОВА*, В.М. БРУСНІКІН**
РОЗВ’ЯЗУВАННЯ ЗАДАЧ З ПОЧАТКОВИМИ УМОВАМИ ДЛЯ СИСТЕМ
ЗВИЧАЙНИХ ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ НА БАГАТОЯДЕРНОМУ
КОМП’ЮТЕРІ З ГРАФІЧНИМИ ПРИСКОРЮВАЧАМИ ІНПАРКОМ
*
Інститут кібернетики імені В.М. Глушкова НАН України, Київ, Україна
**
Інститут проблем математичних машин і систем НАН України, Київ, Україна
Анотація. Розроблено і досліджено гібридний алгоритм методу Рунге-Кутта 4-го порядку
розв’язування задач з початковими умовами для систем звичайних диференціальних рівнянь
(СЗДР). Розглянуто питання програмної реалізації алгоритму на комп’ютерах з графічними про-
цесорами. Наведені результати апробації алгоритму на багатоядерному комп’ютері з графічними
прискорювачами Інпарком, коефіцієнти прискорення та ефективності використання запропоно-
ваного алгоритму.
Ключові слова: паралельні обчислення, CUDA, гібридний алгоритм, СЗДР, метод Рунге-Кутта 4-
го порядку, ефективність розпаралелювання.
Аннотация. Разработан и исследован гибридный алгоритм метода Рунге-Кутта 4-го порядка для
решения задач с начальными условиями для систем обыкновенных дифференциальных уравнений
(СОДУ). Рассмотрены вопросы программной реализации алгоритма на компьютерах с графиче-
скими процессорами. Приведены результаты апробации алгоритма на многоядерном компьютере
с графическими ускорителями Инпарком, коэффициенты ускорения и эффективности использо-
вания предложенного алгоритма.
Ключевые слова: параллельные вычисления, CUDA, гибридный алгоритм, СОДУ, метод Рунге-
Кутта 4-го порядка, эффективность распараллеливания.
Abstract. A hybrid algorithm of the Runge-Kutta 4-th order method intended for the solving of initial-
value problems in systems of ordinary differential equations (SODE) has been developed and investigated.
The paper deals with problems related to program implementation of algorithm on multi-core computers
with graphic accelerators. The results gained during program implementation and testing of algorithm on
multi-core computer with graphic accelerators Inparcom are presented; acceleration and efficiency coef-
ficients for the proposed algorithm are determined as well.
Keywords: parallel computing, CUDA, hybrid algorithm, SODE, Runge-Kutta 4-th order method, paral-
lelization efficiency.
1. Вступ
При моделюванні на комп’ютері будь-яких реальних процесів і явищ за допомогою систем
звичайних диференціальних рівнянь часто виникає необхідність розв’язувати задачі з по-
чатковими умовами (задачі Коші). СЗДР можуть існувати як самостійний клас задач або
можуть виникати на проміжних стадіях розв’язування більш складних математичних за-
дач. Такі задачі виникають, наприклад, при описуванні за допомогою СЗДР рухів, процесів
або явищ, що змінюються в часі. Це стосується, зокрема, процесів хімічної кінетики, про-
цесів, що відбуваються в ядерних реакторах, а також динамічних задач аналізу міцності
конструкцій при застосуванні методу скінченних елементів по просторових змінних та ін.
При розв’язуванні деяких задач, наприклад, пов’язаних із рухом керованих об’єктів, вини-
кає необхідність розв’язувати СЗДР швидше, ніж відбувається процес у реальному часі;
більш того, їх розв’язування потребує багатоваріантних розрахунків та значних обчислю-
вальних ресурсів. Дуже часто виникає необхідність розв’язувати задачі з початковими
умовами у випадку, коли вихідні дані (тобто формули для обчислення правих частин СЗДР
та початкові умови) задані наближено. Такі задачі можна ефективно розв’язувати на висо-
ISSN 1028-9763. Математичні машини і системи, 2015, № 2 21
копродуктивних комп’ютерах з паралельною організацією обчислень, зокрема, на
комп’ютерах MIMD- архітектури [1].
Вимоги до високопродуктивної обчислювальної техніки випереджають можливості
традиційних паралельних комп’ютерів. У даний час такі комп’ютери можуть налічувати
сотні і навіть тисячі процесорів (ядер). Але збільшення числа процесорів у паралельних
комп’ютерах часто призводить до значного збільшення комунікаційних втрат і зниження
їх ефективності. Одним із основних напрямів підвищення продуктивності комп’ютерів є
використання графічних процесорів (GPU). Цей напрям є особливо ефективним у випадку,
коли необхідно виконувати великі обсяги однорідних арифметичних операцій. Викорис-
тання графічних процесорів дало можливість розробити комп’ютери гібридної архітекту-
ри, яка об'єднує багатоядерні процесори MIMD- архітектури та графічні прискорювачі
SIMD-архітектури.
У статті розглядається питання організації обчислень при розв’язуванні задач з по-
чатковими умовами для СЗДР високого порядку на комп’ютерах гібридної архітектури на
прикладі застосування гібридного алгоритму методу Рунге-Кутта 4-го порядку, який вико-
ристовує обчислювальні можливості CPU та GPU.
2. Постановка задачі
Нехай дано систему n звичайних диференціальних рівнянь. Задачу з початковими умова-
ми для СЗДР n -го порядку на інтервалі ],[ 0 Tt розглядатимемо у вигляді
),,( ytf
dt
dy = (1)
,)( )0(
0 yty = (2)
де ( )Tnyyyy ,,, 21 …= − шуканий вектор, а права частина системи – n -вимірна неперервна
вектор-функція ( ) ( ) ( ) ( )( )Tn ytfytfytfytf ,,,,,,, 21 …= .
При моделюванні реальних процесів на комп'ютері за допомогою СЗДР виникає ряд
труднощів, зокрема, потреба мати справу з задачами з наближеними вихідними даними.
Наближений характер вихідних даних може бути обумовлений такими причинами:
− похибками в вихідних даних;
− похибками у значеннях правої частини;
− застосуванням чисельного (дискретного) методу інтегрування і округленням чи-
сел при обчисленнях;
− дискретизацією динамічних задач по просторових змінних.
Тому на практиці, як правило, замість задачі (1), (2) маємо задачу з наближеними
вихідними даними:
),,( vtf
dt
dv = (3)
,00 )( vtv = (4)
де δ≤− 00 vy , ( ) ( ) ( ) ( ) ∆≤∆∆+=ϕ wtwtwtfwt ,,,,, для довільних значень )(tw .
Такі задачі розв’язуються на комп'ютерах за допомогою чисельних методів.
22 ISSN 1028-9763. Математичні машини і системи, 2015, № 2
3. Паралельний алгоритм методу Рунге-Кутта 4-го порядку для комп’ютерів гібрид-
ної архітектури
Зупинимося на питанні організації обчислень при розв’язуванні задач з початковими умо-
вами для СЗДР високого порядку на комп’ютерах гібридної архітектури (CPU+GPU) мето-
дом Рунге-Кутта 4-го порядку.
3.1. Декомпозиція даних
Для розв’язування СЗДР чисельними методами необхідно задавати таку вихідну інформа-
цію: порядок системи звичайних диференціальних рівнянь; початкову та кінцеву точки ін-
тервалу інтегрування; визначальну точність отриманого розв’язку; похибку завдання поча-
ткових умов; похибку завдання вектор-функції; повний вектор розв’язку (оскільки в зага-
льному випадку всі компоненти вектор-функції правих частин системи залежать від усього
вектора розв’язку), на початку інтегрування цей вектор містить початкові значення
розв’язку; функцію обчислення значень вектор-функції.
Реалізація методів розв’язування задач даного класу на комп'ютерах гібридної архі-
тектури вимагає автоматичного розподілу вихідних даних та компонент векторів правих
частин у локальній пам'яті ядер кожного процесора. Кожний процес одночасно і незалежно
реалізує власну програму обчислень з використанням функцій CUBLAS на GPU [2]. Кому-
нікаційні операції та синхронізація роботи процесів здійснюються засобами MPI [3].
Щоб розв’язати СЗДР n -го порядку на MIMD-комп'ютері, її заздалегідь необхідно
розбити на p блоків ( p − кількість ядер). В паралельних алгоритмах розв’язування СЗДР
на комп’ютерах гібридної архітектури використовується одновимірний блочний розподіл
даних та обчислень. Блоки вибираються приблизно одного розміру в залежності від поряд-
ку СЗДР n та кількості процесів (CPU) p , що використовуються для розв’язування задачі.
Тоді розмір блока обчислюється за формулою
/ 1 /
,
/ /
=
q
n p + , q < n - p n p
s
n p , q³n - p n p
де 0,1, ..., 1= −q p – логічний номер CPU, значення a дорівнює цілій частині числа a . За
цією схемою розподіляються компоненти векторів y та ),( ytf . Такий розподіл дозволяє
виконувати автоматичний розподіл обчислень компонент вектор-функції СЗДР на p проце-
сів.
3.2. Розпаралелювання обчислень вектор-функції правих частин СЗДР
При розв’язуванні задач з початковими умовами на MIMD-комп'ютерах СЗДР необхідно
задавати спеціальним чином, щоб забезпечити максимально можливе розпаралелювання
операцій на кожному кроці інтегрування, зокрема, при обчисленні вектор-функції правих
частин, та, якщо необхідно, наближення до матриці Якобі. При автоматичному розпарале-
люванні обчислень на GPU слід враховувати, що лише в рідкісних випадках правила обчи-
слення значень компонент вектор-функції СЗДР істотно відрізняються одна від одної. В
цих випадках системи рівнянь, як правило не мають великого порядку і тому розв’язувати
їх на комп'ютерах гібридної архітектури недоцільно. В більшості ж випадків побудова век-
тор-функції правих частин підпорядковується деякому спеціальному правилу і такі систе-
ми можуть мати достатньо великий порядок.
Як правило, при розв’язуванні задач з початковими умовами для СЗДР значна части-
на арифметичних операцій припадає на обчислення вектор-функції правих частин системи.
Тому у більшості чисельних методів в першу чергу розпаралелюється обчислення компо-
ISSN 1028-9763. Математичні машини і системи, 2015, № 2 23
нент вектор-функції правих частин системи рівнянь на вибраній кількості CPU багатопро-
цесорного комп’ютера з графічними прискорювачами [4]. Останні ( ) nqps −+= 1 проце-
сорів оброблятимуть блоки по q рівнянь, а перші sp − процесорів – блоки по ( )1+q -му
рівнянню; тут p − кількість процесорів, 1...,,1,0 −= pq – логічний номер CPU.
Опишемо один із можливих способів завдання вектор-функції правих частин на мо-
ві програмування Сі. В кожному процесорі праві частини системи обчислюються за про-
грамою
diffun (n, l, m, t, y, f)
{. . . . .
for ( i = l ; i < m; i++ )
{ …f =...; }
}
У кожному процесорі обчислюється вектор-функція від l -ої до ( )1−m -ої компонен-
ти. При цьому kql = , ( ) 11 −+= qkm , де k − логічний номер процесора, 1...,,1,0 −= pk .
Величини l і m для кожного процесора повинні бути обчислені перед зверненням до про-
грами обчислення вектор-функції правих частин. Цей шаблон використовується для всіх
випадків завдання правих частин. Тут введені такі позначення: n – порядок системи зви-
чайних диференціальних рівнянь, t – точка інтегрування, y – значення вектор-функції в
точці t . Такий спосіб завдання вектор-функції має переваги:
• по-перше, полегшення при програмуванні СЗДР великого порядку, оскільки такі
системи, як правило, мають регулярну структуру і тому фактично необхідно написати за-
головок циклу і рівняння, залежне від параметра циклу;
• по-друге, при прихованому паралелізмі обчислення вектор-функції правих частин
автоматично розподіляється між вибраною кількістю процесорів.
Якщо ж система звичайних диференціальних рівнянь має нерегулярну структуру, то
кожне рівняння доведеться позначати власною міткою типу «case k:» (k: – ціле число) і за-
безпечувати звернення до функції за описаним вище правилом, використовуючи у програ-
мі оператор типу «switch (i)».
Слід зазначити, що кількість арифметичних операцій, необхідних для обчислення
компонент вектор-функції правих частин СЗДР, істотно впливає на ефективність і приско-
рення обчислень при розпаралелюванні на комп'ютері з графічними прискорювачами. Слід
також зазначити, що задача може бути ефективно розв’язана, коли порядок системи n є
достатньо великим числом, а також достатньо великим числом є і кількість операцій, не-
обхідна для обчислення компонент вектор-функції ( )uf .
3.3. Гібридний алгоритм методу Рунге-Кутта 4-го порядку
Одним із методів, що застосовується для чисельного інтегрування задач з початковими
умовами для СЗДР, є метод Рунге-Кутта 4-го порядку. Цей метод є найбільш розповсю-
дженим методом чисельного розв’язування задач з початковими умовами для СЗДР.
Класичний метод Рунге-Кутта 4-го порядку реалізується за формулами:
,6/)22( 4321
)()1( kkkkyy ii ++++=+ (5)
де
),,( )(
1
i
ii ytfhk =
),5,0,2/( 1
)(
2 kyhtfhk i
iii ++=
),5,0,2/( 2
)(
3 kyhtfhk i
iii ++=
24 ISSN 1028-9763. Математичні машини і системи, 2015, № 2
,...)2,1,0(),5,0,( 3
)(
4 =++= ikyhtfhk i
iii .
На кожному кроці інтегрування цей метод потребує чотириразового обчислення ве-
ктор-функції ( )ytf , . Але для оцінки головного члена похибки, який визначає вибір кроку
інтегрування, доводиться тричі застосовувати метод Рунге-Кутта.
Наведемо обчислювальну схему паралельного алгоритму методу Рунге-Кутта 4-го
порядку для знаходження розв’язку систем звичайних диференціальних рівнянь на ком-
п'ютерах гібридної архітектури (CPU+GPU) [5]:
1. У пам'ять кожного з p CPU посилається вихідна інформація.
Для подальшого викладу позначимо через m кількість компонент вектор-функції,
що будуть обчислюватись одним CPU.
2. На інтервалі від початкового значення незалежної змінної до координати точки
виводу при кожному значенні ∑
−
=
+=
1
0
0
i
j
ji htt (i= 1, 2,...) проводяться обчислення з викорис-
танням CPU та графічних процесорів у такому порядку:
a) у CPU обчислюється прогнозована довжина кроку інтегрування ih і посилається
в GPU;
b) далі виконується інтегрування системи, кожний i -ий крок якого обчислюється за
схемою:
– у GPU обчислюються m компонент вектора 1k , обчислені компоненти вектора 1k
посилаються в CPU;
– у кожному CPU обчислюються m компонент вектора 1
)( 5,0 ky i + , проводиться му-
льтизбирання цього вектора та пересилка його в GPU;
– у GPU обчислюються m компонент вектора 2k , обчислені компоненти вектора 2k
посилаються в CPU,
у кожному CPU обчислюються m компонент вектора 2
)( 5,0 ky i + , проводиться му-
льтизбирання цього вектора та пересилка його в GPU;
– у GPU обчислюються m компонент вектора 3k , обчислені компоненти вектора 3k
посилаються в CPU;
– у CPU обчислюються m компонент вектора 3
)( ky i + , проводиться мультизбиран-
ня цього вектора та пересилка його в GPU;
у GPU обчислюються m компонент вектора 4k , а потім m компонент вектора
6)()1( ν+=+ ii yy де 4321 22 kkkk +++=ν ; обчислені компоненти вектора )1( +iy посила-
ються в CPU;
– кожен CPU проводить мультизбирання всього вектора )1( +iy та посилає його в
GPU.
Цим завершується i -ий крок інтегрування системи;
c) за схемою, описаною в п. «b», двократним інтегруванням з довжиною кроку 2ih
обчислюється вектор ( )1+iy та однократним інтегруванням з довжиною кроку ih обчислю-
ється вектор ( )1+iy ; ці вектори посилаються в GPU;
d) у GPU обчислюється похибка апроксимації системи ( ) ( ) ( )11
1
1 max ++
≤≤
+ −=ψ i
j
i
j
nj
i yy ; ця
похибка апроксимації посилається в CPU;
e) при виконанні умов досягнення заданої точності в CPU обчислюється уточнена
довжина кроку інтегрування;
ISSN 1028-9763. Математичні машини і системи, 2015, № 2 25
f) в CPU перевіряється умова pii tht >+ ; якщо умова виконується, то як довжина
кроку інтегрування вибирається ipi tth −= де pt − координата точки виводу розв’язку, в
іншому випадку довжина кроку інтегрування не коригується, вибрана довжина кроку по-
силається для продовження обчислень у GPU;
g) для отримання розв’язку )1( +iy в точці iii htt +=+1 повторюються пункти а) – e) з
обчисленою довжиною кроку інтегрування.
Процес розв’язування задачі продовжується, доки не буде досягнуто кінцевої точки
інтервалу інтегрування T. Після обчислення розв’язку в точці виводу запам'ятовуються ве-
ктор розв’язку, константа Ліпшиця та оцінка похибки розв’язку.
4. Програмна реалізація та чисельний експеримент. Експериментальне дослідження
ефективності гібридного алгоритму
Розрахунки проводились на вузлі кластера Iнпарком-G з такими характеристиками:
– процесори: 2 Xeon 5606 (4 ядра з частотою 2,13 ГГц);
– графічні прискорювачі: 2 Tesla M2090 (6 Гб пам’яті);
– об’єм оперативної пам’яті: 24 Гб;
– комунікаційне середовище: InfiniBand 40 Гбіт/с (з підтримкою GPUDirect), Gigabit
Ethernet.
Також на вузлах встановлена бібліотека MKL10.2.6 та CUDA, починаючи з версії
3.2.
Розв’язувалась така тестова задача.
На інтервалі [0,0; 0,4] розв’язати СЗДР n -го порядку:
( ) ttnuu
dt
du
i
n
j
j
i ++++−−= ∑
−
=
21
1
0
з початковими умовами ( ) 10 =iu 1,,2,1,0 −= ni … .
В обчислювальному вузлі використовується чотириядерний процесор, на одне ядро
приходиться одна карточка GPU. На кожному вузлі як обчислювальні процесори викорис-
товуються дві ігрові відеокарти.
Зупинимося на програмній реалізації алгоритму при роботі з GPU. Основними бло-
ками операцій, що виконуються з GPU, є виділення пам’яті для змінних, копіювання даних
на GPU, запуск обчислень, копіювання результатів в оперативну пам’ять, звільнення
пам’яті GPU. Зауважимо, що кожний процес одночасно і незалежно реалізує власну про-
граму обчислень з використанням функцій CUBLAS на GPU для матрично-векторних опе-
рацій [2]. Комунікаційні операції та синхронізація роботи процесів здійснюються засобами
MPI [3].
Для даної тестової задачі вектор-функція правої частини може бути легко обчисле-
на на графічних прискорювачах, оскільки система має регулярну структуру і порядок цієї
системи n є достатньо великим числом. Якщо ж права частина дуже складна, то в описа-
ному алгоритмі треба ігнорувати обчислення вектор-функції в GPU і залишити її обчис-
лення в CPU.
Нижче наведено таблицю, що містить часи розв’язування цієї тестової задачі при
n=20000 на експериментальному зразку паралельного комп’ютера гібридної архітектури
Інпарком. Результати експериментів наведені для гібридної архітектури 1 CPU, 1 GPU. У
таблиці порівнюються часи розв’язування задачі при обчисленні компонент вектор-
функції правої частини на СPU (перший рядок у таблиці) та на GPU (другий рядок у табл.
1). Зауважимо, що час розв’язування задачі на CPU становить 220 секунд.
26 ISSN 1028-9763. Математичні машини і системи, 2015, № 2
0
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
кількість процесів
к
о
е
ф
іц
іє
н
т
п
р
и
с
к
о
р
е
н
н
я
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
кількість процесів
к
о
е
ф
іц
іє
н
т
е
ф
е
к
т
и
в
н
о
с
т
і
Таблиця 1. Час розв’язування тестової задачі на CPU і GPU
np=2 np=4 np=8 np=16
1 114,96 69,48 42,46 22,44
2 11,73 6,84 3,9 2,04
Нижче наведено графіки, з яких видно залежність коефіцієнта прискорення та кое-
фіцієнта ефективності від кількості процесорів.
З графіка видно, що коефіцієнт прискорення практично лінійно збільшується зі збі-
льшенням кількості процесів, що використовуються.
На наступному графіку зображено коефіцієнт ефективності використання кількості
процесів.
5. Висновки
Дослідження паралельних алгоритмів розв’язування систем звичайних диференціальних
рівнянь показали, що багатоядерні комп’ютери з графічними процесорами дають можли-
вість суттєво прискорити час розв’язування задач, особливо у випадку, коли праві частини
СЗДР обчислюються на GPU. У випадку, коли права частина дуже складна і має нерегуля-
рну структуру, то обчислення вектор-функції доведеться залишити в CPU, що суттєво по-
гіршить час розв’язування задачі.
Запропоновано алгоритм, який забезпечує високу ефективність розпаралелювання
на GPU, оптимізує використання пам’яті CPU. Показано ефективність гібридного алгорит-
му методу Рунге-Кутта 4-го порядку розв’язування задач з початковими умовами для сис-
тем звичайних диференціальних рівнянь (СЗДР). У подальшому науковий інтерес предста-
вляють алгоритми для архітектури з n CPU, m GPU зі спільною або розподіленою
пам’яттю.
ISSN 1028-9763. Математичні машини і системи, 2015, № 2 27
СПИСОК ЛІТЕРАТУРИ
1. Молчанов И.Н. Интеллектуальные параллельные компьютеры на графических процессорах для
решения научно-технических задач / И.Н. Молчанов // Праці Міжнародної молодіжної математич-
ної школи «Питання оптимізації обчислень (ПОО – XXXVII)». – К.: Інститут кібернетики ім. В.М.
Глушкова НАН України, 2011. – С. 121 – 122.
2. http://developer.download.nvidia.com/compute/cuda/1_0/CUBLAS_Library.
3. http://www.mpi.org.
4. Яковлев М.Ф. Особливості розв’язування систем нелінійних та диференціальних рівнянь на па-
ралельних комп’ютерах / М.Ф. Яковлев, Т.О. Герасимова, А.Н. Нестеренко // Праці Міжнародного
симпозіуму «Питання оптимізації обчислень (ПОО – XXXV)». – Київ: Інститут кібернетики ім.
В.М. Глушкова НАН України, 2009. – Т. 2. – С. 435 – 439.
5. Параллельные алгоритмы решения задач вычислительной математики / Химич А.Н., Молчанов
И.Н., Попов А.В., Чистякова Т.В. [и др.]. − Киев: Наукова думка, 2008. − 248 с.
Стаття надійшла до редакції 28.01.2015
|