Algorithm for automatic loop parallelization for graphics processing units
Parallelization of loop operators is a long standing problem of parallel programming. The widespread use of graphics processing units for computational tasks has resulted in the new statement of the mentioned problem for this class of multicore systems. The purpose of this work is to improve the mec...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/308 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-308 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/6a/2101052282a8b7c3387f1bdaceb1b96a.pdf |
| spelling |
pp_isofts_kiev_ua-article-3082024-04-28T11:45:31Z Algorithm for automatic loop parallelization for graphics processing units Алгоритм автоматизированного распараллеливания циклических операторов для графических ускорителей Алгоритм автоматизованого розпаралелювання циклічних операторів для графічних прискорювачів Doroshenko, А.Yu. Yatsenko, O.A. Beketov, O.G. parallelization methods; loop optimization; general-purpose computing on graphics processing units; program design and synthesis UDC 004.4'24 методы параллелизации; оптимизация циклов; вычисления общего назначения на графических процессорах; проектирование и синтез программ УДК 004.4'24 методи паралелізації; оптимізація циклів; обчислення загального призначення на графічних процесорах; проектування та синтез програм УДК 004.4'24 Parallelization of loop operators is a long standing problem of parallel programming. The widespread use of graphics processing units for computational tasks has resulted in the new statement of the mentioned problem for this class of multicore systems. The purpose of this work is to improve the mechanism of transformation of cyclic operators for loop parallelization for execution on a graphics processing unit. Software tool for computation optimization that allows to parallelize cyclic operators semi‑automatically was developed. Data bufferization synchronized with main loop execution was implemented, and the software tool using the rewriting rules system TermWare was built and integrated with the toolkit for design and synthesis of programs IDS. The developed system was tested using heterogeneous multicore cluster. The advantages of the developed system in comparison with well-known parallelization system Par4All consist in processing speed and the possibility of processing of data amounts exceeding the amount of memory of a graphics processing unit, and also the ability to use several graphics processing units simultaneously. The developed system was applied for parallelization of a serial loop, which is the part of a numerical weather forecasting program.Problems in programming 2017; 4: 028-036 Распараллеливание циклических операторов является давно известной проблемой параллельного программирования. С широким использованием графических ускорителей для вычислительных задач возникла новая постановка данной проблемы для этого класса мультиядерных систем. Целью данной работы является усовершенствование механизма преобразования операторов цикла для его параллелизации для выполнения на графическом ускорителе. Разработано программное средство для оптимизации вычислений, которое позволяет в полуавтоматическом режиме осуществлять параллелизацию циклических операторов программы. Осуществлена буферизация данных, синхронизированная с выполнением основного цикла, и с помощью системы переписывающих правил TermWare построено средство, которое интегрировано с инструментарием проектирования и синтеза программ ИПС. Проведены испытания разработанной системы на гетерогенном мультиядерном кластере. Выполнено сравнение с известной системой параллелизации Par4All, в результате которого выявлены преимущества разработанной системы в плане быстродействия и возможности обработки объёмов данных, которые превышают объём памяти графического ускорителя, а также возможности использования нескольких ускорителей одновременно. Созданная система применена для распараллеливания последовательного цикла, входящего в состав программы численного прогнозирования погоды.Problems in programming 2017; 4: 028-036 Розроблено програмний засіб для оптимізації обчислень, що дозволяє в напівавтоматичному режимі здійснити паралелізацію циклічних операторів програми для виконання обчислень на графічних прискорювачах. Здійснено буферизацію даних, синхронізовану із виконанням основного циклу, та побудований за допомогою системи переписувальних правил TermWare засіб інтегровано з інструментарієм проектування та синтезу програм (ІПС). Проведено випробування розробленої системи на гетерогенному мультиядерному кластері.Problems in programming 2017; 4: 028-036 Інститут програмних систем НАН України 2018-11-15 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/308 10.15407/pp2017.04.028 PROBLEMS IN PROGRAMMING; No 4 (2017); 28-36 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2017); 28-36 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2017); 28-36 1727-4907 10.15407/pp2017.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/308/303 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:45:31Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
parallelization methods loop optimization general-purpose computing on graphics processing units program design and synthesis UDC 004.4'24 |
| spellingShingle |
parallelization methods loop optimization general-purpose computing on graphics processing units program design and synthesis UDC 004.4'24 Doroshenko, А.Yu. Yatsenko, O.A. Beketov, O.G. Algorithm for automatic loop parallelization for graphics processing units |
| topic_facet |
parallelization methods loop optimization general-purpose computing on graphics processing units program design and synthesis UDC 004.4'24 методы параллелизации оптимизация циклов вычисления общего назначения на графических процессорах проектирование и синтез программ УДК 004.4'24 методи паралелізації оптимізація циклів обчислення загального призначення на графічних процесорах проектування та синтез програм УДК 004.4'24 |
| format |
Article |
| author |
Doroshenko, А.Yu. Yatsenko, O.A. Beketov, O.G. |
| author_facet |
Doroshenko, А.Yu. Yatsenko, O.A. Beketov, O.G. |
| author_sort |
Doroshenko, А.Yu. |
| title |
Algorithm for automatic loop parallelization for graphics processing units |
| title_short |
Algorithm for automatic loop parallelization for graphics processing units |
| title_full |
Algorithm for automatic loop parallelization for graphics processing units |
| title_fullStr |
Algorithm for automatic loop parallelization for graphics processing units |
| title_full_unstemmed |
Algorithm for automatic loop parallelization for graphics processing units |
| title_sort |
algorithm for automatic loop parallelization for graphics processing units |
| title_alt |
Алгоритм автоматизированного распараллеливания циклических операторов для графических ускорителей Алгоритм автоматизованого розпаралелювання циклічних операторів для графічних прискорювачів |
| description |
Parallelization of loop operators is a long standing problem of parallel programming. The widespread use of graphics processing units for computational tasks has resulted in the new statement of the mentioned problem for this class of multicore systems. The purpose of this work is to improve the mechanism of transformation of cyclic operators for loop parallelization for execution on a graphics processing unit. Software tool for computation optimization that allows to parallelize cyclic operators semi‑automatically was developed. Data bufferization synchronized with main loop execution was implemented, and the software tool using the rewriting rules system TermWare was built and integrated with the toolkit for design and synthesis of programs IDS. The developed system was tested using heterogeneous multicore cluster. The advantages of the developed system in comparison with well-known parallelization system Par4All consist in processing speed and the possibility of processing of data amounts exceeding the amount of memory of a graphics processing unit, and also the ability to use several graphics processing units simultaneously. The developed system was applied for parallelization of a serial loop, which is the part of a numerical weather forecasting program.Problems in programming 2017; 4: 028-036 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/308 |
| work_keys_str_mv |
AT doroshenkoayu algorithmforautomaticloopparallelizationforgraphicsprocessingunits AT yatsenkooa algorithmforautomaticloopparallelizationforgraphicsprocessingunits AT beketovog algorithmforautomaticloopparallelizationforgraphicsprocessingunits AT doroshenkoayu algoritmavtomatizirovannogorasparallelivaniâcikličeskihoperatorovdlâgrafičeskihuskoritelej AT yatsenkooa algoritmavtomatizirovannogorasparallelivaniâcikličeskihoperatorovdlâgrafičeskihuskoritelej AT beketovog algoritmavtomatizirovannogorasparallelivaniâcikličeskihoperatorovdlâgrafičeskihuskoritelej AT doroshenkoayu algoritmavtomatizovanogorozparalelûvannâciklíčnihoperatorívdlâgrafíčnihpriskorûvačív AT yatsenkooa algoritmavtomatizovanogorozparalelûvannâciklíčnihoperatorívdlâgrafíčnihpriskorûvačív AT beketovog algoritmavtomatizovanogorozparalelûvannâciklíčnihoperatorívdlâgrafíčnihpriskorûvačív |
| first_indexed |
2024-09-16T04:08:31Z |
| last_indexed |
2024-09-16T04:08:31Z |
| _version_ |
1818568444192227328 |
| fulltext |
Інструментальні засоби та середовища програмування
© А.Ю. Дорошенко, О.А. Яценко, О.Г. Бекетов, 2017
28 ISSN 1727-4907. Проблеми програмування. 2017. № 4
УДК 004.4'24
А.Ю. Дорошенко, О.А. Яценко, О.Г. Бекетов
АЛГОРИТМ АВТОМАТИЗОВАНОГО РОЗПАРАЛЕЛЮВАННЯ
ЦИКЛІЧНИХ ОПЕРАТОРІВ ДЛЯ ГРАФІЧНИХ
ПРИСКОРЮВАЧІВ
Розроблено програмний засіб для оптимізації обчислень, що дозволяє в напівавтоматичному режимі
здійснити паралелізацію циклічних операторів програми для виконання обчислень на графічних прис-
корювачах. Здійснено буферизацію даних, синхронізовану із виконанням основного циклу, та побудо-
ваний за допомогою системи переписувальних правил TermWare засіб інтегровано з інструментарієм
проектування та синтезу програм (ІПС). Проведено випробування розробленої системи на гетероген-
ному мультиядерному кластері.
Ключові слова: методи паралелізації, оптимізація циклів, обчислення загального призначення на графі-
чних процесорах, проектування та синтез програм.
Вступ
Розпаралелювання циклічних опе-
раторів є давно відомою проблемою пара-
лельного програмування. З широким вико-
ристанням графічних прискорювачів для
обчислювальних задач виникла нова пос-
тановка цієї проблеми для цього класу
мультиядерних систем. Мета даної статті –
вдосконалення механізму перетворень
операторів циклу для його паралелізації
для виконання на графічному прискорюва-
чі, наведеного в попередній статті [1]. Не-
доліком попередньої схеми перетворень
було використання попередньої лінеари-
зації даних перед їх буферизацією, що
суттєво ускладнювало подальшу проце-
дуру передачі даних, оскільки потребува-
ло окремого механізму контролю синхро-
нізації. В даній роботі натомість реалізо-
вано буферизацію даних, синхронізовану
із виконанням основного циклу. Крім то-
го, з метою підтвердження концепції було
створено автоматизований інструментарій
перетворення циклів за допомогою систе-
ми переписувальних правил TermWare і
інтегрування його з інструментарієм про-
ектування та синтезу програм ІПС. Наве-
дено порівняння властивостей програм,
отриманих при застосуванні наведеного
перетворення та за допомогою системи
автоматизованої паралелізації Par4All [2].
1. Механізм перетворення циклу
Нехай задане гніздо циклу, складе-
не з циклів із лічильником, таке, що його
ітерації незалежні між собою, а області
значень ітераторів задані статично.
Графічний прискорювач є багато-
потоковим обчислювальним пристроєм з
SIMD архітектурою, тобто окремі парале-
льні потоки виконують один спільний на-
бір команд, але над різними даними. Оскі-
льки ітерації циклу незалежні, можливе їх
виконання паралельними потоками. Отже,
слід розбити цикл на окремі ітерації так,
щоб кожна ітерація виконувалась окремим
потоком, і кожному потоку надати набір
даних, що відповідає виконуваній ітерації.
Наявність власної оперативної па-
м’яті призводить до необхідності обміну
даними з центральним пристроєм. Обсяг
даних, що обробляються, може перевищу-
вати обсяг пам’яті графічного прискорю-
вача, тому дані слід передавати порціями.
У тому випадку, коли дані, що обробля-
ються, не вміщуються у пам’ять графічно-
го прискорювача, або у випадку обробки
неперервного потоку даних, постає необ-
хідність розбиття початкового циклу на
окремі підцикли.
Розглянемо складений цикл, що має
наступний вигляд:
00 ...#0 Iifor
11 ...#0 Iifor
...
NN Iifor ...#0
);)( ,)(,( ipipiF outin
(1)
Інструментальні засоби та середовища програмування
29
де
N
III ,...,, 10 – множини значень індексів
Niii ,...,, 10 ; 1+N – глибина вкладеності
циклу, символом i позначено множину
Njii j ,...,0 ;
outinPjipPip j , ,# ...0 )()(
– множини значень параметрів вхідних
та вихідних даних, F – відображення,
що здійснює перетворення даних. Для
спрощення припустимо, що множини
вхідних та вихідних параметрів не пере-
тинаються.
Позначимо T кількість потоків, що
будуть задіяні при виконанні ядра kernel.
Після перетворень цикл набуде наступного
вигляду:
Lefor :0
);(inBuffill
);(inBufpush
); , ,( outBufinBufekernel
);(outBufpull
);(outBufunpack
(2)
де L – кількість викликів ядра, що обира-
ється таким чином, щоб TL не переви-
щувало G – загальної кількості ітерацій
початкового циклу; fill – функція запов-
нення буферу початкових даних; push –
переміщення буферу початкових даних у
пам'ять прискорювача; kernel – виклик яд-
ра; pull – переміщення оброблених даних
із пам'яті прискорювача до буферу оброб-
лених даних; unpack – копіювання даних із
буферу оброблених даних у відповідні
змінні. Функція fill має наступний вигляд:
Ttfor :0
;tTeid
)).(( idgpinbuf in
t
Таким чином, id визначає номер по-
точної ітерації. Тут g – функція, що співс-
тавляє номеру ітерації відповідний набір
значень ітераторів циклу [1], tinbuf – бу-
фер вхідних даних ітерації t. Функція
kernel складається із виклику вмісту поча-
ткового циклу:
),)( ),(,( ioutbufiinbufiF idid
де id – номер потоку графічного приско-
рювача, що виконує ітерацію. Функція
unpack аналогічна fill:
Ttfor :0
;tTeid
. ))(( t
out outbufidgp
Таким чином, при паралелізації ок-
ремого циклу структура основної програ-
ми залишається незмінною.
На рис. 1 наведено діаграму послі-
довності паралельної програми для одного
прискорювача. Обчислення виконуються у
три потоки, що одночасно виконують фун-
кції fill, kernel та unpack.
2. Реалізація методу
За допомогою системи символь-
них обчислень TermWare [3] було реалі-
зовано експериментальний інструмент
LoopRipper, що дозволяє, маючи списки
вхідних та вихідних змінних, згенерувати
функції kernel, fill та unpack, із яких пара-
лельна програма компонується за допомо-
гою інструментарію проектування та син-
тезу програм [4]. Генерація функцій здійс-
нюється шляхом заміни параметрів вхід-
ним та вихідним буферами даних та пере-
розрахунком ітераторів у заданому почат-
ковому циклі. Таким чином, від користу-
вача вимагається надати цикл та списки
параметрів. Подальша автоматизація про-
цесу потребує аналізу дерева залежностей
параметрів.
3. Інтеграція з системою ІПС
З метою автоматизації проектуван-
ня та перетворення (паралелізації) програ-
ми у даній роботі спільно з системою
TermWare [3] застосовується інструмента-
рій проектування та синтезу про-
грам (ІПС) [4].
Інструментальні засоби та середовища програмування
30
Рис. 1. Діаграма послідовності паралельної програми для одного прискорювача
Інструментальні засоби та середовища програмування
31
Система ІПС призначена для конс-
труювання послідовних і паралельних
САА-схем алгоритмів, поданих в модифі-
кованих системах алгоритмічних алгебр
В.М. Глушкова (САА-М), а також генера-
ції програм мовами C++, Java, C for
CUDA та ін. Основним компонентом сис-
теми є діалоговий конструктор синтакси-
чно правильних програм (ДСП-
конструктор), за допомогою якого вико-
нується порівневе проектування САА-
схем зверху вниз шляхом деталізації мов-
них конструкцій САА-М. На кожному
кроці проектування система надає корис-
тувачу на вибір лише ті конструкції, підс-
тановка яких у текст схеми, що формуєть-
ся, не порушує її синтаксичну правиль-
ність. ДСП-конструктор використовує
список конструкцій САА-М і дерево
конструювання алгоритму. Специфікації
конструкцій та їх відображення в цільові
мови програмування зберігаються в базі
даних інструментарію.
Основними етапами процесу розро-
бки та трансформації програми (у рамках
задачі паралелізації циклів, що розгляда-
ється у даній роботі) за допомогою ІПС та
TermWare є такі:
1) конструювання САА-схеми пос-
лідовного алгоритму за допомогою ІПС та
генерація відповідного коду цільовою мо-
вою програмування;
2) трансформація коду послідовно-
го циклу у функцію-ядро та генерація до-
даткових структур даних та макровизна-
чень за допомогою TerwWare;
3) конструювання САА-схеми шаб-
лону виклику ядра у системі ІПС та заміна
послідовного циклу на виклик ядра;
4) вставка коду, згенерованого в
TerwWare, у вихідну програму за допомо-
гою системи ІПС;
5) генерація паралельної програми
цільовою мовою програмування (C for
CUDA) на основі отриманої САА-схеми в
ІПС.
Приклад. Запропонований метод
застосовано для розпаралелювання послі-
довного циклу з глибиною гнізда рівною
чотирьом, що входить до складу програми
чисельного прогнозування погоди, розг-
лянутої в [5], а саме циклу інтерполяції
початкових даних у вузлах локальної сіт-
ки. Далі наведено фрагмент послідовної
САА-схеми, сконструйований в системі
ІПС.
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.321) * Rs * VS[h][k][j][i])";
"(Tp) := (TS[h][k][j][i] *
pow(1000.0 / HS[h][k][j][i],
2.0/7.0))";
"(Tv) := (Tp * (1.0 + 0.6078 *
QS[h][k][j][i]))";
"(Qc[h][k][j][i]) := (a - (0.5 * Tv +
(1.0 - Zmz[k]) * g * F_X[j][i] /
0.321))"
END OF LOOP
END OF LOOP
END OF LOOP
END OF LOOP;
На основі наведеної САА-схеми в
ІПС виконана генерація програмного коду
мовою С. За допомогою TerwWare здійс-
нене перетворення тіла послідовного цик-
лу у функцію-ядро (Kernel) та генерація
додаткових даних і макровизначень. В си-
стемі ІПС спроектовані САА-схеми шаб-
лону виклику ядра (складеного оператора
GPU) та функції-ядра (складеного опера-
тора Kernel), що наведені далі.
"GPU" ====
= "Declare a variable (threadNum) of
type (int) = (threadNum_def)";
"Declare a variable (threadsPerBlock) of
type (int) = (threadsPerBlock_def)";
Інструментальні засоби та середовища програмування
32
"Declare a variable (gIterNum) of
type (int) = (gIterNum_def)";
"Declare a variable (launchNum) of
type (int)";
(launchNum :=
ceiling(gIterNum, threadNum));
"Declare a variable (blocksPerGrid) of
type (int)";
(blocksPerGrid :=
ceiling(threadNum, threadsPerBlock));
"Allocate CPU memory for input and output
buffers (HI0, HI1, HO0, HO1)";
"Allocate GPU memory for input and
output buffers (DI0, DI1, DO0, DO1)";
FOR (t FROM 0 TO threadNum - 1)
LOOP
"Declare a variable (id) of type (int) =
(0*threadNum + t)";
"Copy parameters to input data buffer
(HI0)"
END OF LOOP;
"Copy variable (HI0) from CPU memory to
variable (DI0) of size (threadNum *
sizeof(inDataChunk)) on GPU";
FOR (t FROM 0 TO threadNum - 1)
LOOP
"Declare a variable (id) of type (int) =
(1*threadNum + t)";
"Copy parameters to input data buffer
(HI1)"
END OF LOOP;
FOR (e FROM 0 TO launchNum - 1)
LOOP
("Copy data from (HI0, HI1) to (buf)
according to (e)"
PARALLEL
(IF 'Even number (e)'
THEN
"Copy variable (HI1) from CPU
memory to variable (DI1) of size
(threadNum * sizeof(inDataChunk))
on GPU in the stream (stream1)
asynchronously";
Call_GPU_kernel(blocksPerGrid,
threadsPerBlock, 0, stream2)
(
"Kernel(DI0, DO0, threadNum)"
);
"Copy variable (DO1) from GPU
memory to variable (HO1) of size
(threadNum*sizeof(outDataChunk))
on CPU asynchronously in the
stream (stream3)"
ELSE
"Copy variable (HI0) from CPU
memory to variable (DI0) of size
(threadNum * sizeof(inDataChunk))
on GPU in the stream (stream1)
asynchronously";
Call_GPU_kernel(blocksPerGrid,
threadsPerBlock, 0, stream2)
(
"Kernel(DI1, DO1, threadNum)"
);
"Copy variable (DO0) from GPU
memory to variable (HO0) of size
(threadNum*sizeof(outDataChunk))
on CPU asynchronously in the stream
(stream3)"
END IF;
WAIT 'All threads completed work'
PARALLEL
"Copy data from (HO0, HO1) to (outbuf)
according to (e) and unpack outbuf"
))
END OF LOOP;
"Copy data from (HO0, HO1) to (outbuf)
according to (launchNum-1) and unpack
Інструментальні засоби та середовища програмування
33
outbuf";
"Free the memory for variable (DI0) on
GPU";
"Free the memory for variable (DO0) on
GPU";
"Kernel(inDataBuf, outDataBuf, threadNum)"
==== "Insert program code from the file
(kernel.cu)";
У вищенаведеному складеному
операторі GPU виклики функції-ядра ви-
конуються асинхронно за допомогою опе-
рації
Call_GPU_kernel(blocksPerGrid,
threadsPerBlock, 0, stream)
(
"Kernel(inDataBuf, outDataBuf,
threadNum)"
),
де blocksPerGrid – кількість блоків у сітці;
threadsPerBlock – кількість потоків у кож-
ному блоці; stream – черга виконання фу-
нкцій-ядер; Kernel – функція-ядро;
inDataBuf, outDataBuf – вхідний та вихід-
ний буфери даних, відповідно; threadNum
– кількість потоків. (Більш детально опе-
рації САА-М, призначені для формалізації
обчислень на GPU, розглядаються в робо-
ті [4]).
У складеному операторі Kernel за-
значено базисний оператор вставки про-
грамного коду функції-ядра мовою C з
файлу, згенерованого за допомогою
TerwWare:
"Insert program code from the file
(kernel.cu)"
Код згаданої функції-ядра має ви-
гляд:
__global__ void Kernel(
inDataChunk *inDataBuf,
outDataChunk *outDataBuf,
int threadNum)
{
LocalDataInit;
int myId = blockDim.x*blockIdx.x +
threadIdx.x; // cuda grid id
if (myId < threadNum)
{
a = (WZZ + inDataBuf[myId].a0 / 0.321)*
Rs * inDataBuf[myId].a1;
Tp = inDataBuf[myId].a2 * pow(1000.0 /
inDataBuf[myId].a3, 2.0/7.0);
Tv = Tp * (1.0 + 0.6078 *
inDataBuf[myId].a4);
outDataBuf[myId].a0 = a - (0.5 * Tv +
(1.0 - inDataBuf[myId].a5) * g *
inDataBuf[myId].a6 / 0.321);
}
}
Вставка згенерованих у TermWare
додаткових структур даних та макровизна-
чень у паралельну програму здійснюється
також за допомогою базисного оператора
вставки коду з файлу.
На основі побудованої паралельної
САА-схеми алгоритму в ІПС було викона-
но генерацію паралельної програми мовою
C for CUDA, результати виконання якої на
наведено у наступному розділі.
4. Експеримент
Для визначення ефективності пере-
твореної програми проведено експери-
мент, що складається із двох частин.
В першій частині здійснено порів-
няння результатів виконання програм,
отриманих за допомогою описаної систе-
ми перетворень та системи автоматичної
паралелізації Par4All, що використовує
поліедральний метод паралелізації циклів
і дозволяє генерувати програми для гра-
фічних процесорів на рівні коду CUDA в
Linux системах. Система Par4All має сут-
тєві обмеження. По-перше, ця система не
дозволяє працювати із обсягом даних, що
Інструментальні засоби та середовища програмування
34
перевищує обсяг пам’яті відеокарти. По-
друге, як виявилося при застосуванні
Par4All до експериментальної програми,
система не спроможна виконати обробку
вказівників, тому довелося відмовитись
від їх використання. При проведенні пер-
шої частини експерименту використову-
валися лише статичні масиви із залучен-
ням стеку великих обсягів (понад 2 Гб).
Експеримент виконано на операційній си-
стемі Ubuntu 16.04 із використанням ком-
пілятора nvcc 8.0.61.
В другій частині порівнюються ре-
зультати виконання перетвореної програ-
ми для однієї та для двох відеокарт.
Par4All не передбачає можливості викори-
стання більш ніж одного прискорювача
одночасно, тому в експерименті задіяна
лише система LoopRipper.
Експеримент проводився з викорис-
танням апаратної системи, оснащеної про-
цесором Intel Core i5-3570 (4 ядра,
3.8 ГГц), оперативною пам’яттю обсягом
8 Гб та відекартами NVIDIA Tesla M2050
(3 Гб оперативної пам’яті, ширина шини
передачі даних 384 біт, 448 ядер CUDA,
підключення через інтерфейс PCI Express
x16) та NVIDIA GeForce GTX 650Ti (1 Гб
оперативної пам’яті, ширина шини пере-
дачі даних 128 біт, 768 ядер CUDA, підк-
лючення через інтерфейс PCI Express x1).
Попри більшу кількість ядер, друга відео-
карта має повільнішу шину обміну даних,
до того ж, підключення через повільний
інтерфейс PCIex1 додатково обмежує
швидкість передачі, тому розподіл наван-
таження між відеокартами встановлено на
рівні 4:1. При такому розподілі час на ви-
конання обчислень у обох відеокарт приб-
лизно однаковий.
Масштабування дослідної задачі
здійснювалось шляхом вибору розміру ло-
кальної сітки і варіювалось у межах досту-
пної пам’яті центрального пристрою. Па-
раметр T (кількість потоків відеокарти, за-
діяних при виклику ядра) підібрано таким
чином, щоб мінімізувати час виконання
програми. Після виконання результати по-
слідовної та паралельної програм порів-
нювались між собою.
Як видно із графіка першого експе-
рименту (рис. 2), експериментальна систе-
ма випереджає Par4All, коефіцієнт віднос-
ного прискорення досягає 1.45. При ви-
конанні експерименту з двома відеокарта-
ми (рис. 3) використовувалось динамічне
Рис. 2. Графік першого експерименту
Інструментальні засоби та середовища програмування
35
Рис. 3. Графік другого експерименту
керування пам’яттю, експеримент викона-
но на операційній системі Windows 7 із
використанням компілятора nvcc 5.5.0.
Оскільки повна паралелізація за схемою із
копіюванням даних в окремих потоках
потребує трьох потоків на відеокарту, при
наявних чотирьох ядрах центрального про-
цесора для уникнення конкуренції між по-
токами копіювання даних виконувалось
послідовно із запуском ядра, тобто із залу-
ченням по одному потоку для кожної
відеокарти. При залученні додаткової
відеокарти зростання швидкості набли-
жається до 1.2 рази, що пропорційно роз-
поділу навантажень. Було виявлено відста-
вання програм, виконуваних в системі
Ubuntu, в порівнянні з системою Windows,
причини якого наразі не з’ясовано.
Висновки
Реалізовано програмний засіб пара-
лелізації циклів для оптимізації обчислень
за допомогою графічних прискорювачів,
що дозволяє в напіватоматичному режимі
здійснити перехід від послідовної до пара-
лельної програми. Проведено порівняння з
відомою автоматизованою системою пара-
лелізації Par4All, виявлено переваги роз-
робленої системи у швидкодії, можливості
обробки обсягів даних, що перевищують
обсяг пам’яті графічного прискорювача та
можливості залучення декількох приско-
рювачів одночасно.
1. Дорошенко А.Ю., Бекетов О.Г. Метод па-
ралелізації циклів сіткових обчислюваль-
них задач для графічних прискорювачів.
Проблеми програмування. 2017. № 1.
С. 59–66.
2. PIPS: Automatic Parallelizer and Code
Transformation Framework [Електронний
ресурс]. Режим доступу до ресурсу:
http://pips4u.org/
Інструментальні засоби та середовища програмування
36
3. Doroshenko A., Shevchenko R. A rewriting
framework for rule-based programming
dynamic applications. Fundamenta
Informaticae. 2006. Vol. 72, N 1–3.
P. 95–108.
4. Андон Ф.И., Дорошенко А.Е., Жереб К.А.,
Шевченко Р.С., Яценко Е.А. Методы
алгебраического программирования: фор-
мальные методы разработки параллель-
ных программ. Киев: Наукова думка,
2017. 440 с.
5. Дорошенко А.Ю., Бекетов О.Г., Прусов
В.А., Тирчак Ю.М., Яценко О.А. Формалі-
зоване проектування та генерація парале-
льної програми чисельного моделювання
погоди. Проблеми програмування. 2014.
№ 2–3. С. 72–81.
References
1. Doroshenko A.Yu., Beketov O.G. (2017)
Method of parallelization of loops for grid
calculation problems on GPU accelerators.
Problems in programming. (1). P. 59–66. (in
Ukrainian).
2. PIPS: Automatic Parallelizer and Code
Transformation Framework [Online].
Available from: http://pips4u.org/
3. Doroshenko A. & Shevchenko R. (2006)
A rewriting framework for rule-based
programming dynamic applications.
Fundamenta Informaticae. 72 (1-3).
P. 95–108.
4. Andon P.I. et al. (2017) Methods of algebraic
programming: formal methods of parallel
program development. Kyiv: Naukova
dumka. (in Russian).
5. Doroshenko A.Yu., Beketov O.G.,
Prusov V.A., Tyrchak Yu.M. & Yat-
senko 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).
Одержано 10.10.2017
Про авторів:
Дорошенко Анатолій Юхимович,
доктор фізико-математичних наук,
професор, завідувач відділу теорії
комп’ютерних обчислень
Інституту програмних систем
НАН України,
професор кафедри автоматики
і управління в технічних системах НТУУ
"КПІ імені Ігоря Сікорського".
Кількість наукових публікацій в
українських виданнях – понад 150.
Кількість наукових публікацій в
зарубіжних виданнях – понад 50.
Індекс Хірша – 5.
http://orcid.org/0000-0002-8435-1451,
Яценко Олена Анатоліївна,
кандидат фізико-математичних наук,
старший науковий співробітник
Інституту програмних систем
НАН України.
Кількість наукових публікацій в
українських виданнях – 36.
Кількість наукових публікацій в
зарубіжних виданнях – 12.
http://orcid.org/0000-0002-4700-6704,
Бекетов Олексій Геннадійович,
молодший науковий співробітник
Інституту програмних систем
НАН України.
Кількість наукових публікацій в
українських виданнях – 11.
Кількість наукових публікацій в
зарубіжних виданнях – 1.
http://orcid.org/0000-0003-4715-5053.
Місце роботи авторів:
Інститут програмних систем
НАН України,
03187, м. Київ-187,
проспект Академіка Глушкова, 40.
Тел.: (044) 526 3559.
E-mail: doroshenkoanatoliy2@gmail.com,
oayat@ukr.net,
beketov.oleksii@gmail.com
mailto:oayat@ukr.net
|