Formalized design and synthesis of parallel programs for videographic shortcuts

Prombles in programming 2013; 3: 38-46

Збережено в:

Бібліографічні деталі
Дата:	2025
Автори:	Doroshenko, A.Yu., Beketov, O.G., Zhereb, K.A., Yatsenko, О.A.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2025
Теми:	UDC 681.3
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/751
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-751
record_format	ojs
resource_txt_mv	ppisoftskievua/9e/5a5bd89572d97993d00ae1eab365939e.pdf
spelling	pp_isofts_kiev_ua-article-7512025-06-21T15:30:49Z Formalized design and synthesis of parallel programs for videographic shortcuts Формалізоване проектування та синтез паралельних програм для відеографічних прискорювачів Doroshenko, A.Yu. Beketov, O.G. Zhereb, K.A. Yatsenko, О.A. UDC 681.3 УДК 681.3 Prombles in programming 2013; 3: 38-46 Проведено налаштування алгеброалгоритмічного інструментарію на формалізоване проектування та синтез програм, що використовують відеографічні прискорювачі. Продемонстрована ефективність використання багатопроцесорних графічних прискорювачів для обчислювальних задач на прикладі спеціально розробленого паралельного алгоритму чисельного інтегрування задачі N тіл.Prombles in programming 2013; 3: 38-46 Інститут програмних систем НАН України 2025-06-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/751 PROBLEMS IN PROGRAMMING; No 3 (2013); 38-46 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2013); 38-46 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2013); 38-46 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/751/803 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-06-21T15:30:49Z
collection	OJS
language	Ukrainian
topic	UDC 681.3
spellingShingle	UDC 681.3 Doroshenko, A.Yu. Beketov, O.G. Zhereb, K.A. Yatsenko, О.A. Formalized design and synthesis of parallel programs for videographic shortcuts
topic_facet	UDC 681.3 УДК 681.3
format	Article
author	Doroshenko, A.Yu. Beketov, O.G. Zhereb, K.A. Yatsenko, О.A.
author_facet	Doroshenko, A.Yu. Beketov, O.G. Zhereb, K.A. Yatsenko, О.A.
author_sort	Doroshenko, A.Yu.
title	Formalized design and synthesis of parallel programs for videographic shortcuts
title_short	Formalized design and synthesis of parallel programs for videographic shortcuts
title_full	Formalized design and synthesis of parallel programs for videographic shortcuts
title_fullStr	Formalized design and synthesis of parallel programs for videographic shortcuts
title_full_unstemmed	Formalized design and synthesis of parallel programs for videographic shortcuts
title_sort	formalized design and synthesis of parallel programs for videographic shortcuts
title_alt	Формалізоване проектування та синтез паралельних програм для відеографічних прискорювачів
description	Prombles in programming 2013; 3: 38-46
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/751
work_keys_str_mv	AT doroshenkoayu formalizeddesignandsynthesisofparallelprogramsforvideographicshortcuts AT beketovog formalizeddesignandsynthesisofparallelprogramsforvideographicshortcuts AT zherebka formalizeddesignandsynthesisofparallelprogramsforvideographicshortcuts AT yatsenkooa formalizeddesignandsynthesisofparallelprogramsforvideographicshortcuts AT doroshenkoayu formalízovaneproektuvannâtasintezparalelʹnihprogramdlâvídeografíčnihpriskorûvačív AT beketovog formalízovaneproektuvannâtasintezparalelʹnihprogramdlâvídeografíčnihpriskorûvačív AT zherebka formalízovaneproektuvannâtasintezparalelʹnihprogramdlâvídeografíčnihpriskorûvačív AT yatsenkooa formalízovaneproektuvannâtasintezparalelʹnihprogramdlâvídeografíčnihpriskorûvačív
first_indexed	2025-07-17T10:03:31Z
last_indexed	2025-07-17T10:03:31Z
_version_	1838410431740248064
fulltext	Моделі та засоби паралельних і розподілених програм © А.Ю. Дорошенко, О.Г. Бекетов, К.А. Жереб, О.А. Яценко, 2013 38 ISSN 1727-4907. Проблеми програмування. 2013. № 3 УДК 681.3 А.Ю. Дорошенко, О.Г. Бекетов, К.А. Жереб, О.А. Яценко ФОРМАЛІЗОВАНЕ ПРОЕКТУВАННЯ ТА СИНТЕЗ ПАРАЛЕЛЬНИХ ПРОГРАМ ДЛЯ ВІДЕОГРАФІЧНИХ ПРИСКОРЮВАЧІВ Проведено налаштування алгеброалгоритмічного інструментарію на формалізоване проектування та синтез програм, що використовують відеографічні прискорювачі. Продемонстрована ефективність ви- користання багатопроцесорних графічних прискорювачів для обчислювальних задач на прикладі спеці- ально розробленого паралельного алгоритму чисельного інтегрування задачі N тіл. Вступ Сучасна обчислювальна техніка до- сягла того рівня розвитку, коли подальше зростання продуктивності за рахунок зме- ншення розміру кристалів ускладнюється природними перешкодами. Тому останнім часом розвитку набувають технології, що використовують масивно-паралельні бло- ки обчислювачів; ПК на основі багатояде- рних процесорів вже давно набули побуто- вого поширення. В 2006 році розробник графічних прискорювачів NVIDIA презентував GPGPU технологію CUDA (Compute Unified Device Architecture), що дозволяє проводити обчислення використовуючи графічні прискорювачі [1–3]. Маючи ви- робничу продуктивність порядку сотень гігафлопс, графічні прискорювачі надають змогу проводити об’ємні обчислення на- віть на звичайному ПК. Незважаючи на наявність спеціалі- зованих засобів CUDA, розробка програм для графічних прискорювачів (Graphics Processing Unit, GPU) залишається трудо- місткою задачею, яка вимагає від розроб- лювача знання низькорівневих деталей апаратної і програмної платформи. Тому актуальною є задача автоматизації процесу розробки. У даній роботі запропонований розвиток формальних методів проектуван- ня, що ґрунтується на концепції алгебри алгоритмів [4] з використанням техніки пе- реписувальних правил [5] для автоматизо- ваної розробки ефективних програм для графічних прискорювачів. Дана робота продовжує дослідження, розпочаті в [4, 6, 7], з автоматизації процесу проектування і розробки ефективних паралельних про- грам. Особливість даної роботи – викорис- тання нової апаратної платформи для па- ралельних обчислень, графічних приско- рювачів, що дозволяє досягти значного пі- двищення продуктивності в порівнянні з використанням багатоядерних процесорів загального призначення. У даній статті виконано налашту- вання розробленого у попередніх роботах Інтегрованого інструментарію проекту- вання та синтезу програм (ІПС) [4, 6] на автоматизацію конструювання паралель- них програм, що використовують відеог- рафічні прискорювачі. Ефективність вико- ристання ІПС та GPU продемонстрована на прикладі задачі N тіл. Згадана задача полягає в дослідженні поведінки системи матеріальних точок, в якій кожна точка неперервно взаємодіє з усіма іншими точ- ками системи [8]. Найпростішим методом розрахунку в задачі N тіл є обчислення сил взаємодії попарно між усіма точками сис- теми на дискретній часовій сітці. Для зада- чі N тіл кількість операцій, необхідних для здійснення одного кроку по часу, квадра- тично збільшується із зростанням кількості частинок. Велика кількість операцій з да- ними, які необхідно здійснити при розра- хунках внутрішніх взаємодій системи, призводить до необхідності розробки ал- горитмів прискорення обчислення взаємо- дій. Оскільки основна задача може бути повністю розщеплена на паралельно вико- нувані підзадачі, виникає можливість за- стосування паралельних алгоритмів обчи- слень [9, 10]. Якщо до розрахунків залучи- Моделі та засоби паралельних і розподілених програм 39 ти кластер з кількістю обчислювальних ву- злів N, і кожен вузол буде проводити роз- рахунки для окремої точки, обчислення будуть виконуватись одночасно, що до- зволить суттєво заощадити розрахунковий час. 1. Система ІПС та її налаштування на розробку CUDA програм Інструментарій ІПС ґрунтується на системах алгоритмічних алгебр (САА) В.М. Глушкова і методі діалогового конс- труювання синтаксично правильних про- грам [1]. Його особливість полягає в спі- льному використанні трьох форм подання алгоритму при його конструюванні: аналі- тичної (формула в алгебрі алгоритмів), природно-лінгвістичної (текстової) і гра- фової (граф-схеми). Компонентами розро- бленого інтегрованого інструментарію [1] є діалоговий конструктор синтаксично правильних програм (ДСП-конструктор), редактор граф-схем, генератор САА-схем і база даних. У ДСП-конструкторі здійсню- ється проектування алгоритмів у природ- но-лінгвістичній (САА-схема) і алгебраїч- ній (регулярна схема) формах. При цьому конструювання алгоритму виконується порівнево зверху вниз за допомогою супе- рпозиції операторних і предикатних опе- рацій САА і подане у вигляді дерева. База даних ІПС призначена для зберігання, вве- дення і редагування операцій САА в алге- браїчній та текстовій формах, а також міс- тить шаблони реалізацій операцій цільо- вими мовами програмування (C, C++, Java). За схемами алгоритмів та описами САА конструкцій (із бази даних) ДСП- конструктор виконує синтез програм. З метою орієнтації ДСП- конструктора на проектування і генерацію програм для відеографічних прискорюва- чів, в БД ІПС були включені додаткові конструкції. Перш ніж розглянути згадані конструкції, наведемо спочатку стислий огляд моделі GPU в структурі CUDA. CUDA (Compute Unified Device Architecture) [2, 3] — програмно-апаратна архітектура, розроблена компанією NVIDIA, що дозволяє проводити обчис- лення, використовуючи графічні процесо- ри NVIDIA, що підтримують технологію GPGPU (General Purpose computing on Graphics Processing Units). CUDA SDK до- зволяє програмістам реалізовувати на спе- ціальному спрощеному діалекті мови про- грамування С алгоритми, виконувані на графічних процесорах NVIDIA, та включа- ти спеціальні функції в текст програми на C. CUDA дає розробнику можливість самостійно організовувати доступ до на- бору інструкцій графічного прискорювача та керувати його пам'яттю, організовувати складні паралельні обчислення. В моделі CUDA графічний приско- рювач розглядається як спеціальний при- стрій, що є масивно-паралельним співпро- цесором центрального пристрою, має вла- сну пам’ять та здатен одночасно виконува- ти велику кількість підпрограм – потоків. При виконанні програма на CUDA викори- стовує як центральний пристрій, так і гра- фічний. Типова схема виконання програми наступна: виділення області пам’яті на GPU та копіювання даних з CPU у виділе- ну область пам’яті GPU; запуск ядра – паралельної части- ни програми, що виконується на GPU. За- пуск виконує та керує ним CPU; копіювання отриманих результа- тів з пам’яті GPU до CPU та очищення ви- діленої пам’яті. Основний процес CUDA працює на головному пристрої. Код для CPU робить наступне: ініціалізує GPU, розподіляє па- м'ять на відеокарті і системі, копіює вихід- ні дані в пам'ять відеокарти, здійснює за- пуск ядер, копіює отримані результати з відеопам'яті, звільняє пам'ять і завершує роботу. Апаратно графічні прискорювачі NVIDIA, що підтримують технологію CUDA, складаються з деякої кількості CUDA-ядер, кожне з яких здатне одночас- но виконувати певну кількість потоків. Усі потоки підпорядковуються наступній ієра- рхії. Верхній рівень ієрархії – сітка – під- порядковує усі потоки, що виконують яд- ро. Сітка являє собою одно- або двовимір- ний масив блоків. Кожен блок – це одно- вимірний або двовимірний масив потоків, причому всі блоки, що утворюють сітку, Моделі та засоби паралельних і розподілених програм 40 мають однакові розмірність та розмір. Зве- ртання до окремих потоків відбувається за допомогою індексів: кожен блок у сітці має адресу (індекс блоку у сітці), аналогіч- но кожен потік у блоці має свій власний індекс всередині блоку; таким чином, ко- жний потік має унікальний ідентифікатор. Потоки можуть взаємодіяти між собою лише всередині одного блоку; під взаємо- дією розуміється використання окремої для кожного блоку так званої спільної пам’яті, а також синхронізація потоків, що може бути здійснена між потоками окре- мого блоку, проте не може бути здійснена на всьому GPU. Програма GPU (ядро) ви- конується над сіткою блоків потоків. Таким чином, розділяючи основну задачу на сукупність підзадач, що можуть виконуватись незалежно одна від одної, і розв’язуючи ці підзадачі, використовуючи одночасно виконувані потоки, досягається паралелізм виконання алгоритму. З метою налаштування системи ІПС на конструювання та генерацію програм для GPU в сигнатуру САА, а також в БД ІПС, було додано такі операції: операції взаємодії з відео- пам’яттю, а саме: виділення і очищення пам’яті GPU; копіювання даних із пам’яті CPU в пам’ять GPU і у зворотному напря- мку. Наприклад, текст оператору виділен- ня пам’яті GPU має вигляд: "Виділити пам’ять для змін- ної (var) розміром (size) в відеопам’яті" операція запуску ядра: ЗапускЯдра (blocksPerGrid, threadsPerBlock) ( "оператор" ) де blocksPerGrid – кількість блоків у сі- тці; threadsPerBlock – кількість потоків у кожному блоці; "оператор" – частина алгоритму, що буде виконуватися парале- льно потоками CUDA; синхронізатор – операція, що здійснює очікування завершення обчис- лень усіма потоками CUDA: ЧЕКАТИ ‘Обробка у всіх потоках закінчена’ Застосування цих операцій у даній роботі продемонстроване на прикладі проектування паралельного алгоритму для розв’язання задачі N тіл. У розділі 2 розг- лянуті загальна постановка задачі та вико- ристовуваний метод чисельного інтегру- вання. У розділі 3 наведено опис та САА- схеми послідовної та паралельної реаліза- цій алгоритму. 2. Гравітаційна задача N тіл та чисельне інтегрування 2.1. Постановка задачі. Задача багатьох тіл, що взаємодіють між собою під дією гравітаційних сил, є класичною задачею ньютонівської механіки, і є випадком задачі N тіл [8]. Задача розв’язна аналітично у випадку двох тіл, у випадку трьох тіл розв’язки побудовано для часткових випадків початкових даних та у вигляді збіжних рядів для загального випадку, а також доведено, що загальний розв’язок неможливо виразити через алгебраїчні чи трансцендентні функції швидкостей та координат. Розглянемо систему N матеріальних точок з відомими масами im , що попарно взаємодіють між собою згідно закону тя- жіння Ньютона. Нехай положення та шви- дкості тіл в початковий момент часу 0t відомі і становлять 0 0i tr r та 0 0i tv v відповідно. Необхідно наближено знайти положення та швидкості в наступні моме- нти часу. Еволюція системи N матеріальних точок описується системою рівнянь i i v dt dr , ij ij ij j i rr rr Gm dt dv 3 , де Ni ,1 , G – гравітаційна стала. Таким чином, задача зводиться до інтегрування системи з 2N диференціальних рівнянь першого порядку. Моделі та засоби паралельних і розподілених програм 41 2.2. Чисельне інтегрування. Проінтегруємо подану задачу чисельно з дискретизацією за часовою змінною. Застосуємо метод типу предиктор- коректор з використанням інтерполяцій- них многочленів Ерміта [11]. Оберемо досить малий крок часу t . Інтегрування відбувається за наступною схемою. 1. Для кожної точки, виходячи з відомих положень точок системи та їх швидкостей в момент часу t , обчислю- ються сила, що діє на неї з боку інших точок, нормована на масу даної частинки, та її похідна: 0, 2 2 3/2( ) ij i j j i ij r a Gm r , (1) 0, 2 2 3/2( ) ij i j j i ij v a Gm r 2 2 5/2 3( ) ( ) ij ij ij ij v r r r , (2) де ijij rrr , jiij vvv , а – пом'якшуючий параметр, необхід- ність введення якого зумовлена дискретні- стю часової сітки. 2. З урахуванням отриманих зна- чень ia ,0 та 0,ia обчислюються положення точок системи в момент часу t t : iiiiip rtva t a t r ,0,0 2 ,0 3 , 26  , (3) iiiip vtaa t v ,0,0 2 , 2  . (4) 3. З урахуванням нових положень точок системи обчислюються сила 1,ia та її похідна 1,ia , що діє на точку в момент часу t t , використовуючи формули, аналогі- чні формулам другого пункту: 1, 2 2 3/2( ) ij i j j i ij r a Gm r , (5) 1, 2 2 3/2( ) ij i j j i ij v a Gm r 2 2 5/2 3( ) ( ) ij ij ij ij v r r r . (6) 4. Використовуючи інтерполяцій- ний поліном Ерміта, апроксимуються дру- га та третя похідні сили, що діють на i-ту точку системи в початковий момент часу, виходячи із значень 0,ia , 0,ia , 1,ia та 1,ia : 2 ,1,0,1,0 ,0 )24()(6 t aataa a iiii i   , (7) 3 ,1,0,1,0 ,0 )(6)(12 t aataa a iiii i   . (8) 5. На останньому кроці алгоритму вводяться поправки для отриманих поло- жень і швидкостей точок з урахуванням отриманих значень ia ,0 та ia ,0 : iiipi a t a t rr ,0 5 ,0 4 , 12024  , (9) iiipi a t a t vv ,0 4 ,0 3 , 246  , (10) і таким чином, отримуються остаточні значення положень і швидкостей в момент часу t t . Складність наведеного алгоритму становить 2( )O N . Точність даних, отри- маних в результаті застосування поданого алгоритму, можна оцінити виходячи із оцінки похибки імпульсу системи. 3. Послідовна та паралельна реалізації алгоритму 3.1. CPU реалізація. При проведенні обчислень з використанням центрального процесора використаний алгоритм (рис. 1), що в точності повторює алгоритм, описаний у розділі 2. Рис. 1. Схема роботи послідовного алгоритму Моделі та засоби паралельних і розподілених програм 42 Оскільки відеокарти персональних комп’ютерів оптимізовані під виконання 32-бітних обчислень, в послідовних обчис- леннях на центральному процесорі також використовувався 32-бітний тип даних. Узагальнена САА-схема послідов- ного алгоритму має вигляд: СХЕМА "NBODY_SERIAL" ==== "Задати початкові значення мас, координат та швидкостей частнок"; ДЛЯ (k ВІД 0 ДО STEPS - 1) ЦИКЛ ДЛЯ (i ВІД 0 ДО N - 1) ЦИКЛ "Обчислення прискорення час- тинок і його похідної (i)" КІНЕЦЬ ЦИКЛУ; ДЛЯ (i ВІД 0 ДО N - 1) ЦИКЛ "Виконати попередні обчислення координат та швидкостей (i)" КІНЕЦЬ ЦИКЛУ ДЛЯ (i ВІД 0 ДО N - 1) ЦИКЛ "Виконати обчислення поправок для координат та швидкостей (i)" КІНЕЦЬ ЦИКЛУ ДЛЯ (i ВІД 0 ДО N - 1) ЦИКЛ "Внести поправки для отриманих координат та швидкостей (i)" КІНЕЦЬ ЦИКЛУ КІНЕЦЬ ЦИКЛУ КІНЕЦЬ СХЕМИ "NBODY_SERIAL" 3.2. GPU реалізація. Основна ідея паралелізації алгоритму полягає у тому, що за проведення операцій з кожною окремою частинкою відповідає окремий потік GPU. Існує ряд обмежень, яких слід дотримуватись при складанні алгоритму задля коректної роботи програми: 1) максимальна та мінімальна кіль- кості потоків у блоці складають 512 та 64 одиниць відповідно, причому найбільша ефективність роботи ядер CUDA досяга- ється, якщо використовувати 256 потоків на блок. Таким чином, кількість блоків B, що використовуються, обирається рівною ;256,1 256 ,256, 256   N N N N B 2) обмеження максимальної кіль- кості операцій, що потік виконує за один запуск ядра. Виходячи з цього обмеження, при досить великих кількостях частинок, у потоках не можна використовувати цикли за повною кількістю частинок. В таких випадках необхідно розбити внутрішні цикли на підцикли та виконувати циклічний запуск ядра. Керуючись наявними типами пам’яті з метою оптимального її викорис- тання і, таким чином, досягнення найбільш ефективної роботи GPU, розроблено алго- ритм, що працює за наступною схемою. 1. Нехай частинки занумеровані та кожній із них співставлено відповідний потік. Кожен потік отримує початкові параметри своєї власної частинки, яку він буде обробляти. 2. За порядковим номером обира- ється поточна частинка, починаючи з пер- шої. Координати, швидкості та маса час- тинки заносяться у спільну пам'ять кожно- го блоку потоків. Таким чином, потоки кожного блоку отримують змогу швидкого доступу до координат поточної частинки. Кожен потік здійснює обчислення внеску взаємодії між своєю та поточною частин- ками в суми (1) та (2). Крок повторюється, доки не будуть підраховані всі попарні взаємодії між частинками (рис. 2). Рис. 2. Схема роботи паралельного алгоритму 3. Кожен потік проводить розра- хунки попередніх значень координат та швидкостей згідно формул (3), (4). 4. Аналогічно другому пункту цієї схеми проводяться розрахунки за формулами (5) та (6). 5. Кожен потік вводить поправки до отриманих раніше попередніх значень положень та швидкостей згідно формул Моделі та засоби паралельних і розподілених програм 43 (7), (8), (9), (10), і, таким чином, отримує остаточні результати. Пункти 1–5 повторюються для ко- жного часового кроку, доки не будуть отримані значення в кінцевий момент часу. Для переходу від послідовної САА- схеми алгоритму до паралельної виконано такі основні трансформації: 1) додано оператори взаємодії із ві- деопам’яттю; 2) у вкладених циклах за змінною i для першого та третього циклів виконано заміну N на N/512. В циклах обчислення проводяться не для всіх частинок одразу, а для наборів по 512, оскільки проведення обчислень для всіх частинок одразу або для наборів більшого розміру призводить до нестабільної роботи GPU; 3) вилучено другий та четвертий вкладені цикли за змінною i, і залишено лише оператори тіла даних циклів; 4) додано виклики операції ЗапускЯдра(blocksPerGrid, threads PerBlock), де кількість потоків у межах кожного блоку threadsPerBlock = = 256; кількість блоків blocksPerGrid = = N / threadsPerBlock; 5) вставлено виклики синхроніза- торів. Далі наведена отримана в результаті перетворень паралельна САА-схема. СХЕМА "NBODY_PARALLEL" ==== "Задати початкові значення мас, координат та швидкостей частинок"; "Виділити область пам’яті на GPU та скопіювати дані з CPU в GPU"; ДЛЯ (k ВІД 0 ДО STEPS - 1) ЦИКЛ ДЛЯ (i ВІД 0 ДО N / 512 - 1) ЦИКЛ ЗапускЯдра (blocksPerGrid, threadsPerBlock) ( "Обчислення прискорення частинок і його похідної (i)" ); ЧЕКАТИ ‘Обробка у всіх потоках закінчена’ КІНЕЦЬ ЦИКЛУ; ЗапускЯдра (blocksPerGrid, threadsPerBlock) ( "Виконати попередні обчис- лення координат та швидкос- тей" ); ЧЕКАТИ ‘Обробка у всіх потоках закінчена’ ЗАТЕМ ДЛЯ (i ВІД 0 ДО N / 512 - 1) ЦИКЛ ЗапускЯдра (blocksPerGrid, threadsPerBlock) ( "Виконати обчислення поправок для координат та швидкостей(i)" ); ЧЕКАТИ ‘Обробка у всіх потоках закінчена’ КІНЕЦЬ ЦИКЛУ; ЗапускЯдра (blocksPerGrid, threadsPerBlock) ( "Внести поправки для отриманих координат та швидкостей" ); ЧЕКАТИ ‘Обробка у всіх потоках закінчена’ КІНЕЦЬ ЦИКЛУ; "Скопіювати отримані результати з пам’яті GPU до CPU та очистити виділену пам’ять" КІНЕЦЬ СХЕМИ "NBODY_PARALLEL" Для автоматизованої трансформації алгоритмів спільно з ІПС використо- вується система переписування термів TermWare [5]. Продемонструємо застосу- вання правил TermWare для виконання згаданих вище перетворень (2) та (4). На- приклад, терм для першого вкладеного ци- клу із послідовного алгоритму має вигляд: ForLoop(i, 0, Minus(N, 1), force0(i)) Для виконання вказаних двох трансформацій необхідно до даного терму застосувати правило ForLoop($x1, $x2, Minus(N,1), $x3) -> Моделі та засоби паралельних і розподілених програм 44 ForLoop($x1, $x2, Minus(Div(N, 512), 1), CALL_GPU(blocksPerGrid, threadsPerBlock, $x3)), де $x1, $x2, $x3 – змінні, що вико- ристовуються у процесі трансформації. В результаті отримаємо терм ForLoop(i, 0, Minus(Div(N, 512), 1), CALL_GPU(blocksPerGrid, threadsPerBlock, force0(i))) За наведеною САА-схемою в системі ІПС було виконано генерацію паралельної програми мовою С++ із використанням функцій CUDA. Результати виконання цієї програми на GPU наведено у наступному розділі. 4. Результати експерименту Обчислення в експериментальній задачі для підрахунку часу проводились з наступними початковими умовами. В по- чатковий момент часу частинки розміщені у вузлах тривимірної паралелепіпедоподі- бної області розміру 16 16 ( / 256)N . Кі- лькість частинок обиралась кратною 256. Стартові швидкості частинок задані дові- льним чином і нормовані на одиницю. Пом’якшуючий параметр обрано рівним 0.01, гравітаційну сталу одиничною, часо- вий крок 0.25t . Випробування проводились із вико- ристанням процесора i5-3570 (у 32- бітному режимі) та графічного прискорю- вача GeForce GTX 650 Ti, що має наступні характеристики: 768 stream-процесори (CUDA- ядра), базова частота 928MHz; Рис. 3. Залежність часу виконання послідовного та паралельного алгоритмів від кіль- кості досліджуваних частинок Моделі та засоби паралельних і розподілених програм 45 обсяг глобальної пам’яті 1024Mb; базова частота пам’яті 5400MHz. Час виконання вимірювався для кі- лькості частинок від 256 до 16384 з кроком 256 частинок та при окремих значеннях N (32768, 65536) на один крок за часом. В таблиці представлена вибірка отриманих значень від 256 частинок з подвоєнням кі- лькості. Тут N – кількість задіяних части- нок, CPUT (с) – час виконання послідовної програми, GPUT (с) – час виконання пара- лельної програми, /CPU GPUT T – коефіцієнт прискорення. Таблиця. Час виконання послідовної та паралельної програм N CPUT , с GPUT , с /CPU GPUT T 256 0.02797 0.00525 5.32761 512 0.0766 0.00844 9.07582 1024 0.3031 0.01907 15.8941 2048 1.2422 0.03843 32.3237 4096 5.375 0.0703 76.4580 8192 32.094 0.1953 164.331 16384 161.453 0.75 215.270 32768 718.875 1.5516 463.312 65536 3045.22 6.0585 502.636 Низький рівень прискорення при невеликих значеннях N пояснюється непо- вною завантаженістю відеокарти, через що не досягається максимальна ефективність. Крім того, суттєвий вплив має те, що час, витрачений на проведення кроку алгорит- му, складається, окрім часу, витраченого на проведення обчислень, з часу, витраче- ного на передачу даних з CPU на GPU та в зворотному напрямку. На графіку, поданому на рис. 3, зо- бражено залежність часу виконання кроку алгоритму від кількості досліджуваних ма- теріальних частинок для CPU та GPU про- грам. Висновки Проведено налаштування розробле- ного у попередніх роботах алгеброалгори- тмічного інструментарію на формалізоване проектування та синтез програм, що вико- ристовують відеографічні прискорювачі. Продемонстрована ефективність викорис- тання ІПС та GPU для обчислювальних за- дач на прикладі спеціально розробленого паралельного алгоритму чисельного інтег- рування задачі N тіл. Для проектування ал- горитму використана мова САА-схем, пе- ревагою якої є простота в навчанні і вико- ристанні, а також незалежність від мови програмування і можливість перекладу в довільну цільову мову. Перевагою засто- сування системи ІПС є також використан- ня методу конструювання синтаксично правильних програм, який виключає мож- ливість появи синтаксичних помилок у процесі проектування алгоритмів. Прове- дено експеримент з виконання згенерова- ної за допомогою ІПС паралельної про- грами на відеографічному прискорювачі. 1. Harris M. GPGPU: General-Purpose Compu- tation on GPUs. – In SIG-GRAPH 2005 GPGPU COURSE, 2005. 2. NVIDIA. CUDA Programming Model Over- view, 2008. http://www.sdsc.edu/us/training/assets/docs/N VIDIA-02-BasicsOfCUDA.pdf 3. Боресков А.В., Харламов А.А. Основы ра- боты с технологией CUDA. – ДМК-Пресс, 2010. – 232 c. 4. Андон Ф.И., Дорошенко А.Е., Цейт- лин Г.Е., Яценко Е.А. Алгеброалгоритмиче- ские модели и методы параллельного про- граммирования. – Киев: Академпериодика, 2007. – 631 с. 5. Дорошенко А.Е., Шевченко Р.С. Система символьных вычислений для программи- рования динамических приложений // Про- блеми програмування. – 2005. – № 4. – С. 718–727. 6. Дорошенко А.Е., Жереб К.А., Яценко Е.А. Формализованное проектирование эффек- тивных многопоточных программ // Про- Моделі та засоби паралельних і розподілених програм 46 блеми програмування. – 2007. – № 1. – С. 17–30. 7. Дорошенко А.Е., Жереб К.А., Яценко Е.А. Об оценке сложности и координации вы- числений в многопоточных программах // Проблеми програмування. – 2007. – № 2. – С. 41–55. 8. Aarseth S.J. Gravitational N-body simula- tions. – Cambridge University Press, 2003. – P. 1–17. 9. Nyland L., Harris M., Prins J. Fast N-body simulation with CUDA. – In GPU Gems 3, Addison-Wesley Professional, 2007. – P. 677–695. 10. Zwart S., Belleman R., Geldof P. High Per- formance Direct Gravitational N-body Simu- lations on Graphics Processing Units // New Astronomy. –– 2007. – Vol. 12, Issue 8. – P. 641–650. 11. Makino J., Aarseth S.J. On a Hermite integra- tor with Ahmad-Cohen // Publications of the Astronomical Society of Japan, 44. – 1992. – P. 141–151. Одержано 19.11.2012 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп'ютерних обчислень, Бекетов Олексій Геннадійович, аспірант, Жереб Костянтин Анатолійович, кандидат фізико-математичних наук, науковий співробітник, Яценко Олена Анатоліївна, кандидат фізико-математичних наук, старший науковий співробітник. Місце роботи авторів: Інститут програмних систем НАН України. Тел.: (044) 526 3559, E-mail: dor@isofts.kiev.ua beketov.oleksii@gmail.com zhereb@gmail.com oayat@ukr.net mailto:dor@isofts.kiev.ua mailto:zhereb@gmail.com mailto:oayat@ukr.net

Formalized design and synthesis of parallel programs for videographic shortcuts

Репозитарії

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