Method of parallelization of loops for grid calculation problems on GPU accelerators

The formal parallelizing transformation of a nest of calculation loop for SIMD architecture devices, particularly for graphics processing units applying CUDA technology and heterogeneous clusters is developed. Procedure of transition from sequential to parallel algorithm is described and illustrated...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Doroshenko, А.Yu., Beketov, O.G.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	automatic parallelization loop optimization general-purpose computing on graphics processing units UDC 681.3
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/222
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-222
record_format	ojs
resource_txt_mv	ppisoftskievua/1c/7b3d9520f8ff5089e98ed5c65b479e1c.pdf
spelling	pp_isofts_kiev_ua-article-2222024-04-28T11:56:41Z Method of parallelization of loops for grid calculation problems on GPU accelerators Метод распараллеливания циклов сеточных вычислительных задач для графических ускорителей Метод паралелізації циклів сіткових обчислювальних задач для графічних прискорювачів Doroshenko, А.Yu. Beketov, O.G. automatic parallelization; loop optimization; general-purpose computing on graphics processing units UDC 681.3 автоматизированные методы параллелизации; оптимизация циклов; вычисления общего назначения на графических процессорах УДК 681.3 методи паралелізації; оптимізація циклів; обчислення загального призначення на графічних процесорах УДК 681.3 The formal parallelizing transformation of a nest of calculation loop for SIMD architecture devices, particularly for graphics processing units applying CUDA technology and heterogeneous clusters is developed. Procedure of transition from sequential to parallel algorithm is described and illustrated. Serialization of data is applied to optimize processing of large volumes of data. The advantage of the suggested method is its applicability for transformation of data which volumes exceed the memory of operating device. The experiment is conducted to demonstrate feasibility of the proposed approach. Technique presented in the provides the basis for further practical implementation of the automated system for parallelizing of nested loops.Problems in programming 2017; 1: 59-66 Разработано формальное преобразование гнезда вычислительного цикла, позволяющее осуществить переход от последовательного алгоритма к параллельному, ориентированное на выполнение на устройствах с SIMD архитектурой, в частности, на графическом ускорителе с использованием технологии CUDA и на гетерогенных кластерах. Описана и проиллюстрирована процедура перехода от последовательного к параллельному алгоритму. Для оптимизации обработки больших объемов данных использована процедура сериализации данных. Преимуществом предложенного метода является то, что он позволяет осуществлять преобразование данных, объем которых превышает объем памяти исполняющего устройства. Проведен эксперимент над задачей метеорологического прогнозирования погоды для демонстрации возможностей разработанного подхода. Методика, предложенная в данной работе, закладывает основу для дальнейшей практической реализации автоматизированной системы распараллеливания вложенных циклов.Problems in programming 2017; 1: 59-66 Розроблено формальне перетворення гнізда обчислювального циклу, що дозволяє здійснити перехід від послідовного алгоритму до паралельного, орієнтованого на виконання на пристрої з SIMD архітектурою, зокрема, на графічному прискорювачі із використанням технології CUDA та на гетерогенних кластерах.Problems in programming 2017; 1: 59-66 Інститут програмних систем НАН України 2018-11-20 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/222 10.15407/pp2017.01.059 PROBLEMS IN PROGRAMMING; No 1 (2017); 59-66 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2017); 59-66 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2017); 59-66 1727-4907 10.15407/pp2017.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/222/215 Copyright (c) 2018 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:56:41Z
collection	OJS
language	Ukrainian
topic	automatic parallelization loop optimization general-purpose computing on graphics processing units UDC 681.3
spellingShingle	automatic parallelization loop optimization general-purpose computing on graphics processing units UDC 681.3 Doroshenko, А.Yu. Beketov, O.G. Method of parallelization of loops for grid calculation problems on GPU accelerators
topic_facet	automatic parallelization loop optimization general-purpose computing on graphics processing units UDC 681.3 автоматизированные методы параллелизации оптимизация циклов вычисления общего назначения на графических процессорах УДК 681.3 методи паралелізації оптимізація циклів обчислення загального призначення на графічних процесорах УДК 681.3
format	Article
author	Doroshenko, А.Yu. Beketov, O.G.
author_facet	Doroshenko, А.Yu. Beketov, O.G.
author_sort	Doroshenko, А.Yu.
title	Method of parallelization of loops for grid calculation problems on GPU accelerators
title_short	Method of parallelization of loops for grid calculation problems on GPU accelerators
title_full	Method of parallelization of loops for grid calculation problems on GPU accelerators
title_fullStr	Method of parallelization of loops for grid calculation problems on GPU accelerators
title_full_unstemmed	Method of parallelization of loops for grid calculation problems on GPU accelerators
title_sort	method of parallelization of loops for grid calculation problems on gpu accelerators
title_alt	Метод распараллеливания циклов сеточных вычислительных задач для графических ускорителей Метод паралелізації циклів сіткових обчислювальних задач для графічних прискорювачів
description	The formal parallelizing transformation of a nest of calculation loop for SIMD architecture devices, particularly for graphics processing units applying CUDA technology and heterogeneous clusters is developed. Procedure of transition from sequential to parallel algorithm is described and illustrated. Serialization of data is applied to optimize processing of large volumes of data. The advantage of the suggested method is its applicability for transformation of data which volumes exceed the memory of operating device. The experiment is conducted to demonstrate feasibility of the proposed approach. Technique presented in the provides the basis for further practical implementation of the automated system for parallelizing of nested loops.Problems in programming 2017; 1: 59-66
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/222
work_keys_str_mv	AT doroshenkoayu methodofparallelizationofloopsforgridcalculationproblemsongpuaccelerators AT beketovog methodofparallelizationofloopsforgridcalculationproblemsongpuaccelerators AT doroshenkoayu metodrasparallelivaniâciklovsetočnyhvyčislitelʹnyhzadačdlâgrafičeskihuskoritelej AT beketovog metodrasparallelivaniâciklovsetočnyhvyčislitelʹnyhzadačdlâgrafičeskihuskoritelej AT doroshenkoayu metodparalelízacííciklívsítkovihobčislûvalʹnihzadačdlâgrafíčnihpriskorûvačív AT beketovog metodparalelízacííciklívsítkovihobčislûvalʹnihzadačdlâgrafíčnihpriskorûvačív
first_indexed	2024-09-25T04:02:51Z
last_indexed	2024-09-25T04:02:51Z
_version_	1818527346994446336
fulltext	Моделі та засоби паралельних і розподілених програм © А.Ю. Дорошенко, О.Г. Бекетов, 2017 ISSN 1727-4907. Проблеми програмування. 2017. № 1 59 УДК 681.3 А.Ю. Дорошенко, О.Г. Бекетов МЕТОД ПАРАЛЕЛІЗАЦІЇ ЦИКЛІВ СІТКОВИХ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ДЛЯ ГРАФІЧНИХ ПРИСКОРЮВАЧІВ Розроблено формальне перетворення гнізда обчислювального циклу, що дозволяє здійснити перехід від послідовного алгоритму до паралельного, орієнтованого на виконання на пристрої з SIMD архітекту- рою, зокрема, на графічному прискорювачі із використанням технології CUDA та на гетерогенних кла- стерах. Ключові слова: методи паралелізації, оптимізація циклів, обчислення загального призначення на графі- чних процесорах. Вступ Сучасні обчислювальні комплекси мають гетерогенну архітектуру і включа- ють як багатоядерні процесори, так і гра- фічні прискорювачі. Проте велику кіль- кість існуючих програмних засобів ство- рено для послідовного виконання на од- ноядерних машинах. Крім того, створення нових програмних засобів здебільшого проходить через етап послідовної програ- ми. Таким чином, задача автоматичної паралелізації має велику актуальність. В більшості обчислювальних задач значну частину апаратних ресурсів витрачають обчислення, що здійснюються всередині циклів, тому використання автоматичної паралелізації на рівні потоків найбільш ефективне саме для них. Так, наприклад, більшість задач математичної фізики розв’язуються чисельними методами з ви- користанням сіткових обчислень. До ви- никнення циклів призводять різницеві схеми, метод скінченних елементів, зага- лом, задачі, що вимагають виконання операцій над матрицями даних. Типовий для сіткової задачі обчислювальний цикл має вигляд: 0 0for i I 1 1for i I ... N Nfor i I 0( , ,..., );NF data i i (1) де data – множина даних, що обробляють- ся, 0 1, ,..., NI I I – множини значень індек- сів 0 1, ,..., Ni i i , N+1 – глибина вкладеності циклу, data – множина даних, 0: ( , ,..., )NF data I I data – відобра- ження, що здійснює перетворення даних. Цикли такого роду у випадку відсутності залежності між вхідними та вихідними даними природним чином розкладаються на паралельні потоки обчислень, оскільки на різних ітераціях цикл повторює одно- манітні операції над різними даними. Par4All [1] – програмний засіб, що дозво- ляє на рівні коду в автоматичному режимі здійснити перехід від послідовних про- грам, написаних мовами С та Fortran, до паралельних для різних апаратних плат- форм, в тому числі графічного прискорю- вача із використанням CUDA API. Par4All використовує механізм сіток для знижен- ня глибини вкладеності циклів, проте не надає можливості обробляти обсяги да- них, що перевищують обсяг пам’яті прис- корювача, а також використовувати гете- рогенні обчислювальні кластери. 1. Зміна індексації ітераторів циклу Розглянемо складений цикл глиби- ною N+1, що має вигляд 0 00..#for i I Моделі та засоби паралельних і розподілених програм 60 1 10..#for i I ... 0..#N Nfor i I 0( , , ,..., ),NF in out i i (2) де in – множина вхідних даних, out – множина вихідних даних, причому перет- ворення 0: ( , ,..., )NF in I I out таке, що для кожного набору індексів 0( ,..., )Ni i із гіперкуба 0 ... NI I  виконується умова in out  (), а символом октоторпа позначено потужність відповідної множи- ни. Таким чином, для проведення обчис- лень цикл (2) здійснює 0#( ... )NC I I   викликів F. Не обмежуючи загальності, цикл вигляду (2) можна вважати рівноси- льним циклу (1). Пронумеруємо елементи гіперкуба 0 ... NI I  наступним чином. Нехай еле- мент, що відповідає набору індексів 0 1( , ,..., )Ni i i , має номер 1 0 1 0 # kN k m k m i i I       . Введемо відображення ( )f k , 00 #( ... )Nk I I    : 1 0 1 1 ( ) # # , N Nk j l j j l j j k f k D i I I                  0,k  1 0 1 1 (0) # mod # N Nk j l j j l j j k f D i I I                  , 0 N k k D I    . Відображення ( )f k за номером елемента гіперкуба 0 ... NI I  відновлює відповід- ний індекс ki . Розглянемо цикл такого ви- гляду: 0..for k D 0..for j N ' ( );ji f j ' ' 0( , , ,..., ).NF in out i i (3) При проходженні зовнішнього циклу в (3) індекси k i пробігають ті самі значення, що і в (2), тому цикли (2) та (3) є рівносиль- ними. Зафіксуємо 0 d N  і введемо ві- дображення ( , )g k id , 0 k N  , 1 0 0 # d j j id I      : 1 11 0 1 1 ( , ) # # , d dk j l j j l j j k g k e id i I I                   1,k d  12 1 0 1 ( 1, ) # # dd j l d j l j g d e id i I I                 . Відображення ( , )g k e побудоване таким чином, що при проходженні наступного циклу індекси ki пробігають ті самі зна- чення, що і в (2): 1 0 0.. # d j j for e I     0.. # N m m d for id I    .. for k d N ' ( );ji f k 0.. 1for k d  ' ( , );ki g k id ' ' 0( , , ,..., ),NF in out i i (4) тому останній наведений цикл (4) також рівносильний циклу (2). При цьому ітера- тори циклів, що мають глибину меншу, ніж d , лишаються сталими впродовж од- нієї ітерації внутрішнього циклу. 2. Підготовка початкових даних Оскільки на F діє обмеження (), операції над вхідними даними є незалеж- ними, і можуть бути виконані паралель- Моделі та засоби паралельних і розподілених програм 61 ними потоками. Припустимо, що F таке, що не містить умовних переходів, тоді рі- зні потоки будуть здійснювати однотипні операції над різними даними і для вико- нання обчислень доцільно використовува- ти апаратну SIMD платформу. Пронуме- руємо потоки символом [0, ]id D . У ви- падку (3) кожен із потоків виконує окрему гілку зовнішнього циклу. У випадку (4) зовнішній цикл здійснюється окремим ке- руючим потоком. Таким чином, за допо- могою заміни індексів циклу здійснюєть- ся перехід до багатопоточного алгоритму, при цьому не змінюючи F. Крім того, у випадку, коли в почат- ковому алгоритмі програми використо- вуються багатовимірні масиви даних, вра- ховуючи той факт, що читання із пам’яті відбувається швидше із лінійних ділянок пам’яті, для оптимізації обробки великих обсягів даних доцільно використовувати перетворення серіалізації, що справедли- во навіть для SISD пристроїв, не врахо- вуючи витрат, необхідних для серіалізації даних. 3. Загальна схема перетворення алгоритму Перехід від послідовного до пара- лельного алгоритму програми здійсню- ється у кілька етапів. Загальна схема пе- реходу виглядає так. 1. Підготовчий етап. Полягає у зве- денні вихідного алгоритму до циклу ви- гляду (2). При цьому слід позбавитись міжітераційних залежностей. На цьому етапі можуть використовуватись розбиття циклів, їх перестановка, афінні перетво- рення, попередній розрахунок даних то- що. 2. Визначення обсягу даних, що обробляються та кількості незалежних операцій, що виконуються всередині ок- ремих циклів гнізда. Ці параметри мож- ливо визначити за умови відсутності умо- вних переходів в обчисленнях. 3. Визначення параметра d згідно апаратних можливостей виконуючого пристрою. Параметр d обирається та- ким чином, щоб, з одного боку, обсяг да- них, що обробляється циклом глибини d , не перевищував обсяг пам’яті викону- ючого пристрою, і з іншого, щоб най- більш повно задіяти наявні апаратні потоки пристрою. 4. Заміна ітераторів згідно правил, описаних в розділі 1. При цьому програма залишається послідовною, змінюється лише спосіб індексації даних. Після цього перетворення залишаються лише два цик- ли – зовнішній (керуючий) та внутрішній. 5. Створення модуля серіалізації вхідних даних, який підготовляє порцію даних, що буде оброблятися поточною ітерацією керуючого циклу. 6. Створення модуля десеріалізації вихідних даних. Модуль приймає буфер вихідних даних, отриманих після вико- нання обчислень на поточній ітерації, та передає дані для подальшого викорис- тання. 7. Перехід до буферної схеми пере- несення даних. На цьому етапі залучають- ся серіалізатор та десеріалізатор, що ви- кликаються до початку та після виконан- ня внутрішнього циклу відповідно. Змінні внутрішнього циклу переадресовуються на відповідні ділянки вхідного та вихідно- го буферів даних. 8. Створення ядра, тобто частини програми, що буде безпосередньо перене- сена на виконуючий пристрій. Ядро є фу- нкцією, що приймає буфер вхідних даних та номер ітерації зовнішнього циклу, та повертає буфер вихідних даних. Функціо- нально ядро має виконувати ті самі опе- рації, що і внутрішній цикл. Ітератор id внутрішнього циклу замінюється номером потоку виконуючого пристрою. 9. Залучення ядра. Внутрішній цикл замінюється на директиву виклику ядра. Також додаються операції перенесення вхідного буферу даних до виконуючого пристрою та повернення вихідного буфе- ру даних назад в центральний обчислюва- льний пристрій. 10. Винесення роботи із буферними даними та з графічним прискорювачем в окремі потоки керуючого пристрою з ме- тою уникнення простою виконуючого пристрою. Моделі та засоби паралельних і розподілених програм 62 Проміжні етапи 4, 7, а також фінальні 9, 10 потребують тестових випробувань, які проводяться за допомогою засобів пе- ревірки коректності результатів виконан- ня обчислень. Наприклад, це може бути обробка тестового набору даних і порів- няння із наперед відомими результатами. Етап 5 може бути здійснений автомати- зовано за допомогою техніки переписува- них правил [2], що дозволить суттєво спростити здійснення перетворень. Для здійснення перетворень на етапі 9 доціль- но задіяти Інтегрований інструментарій Проектування та Синтезу програм (ІПС) [3], що зокрема був налаштований на ро- боту із CUDA API [4, 5]. Роль параметра d циклу (4) поля- гає в тому, що він визначає глибину, по- чинаючи з якої цикли виконуються безпо- середньо виконуючим пристроєм. Таким чином, d встановлює кількість викликів та розподіл навантаження обчислюваль- ного ядра внутрішнього циклу. Така тех- ніка надає перевагу в тому разі, якщо об’єм даних, що обробляються, переви- щує ємність обчислювального пристрою. При значеннях 0 d N  цикл (2) розби- вається на 1 0 d i i P N     частин, кожна з яких оброблюється окремо. Відповідно, керу- ючий пристрій через змінну Pe 0 пе- редає виконуючому пристою номер ітера- ції, та необхідну на даній ітерації порцію вхідних даних. Порції вхідних даних під- готовлюються окремим потоком. В свою чергу, обчислюючий пристрій за допомо- гою відображень ,f g із e відновлює ін- декси елементів поданої порції даних, що відповідають ітерації зовнішнього керую- чого циклу. Таким чином, при значенні 0d  всі операції у циклі (2) будуть здій- снюватись виконуючим пристроєм за один виклик ядра, і всі оброблювані дані мають бути передані виконуючому при- строю одночасно, і тоді випадок (4) прий- має вигляд (3). Проілюструємо наведений ланцюжок перетворень на прикладі. Розглянемо частковий випадок циклу вигляду (2) глибини 5: 0.. for l L 0.. for m M 0.. for n N 0.. for k K 0.. for j J ( , );lmnkj lmnkjF i o де , , , , L M N K J – натуральні числа, ,lmnkj lmnkji o – елементи множин вхідних та вихідних даних I, O відповідно. Обсяг вхідних даних рівний обсягу вихідних даних для кожного із циклів і становить L M N K J s     , M N K J s    , N K J s   , K J s  , J s починаючи із зо- внішнього циклу відповідно; s позначає розмір елемента даних. Оберемо параметр d рівним двом та виконаємо переіндекса- цію даних. Тоді останній цикл набуде на- ступного вигляду: 0.. for e L M  0.. for id N K J   / ;l e T ;m e T ( ) / ( ); n id l M N K J m N K J K J             ( ) / ; k id l M N K J m N K J n K J J               ( ) ; j id l M N K J m N K J n K J k J J                 ( , ).lmnkj lmnkjF i o Відображення-серіалізатор ( , , )Serialize I e inbuf будується наступним чином: / ;l e T ;m e T 0.. for n N 0.. for k K Моделі та засоби паралельних і розподілених програм 63 0.. for j J ;index n K J k J j      ;i nd e x l mnk jinbuf i де inbuf – буфер вхідних даних. Дані вмі- щуються у єдиний буфер, що згодом дасть зручну можливість переносити дані в ви- конуючий пристрій однією операцією пе- ренесення. Десеріалізатор ( , , )Deserialize e outbuf O будується аналогічно серіалізатору: / ;l e T ;m e T 0..for n N 0..for k K 0.. for j J ;index n K J k J j      ;l mnk j i nd e xo outbuf де outbuf – буфер вихідних даних. Після впровадження серіалізатора та десеріалізатора цикл набуває наступно- го вигляду: 0.. for e L M  ( , , );Serialize I e inbuf 0.. for id N K J   / ;l e T ;m e T ( ) / ( ); n id l M N K J m N K J K J             ( ) / ; k id l M N K J m N K J n K J J               ( ) ; j id l M N K J m N K J n K J k J J                 ( , );nkj nkjF inbuf outbuf ( , , ).Deserialize e outbuf O Ядро ( , , )Kernel e inbuf outbuf вико- нує ті самі операції, що і внутрішній цикл: ();id threadId if id N K J   / ;l e T ;m e T ( ) / ( ); n id l M N K J m N K J K J             ( ) / ; k id l M N K J m N K J n K J J               ( ) ; j id l M N K J m N K J n K J k J J                 ( , ),nkj nkjF inbuf outbuf де процедура ()threadId повертає номер потоку. Таким чином, після всіх перетво- рень вихідний цикл набуває остаточного вигляду: 0.. for e L M  ( , , );Serialize I e inbuf ' ( , );CopyInput inbuf inbuf ' ' ( , , );Kernel e inbuf outbuf ' ( , ut );CopyOutput outbuf o buf ( , , );Deserialize e outbuf O де процедури CopyInput та CopyOutput переносять буфер вхідних та буфер вихід- них даних від керуючого до обчислюва- льного пристрою та в зворотному порядку відповідно. Процедуру Serialize доцільно винести в окремий потік керуючого при- строю. Для цього створюється окремий додатковий буфер, і робота Serialize ви- конується почергово: 0 ( , , );Serialize I e inbuf 0.. for e L M  0 :thread Моделі та засоби паралельних і розподілених програм 64 ( 1) 2 ( , , );eSerialize I e inbuf  1 :thread ' 2 ( , );eCopyInput inbuf inbuf ' ' ( , , );Kernel e inbuf outbuf ' 2 ( , ut );eCopyOutput outbuf o buf 3 :thread ( 1) 2 ( , , ).eDeserialize e outbuf O Крім того, для проведення обчис- лень можливо залучити гетерогенний кла- стер, до складу якого входять кілька SIMD пристроїв. В такому випадку окремі ітерації викликів ()Kernel керуватимуться окремими потоками керуючого пристрою. 4. GPU та технологія CUDA Як обчислювальний пристрій бу- демо використовувати графічний приско- рювач. В такому випадку керуючий потік виконується на CPU, а решта потоків пе- реносяться на GPU та виконуються в ме- жах ядра. Для роботи з графічним прис- корювачем будемо використовувати про- грамно-апаратну технологію CUDA [6], що дозволяє використовувати GPU як об- числювальний пристрій. CUDA відрізня- ється від інших GPGPU технологій тим, що надає безпосередній доступ до при- строю через програмний інтерфейс, що дозволяє гнучко керувати окремими пото- ками та всіма рівнями пам’яті графічного прискорювача. Крім того, саме для архі- тектури CUDA створюються спеціалізо- вані графічні прискорювачі для наукових та технічних обчислень загального приз- начення [7]. CUDA накладає обмеження на розмірність масивів даних, що не має перевищувати трьох. Це обмеження оми- нається на етапі серіалізації даних. Про- блема, що виникає у тому випадку, якщо необхідна для проведення обчислень кі- лькість потоків більша, ніж кількість апа- ратних потоків графічного прискорювача, автоматично оминається механізмом сіток CUDA. Таким чином, при використанні графічних прискорювачів, що дозволяють використання технології CUDA, основним обмеженням виступає обсяг пам’яті гра- фічного прискорювача. 5. Експеримент Проведено експеримент із циклом, що був взятий у задачі прогнозування погоди [8, 9]. Гніздо циклу складене із чо- тирьох вкладених циклів і обробляє чоти- ривимірний масив даних числових зна- чень типу float. Навантаження масштабу- ється шляхом зміни розмірності задачі. Було здійснено перехід від послідовної реалізації циклу до паралельної із засто- суванням описаної методології та порів- няно часові показники для різного масш- табу навантаження та різних значень па- раметра d. Випробування проводились із ви- користанням процесора i5-3570 (у 64-бітному режимі) та графічного прис- корювача GeForce GTX 650 Ti, що має на- ступні характеристики:  768 stream-процесори (CUDA- ядра), базова частота 928 MHz;  обсяг глобальної пам’яті 1024 Mb;  базова частота пам’яті 5400 MHz. Обсяг пам’яті ОЗП становив 8 Гб. При випробуваннях досліджено поведінку послідовної та паралельної програм при фіксованому значенні пара- метра d , та зміні розмірності задачі, що відповідає зміні кількості викликів ядра при сталому навантаженні на нього, та при зміні розмірності задачі, що відпові- дає зміні навантаження на один виклик ядра. Графік на рисунку показує залеж- ність часу виконання обчислень від об- сягу даних для 1d  , при сталому наван- таженні на ядро. При цьому відносне прискорення є сталим та становить близь- ко 4,2. Моделі та засоби паралельних і розподілених програм 65 Рисунок. Графік залежності часу виконання послідовної та паралельної програм від обсягу даних, що обробляються Висновки Побудовано перетворення алгори- тму виконання складеного циклу, що до- зволяють здійснити перехід від послідов- ного до паралельного алгоритму прове- дення обчислень, що дозволяє залучення гетерогенної обчислювальної платформи. Перевагою застосування методу є те, що він дозволяє здійснювати перетворення над даними, обсяг яких перевищує обсяг пам’яті виконуючого пристрою, а також є автоматизовним. Проведено експеримент, що підтверджує доцільність запропонова- ного підходу. Таким чином, розроблено основу для подальшої практичної реаліза- ції автоматизованої системи паралелізації вкладених циклів. 1. Дорошенко А.Е., Шевченко Р.С. Система символьных вычислений для програ- ммирования динамических приложений. Проблеми програмування. 2005. № 4. С. 718–727. 2. Яценко Е.А. Интеграция инструменталь- ных средств алгебры алгоритмов и переписывания термов для разработки эффективных параллельных программ. Проблеми програмування. 2013. № 2. С. 62–70. 3. Дорошенко А.Ю., Бекетов О.Г., Прусов В.А., Тирчак Ю.М., Яценко О.А. Формалі- зоване проектування та генерація парале- льної програми чисельного прогнозування погоди. Проблеми програмування. 2014. № 2–3. С. 72–81. 4. Дорошенко А.Ю., Бекетов О.Г., Іванів Р.Б., Іовчев В.О., Мироненко І.О., Яценко О.А. Автоматизована генерація паралельних програм для графічних прискорювачів на основі схем алгоритмів. Проблеми програ- мування. 2015. № 1. С. 19–28. Моделі та засоби паралельних і розподілених програм 66 5. CUDA [Електронний ресурс] – Режим дос- тупу до ресурсу: http://www.nvidia.com/object/cuda_home_ne w.html. 6. TESLA [Електронний ресурс] – Режим до- ступу до ресурсу: http://www.nvidia.com/object/tesla- servers.html. 7. PIPS: Automatic Parallelizer and Code Transformation Framework [Електронний ресурс] – Режим доступу до ресурсу: http://pips4u.org/. 8. Прусов В.А., Дорошенко А.Ю. Моделюван- ня природних і техногенних процесів в ат- мосфері. Київ: Наукова думка. 2006. 542 с. 9. Прусов В.А., Сніжко С.І. Математичне мо- делювання атмосферних процесів. Київ: Ніка-Центр. 2005. 496 с. References 1. Doroshenko, A.Yu. & Shevchenko R.S. (2005) Symbolic computation system for dynamical application programming. Problems in programming. (4). P. 718–727. (in Russian) 2. Yatsenko, O.A. (2013) Integration of Software Tools of Algebra of Algorithms and Rewriting Terms for Development of Effective Parallel programs. Problems in programming. (2). P. 62–70. (in Russian). 3. Doroshenko, A.Yu., Beketov, O.G , Prusov, V.A., Tyrchak, Yu.M. & Yatsenko, O.A. (2014) Formalized design and generation of parallel programs for numerical weather forecast. Problems in programming. (2-3). P. 72–81. (in Ukrainian). 4. Doroshenko, А.Yu., Beketov, O.G., Ivaniv, R.B., Iovchev, V.O., Mironenko, I.O. & Yatsenko, O.A. (2015) Automated generation of parallel programs for graphics processing units based on algorithm schemes. Problems in programming. (1). P. 19–28. (in Ukrainian). 5. CUDA [Online] – Available from: http://www.nvidia.com/object/cuda_home_ne w.html. 6. TESLA [Online] – Available from: http://www.nvidia.com/object/tesla- servers.html. 7. PIPS: Automatic Parallelizer and Code Transformation Framework [Online] – Available from: http://pips4u.org/. 8. Prusov V.A. & Doroshenko A.Yu. (2006) Simulation of natural and anthropogenic processes in the atmosphere. Kyiv: Naukova Dumka. (in Ukrainian). 9. Prusov, V.A. & Snizhko, S.I. (2005) Mathematical modeling of atmospheric processes. Kyiv: NikaTsentr. (in Ukrainian). Одержано 01.02.2017 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп’ютерних обчислень, професор кафедри автоматики та управління в технічних системах НТУ України “КПІ”. Кількість наукових публікацій в українських виданнях – понад 200. Кількість наукових публікацій в зарубіжних виданнях – понад 50. Індекс Хірша – 5. http://orcid.org/0000-0002-8435-1451, Бекетов Олексій Геннадійович, молодший науковий співробітник. Кількість наукових публікацій в українських виданнях – 10. Кількість наукових публікацій в зарубіжних виданнях – 1. http://orcid.org/0000-0003-4715-5053. Місце роботи авторів: Інститут програмних систем НАН України. проспект Академіка Глушкова, 40. 03187, Київ, НТУ України «КПІ» Тел.: (044) 526 3559. E-mail: dor@isofts.kiev.ua, beketov.oleksii@gmail.com mailto:dor@isofts.kiev.ua

Method of parallelization of loops for grid calculation problems on GPU accelerators

Репозитарії

Схожі ресурси