Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу
Further progress in improving the quality of parallel software development is linked to the use of heterogeneous architectures of parallel computing systems. Heterogeneous parallel systems, in particular, include hybrid computing platforms combining the use of central and graphics processing units....
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/346 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозиторії
Problems in programming| id |
pp_isofts_kiev_ua-article-346 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/fb/e915ab6a8e465424fa9851ebf7d543fb.pdf |
| spelling |
pp_isofts_kiev_ua-article-3462024-04-28T11:00:17Z Automated design of OpenCL programs based on algebra-algorithmic approach Автоматизированное проектирование OpenCL программ на основе алгебро-алгоритмического подхода Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу Doroshenko, А.Yu. Bondarenko, M.M. Yatsenko, O.A. automated software design; algorithm algebra; CUDA; heterogeneous parallel computing systems; meteorological forecasting; OpenCL; software synthesis UDC 004.4'24 автоматизированное проектирование программ; алгебра алгоритмов; метеорологическое прогнозирование; неоднородные параллельные вычислительные системы; синтез программ; CUDA; OpenCL УДК 004.4'24 автоматизоване проектування програм; алгебра алгоритмів; метеорологічне прогнозування; неоднорідні паралельні обчислювальні системи; синтез програм; CUDA; OpenCL УДК 004.4'24 Further progress in improving the quality of parallel software development is linked to the use of heterogeneous architectures of parallel computing systems. Heterogeneous parallel systems, in particular, include hybrid computing platforms combining the use of central and graphics processing units. One of the facilities for programming such systems is OpenCL. The paper proposes the further development of previously developed algebra-algorithmic tools in the direction of automated design and synthesis of OpenCL programs. The particular feature of the proposed approach consists in using a high-level language based on Glushkov’s system of algorithmic algebra. The approach is illustrated on the development of a parallel interpolation algorithm, which is the part of the numerical weather forecasting program. The results of the experiment consisting in executing of the generated OpenCL program on a graphics processing unit are given. The program is compared with the implementation for CUDA platform. Problems in programming 2019; 1: 27-36 Дальнейший прогресс в улучшении показателей качества создания параллельных программ связан с использованием гетерогенных архитектур вычислительных систем. Неоднородные параллельные системы включают у себя, в частности, гибридные вычислительные платформы, сочетающие использование центральных процессоров и графических ускорителей. Одним из инструментальных средств программирования таких систем является OpenCL. В статье выполнена настройка ранее созданного алгебро-алгоритмического инструментария проектирования и синтеза на автоматизированную разработку OpenCL программ. Особенностью предложенного подхода к проектированию является использование высокоуровневого языка, основывающегося на системах алгоритмических алгебр Глушкова. Подход продемонстрирован на разработке программы интерполяции для задачи метеорологического прогнозирования. Проведен эксперимент по выполнению сгенерированной с помощью разработанного инструментария параллельной программы на графическом ускорителе. Выполнено сравнение с реализацией программы на платформе CUDA. Problems in programming 2019; 1: 27-36 Подальший прогрес у покращенні показників якості створення паралельних програм пов'язаний з використанням гетерогенних архітектур обчислювальних систем. Неоднорідні паралельні системи включають у себе, зокрема, гібридні обчислювальні платформи, що поєднують використання центральних процесорів і графічних прискорювачів. Одним з інструментальних засобів програмування таких систем є OpenCL. У статті виконане налаштування раніше створеного алгебро-алгоритмічного інструментарію проектування і синтезу на автоматизовану разробку OpenCL-програм. Особливістю запропонованого підходу до проектування є використання мови, що ґрунтується на системах алгоритмічних алгебр Глушкова. Підхід продемонстровано на проектуванні програми інтерполяції для задачі метеорологічного прогнозування. Проведено експеримент з виконання згенерованої за допомогою розробленого інструментарію паралельної програми на графічному прискорювачі. Виконане порівняння з реалізацією програми на CUDA.Problems in programming 2019; 1: 27-36 Інститут програмних систем НАН України 2019-03-26 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/346 10.15407/pp2019.01.027 PROBLEMS IN PROGRAMMING; No 1 (2019); 27-36 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2019); 27-36 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2019); 27-36 1727-4907 10.15407/pp2019.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/346/343 Copyright (c) 2019 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:00:17Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
automated software design algorithm algebra CUDA heterogeneous parallel computing systems meteorological forecasting OpenCL software synthesis UDC 004.4'24 автоматизированное проектирование программ алгебра алгоритмов метеорологическое прогнозирование неоднородные параллельные вычислительные системы синтез программ CUDA OpenCL УДК 004.4'24 автоматизоване проектування програм алгебра алгоритмів метеорологічне прогнозування неоднорідні паралельні обчислювальні системи синтез програм CUDA OpenCL УДК 004.4'24 |
| spellingShingle |
automated software design algorithm algebra CUDA heterogeneous parallel computing systems meteorological forecasting OpenCL software synthesis UDC 004.4'24 автоматизированное проектирование программ алгебра алгоритмов метеорологическое прогнозирование неоднородные параллельные вычислительные системы синтез программ CUDA OpenCL УДК 004.4'24 автоматизоване проектування програм алгебра алгоритмів метеорологічне прогнозування неоднорідні паралельні обчислювальні системи синтез програм CUDA OpenCL УДК 004.4'24 Doroshenko, А.Yu. Bondarenko, M.M. Yatsenko, O.A. Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| topic_facet |
automated software design algorithm algebra CUDA heterogeneous parallel computing systems meteorological forecasting OpenCL software synthesis UDC 004.4'24 автоматизированное проектирование программ алгебра алгоритмов метеорологическое прогнозирование неоднородные параллельные вычислительные системы синтез программ CUDA OpenCL УДК 004.4'24 автоматизоване проектування програм алгебра алгоритмів метеорологічне прогнозування неоднорідні паралельні обчислювальні системи синтез програм CUDA OpenCL УДК 004.4'24 |
| format |
Article |
| author |
Doroshenko, А.Yu. Bondarenko, M.M. Yatsenko, O.A. |
| author_facet |
Doroshenko, А.Yu. Bondarenko, M.M. Yatsenko, O.A. |
| author_sort |
Doroshenko, А.Yu. |
| title |
Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| title_short |
Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| title_full |
Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| title_fullStr |
Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| title_full_unstemmed |
Автоматизоване проектування OpenCL програм на основі алгебро-алгоритмічного підходу |
| title_sort |
автоматизоване проектування opencl програм на основі алгебро-алгоритмічного підходу |
| title_alt |
Automated design of OpenCL programs based on algebra-algorithmic approach Автоматизированное проектирование OpenCL программ на основе алгебро-алгоритмического подхода |
| description |
Further progress in improving the quality of parallel software development is linked to the use of heterogeneous architectures of parallel computing systems. Heterogeneous parallel systems, in particular, include hybrid computing platforms combining the use of central and graphics processing units. One of the facilities for programming such systems is OpenCL. The paper proposes the further development of previously developed algebra-algorithmic tools in the direction of automated design and synthesis of OpenCL programs. The particular feature of the proposed approach consists in using a high-level language based on Glushkov’s system of algorithmic algebra. The approach is illustrated on the development of a parallel interpolation algorithm, which is the part of the numerical weather forecasting program. The results of the experiment consisting in executing of the generated OpenCL program on a graphics processing unit are given. The program is compared with the implementation for CUDA platform. Problems in programming 2019; 1: 27-36 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2019 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/346 |
| work_keys_str_mv |
AT doroshenkoayu automateddesignofopenclprogramsbasedonalgebraalgorithmicapproach AT bondarenkomm automateddesignofopenclprogramsbasedonalgebraalgorithmicapproach AT yatsenkooa automateddesignofopenclprogramsbasedonalgebraalgorithmicapproach AT doroshenkoayu avtomatizirovannoeproektirovanieopenclprogrammnaosnovealgebroalgoritmičeskogopodhoda AT bondarenkomm avtomatizirovannoeproektirovanieopenclprogrammnaosnovealgebroalgoritmičeskogopodhoda AT yatsenkooa avtomatizirovannoeproektirovanieopenclprogrammnaosnovealgebroalgoritmičeskogopodhoda AT doroshenkoayu avtomatizovaneproektuvannâopenclprogramnaosnovíalgebroalgoritmíčnogopídhodu AT bondarenkomm avtomatizovaneproektuvannâopenclprogramnaosnovíalgebroalgoritmíčnogopídhodu AT yatsenkooa avtomatizovaneproektuvannâopenclprogramnaosnovíalgebroalgoritmíčnogopídhodu |
| first_indexed |
2024-09-16T04:08:34Z |
| last_indexed |
2024-09-16T04:08:34Z |
| _version_ |
1812407982135181312 |
| fulltext |
Інструментальні засоби та середовища програмування
© А.Ю. Дорошенко, М.М. Бондаренко, О.Я. Яценко, 2019
ISSN 1727-4907. Проблеми програмування. 2019. № 1 27
УДК 004.4'24 https://doi.org/10.15407/pp2019.01.027
А.Ю. Дорошенко, М.М. Бондаренко, О.А. Яценко
АВТОМАТИЗОВАНЕ ПРОЕКТУВАННЯ OPENCL ПРОГРАМ
НА ОСНОВІ АЛГЕБРО-АЛГОРИТМІЧНОГО ПІДХОДУ
Подальший прогрес у покращенні показників якості створення паралельних програм пов'язаний з вико-
ристанням гетерогенних архітектур обчислювальних систем. Неоднорідні паралельні системи включа-
ють у себе, зокрема, гібридні обчислювальні платформи, що поєднують використання центральних
процесорів і графічних прискорювачів. Одним з інструментальних засобів програмування таких систем
є OpenCL. У статті виконане налаштування раніше створеного алгебро-алгоритмічного інструментарію
проектування і синтезу на автоматизовану разробку OpenCL-програм. Особливістю запропонованого
підходу до проектування є використання мови, що ґрунтується на системах алгоритмічних алгебр Глу-
шкова. Підхід продемонстровано на проектуванні програми інтерполяції для задачі метеорологічного
прогнозування. Проведено експеримент з виконання згенерованої за допомогою розробленого інстру-
ментарію паралельної програми на графічному прискорювачі. Виконане порівняння з реалізацією про-
грами на CUDA.
Ключові слова: автоматизоване проектування програм, алгебра алгоритмів, метеорологічне прогнозу-
вання, неоднорідні паралельні обчислювальні системи, синтез програм, CUDA, OpenCL.
Вступ
Паралельні та розподілені обчис-
лення на мультипроцесорних платформах
на даний час є основним джерелом забез-
печення необхідних потреб у високій про-
дуктивності обчислень при розв’язанні
складних науково-технічних і господарсь-
ких проблем. Подальший прогрес у пок-
ращенні показників якості створення пара-
лельних програм пов’язаний із викорис-
танням неоднорідних архітектур обчислю-
вальних систем. Неоднорідні паралельні
системи включають у себе, зокрема, гібри-
дні обчислювальні платформи, що поєд-
нують використання центральних проце-
сорів (Central Processing Units, CPUs) та
графічних прискорювачів (Graphics
Processing Units, GPUs). Одним з інстру-
ментальних засобів програмування таких
систем є OpenCL (Open Computing
Language) [1] – фреймворк для створення
програмних застосувань, що виконуються
у гетерогенному середовищі. На відміну
від Nvidia CUDA [2], яка є реалізацією
GPGPU (обчислення загального призна-
чення на графічних процесорах) лише для
відеокарт Nvidia, OpenCL є специфікацією,
яку можуть реалізовувати різні виробники
апаратного забезпечення. Існують реаліза-
ції OpenCL для відеокарт Nvidia, AMD,
Intel, ARM, а також програмованих корис-
тувачем вентильних матриць (FPGA). Та-
кож на відміну від платформи Nvidia
CUDA, програми для якої потрібно компі-
лювати за допомогою спеціального компі-
лятора, програми OpenCL можна збирати
будь-яким компілятором, треба лише вка-
зати бінарний файл бібліотеки при збірці.
Зазначимо, що програмування гібридних
систем – це досить складна задача порів-
няно з розробкою застосувань для однорі-
дних архітектур, тому актуальним є пи-
тання розробки спеціальних засобів авто-
матизації розробки програмного забезпе-
чення, що дозволяли б найбільш ефектив-
но генерувати найпродуктивніший код для
таких систем.
В роботах [3, 4] запропоновані тео-
рія, методологія та інструментарій для ав-
томатизованого проектування, синтезу та
перетворення послідовних та паралельних
програм, що ґрунтуються на засобах ал-
гебр алгоритмів та переписувальних пра-
вил. В роботах [5–7] розроблені засоби за-
стосовані для генерації паралельних про-
грам для платформи Nvidia CUDA на ос-
нові схем алгоритмів. У даній роботі вико-
нане налаштування алгебро-алгоритміч-
ного інструментарію на формалізоване
проектування та синтез програм, що вико-
ристовують OpenCL. Застосування інстру-
ментарію продемонстроване на розробці
паралельної програми інтерполяції, що
http://dx.doi.org/10.7124/bc.000027
Інструментальні засоби та середовища програмування
28
входить до складу програми чисельного
прогнозування погоди [6, 7]. Проведено
експеримент з виконання згенерованої па-
ралельної OpenCL програми на графічно-
му прискорювачі.
Запропонований у даній статті під-
хід є близьким до робіт, присвячених гене-
рації OpenCL програм [8–11]. Зокрема,
в роботі [8] розглядається підхід та про-
грамний засіб Gaspard2 для специфікації,
проектування та генерації вищезгаданих
програм на основі використання уніфіко-
ваної мови моделювання UML. В роботі
[9] запропоновані програмний засіб
STEPOCL та предметно-орієнтована мова
для спрощення розробки програм, що ви-
користовують декілька прискорювачів од-
ночасно. В [10] розглядається автоматич-
ний генератор функцій-ядер OpenCL для
задач лінійної алгебри на основі високорі-
вневих специфікацій, поданих користува-
чем у предметно-орієнтованій мові, що
ґрунтується на C++. В ргоботі [11] запро-
понований підхід до генерації OpenCL на
основі високорівневих функціональних
специфікацій та використання переписува-
льних правил.
Відмінність підходу, викладеного у
даній статті, полягає у використанні для
автоматизованого проектування паралель-
них програм специфікацій систем алгори-
тмічних алгебр Глушкова, поданих у при-
родно-лінгвістичній формі, що полегшує
розуміння алгоритмів і досягнення необ-
хідної якості програм. Іншою перевагою
розроблених інструментальних засобів є
застосування методу діалогового констру-
ювання синтаксично правильних програм,
що виключає можливість виникнення син-
таксичних помилок у процесі проектуван-
ня схем.
1. Алгебро-алгоритмічні засоби
проектування та їх налаштування
на розробку OpenCL програм
В основу пропонованого підходу до
проектування паралельних програм покла-
дений апарат систем алгоритмічних ал-
гебр (САА) та їх модифікацій [3, 4]. Мо-
дифіковані САА (САА-М) призначені для
формалізації процесів мультиобробки, що
виникають при конструюванні програмно-
го забезпечення в мультипроцесорних сис-
темах. На САА-М ґрунтуються розроблені
інструментальні засоби автоматизованого
проектування та генерації програм [3–7].
1.1. Системи алгоритмічних ал-
гебр. Модифіковані САА є двоосновною
алгеброю , ; Pr Op , де Pr – множина
логічних умов (предикатів); Op – множина
операторів; – сигнатура, що складається
з логічних операцій (диз’юнкції,
кон’юнкції, заперечення, лівого множення
оператора на умову) та операторних опе-
рацій (композиції, альтернативи, циклу та
ін.), що будуть розглянуті далі. Предикати
та оператори можуть бути базисними або
складеними. Базисні елементи вважаються
атомарними, неподільними абстракціями
та пов’язані з предметною областю алго-
ритму, що проектується. Складені опера-
тори будуються з елементарних за допомо-
гою операцій послідовного й паралельного
виконання операторів.
На САА-М ґрунтується алгоритміч-
на мова САА/1 [5, 6], призначена для бага-
торівневого структурного проектування і
документування послідовних та паралель-
них алгоритмів і програм. Перевагою її ви-
користання є можливість опису алгоритмів
у природно-лінгвістичній формі. Подання
операторів мовою САА/1 називаються
САА-схемами.
Далі наведено перелік назв та спе-
цифікації основних операторних операцій
сигнатури САА-М, поданих у природньо-
лінгвістичній формі.
1. Композиція (послідовне вико-
нання операторів):
“operator 1”;
“operator 2”.
2. Альтернатива (умовний опера-
тор):
IF ‘condition’ THEN
“operator 1”
ELSE
“operator 2”
END IF.
3. Цикл типу while:
Інструментальні засоби та середовища програмування
29
WHILE ‘condition’
LOOP “operator”
END OF LOOP.
4. Цикл типу for:
FOR (counter FROM start TO fin)
LOOP “operator”
END OF LOOP.
5. Синхронізатор, що виконує за-
тримку обчислень доти, поки значення
умови не стане істинним:
WAIT ‘condition’.
В роботі [5] розглядаються додат-
кові операції, призначені для формалізова-
ного проектування програм, що викорис-
товують платформу Nvidia CUDA. В робо-
ті [6] згадані засоби використані для прое-
ктування програми чисельного прогнозу-
вання погоди.
1.2. Розширення САА-М операці-
ями, орієнтованими на паралельні обчи-
слення в гетерогенному середовищі. В
даному підрозділі розглядаються нові опе-
рації алгебри алгоритмів, призначені для
проектування OpenCL програм [1].
OpenCL є технологією створення програм-
них застосувань, що виконуються у гете-
рогенному середовищі. OpenCL поєднує
прикладний програмний інтерфейс (API)
та варіант мови C для програмування та
одночасного використання різних пристро-
їв, здатних виконувати паралельні обчис-
лення (наприклад, CPU, GPU та Xeon Phi).
Для координації роботи пристроїв у гете-
рогенному середовищі присутній один
“головний” пристрій (host), який взаємодіє
з усіма іншими обчислювальними при-
строями (device) за допомогою OpenCL
API. OpenCL програма працює з так зва-
ними платформами (platform). Платформа
є програмним пакетом, який надається ві-
дповідним розробником апаратних засобів
(наприклад, AMD Accelerated Parallel
Processing, Nvidia CUDA, Intel OpenCL).
Платформа OpenCL складається з головно-
го пристрою, з’єднаного з обчислюваль-
ними пристроями, що підтримують
OpenCL. Кожний OpenCL-пристрій скла-
дається з обчислювальних блоків (compute
unit), які далі розділяються на один або бі-
льше елементів-обробників (processing
elements, PE). Програма в OpenCL склада-
ється з двох частин: головної, яка викону-
ється на керуючому пристрої, та обчислю-
вальної – однієї або кількох функцій-ядер,
що виконуються на елементах-обробниках
OpenCL-пристроїв. Головна частина про-
грами визначає середовище (контекст), у
якому виконуються ядра, і керує їх вико-
нанням. Контекст включає платформу, об-
числювальні пристрої та буфери пам’яті
для них. Для обчислювального пристрою в
рамках контексту створюється черга ко-
манд для виконання (command queue).
Операції з обчислювальним пристроєм, та-
кі, як читання/запис даних і запуск ядра,
заносяться в цю чергу і послідовно вико-
нуються. Коли ядро ставиться в чергу на
виконання, визначається простір індексів.
Копія ядра виконується для кожного інде-
ксу з цього простору і називається робо-
чою одиницею (задачею, work-item). Робо-
чі одиниці організовані в групи (work-
groups) і виконуються паралельно на еле-
менті-обробнику обчислювального при-
строю.
Далі наведено послідовність дій для
створення OpenCL програм та відповідні
нові базисні оператори, додані в алгебру
алгоритмів.
1. Отримання списку доступних
платформ та запис їх у змінну pl:
“Get all available platforms (pl)”.
2. Отримання списку пристроїв з
отриманої платформи pl:
“Get all devices (dvs) available on a
platform (pl)”.
3. Створення контексту виконання
для пристроїв:
“Create a context (cnt) for devices
(dvs)”.
4. Створення черги виконання для
пристрою:
Інструментальні засоби та середовища програмування
30
“Create a command queue (cmdqueue)
for a context (cnt) and a device (dv)”.
5. Компіляція файлу, що містить
вихідний код функції-ядра OpenCL:
“Create a kernel (krnl) from
a source (program)”,
де krnl – назва функції-ядра; program –
шлях до файлу з вихідним кодом цієї фун-
кції.
Наведемо приклад САА-схеми для
функції-ядра, що виконує додавання двох
векторів a та b довжини n :
SCHEME VECTOR ADD ====
“vecAdd(a, b, c, n)”
==== “Declare a variable (id) of type (int)”;
(id := “Get the global work-item
identifier for dimension (0)”);
IF (id < n)
THEN
“(c[id]) := (a[id] + b[id])”
END IF;
END OF SCHEME VECTOR ADD
У схемі базисний оператор “Get the
global work-item identifier for dimension (0)”
повертає глобальний ідентифікатор задачі.
6. Створення буферу для даних, за-
значених у змінній var:
“Create a memory buffer (buff)
for data (var) on devices in
the context (cnt)”.
7. Завантаження буферу для змінної
var в пам’ять пристрою за допомогою чер-
ги:
“Add commands to queue (cmdqueue)
writing a buffer of data (var) from
host to device”.
8. Установка значення arg_value для
параметра під номером arg_index ядра krnl:
“Set the argument value (arg_value)
for a parameter (arg_index) of
a kernel (krnl)”.
9. Завантаження ядра krnl в чергу
пристрою та його асинхронне виконання:
“Add a command to queue
(cmdqueue) executing a kernel
(krnl)(globalworksize)
(localworksize) on a device”,
де globalworksize – загальна розмірність
простору індексів; localworksize – розмір-
ність локальної підмножини задач у групі.
10. Синхронізація (очікування заве-
ршення) виконання усіх задач, що були за-
несені в чергу:
WAIT ‘All previously queued
commands in (cmdqueue)
are issued to the device and
have completed’.
11. Зчитування даних з буферу, в
який записувався результат:
“Add commands to queue
(cmdqueue) reading from a buffer
of data (var) from device to host”.
Приклад використання вищенаве-
дених конструкцій розглядається у розді-
лі 2.
1.3. Інструментарій автоматизо-
ваної розробки програм. Розроблений ін-
тегрований інструментарій проектування
та синтезу програм (ІПС) ґрунтується на
використанні розглянутих засобів САА-М
та методу діалогового конструювання син-
таксично правильних програм (ДСП-
методу) [3, 4]. На відміну від традиційних
синтаксичних аналізаторів, ДСП-метод
орієнтований не на пошук і виправлення
синтаксичних помилок, а на виключення
можливості їх появи в процесі побудови
алгоритму. Основна ідея методу полягає у
порівневому конструюванні схем зверху
Інструментальні засоби та середовища програмування
31
вниз шляхом суперпозиції мовних конс-
трукцій САА-М. На кожному кроці конс-
труювання система надає користувачу на
вибір лише ті конструкції, підстановка
яких у текст алгоритму, що проектується,
не порушує синтаксичну правильність
схеми. На основі побудованої схеми алго-
ритму виконується автоматична генерація
тексту програми цільовою мовою програ-
мування. Відображення операцій САА-М у
текст мовою програмування подане у ви-
гляді шаблонів і зберігається в базі даних
інструментарію.
Основними компонентами системи
ІПС є такі:
діалоговий конструктор синтак-
сично правильних програм (ДСП-конст-
руктор), призначений для діалогового про-
ектування схем алгоритмів та синтезу про-
грам мовами Java та C, C++;
редактор граф-схем;
база даних алгеброалгоритмічних
специфікацій, у якій зберігається текст
конструкцій САА-М і базисних елементів
схем, а також їх програмні реалізації;
генератор САА-схем за гіперсхе-
мами.
Для автоматизації виконання тран-
сформацій алгоритмів система ІПС може
застосовуватися спільно з системою
TermWare [12, 13], що ґрунтується на па-
радигмі переписувальних правил. В роботі
[7] на основі використання TermWare роз-
роблено програмний засіб для оптимізації
обчислень, що дозволяє в напівавтоматич-
ному режимі здійснювати паралелізацію
циклічних операторів програм, що викори-
стовують Nvidia CUDA.
З метою налаштування системи ІПС
на проектування і генерацію OpenCL про-
грам, в базу даних системи включені нові
конструкції, розглянуті вище в підрозді-
лі 1.2.
2. Приклад застосування системи
ІПС для проектування
OpenCL програми
У даному розділі розглядається ви-
користання інтегрованого інструментарію
для автоматизованої розробки паралельної
OpenCL програми інтерполяції початкових
метеорологічних даних, що входить до
складу програмного забезпечення чисель-
ного прогнозування погоди [6, 7].
Далі наведено фрагмент початкової
послідовної САА-схеми інтерполяції, по-
будованої в [7].
SCHEME INTERPOLATION
SEQUENTIAL
“interpolation_sequential”
==== FOR (h FROM 0 TO Pk–1)
LOOP
FOR (k FROM 0 TO Lmz–1)
LOOP
FOR (j FROM 0 TO Mmz–1)
LOOP
FOR (i FROM 0 TO Nmz–1)
LOOP
“(a) := ((WZZ + US[h][k][j][i] /
0.321f) * Rs * VS[h][k][j][i])”;
“(Tp) := (TS[h][k][j][i] *
pow(1000.f / HS[h][k][j][i],
2.f/7.f))”;
“(Tv) := (Tp * (1.f + 0.6078f *
QS[h][k][j][i]))”;
“(Qc[h][k][j][i]) := (a – (0.5f *
Tv + (1.f – Zmz[k]) * g *
F_X[j][i] / 0.321f))”
END OF LOOP
END OF LOOP
END OF LOOP
END OF LOOP;
END OF SCHEME
INTERPOLATION SEQUENTIAL
Наведена схема є чотирма вкладе-
ними циклами за ітераторами [0 ... h
... 1]Pk , [0 ... –1]k Lmz , [0 ... –j Mmz
–1] , [0 ... –1]i Nmz , де Pk , Lmz , Mmz ,
Nmz – натуральні числа, що визначають
розмір скінченно-різницевої сітки. У схемі
US, VS, TS, HS, QS – вхідні масиви метео-
рологічних величин (горизонтальні скла-
дові вектору швидкості вітру, температура,
вологість і т. п.); Qc – вихідний масив.
Оскільки ітерації у циклах є незалежними,
вони можуть бути виконані паралельно.
Проектування паралельної OpenCL
програми за допомогою системи ІПС
включає у себе розробку САА-схем для
Інструментальні засоби та середовища програмування
32
функції-ядра та керуючої програми, а та-
кож генерацію на їх основі відповідного
коду мовою програмування.
Далі наведена САА-схема для фун-
кції-ядра, сконструйована за допомогою
інструментарію ІПС на основі перетворен-
ня послідовної схеми. У параметрах, вка-
заних у дужках після назви функції
(interpolation) зазначені вхідні та вихідні
дані для задачі. Розпаралелювання здійс-
нюється за індексами h , k , j (їх значення
обчислюється за допомогою оператора
“Get the global work-item identifier for
dimension”). За індексом i в ядрі викону-
ється цикл основних обчислень.
SCHEME INTERPOLATION KERNEL
“interpolation(US, VS, HS, QS, TS, F_x,
Zmz, Qc, Pk, Lmz, Mmz, Nmz)”
==== “Declare the list of variables (h, k, j) of
type (int)”;
(h := “Get the global work-item
identifier for dimension (0)”);
(k := “Get the global work-item
identifier for dimension (1)”);
(j := “Get the global work-item
identifier for dimension (2)”);
IF NOT((h >= Pk) OR (k >= Lmz) OR
(j >= Mmz))
THEN
FOR (i FROM 0 TO Nmz–1)
LOOP
“Declare a constant (ind) of type
(unsigned int)”;
“Declare the list of variables
(a, Tp, Tv) of type (float)”;
“(ind) := (h + Pk * k + Pk * Lmz *
j + Pk * Lmz * Mmz * i)”;
“(a) := ((WZZ + US[ind] / 0.321f)
* Rs * VS[ind])”;
“(Tp) := (TS[ind] *
pow(1000.f / HS[ind], 2.f / 7.f))”;
“(Tv) := (Tp * (1.f + 0.6078f *
QS[ind]))”;
“(Qc[ind]) := (a – (0.5f * Tv +
(1.f – Zmz[k]) * g *
F_x[j + i * Mmz] /
0.321f))”
END OF LOOP
END IF;
END OF SCHEME INTERPOLATION
KERNEL
На відміну від реалізації алгоритму
для CUDA [7], в якій дані US, VS, HS, QS,
TS, Qc зберігалися як чотиривимірні вказі-
вники, що є неефективним і не дозволяє
використовувати кешування даних проце-
сором, в реалізації алгоритму на OpenCL,
що розглядається у даній роботі, дані пе-
редаються суцільним блоком (continuous
array). Індекс для обробки поточного еле-
мента масиву обчислюється спеціальним
чином та заноситься у змінну ind. При роз-
паралелюванні послідовного алгоритму
звертання до елементів згаданих масивів
(наприклад, US[h][k][j][i]) замінюється на
відповідний запис з індексом ind (напри-
клад, US[ind]).
Далі наведена САА-схема головної
частини програми, побудована на основі
кроків 1–11, розглянутих у підрозділі 1.2.
SCHEME INTERPOLATION HOST
“main(argc, argv)”
==== “Read input parameters
(Pk, Lmz, Mmz, Nmz)
from command line (argc, argv)”;
“Get all available platforms (pl)”;
“Get all devices (dvs) available on a
platform (pl[0])”;
“Create a context (cnt) for
devices (dvs)”;
“Create a command queue
(cmdqueue) for a context (cnt) and a
device (dvs[0])”;
“Create a kernel (“interpolation”)
from a source
(“kernels/interpolation.cl”)”;
“Declare and fill 4D continuous arrays
(US, VS, HS, QS, TS, Qc)
of type (auto) and size
(Pk, Lmz, Mmz, Nmz)”;
“Declare and fill a 2D continuous
Інструментальні засоби та середовища програмування
33
array (F_X) of type (auto)
and size (Mmz, Nmz)”;
“Declare and fill a 1D continuous
array (Zmz) of type (auto) and
size (Nmz)”;
“Create memory buffers for data
(US, VS, HS, QS, TS, Qc, F_X,Zmz)
on devices in the context (cnt)”;
“Add commands to queue (cmdqueue)
writing buffers of data
(US, VS, HS, QS, TS, F_X, Zmz)
from host to device”;
“Set the argument values for
parameters of a kernel (krnl)”;
“Add a command to queue
(cmdqueue) executing a kernel
(krnl)(3)({Pk, Lmz, Mmz})
on a device”;
WAIT ‘All previously queued
commands in (cmdqueue) are issued
to the device and have completed’;
“Add commands to queue (cmdqueue)
reading from a buffer of data (Qc)
from device to host”;
END OF SCHEME INTERPOLATION
HOST
На основі побудованих САА-схем в
системі ІПС виконана генерація програм-
ного коду OpenCL, результати виконання
якого на графічному прискорювачі наве-
дено у наступному розділі.
3. Результати експерименту
Проведено експеримент з виконан-
ня розробленої паралельної програми в
обчислювальному середовищі, що склада-
ється з двоядерного процесора Intel Core
i5-4210U (частота 1,7–2,7 ГГц) та графіч-
ного процесора nVidia GeForce 840M (384
ядра, 2 Гб оперативної пам’яті). Для порі-
вняння виконано також відповідну про-
граму, що використовує Nvidia CUDA [7].
На рис. 1 показано графік залежно-
сті часу виконання програми інтерполяції
від розміру вхідних даних на CPU, а також
програм CUDA та OpenCL. На рис. 2 пока-
зано графіки залежності мультипроцесор-
ного прискорення
CPU
GPU
T
Sp
T
,
де CPUT , GPUT — час виконання на CPU та
GPU, відповідно.
Рис. 1. Залежність часу виконання програми інтерполяції на CPU,
CUDA та OpenCL від розміру вхідних даних
Інструментальні засоби та середовища програмування
34
Рис. 2. Залежність мультипроцесорного прискорення від розміру вхідних даних
для реалізацій паралельної програми інтерполяції на OpenCL та CUDA
Як видно з наведених результатів,
OpenCL програма значно випереджає від-
повідний варіант для CUDA. Максимальне
значення прискорення Sp OpenCL про-
грами становить 52,7 (за розміру вхідних
даних 11,451 Мб), для CUDA програми
максимальне значення Sp є 1,7 (за розміру
вхідних даних 400,553 Мб). Підвищена
швидкодія OpenCL програми порівняно з
реалізацією для CUDA пояснюється вико-
ристанням одновимірних масивів даних
замість чотиривимірних (див. розділ 2).
Висновки
Виконане налаштування алгебро-
алгоритмічного інструментарію на форма-
лізоване проектування та синтез OpenCL
програм. Особливістю запропонованого
підходу до проектування є використання
мови САА-схем, перевагою якої є простота
в навчанні і використанні, а також засто-
сування методу конструювання синтакси-
чно правильних схем, який виключає мож-
ливість появи синтаксичних помилок у
процесі проектування алгоритмів.
Проведено експеримент з виконан-
ня згенерованої за допомогою системи ІПС
паралельної програми інтерполяції почат-
кових даних для задачі метеорологічного
прогнозування на графічному прискорю-
вачі. Результати експерименту продемонс-
трували гарний ступінь розпаралелювано-
сті обчислень та переваги використання
OpenCL порівняно з Nvidia CUDA для зга-
даної задачі.
Література
1. OpenCL overview. The open standard for
parallel programming of heterogeneous
systems [Електронний ресурс]. Режим дос-
тупу до ресурсу: https://www.khronos.
org/opencl (дата звернення 22.01.2019 р.).
2. Nvidia CUDA technology [Електронний ре-
сурс]. Режим доступу до ресурсу:
http://www.nvidia.com/cuda (дата звернення
22.01.2019 р.).
3. Андон Ф.И., Дорошенко А.Е., Жереб К.А.,
Шевченко Р.С., Яценко Е.А. Методы ал-
гебраического программирования. Форма-
льные методы разработки параллельных
программ. Киев: Наукова думка, 2017.
440 с.
4. Андон Ф.И., Дорошенко А.Е., Цейт-
лин Г.Е., Яценко Е.А. Алгеброалгоритми-
ческие модели и методы параллельного
программирования. Киев: Академпериоди-
ка, 2007. 631 с.
5. Дорошенко А.Ю., Бекетов О.Г., Жереб
К.А., Яценко О.А. Формалізоване проекту-
вання та синтез паралельних програм для
http://www.nvidia.com/cuda
Інструментальні засоби та середовища програмування
35
відеографічних прискорювачів. Проблеми
програмування. 2013. № 3. С. 38–46.
6. Дорошенко А.Ю., Бекетов О.Г., Прусов
В.А., Тирчак Ю.М., Яценко О.А. Формалі-
зоване проектування та генерація парале-
льної програми чисельного моделювання
погоди. Проблеми програмування. 2014.
№ 2–3. С. 72–81.
7. Дорошенко А.Ю., Яценко О.А., Бекетов
О.Г. Алгоритм автоматизованого розпара-
лелювання циклічних операторів для гра-
фічних прискорювачів. Проблеми програ-
мування. 2017. № 4. C. 28–36.
8. Rodrigues A., Guyomarc’h F., Dekeyser J.-L.
An MDE approach for automatic code
generation from UML/MARTE to OpenCL.
Computing in Science and Engineering. 2012.
Vol. 15, N 1. P. 46–55.
9. Li P., Brunet E., Trahay F., Parrot C., Thomas
G., Namyst, R. Automatic OpenCL code
generation for multi-device heterogeneous
architectures. Proc. 44th International
Conference on Parallel Processing (ICPP
2015), Beijing, China (1–4 September, 2015).
Piscataway, NJ: IEEE, 2015. P. 959–968.
10. Tillet P., Rupp K., Selberherr S. An automatic
OpenCL compute kernel generator for basic
linear algebra operations. Proc. 2012
Symposium on High Performance Computing
(HPC’12), Orlando, Florida, USA (26–30
March, 2012). San Diego, CA: Society for
Computer Simulation International, 2012.
P. 4:1–4:2.
11. Steuwer M., Fensch C., Lindley S., Dubach C.
Generating performance portable code using
rewrite rules: from high-level functional
expressions to high-performance OpenCL
code. Proc. 20th ACM SIGPLAN
International Conference on Functional
Programming (ICFP’15), Vancouver, Canada
(31 August – 2 September, 2015). New York:
ACM, 2015. P. 205–217.
12. Doroshenko A., Shevchenko R. A rewriting
framework for rule-based programming
dynamic applications. Fundamenta
Informaticae. 2006. Vol. 72, N 1–3.
P. 95–108.
13. Doroshenko A., Zhereb K., Yatsenko O.
Developing and optimizing parallel programs
with algebra-algorithmic and term rewriting
tools. Communications in Computer and
Information Science. Information and
Communication Technologies in Education,
Research, and Industrial Applications.
Springer, Heidelberg, 2013. Vol. 412.
P. 70–92.
References
1. OpenCL Overview. The open standard for
parallel programming of heterogeneous
systems. [Online] Available from:
https://www.khronos.org/opencl [Accessed:
22 January 2019]
2. Nvidia CUDA technology. [Online] Available
from: http://www.nvidia.com/cuda [Accessed:
22 January 2019]
3. Andon, P.I. et al. (2017) Methods of algebraic
programming. Formal methods of parallel
program development. Kyiv: Naukova
dumka. (in Russian)
4. Andon P.I. et al. (2007) Algebra-algorithmic
models and methods of parallel programming.
Kyiv: Akademperiodyka. (in Russian)
5. Doroshenko A.Yu., Beketov O.G.,
Zhereb K.A. & Yatsenko O.A. (2013)
Formalized designing and synthesis of parallel
programs for graphics processing units.
Problems in programming. (3). P. 38–46. (in
Ukrainian)
6. Doroshenko A.Yu., Beketov O.G.,
Prusov V.A., Tyrchak Yu.M. & Yatsenko
O.A. (2014) Formalized designing and
generation of parallel program for numerical
weather forecasting task. Problems in
programming. (2–3). P. 72–81. (in Ukrainian)
7. Doroshenko A.Yu., Yatsenko O.A. &
Beketov O.G. (2017) Algorithm for automatic
loop parallelization for graphics processing
units. Problems in programming. (4).
P. 28–36. (in Ukrainian)
8. Rodrigues A., Guyomarc'h F. & Dekeyser
J.-L. (2012) An MDE approach for automatic
code generation from UML/MARTE to
OpenCL. Computing in Science and
Engineering. 15 (1). P. 46–55.
9. Li P., Brunet E., Trahay F., Parrot C., Thomas
G. & Namyst R. (2015) Automatic OpenCL
code generation for multi-device
heterogeneous architectures. In Proc. 44th
International Conference on Parallel
Processing (ICPP 2015). Beijing, China,
1–4 September 2015. Piscataway, NJ: IEEE.
P. 959–968.
10. Tillet P., Rupp K. & Selberherr S. (2012) An
automatic OpenCL compute kernel generator
for basic linear algebra operations. In Proc.
2012 Symposium on High Performance
Computing (HPC’12). Orlando, Florida, USA,
26-30 March 2012. San Diego, CA: Society
for Computer Simulation International.
P. 4:1–4:2.
http://www.nvidia.com/cuda
Інструментальні засоби та середовища програмування
36
11. Steuwer M., Fensch C., Lindley S. & Dubach
C. (2015) Generating performance portable
code using rewrite rules: from high-level
functional expressions to high-performance
OpenCL code. In Proc. 20th ACM SIGPLAN
International Conference on Functional
Programming (ICFP’15). Vancouver, Canada,
31 August – 2 September 2015. New York:
ACM. P. 205–217.
12. Doroshenko A. & Shevchenko R. (2006)
A rewriting framework for rule-based
programming dynamic applications.
Fundamenta Informaticae. 72 (1–3).
P. 95–108.
13. Doroshenko A., Zhereb K. & Yatsenko O.
(2013) Developing and optimizing parallel
programs with algebra-algorithmic and term
rewriting tools. In Proc. 9th International
Conference “ICT in Education, Research, and
Industrial Applications” (ICTERI 2013),
Revised Selected Papers. Kherson, Ukraine,
19-22 June 2013. Berlin: Springer. 412.
P. 70–92.
Одержано 10.02.2019
Про авторів:
Дорошенко Анатолій Юхимович,
доктор фізико-математичних наук,
професор, завідувач відділу
теорії комп’ютерних обчислень,
професор кафедри автоматики та
управління в технічних системах
НТУУ “КПІ імені Ігоря Сікорського ”.
Кількість наукових публікацій в
українських виданнях – понад 150.
Кількість наукових публікацій в
зарубіжних виданнях – понад 50.
Індекс Хірша – 5.
http://orcid.org/0000-0002-8435-1451,
Бондаренко Микола Миколайович,
магістр факультету комп’ютерних наук
та кібернетики.
http://orcid.org/0000-0002-6362-414X,
Яценко Олена Анатоліївна,
кандидат фізико-математичних наук,
старший науковий співробітник.
Кількість наукових публікацій в
українських виданнях – 43.
Кількість наукових публікацій в
зарубіжних виданнях – 13.
Індекс Хірша – 2.
http://orcid.org/0000-0002-4700-6704.
Місце роботи авторів:
Інститут програмних систем
НАН України,
03187, м. Київ-187,
проспект Академіка Глушкова, 40.
Тел.: (044) 526 3559.
Київський національний університет
імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 60.
E-mail: doroshenkoanatoliy2@gmail.com,
bondarenko_mykola@yahoo.com.ua,
oayat@ukr.net
mailto:oayat@ukr.net
|