Automated generation of parallel programs for graphics processing units based on algorithm schemes
The algebra-algorithmic approach to automated designing and generation of programs for graphics processor units is proposed. The particular feature of our approach consists in using high-level specifications, represented in algebra of algorithms, and applying a method, ensuring the syntactical regul...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , , , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/125 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-125 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/13/e164609de63952ac7a57af5b8754ac13.pdf |
| spelling |
pp_isofts_kiev_ua-article-1252018-07-25T14:13:57Z Automated generation of parallel programs for graphics processing units based on algorithm schemes Автоматизированная генерация параллельных программ для графических ускорителей на основе схем алгоритмов Автоматизована генерація паралельних програм для графічних прискорювачів на основі схем алгоритмів Doroshenko, А.Yu. Beketov, O.G. Ivaniv, R.B. Iovchev, V.O. Mironenko, I.O. Yatsenko, O.A. generation of parallel program UDC 681.3 генерация параллельных программ УДК: 681.3 паралельні програми УДК: 681.3 The algebra-algorithmic approach to automated designing and generation of programs for graphics processor units is proposed. The particular feature of our approach consists in using high-level specifications, represented in algebra of algorithms, and applying a method, ensuring the syntactical regularity of algorithms and programs being designed. The approach was implemented in the online toolkit for interactive design of algorithm schemes and generation of programs in target programming languages. The usage of the toolkit is illustrated on development of parallel program for convection-diffusion problem. Предложен алгеброалгоритмический подход к автоматизированному проектированию и генерации программ для графических ускорителей. Особенностью подхода является использование высокоуровневых спецификаций, представленных в алгебре алгоритмов, а также применение метода, обеспечивающего синтаксическую правильность проектируемых алгоритмов и программ. Подход реализован в онлайновом инструментарии, предназначенном для диалогового конструирования схем алгоритмов и генерации программ в целевых языках программирования. Применение инструментария проиллюстрировано на примере разработки параллельной программы для задачи конвективной диффузии. Запропоновано алгеброалгоритмічний підхід до автоматизованого проектування та генерації програм для графічних прискорювачів. Особливість підходу полягає у використанні високорівневих специфікацій, поданих в алгебрі алгоритмів, а також застосуванні методу, який забезпечує синтаксичну правильність алгоритмів та програм, що проектуються. Підхід реалізовано в онлайновому інструментарії, призначеному для діалогового конструювання схем алгоритмів та генерації програм у цільових мовах програмування. Застосування інструментарію проілюстровано на прикладі розробки паралельної програми для задачі конвективної дифузії. Інститут програмних систем НАН України 2017-06-13 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/125 PROBLEMS IN PROGRAMMING; No 1 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2015) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/125/118 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-25T14:13:57Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
generation of parallel program UDC 681.3 |
| spellingShingle |
generation of parallel program UDC 681.3 Doroshenko, А.Yu. Beketov, O.G. Ivaniv, R.B. Iovchev, V.O. Mironenko, I.O. Yatsenko, O.A. Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| topic_facet |
generation of parallel program UDC 681.3 генерация параллельных программ УДК: 681.3 паралельні програми УДК: 681.3 |
| format |
Article |
| author |
Doroshenko, А.Yu. Beketov, O.G. Ivaniv, R.B. Iovchev, V.O. Mironenko, I.O. Yatsenko, O.A. |
| author_facet |
Doroshenko, А.Yu. Beketov, O.G. Ivaniv, R.B. Iovchev, V.O. Mironenko, I.O. Yatsenko, O.A. |
| author_sort |
Doroshenko, А.Yu. |
| title |
Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_short |
Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_full |
Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_fullStr |
Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_full_unstemmed |
Automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_sort |
automated generation of parallel programs for graphics processing units based on algorithm schemes |
| title_alt |
Автоматизированная генерация параллельных программ для графических ускорителей на основе схем алгоритмов Автоматизована генерація паралельних програм для графічних прискорювачів на основі схем алгоритмів |
| description |
The algebra-algorithmic approach to automated designing and generation of programs for graphics processor units is proposed. The particular feature of our approach consists in using high-level specifications, represented in algebra of algorithms, and applying a method, ensuring the syntactical regularity of algorithms and programs being designed. The approach was implemented in the online toolkit for interactive design of algorithm schemes and generation of programs in target programming languages. The usage of the toolkit is illustrated on development of parallel program for convection-diffusion problem. |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2017 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/125 |
| work_keys_str_mv |
AT doroshenkoayu automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT beketovog automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT ivanivrb automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT iovchevvo automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT mironenkoio automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT yatsenkooa automatedgenerationofparallelprogramsforgraphicsprocessingunitsbasedonalgorithmschemes AT doroshenkoayu avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT beketovog avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT ivanivrb avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT iovchevvo avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT mironenkoio avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT yatsenkooa avtomatizirovannaâgeneraciâparallelʹnyhprogrammdlâgrafičeskihuskoritelejnaosnoveshemalgoritmov AT doroshenkoayu avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív AT beketovog avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív AT ivanivrb avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív AT iovchevvo avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív AT mironenkoio avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív AT yatsenkooa avtomatizovanageneracíâparalelʹnihprogramdlâgrafíčnihpriskorûvačívnaosnovíshemalgoritmív |
| first_indexed |
2025-07-17T09:58:58Z |
| last_indexed |
2025-07-17T09:58:58Z |
| _version_ |
1838410144026722304 |
| fulltext |
Інструментальні засоби та середовища програмування
© А.Ю. Дорошенко, О.Г. Бекетов, Р.Б. Іванів, В.О. Іовчев, І.О. Мироненко, О.А. Яценко, 2015
ISSN 1727-4907. Проблеми програмування. 2015. № 1 19
УДК 681.3
А.Ю. Дорошенко, О.Г. Бекетов, Р.Б. Іванів, В.О. Іовчев, І.О. Мироненко, О.А. Яценко
АВТОМАТИЗОВАНА ГЕНЕРАЦІЯ ПАРАЛЕЛЬНИХ
ПРОГРАМ ДЛЯ ГРАФІЧНИХ ПРИСКОРЮВАЧІВ
НА ОСНОВІ СХЕМ АЛГОРИТМІВ
Запропоновано алгеброалгоритмічний підхід до автоматизованого проектування та генерації програм
для графічних прискорювачів. Особливість підходу полягає у використанні високорівневих специфіка-
цій, поданих в алгебрі алгоритмів, а також застосуванні методу, який забезпечує синтаксичну правиль-
ність алгоритмів та програм, що проектуються. Підхід реалізовано в онлайновому інструментарії, при-
значеному для діалогового конструювання схем алгоритмів та генерації програм у цільових мовах про-
грамування. Застосування інструментарію проілюстровано на прикладі розробки паралельної програми
для задачі конвективної дифузії.
Вступ
Подальше поширення багатопото-
кового паралелізму в сучасних обчислю-
вальних системах привело до потреби
створення спеціального інструментарію
для розробки паралельного програмного
забезпечення, який охоплює усі етапи
життєвого циклу програми. У відділі тео-
рії комп’ютерних обчислень Інституту
програмних систем НАН України упро-
довж тривалого періоду розвивається тео-
рія, методологія та інструментарій для ав-
томатизованого проектування паралель-
них програм, що ґрунтуються на засобах
високорівневої алгеброалгоритмічної фо-
рмалізації і автоматизації перетворень
програм [1–5]. Зокрема, розроблено Інтег-
рований інструментарій Проектування та
Синтезу програм (ІПС) [2, 3] та його нову
версію – Онлайновий Діалоговий конст-
руктор Синтаксично Правильних програм
(ОДСП). Автоматизована система ОДСП
[4, 5] є онлайновим сервісом, що викорис-
товує технологію Web 2.0, і призначений
для проектування та генерації програм на
основі високорівневих специфікацій алго-
ритмів. Специфікації алгоритмів (схеми)
ґрунтуються на використанні алгебри ал-
горитмів Глушкова [1]. Система забезпе-
чує побудову послідовних та паралельних
алгоритмів у режимі порівневого конст-
руювання, та генерацію відповідних про-
грам в цільових мовах програмування
Java, C++. У попередніх роботах інстру-
ментарій ОДСП застосований для розроб-
ки паралельних програм для багатоядер-
них центральних процесорів (central pro-
cessing units, CPUs). Мета даної роботи
полягає в налаштуванні системи ОДСП на
розробку паралельних програм для графі-
чних прискорювачів (graphics processing
units, GPUs), які дозволяють отримати
значне підвищення продуктивності обчи-
слень порівняно з CPU. Розглядається
проблема автоматизованого проектування
та генерації паралельних програм для
NVIDIA CUDA [6], яка є однією з обчис-
лювальних платформ та програмних мо-
делей для GPU.
Існуючі підходи до генерації коду
для GPU архітектур ґрунтуються, зокрема,
на анотаціях для опису властивостей стру-
ктур даних та областей коду [7], мережах
процесів Кана [8], директивах компілято-
ра [9], графах потоку даних [10], високорі-
вневих абстракціях структур даних, задач
та комунікаційних операторів [11].
Відмінністю підходу, запропонова-
ного у даній роботі, є використання алгеб-
раїчних специфікацій, поданих у природ-
но-лінгвістичній формі, яка полегшує ро-
зуміння алгоритмів та досягнення необхід-
ної якості програм. Інша перевага розроб-
лених засобів полягає у застосуванні мето-
ду діалогового конструювання синтаксич-
но правильних програм, який виключає
можливість виникнення синтаксичних по-
милок у процесі проектування схем.
Матеріал даної роботи організова-
ний таким чином. У розділі 1 розглянуто
операції алгебри алгоритмів, що викорис-
Інструментальні засоби та середовища програмування
20
товуються для проектування паралельних
програм для графічних прискорювачів. У
розділі 2 розглянуто архітектуру та основ-
ні функції системи ОДСП. У розділі 3 про-
ілюстровано застосування розроблених ал-
гебро-алгоритмічних засобів на прикладі
проектування паралельної програми для
розв’язання задачі конвективної дифу-
зії [12, 13]. Роботу завершують висновки
та напрямки подальшої роботи.
1. Алгебра алгоритмів та
формалізоване проектування
паралельних програм для
графічних прискорювачів
В основу пропонованого підходу до
проектування паралельних програм покла-
дений апарат систем алгоритмічних ал-
гебр (САА) Глушкова [1], що призначені
для формалізованого проектування послі-
довних і паралельних алгоритмів та про-
грам. САА є двоосновною алгеброю
};,{ BU , де U – множина операто-
рів, B – множина логічних умов; – сиг-
натура, що складається з предикатних
(кон’юнкція, диз’юнкція, заперечення) та
операторних (композиція, альтернатива,
цикл) операцій. Подання алгоритмів у
САА (алгебраїчні формули) називаються
регулярними схемами. Окрім алгебраїчної
форми, алгоритми можуть бути подані в
природно-лінгвістичній (САА-схеми) та
графовій (граф-схеми) формах.
В розробленій авторами системі
ОДСП [4, 5], яка розглядається у розділі 2
даної статті, застосовується природно-
лінгвістична форма проектування, що ґру-
нтується на мові САА/1 [1]. Основними
об’єктами згаданої мови є абстракції опе-
раторів і умов, що можуть бути елемента-
рними (базисними) або складеними. Скла-
дені оператори й умови будуються з еле-
ментарних за допомогою операцій послі-
довного і паралельного виконання опера-
торів. В ОДСП алгоритми проектуються
англійською мовою.
Назви та текст основних САА опе-
рацій є такими:
композиція (послідовне виконан-
ня) операторів:
operator1; operator2
альтернатива (оператор розгалу-
ження):
If (predicate) Then
operator1
Else
operator2
End If
оператор циклу:
While loop (predicate)
operator
End of loop
З метою орієнтації САА на проек-
тування програм для графічних прискорю-
вачів NVIDIA, що підтримують техноло-
гію CUDA, в сигнатуру включені дода-
ткові конструкції. Відмітимо, що апаратно
графічні прискорювачі NVIDIA склада-
ються з деякої кількості CUDA-ядер, кож-
не з яких здатне одночасно виконувати пе-
вну кількість потоків (threads). Ядром
(kernel) називається підпрограма (функція)
для GPU, що виконується потоками. Мо-
дель програмування в CUDA передбачає
групування потоків у блоки. Кожен блок є
масивом потоків, які взаємодіють між со-
бою за допомогою спільної пам’яті і точок
синхронізації. Блоки, у свою чергу, об’єд-
нуються в сітку блоків.
Додаткові конструкції САА для
проектування програм для GPU є такими:
визначення функції-ядра:
KERNEL fname(param_list) =
function_body;
де fname – назва функції; param_
list – список формальних параметрів;
function_body – реалізація функції,
представлена в САА;
операція виклику функції-ядра:
fname(Nb, Nth, arg_list),
де fname – назва функції; Nb – кількість
блоків у сітці; Nth – кількість потоків у
кожному блоці; arg_list – список фак-
тичних параметрів функції;
оператори, що отримують зна-
чення глобального (унікального) індексу
потоку та індекс потоку в межах блоку
Інструментальні засоби та середовища програмування
21
(локальний індекс), і присвоюють отрима-
не значення цілочисельній змінній i:
Get global index of
the thread (i);
Get local index of
the thread (i);
синхронізатор – операція, що
здійснює очікування завершення обчис-
лень усіма потоками:
Synchronizer (all threads
completed work);
операції виділення та звільнення
відеопам’яті для певної змінної:
Allocate the memory for
variable on GPU (var_name,
count);
Free the memory for varia-
ble on GPU (var_name);
де var_name – назва змінної; count – ро-
змір пам'яті, яку необхідно виділити, в
байтах;
операції копіювання даних із
пам’яті CPU у відеопам’ять і у зворотному
напрямку:
Copy data from CPU to GPU
(dest, src, count);
Copy data from GPU to CPU
(dest, src, count);
де dest – назва змінної, яка є призначен-
ням копіювання; src – назва змінної, зна-
чення якої необхідно скопіювати; count –
розмір даних, що копіюються, в байтах.
Приклад. Проілюструємо викорис-
тання деяких з вищенаведених операцій
для побудови алгоритму для GPU, призна-
ченого для паралельного множення елеме-
нтів одновимірного масиву на певне число.
САА-схема даного алгоритму є такою.
SCHEME Multiplication of array
elements by a value, for GPU;
KERNEL Multiply array elements
by value (A, N, val) =
Get global index of
the thread (i);
Assign value
(A[i], A[i] * val);
Main function =
Declare array (h_A, int, N);
Declare array (d_A, int);
Initialize array with
random values (h_A, N);
Print array (h_A, N);
Allocate the memory for
variable on GPU (d_A,
A_size);
Copy data from CPU to GPU
(d_A, h_A, A_size);
Multiply array elements
by value (Nb, Nth, d_A, N,20);
Copy data from GPU to CPU
(h_A, d_A, A_size);
Free the memory for
variable on GPU (d_A);
Print array (h_A, N);
Схема складається з реалізації фун-
кції-ядра та основної функції схеми. Фун-
кція-ядро, яка має назву " Multiply ar-
ray elements by value (A, N,
val)", виконує множення елемента A[i]
одновимірного цілочисельного масиву A
на число val; тут N – довжина масиву,
i – індекс потоку. В реалізації основної
функції (Main) виконується оголошення
масиву h_A, що підлягає обробці і зберіга-
ється у пам'яті CPU, а також ініціалізація
цього масиву довільними значеннями. На-
ведено також оголошення та виділення
пам'яті для відповідного масиву d_A у па-
м'яті GPU. Далі виконується копіювання
значень масиву h_A в масив d_A. Після
цього здійснюється виклик вищезгаданої
функції-ядра, в результаті якого викону-
ється паралельне множення елементів ма-
сиву d_A на значення val = 20. Значення
параметрів Nb та Nth (кількість блоків у
сітці та кількість потоків у кожному блоці)
обираються таким чином, що Nb * Nth = N.
Далі копіюються дані із масиву d_A в ма-
сив h_A. Після цього виконується звіль-
Інструментальні засоби та середовища програмування
22
нення зарезервованої відеопам'яті та виве-
дення значень результуючого масиву h_A
на екран.
Застосування операцій САА для
проектування паралельного алгоритму для
розв’язання задачі конвективної дифузії
буде розглянуте у розділі 3.
2. Онлайновий діалоговий
конструктор синтаксично
правильних програм
Розроблена автоматизована система
ОДСП призначена для діалогового проек-
тування та генерації програм [4, 5]. Систе-
ма ґрунтується на використанні систем ал-
горитмічних алгебр (див. розділ 1) та ме-
тоду діалогового конструювання синтак-
сично правильних програм (ДСП-
методу) [1]. На відміну від традиційних
синтаксичних аналізаторів, ДСП-метод
орієнтовано не на пошук та виправлення
синтаксичних помилок, а на виключення
можливості їх появи у процесі побудови
алгоритмів. Основна ідея методу полягає у
порівневому конструюванні схем зверху
вниз шляхом суперпозиції мовних конс-
трукцій САА. На кожному кроці констру-
ювання система в діалозі з користувачем
надає на вибір лише ті конструкції, підста-
новка яких у текст, що формується, не по-
рушує синтаксичну правильність схеми.
Особливість системи ОДСП (порів-
няно з раніше розробленим авторами ін-
струментарієм ІПС [2, 3]) полягає в орієн-
тації на багатокористувальницьке викори-
стання інструментарію через Інтернет і ро-
зподілену архітектуру системи. Відмітимо,
що компоненти інструментарію є автоно-
мними, гнучко зв’язаними і мають узго-
джений протокол обміну даними. Таким
чином, дана система, по суті, є сервісно-
орієнтованою.
Інструментарій ОДСП складається з
компонентів, показаних на рис. 1.
Клієнт є Web-інтерфейсом для діа-
логової взаємодії користувача з інструмен-
тарієм та його ресурсами. Він надає мож-
ливість виконувати конструювання схеми
алгоритму із використанням елементів ба-
зи даних, здійснювати генерацію коду ці-
льовою мовою програмування (Java або
C++) та виконувати запуск програми в об-
числювальному середовищі. В основу про-
ектування алгоритмів у системі покладено
діалоговий режим з використанням списку
конструкцій та дерева алгоритму (див.
рис. 2). Специфікації конструкцій ґрунту-
ються на англомовній версії мови САА/1
(див. розділ 1). Побудова схем здійснюєть-
ся зверху вниз за допомогою деталізації
конструкцій. У процесі проектування схе-
ми користувач за чергою обирає необхідні
Рис. 1. Архітектура системи ОДСП
Генератор
програм
Диспетчер
Схема алгоритму
Клієнт
Шлюз
Середовище
виконання
База
даних
Інструментальні засоби та середовища програмування
23
конструкції зі списку і додає їх у дерево,
використовуючи технологію “drag-and-
drop”.
Диспетчер є ядром інструментарію,
яке організовує зв’язок між клієнтом, ге-
нератором програм, шлюзом і базою да-
них.
Генератор програм виконує гене-
рацію тексту програми на основі схеми ал-
горитму, побудованої за допомогою кліє-
нтського інтерфейсу.
Шлюз – сервіс, що забезпечує за-
пуск, аналіз та отримання результатів ви-
конання програм у середовищі виконання.
Середовище виконання є програм-
ною платформою, встановленою на сторо-
ні сервера системи ОДСП. Середовище
включає операційну систему та програмне
забезпечення, необхідне для компіляції та
запуску програм.
У базі даних зберігається інформа-
ція про:
мовні конструкції САА, що ви-
користовуються для проектування алгори-
тмів;
типи мовних конструкцій;
розроблені проекти алгоритмів
(solutions);
використовувані цільові мови
програмування;
типи каркасів проектів (frames);
задачі, виконувані у фоновому
режимі;
типи налаштування запуску про-
ектів.
У базі даних опис кожної мовної
конструкції САА включає її подання в
природно-лінгвістичній формі; інформа-
цію про тип конструкції; реалізацію (шаб-
лон) обраною мовою програмування; на-
зви змінних та список формальних параме-
трів.
Каркас проекту (frame) – фрагмент
тексту мовою програмування, що викорис-
товується як основа (“обгортка”) для підс-
тановки коду, згенерованого системою на
основі схеми алгоритму. Як правило, кар-
кас включає у себе команди підключення
необхідних бібліотек.
Система може виконувати запуск
зкомпільованих програм відразу, або ви-
конувати їх у фоновому режимі. У другому
випадку задача виконується на сервері за
допомогою планувальника операційної си-
стеми.
У попередніх роботах система в ос-
новному використовувалася для розробки
паралельних програм сортування для ви-
конання на CPU. В даній роботі базу даних
ОДСП доповнено операціями, орієнтова-
Рис. 2. Фрагмент копії екрану системи ОДСП
з деревом алгоритму та списком конструкцій
Інструментальні засоби та середовища програмування
24
ними на GPU-обчислення, які розглянуті у
розділі 1. Приклад застосування системи
для розробки паралельної програми для
виконання на GPU розглядається у насту-
пному розділі.
3. Приклад використання
системи ОДСП
У даному розділі проілюстроване
використання САА та системи ОДСП на
прикладі розробки CUDA програми для
розв’язання двовимірної задачі конвектив-
ної дифузії, що виникає при математично-
му моделюванні циркуляції атмосфери в
метеорології.
Згадана тестова задача детально ро-
зглянута в роботах [12, 13], і полягає у
розв’язанні сукупності рівнянь конвектив-
ної дифузії та знаходженні значень залеж-
ної функції ),,( yxtuu , де ]10;0[t – час;
),( yx – координати; ]1,0[]1,0[ –
двовимірна просторова область визначен-
ня задачі. В якості функції u може висту-
пати, наприклад, швидкість вітру.
Розв’язання задачі ґрунтується на
застосуванні скінченно-різницевого чисе-
льного методу, наведеного в [13]. У проце-
сі розв’язання область розбивається на
xS та yS рівномірних кроків (вузлів) по
осям x та y відповідно. Таким чином, за-
гальна кількість вузлів становить yx SS .
Розпаралелювання обчислень для
даної задачі полягає у розбитті області ро-
змірністю yx SS на підмножини та пара-
лельному розв’язанні сукупності підзадач,
що визначені на цих підмножинах [12].
На рис. 3 показано загальну САА-
схему розробленого паралельного GPU-
алгоритму для задачі конвективної дифузії.
Схема побудована в системі ОДСП у від-
повідності з методом діалогового конст-
руювання, що описаний у розділі 2. Алго-
ритм ґрунтується на використанні конс-
трукцій САА, розглянутих у розділі 1.
Алгоритм містить такі основні
змінні: SX та SY – кількість кроків розбит-
тя просторової області по осям x та y від-
повідно; Nb – кількість блоків у сітці
CUDA; Nth – кількість потоків у кожному
блоці; Time = 0 – початкове значення
часу; T = 10 – кінцеве значення часу;
dT = 0.001 – часовий крок; t – час; m –
кількість обчислювальних кроків; h_pX,
d_pX, h_pY, d_pY – масиви аргументів;
Ux та Uy – масиви для зберігання значень
функції u .
Схема алгоритму подана у вигляді
дерева. Коренева вершина схеми містить
текст "Main function" і відповідає за-
головку функції main у програмі мо-
вою C. Тіло основної функції складається
із сукупності операторів, які подано як до-
чірні вершини вузла "Body". Реалізація
основної функції починається з оператора,
який зчитує значення двох параметрів ко-
мандного рядка, і присвоює відповідні
значення змінним SX та SY. Далі викону-
ється ініціалізація даних і починається від-
лік часу. Після цього оператори з аргумен-
тами Nb та Nth здійснюють виклики фун-
кцій-ядер (наприклад, "Input of
initial data (Nb, Nth)"). Функції-
ядра виконують введення початкових да-
них, заповнення масивів коефіцієнтів рів-
нянь та масиву для функції u . Синхроніза-
тор, що наведений після викликів згаданих
функцій, виконує затримку обчислень по-
ки всі потоки не завершать роботу. Відмі-
тимо, що алгоритм містить цикл While, в
тілі якого знаходяться виклики додаткових
функцій-ядер, які здійснюють заповнення
масивів коефіцієнтів, граничних умов, об-
числення значень Ux, Uy та середнього
значення. Алгоритми функцій-ядер пода-
ються в окремих схемах.
Загальним результатом виконання
алгоритму є сукупність обчислених зна-
чень функції u для координат x та y , де
),( yx . В кінці програми виконується
порівняння отриманих значень функції u з
реальними та обчислюється похибка. Далі
значення координат та функції u запису-
ються у файли.
Із використанням ОДСП, на основі
розглянутих схем автоматично згенерова-
но текст програми мовою CUDA C.
На рис. 4 як приклад показано ко-
роткий фрагмент згенерованої CUDA про-
грами, який відповідає кільком операторам
у середині узагальненої схеми алгоритму,
показаної на рис. 3.
Інструментальні засоби та середовища програмування
25
Рис. 3. Загальна схема GPU-алгоритму для задачі конвективної дифузії,
побудована в системі ОДСП
Інструментальні засоби та середовища програмування
26
Наведений фрагмент програми по-
чинається з виклику функції-ядра
d_Init, що виконує введення початко-
вих даних, і закінчується викликом функ-
ції, яка копіює значення змінної d_Px у
змінну h_Px з пам’яті GPU в пам’ять
CPU. Перед викликом кожної функції
вказано коментарій з текстом відповідної
операції САА. У порівнянні зі схемою ал-
горитму, програмний код містить додат-
кові змінні, що не були включені в алго-
ритм з метою його спрощення. Відобра-
ження кожної операції САА в текст мо-
вою програмування зазначається в базі
даних ОДСП у вигляді параметризованих
шаблонів.
Проведено експеримент із вико-
нання розробленої CUDA програми та
відповідної послідовної програми на
одному з вузлів розділу СКІТ-4 кластеру
Інституту кібернетики НАНУ [14]. Згада-
ний вузол містить графічний прискорю-
вач NVIDIA Tesla M2075 (448 обчислю-
вальних ядер) та центральний процесор
Intel Xeon E5-2670. Чисельні експеримен-
ти виконано для значень розміру задачі
від 6464 yx SS до yx SS
.20482048 Отримані значення муль-
типроцесорного прискорення ps TT / , де
sT та pT – час виконання послідовної та
паралельної програми відповідно. На
рис. 5 показано діаграму залежності муль-
типроцесорного прискорення від розміру
задачі yx SS . Максимальне значення
прискорення при 20482048 yx SS
становило 69 разів.
Рис. 4. Фрагмент згенерованої CUDA програми для задачі конвективної дифузії
.....
// Input of initial data (Nb, Nth)
d_Init <<<Nb, Nth>>> (d_pX, d_pY, hx, hy, SX, SY);
// Fill the arrays of equation coefficients
// (Nb, Nth, Time + m * dT)
d_Definition <<<Nb, Nth>>> (d_pX, d_pY, Time+m*dT, d_pV1,
d_pW1, d_pV2, d_pW2, d_pF, SX, SY, SIZE);
// Fill the array for function U with initial values
// (Nb, Nth)
d_RealU <<<Nb, Nth>>> (d_pX, d_pY, Time, d_pV1, d_pW1,
d_pV2, d_pW2, d_pU, SIZE);
// Synchronizer (all threads completed work)
CUDAEvent();
// Copy data from GPU to CPU (h_pX, d_pX, d_pX_size)
cudaMemcpy(h_pX, d_pX, d_pX_size, cudaMemcpyDeviceToHost);
.....
Інструментальні засоби та середовища програмування
27
Висновки
Розроблено алгеброалгоритмічний
підхід до автоматизованого проектування
та генерації програм для графічних прис-
корювачів. Перевагою підходу є викорис-
тання мовних конструкцій, близьких до
природної мови, а також застосування ме-
тоду, який забезпечує синтаксичну прави-
льність алгоритмів та програм, що проек-
туються. Підхід реалізовано в онлайново-
му інструментарії, в основу якого покла-
дене діалогове порівневе конструювання
алгоритмів та генерація програм на основі
компонент повторного використання, у
якості яких виступають конструкції алге-
бри алгоритмів.
Застосування інструментарію проі-
люстровано на прикладі розробки парале-
льної програми для задачі конвективної
дифузії. Проведено експеримент із вико-
нання розробленої програми на графічно-
му прискорювачі, який показав гарну сту-
пінь розпаралелюваності обчислень.
Перспективи виконаної роботи по-
лягають у подальшому розвитку алгебро-
алгоритмічних засобів для опису додатко-
вих можливостей платформи CUDA. Та-
кож планується налаштування інструмен-
тарію на розробку програм, що викорис-
товують інші технології обчислень на
GPU, наприклад, OpenCL.
1. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е.,
Яценко Е.А. Алгеброалгоритмические мо-
дели и методы параллельного программи-
рования. – Киев: Академпериодика, 2007. –
631 с.
2. Дорошенко А.Е., Жереб К.А., Яценко Е.А.
Формализованное проектирование эффек-
тивных многопоточных программ // Про-
блеми програмування. – 2007. – № 1. –
С. 17–30.
3. Яценко Е.А. Интеграция инструменталь-
ных средств алгебры алгоритмов и перепи-
сывания термов для разработки эффектив-
ных параллельных программ // Проблеми
програмування. – 2013. – № 2. – С. 62–70.
4. Иовчев В.А., Мохница А.С. Инструмен-
тальные средства алгебры алгоритмики на
платформе Web 2.0 // Проблеми програ-
мування. – 2010. – № 2–3. – С. 547–555.
5. Дорошенко А.Е., Цейтлин Г.Е., Иовчев В.А.
Высокоуровневые средства автоматизации
проектирования параллельных алгорит-
Рис. 5. Залежність мультипроцесорного прискорення ps TT / від розміру задачі yx SS
для паралельної програми конвективної дифузії
Інструментальні засоби та середовища програмування
28
мов // Проблеми програмування. – 2009. –
№ 3. – С. 19–29.
6. Wilt N. The CUDA handbook. A Comprehen-
sive Guide to GPU Programming. – Boston:
Addison-Wesley, 2013. – 528 p.
7. Ueng S. et al. CUDA-lite: Reducing GPU
Programming Complexity // Proc. 21st Int.
Workshop on Languages and Compilers for
Parallel Computing (LCPC’2008). – 2008. –
P. 1–15.
8. Haid W. et al. Efficient Execution of Kahn
Process Networks on Multi-Processor Sys-
tems Using Protothreads and Windowed
FIFOs // Proc. Workshop on Embedded Sys-
tems for Real-Time Multimedia (ES-
TImedia’09). – 2009. – P. 35–44.
9. Han T.D., Abdelrahman T.S. hiCUDA: A
High-level Language for GPU programming //
IEEE Transactions on Parallel and Distributed
systems. – 2011. – Vol. 22, N 1. – P. 78–90.
10. Jung H., Yi Y., Ha S. Automatic CUDA Code
Synthesis Framework for Multicore CPU and
GPU architectures // Lecture Notes in Com-
puter Science. – 2012. – Vol. 7203. –
P. 579–588.
11. Dubach C., Cheng P., Rabbah R., Ba-
con D.F., Fink S.J. Compiling a High-Level
Language for GPUs (via Language Support
for Architectures and Compilers) // Proc. 33rd
ACM SIGPLAN conference on Programming
Language Design and Implementation
(PLDI’12). – 2012. – P. 1–12.
12. Прусов В.А., Дорошенко А.Ю., Кацало-
ва Л.М., Бекетов О.Г. Паралельні обчис-
лення двовимірної задачі конвективної ди-
фузії на відеокарті // Комп’ютерне моде-
лювання в хімії, технологіях і системах
сталого розвитку – КМХТ-2014: збірник
наукових статей IV Міжнар. наук.-практ.
конф. – К.: НТУУ "КПІ", 2014. – С. 42–47.
13. Прусов В.А., Дорошенко А.Е., Черныш Р.И.
Метод численного решения многомерной
задачи конвективной диффузии // Кибер-
нетика и системный анализ. – 2009. –
№ 1. – С. 100 –107.
14. Суперкомп’ютер Інституту кібернетики
НАН України [Електронний ресурс]. – Ре-
жим доступу: http://icybcluster.org.ua. –
01.10.2014 р.
Одержано 07.10.2014
Про авторів:
Дорошенко Анатолій Юхимович,
доктор фізико-математичних наук,
професор, завідувач відділу теорії
комп’ютерних обчислень Інституту
програмних систем НАН України,
Бекетов Олексій Генадійович,
аспірант Інституту програмних систем
НАН України,
Іванів Руслан Богданович,
магістрант Національного технічного
університету України "КПІ",
Іовчев Володимир Олександрович,
молодший науковий співробітник
Інституту програмних систем
НАН України,
Мироненко Ігор Олексійович,
магістрант Національного технічного
університету України "КПІ",
Яценко Олена Анатоліївна,
кандидат фізико-математичних наук,
старший науковий співробітник
Інституту програмних систем
НАН України.
Місце роботи авторів:
Інститут програмних систем
НАН України,
03187, Київ-187,
проспект Академіка Глушкова, 40.
Тел.: (044) 526 35 59.
E-mail: dor@isofts.kiev.ua,
beketov.oleksii@gmail.com,
iovchev.v@gmail.com,
oayat@ukr.net.
Національний технічний університет
України "КПІ",
03056, Київ-056,
проспект Перемоги, 37.
E-mail: ivanivruslan@gmail.com,
mioe@ukr.net.
http://icybcluster.org.ua/
mailto:dor@isofts.kiev.ua
mailto:oayat@ukr.net
|