Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators

A toolkit for modelling heterogeneous Grid systems with video accelerators gpusim has been developed and used to simulate the time of solving the gravitational problem of interaction of N bodies, which depends on the parameter. The simulation tools allow to choose the most optimal parameter value i...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Doroshenko, A.Yu., Okonsky, I.V., Zhereb, K.A., Beketov, O.G.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 004.424
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/775
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-775
record_format	ojs
resource_txt_mv	ppisoftskievua/fa/f415f865dbef3eab9b9e68566d392efa.pdf
spelling	pp_isofts_kiev_ua-article-7752025-08-27T13:11:22Z Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators Використання засобів моделювання для визначення оптимальних параметрів виконання програм на відеографічних прискорювачах Doroshenko, A.Yu. Okonsky, I.V. Zhereb, K.A. Beketov, O.G. UDC 004.424 УДК 004.424 A toolkit for modelling heterogeneous Grid systems with video accelerators gpusim has been developed and used to simulate the time of solving the gravitational problem of interaction of N bodies, which depends on the parameter. The simulation tools allow to choose the most optimal parameter value in an automated mode and at the same time significantly reduce the time of parameter selection compared to the direct execution of the program.Problems in programming 2013; 2: 23-31 Побудовано інструментарій моделювання гетерогенних Грід-систем з відеографічними прискорювачами gpusim, який використано для моделювання часу виконання гравітаційної задачі взаємодії N тіл, що залежить від параметру. Засоби моделювання дозволяють обрати найбільш оптимальне значення параметру в автоматизованому режимі і при цьому суттєво скоротити час підбору параметрів у порівнянні з безпосереднім виконанням програми.Problems in programming 2013; 2: 23-31 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/775 PROBLEMS IN PROGRAMMING; No 2 (2013); 23-31 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2013); 23-31 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2013); 23-31 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/775/827 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-27T13:11:22Z
collection	OJS
language	Ukrainian
topic	UDC 004.424
spellingShingle	UDC 004.424 Doroshenko, A.Yu. Okonsky, I.V. Zhereb, K.A. Beketov, O.G. Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
topic_facet	UDC 004.424 УДК 004.424
format	Article
author	Doroshenko, A.Yu. Okonsky, I.V. Zhereb, K.A. Beketov, O.G.
author_facet	Doroshenko, A.Yu. Okonsky, I.V. Zhereb, K.A. Beketov, O.G.
author_sort	Doroshenko, A.Yu.
title	Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_short	Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_full	Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_fullStr	Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_full_unstemmed	Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_sort	usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators
title_alt	Використання засобів моделювання для визначення оптимальних параметрів виконання програм на відеографічних прискорювачах
description	A toolkit for modelling heterogeneous Grid systems with video accelerators gpusim has been developed and used to simulate the time of solving the gravitational problem of interaction of N bodies, which depends on the parameter. The simulation tools allow to choose the most optimal parameter value in an automated mode and at the same time significantly reduce the time of parameter selection compared to the direct execution of the program.Problems in programming 2013; 2: 23-31
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/775
work_keys_str_mv	AT doroshenkoayu usageofmodellingtoolsfordeterminingoptimalparametersofprogrammeexecutiononvideographicsaccelerators AT okonskyiv usageofmodellingtoolsfordeterminingoptimalparametersofprogrammeexecutiononvideographicsaccelerators AT zherebka usageofmodellingtoolsfordeterminingoptimalparametersofprogrammeexecutiononvideographicsaccelerators AT beketovog usageofmodellingtoolsfordeterminingoptimalparametersofprogrammeexecutiononvideographicsaccelerators AT doroshenkoayu vikoristannâzasobívmodelûvannâdlâviznačennâoptimalʹnihparametrívvikonannâprogramnavídeografíčnihpriskorûvačah AT okonskyiv vikoristannâzasobívmodelûvannâdlâviznačennâoptimalʹnihparametrívvikonannâprogramnavídeografíčnihpriskorûvačah AT zherebka vikoristannâzasobívmodelûvannâdlâviznačennâoptimalʹnihparametrívvikonannâprogramnavídeografíčnihpriskorûvačah AT beketovog vikoristannâzasobívmodelûvannâdlâviznačennâoptimalʹnihparametrívvikonannâprogramnavídeografíčnihpriskorûvačah
first_indexed	2025-09-17T09:21:30Z
last_indexed	2025-09-17T09:21:30Z
_version_	1850411983645442048
fulltext	Моделі та засоби паралельних і розподілених програм © А.Ю. Дорошенко, І.В. Оконський, К.А. Жереб, О.Г. Бекетов, 2013 ISSN 1727-4907. Проблеми програмування. 2013. № 2 23 УДК 004.424 А.Ю. Дорошенко, І.В. Оконський, К.А. Жереб, О.Г. Бекетов ВИКОРИСТАННЯ ЗАСОБІВ МОДЕЛЮВАННЯ ДЛЯ ВИЗНАЧЕННЯ ОПТИМАЛЬНИХ ПАРАМЕТРІВ ВИКОНАННЯ ПРОГРАМ НА ВІДЕОГРАФІЧНИХ ПРИСКОРЮВАЧАХ Побудовано інструментарій моделювання гетерогенних Грід-систем з відеографічними прискорювача- ми gpusim, який використано для моделювання часу виконання гравітаційної задачі взаємодії N тіл, що залежить від параметру. Засоби моделювання дозволяють обрати найбільш оптимальне значення пара- метру в автоматизованому режимі і при цьому суттєво скоротити час підбору параметрів у порівнянні з безпосереднім виконанням програми. Вступ У роботі [1] автори запропонували систему моделювання виконання задач на відеографічних прискорювачах (graphical processing units, GPU). Запропонована си- стема gpusim побудована на основі плат- форми GridSim [2], і дозволяє моделювати виконання задач на гетерогенних системах, що складаються зі звичайних процесорів (central processing units, CPU) та GPU. Дана робота продовжує розпочаті в [1] дослідження. Основний внесок роботи полягає в наступному. По-перше, розгля- дається більш складна прикладна задача, а саме задача гравітаційної взаємодії N тіл [3]. По-друге, ставиться більш складне пи- тання, а саме пошуку оптимального зна- чення параметра для отримання більш ефективної програми. У роботі проведено дослідження за- лежності часу виконання програми на ві- деографічному прискорювачі на прикладі задачі N тіл від заданого параметра (кіль- кість потоків на блок). Отримано оптима- льні значення для даного параметра. По- будовано модель часу виконання для за- дачі N тіл, що дозволяє отримувати опти- мальне значення параметра без запуску обчислень. Це дозволяє суттєво скоротити час розробки оптимальної програми. Зок- рема, для N = 2^21 оптимальне значен- ня параметра 256 отримано методом моде- лювання за 3 хвилини, тоді як його підтве- рдження експериментальним шляхом пот- ребувало 8 годин обчислень. Задача N тіл широко розглядається у літературі, зокрема, останнім часом вона часто розв’язується на GPU. Ця задача мо- же використовуватись як в астрофізиці для опису еволюції космічних об’єктів [4 – 7], так і в молекулярній динаміці для моделю- вання структури речовини [7 – 8]. Відмін- ність даної роботи полягає у використанні засобів моделювання для знаходження оп- тимальних значень параметрів виконання програми. Матеріал даної роботи організова- ний наступним чином. У розділі 1 наведе- но постановку задачі N тіл і досліджено залежність часу виконання паралельного GPU-алгоритму від параметрів. Розділ 2 присвячено побудові наближеної моделі часу виконання задачі N тіл у рамках ін- струментарію gpusim. У розділі 3 наведено дослідження побудованої моделі та підтве- рджено її адекватність. Роботу завершують висновки та напрямки подальшої роботи. 1. Постановка задачі Розглядається класична задача нью- тонівської механіки еволюції системи N тіл відомої маси в тривимірному евклідо- вому просторі, що попарно взаємодіють під дією гравітаційних сил [3]. В початко- вий момент часу задані положення тіл в просторі та їх швидкості. Мета – прогнозу- вати стан системи в наступні моменти часу. Поведінка системи описується зада- чею Коші з 2 N диференціальних рівнянь Моделі та засоби паралельних і розподілених програм 24 першого порядку. Задача не є розв'язною аналітично в загальному випадку, тому для її чисельного інтегрування використано наближений чисельний метод дискретиза- ції за часовим параметром типу предиктор- коректор з використанням інтерполяцій- них многочленів Ерміта [9]. Реалізовано паралельний алгоритм обчислення цієї задачі на GPU. На рис. 1 показано графік залежності часу виконан- ня даного алгоритму в залежності від роз- міру задачі (кількості тіл) N на графіч- ному прискорювачі Nvidia GeForce GTX 650 (384 CUDA Cores, 1058 MHz, 86,4 GFLOPS FP64, 1024 MB) [10], який використовувався для отримання експе- риментальних даних у подальшій роботі. Прогнозований час виконання одного кро- ку алгоритму для зазначеного прискорю- вача становить 2 88 10 GPU N T   Рис. 1. Залежність часу виконання алгори- тму в секундах від N Оскільки залежність часу виконан- ня від розміру задачі має квадратичний ха- рактер, для великих розмірів задачі актуа- льним є питання оптимізації паралельного алгоритму, зокрема шляхом підбору пара- метрів виконання. Одним з параметрів, що суттєво впливають на час виконання програми на GPU, є розбиття задачі на потоки та блоки потоків. Зокрема, параметром, яким може керувати розробник, є кількість потоків на блок (threads per block, TPB). Згідно ін- струкції користувача CUDA v.5.0 мініма- льне та максимальне значення цього пара- метра складають 1 та 1024 відповідно. Для вирішення прикладних задач рекомендо- вано використовувати 256 потоків на блок і задавати це значення статично в коді про- грами [11]. Проте існує можливість опти- мального вибору цього параметра, що збі- льшує ефективність програми. Початковий алгоритм був доопра- цьований для можливості програмного задання будь-якого значення кількості по- токів на блок у діапазоні обмежень CUDA – [1; 1024]. Внесені доопрацювання не вплинули на характеристики алгоритму, що було перевірено порівнянням результатів роботи та часу виконання на однакових вхідних даних оригінальної та доопрацьованої версій. У подальших дос- лідженнях використовується доопрацьова- на версія алгоритму, для якої значення кі- лькості потоків на блок також є вхідним параметром. Для дослідження впливу значення кількості потоків на блок на час виконан- ня алгоритму було проведено серію екс- периментів для N = [2^10; 2^20] та TPB = = [1; 1024], із мультиплікативним кроком 2. Результати експериментів показані на рис. 2 – 4. Згідно отриманих результатів, для різних значень N мінімальний час ви- конання алгоритму досягається при різних значеннях TPB: для малих N оптимальне значення TPB менше, ніж для великих. Подальше дослідження паралель- ного алгоритму обчислення гравітаційної задачі взаємодії N тіл передбачає ство- рення наближеної моделі для розроблено- го у [1] середовища моделювання гетеро- генних паралельних систем gpusim, оскі- льки для проведення експериментів для N , більших за 2^20, потребується багато часу: вже для N = 2^21 експеримент три- ває 8 годин. Інтерес становить залежність часу виконання від N та TPB, таким чи- ном, вхідними даними для моделі є діапа- зони вхідних значень N та TPB, а вихід- ними – час виконання алгоритму на пара- лельній системі. Моделі та засоби паралельних і розподілених програм 25 Рис. 2. Залежність часу виконання алгори- тму від TPB при N = 2^10 Рис. 3. Залежність часу виконання алгори- тму від TPB при N = 2^15 Рис. 4. Залежність часу виконання алгори- тму від TPB при N = 2^20 2. Розробка наближеної моделі 2.1. Розробка генератора експе- рименту. Використання gpusim для дос- лідження паралельного алгоритму об- числення гравітаційної задачі взаємодії N тіл передбачає розробку експеримен- тального модуля, основною частиною якого є генератор експерименту. Генера- тор експерименту на основі вхідних да- них моделі створює відповідний експе- римент [1]. Кожна симуляція експерименту за- дається конфігураціями Ресурсів Грід (GridResource) та Завдань (Gridlet)[1], від- повідно, модель gpusim паралельного ал- горитму обчислення гравітаційної задачі взаємодії N тіл має бути представлена за допомогою даних сутностей та їх влас- тивостей. Виходячи з аналізу експеримента- льних даних, опису роботи та вихідних ко- дів алгоритму, можна зробити наступні висновки:  на час виконання алгоритму, крім вхідних даних, також мають незначний вплив параметри самого алгоритму та апаратно-програмного середовища, у яко- му він виконується. Точне врахування цих параметрів у моделі не є доцільним, оскі- льки підвищує її складність, час розробки та зменшує швидкість отримання резуль- татів симуляції;  оскільки усі обчислення виконують- ся на GPU, ядра якого мають однакові параметри, то конфігурація ресурсів від- повідає гомогенній паралельній системі, яка складається із одного ресурсу із од- нією ЕОМ із кількістю однакових обчис- лювальних елементів рівною кількості потоків на блок. Значення рейтингу MIPS обчислювальних елементів повинно бути параметром генератора. Крім того, GridSim для симуляції кожного ресурсу використо- вує окремий потік, і для підвищення шви- дкості симуляції замість одного ресурсу із однією ЕОМ та TPB обчислювальних елементів слід використовувати еквівален- тну паралельну модель – кількість потоків на блок відповідає кількості однакових ре- сурсів із однією ЕОМ та одним обчислю- вальним елементом; Моделі та засоби паралельних і розподілених програм 26  оскільки кожний потік обчислює вплив одного тіла на інші, то конфігурацію завдань можна представити у вигляді N однакових завдань із розмірами вхідних та вихідних даних, що лінійно залежать від N . Однак усі поточні дані, необхідні алго- ритму для роботи, зберігаються у швид- кій пам’яті загального користування GPU, тому час, що витрачається на роботу із вхідними та вихідними даними завдання значно менший за час обчислень, тобто модель може знехтувати розмірами вхід- них та вихідних даних завдань;  кількість роботи кожного завдання крім лінійної залежності від N має врахо- вувати операції синхронізації (чим більше потоків використовується у обчисленнях, тим більше часу потребується на їх синх- ронізацію) та операції переключення кон- тексту (чим більше потоків використову- ється у обчисленнях, тим менше операцій зміни контексту необхідно для виконання обчислень). Таким чином, порівняно з поперед- ньою роботою [1], з одного боку, відки- нуто частину параметрів, що не вплива- ють на час виконання – а саме парамет- ри CPU-машини , а також витрати на пе- редачу даних в пам’ять GPU. З іншого боку, додано більш складну структуру GPU-ресурсів. Слід зауважити, що із збільшенням кількості завдань значно зростає час си- муляції за рахунок повільної роботи планувальників ресурсів GridSim, а та- кож особливостей Java при створенні ве- ликої кількості об’єктів у пам’яті. Для зменшення часу симуляції слід зменшити кількість завдань (Gridlet) та еквівалентно збільшити кількість роботи кожного з за- вдань. Виходячи з вищеописаних мірку- вань, для генератора експерименту пропо- нується наступна стратегія формування конфігурації завдань: N M d  ,    2 2 2 1 log logN N T P B R w T P B     , 2S w N T P B   ,   cL N d R S K K      , де використано позначення:  M – кількість завдань;  d – параметр генератора, який приз- начений для зменшення кількості завдань із еквівалентним збільшенням кількості роботи кожного із завдань;  R – складова для врахування опера- цій переключення контексту;  S – складова для врахування опера- цій синхронізації;  1w та 2w – параметри генератора, вагові коефіцієнти R та S відповідно;  L – кількість роботи кожного за- вдання;  , cK K – параметри генератора, му- льтиплікативний та адитивний коефіціє- нти масштабування величини кількості роботи. Таким чином, попередньо встанов- лені такі параметри генератора:  рейтинг кожного з обчислювальних ядер GPU в одиницях MIPS (million instructions per second): gpuCoreRating;  параметр зменшення кількості за- вдань: d = limitationsDivider;  ваговий коефіцієнт складової для врахування операцій переключення кон- тексту 1w = smallTPBPenaltyWeight;  ваговий коефіцієнт складової для врахування операцій синхронізації 2w = = largeTPBPenaltyWeight;  значення мультиплікативного та ади- тивного коефіцієнтів масштабування вели- чини кількості роботи завдань K = = multiplicativeLengthScaleFactor та cK = = additiveLengthScaleFactor відповідно. 2.2. Розробка планувальника gpusim. Кожний з ресурсів GridSim про- понує користувачу 2 стандартних алго- ритми планування завдань у межах ре- сурсу [12]: First-Come-First-Served(FCFS) [13] та RoundRobin [14]. Якщо сценарій симуляції передбачає використання біль- ше одного ресурсу, то користувач GridSim має самостійно реалізувати високорівне- вий алгоритм планування. Для підтрим- Моделі та засоби паралельних і розподілених програм 27 ки можливості використання у сценарії симуляції більше одного ресурсу модуль симулятора gpusim був доопрацьований: розроблено планувальник завдань, який реалізує алгоритм RoundRobin. Для зме- ншення витрат пам’яті сутності завдань створюються з конфігурації по мірі не- обхідності, а не перед початком симу- ляції – це суттєво зменшує час симуляції. На рис. 5 показано блок-схему реалізова- ного алгоритму планування. Початок numFreePE := GridSim.getNumFreePE(resources[i]); gridlets := GridletsContainer.getNextGridlets(nu mFreePE); Gridsim.submitGridlets(resources[i], gridlets); gridlets.isEmpty()? Кінець Gridsim.receiveGridlets(); True False i := 0; i < resourcesCount; i := i + 1 GridletsContainer. hasMoreGridlets()? True False Рис. 5. Блок-схема алгоритму плануваль- ника gpusim Доки всі завдання, задані конфігу- рацією завдань, не оброблено, до кож- ного з ресурсів посилається запит на от- римання кількості вільних обчислюваль- них елементів. Далі контейнер ресурсів створює рівно стільки завдань, скільки у даний час можна розподілити на ре- сурс, і потім вони відсилаються до ресу- рсу на виконання, при цьому ресурс у окремому потоці починає виконання за- вдання одразу після прийому. Після за- вершення кожного кроку розподілення завдань по ресурсах, виконується їх синх- ронізація та запис статистичної інформа- ції, далі починається нова ітерація циклу розподілу. 3. Перевірка адекватності та дослідження моделі 3.1. Перевірка адекватності мо- делі. Для перевірки адекватності моде- лі використовувались метод та інстру- ментарій, описаний у попередній роботі [1]. Експериментальні дані, отримані раніше при дослідженні алгоритму ( N = [2^10..2^20], TPB = [1..1024]), вико- ристані як еталонні. За допомогою модуля оптимізації констант були знайдені точні значення попередньо встановлених параметрів ге- нератора, при яких модель досягає най- меншої середньої відносної похибки 43%:  gpuCoreRating = 1000;  limitationsDivider = 128;  smallTPBPenaltyWeigh t= 0.7;  largeTPBPenaltyWeight = 0.05;  multiplicativeLengthScaleFactor = 0.1;  additiveLengthScaleFactor = 0. На рис. 6 – 9 показано графіки отриманих результатів симуляції (суцільна лінія) у порівнянні із експериментальними даними (пунктирна лінія) для різних зна- чень N та TPB. Як видно з графіків, найбільша від- носна помилка моделі спостерігається при малих значеннях N та TPB. Цю особ- ливість можна пояснити тим, що модель нехтує впливом параметрів алгоритму та програмно-апаратного середовища на час Моделі та засоби паралельних і розподілених програм 28 Рис. 6. Порівняння результатів симуляції із експериментальними даними для TPB = 256, N = [2^10, 2^20] Рис. 7. Порівняння результатів симуляції із експериментальними даними для N = 2^10, TPB = [2, 1024] Рис. 8. Порівняння результатів симуляції із експериментальними даними для N = 2^15, TPB = [2, 1024] Рис. 9. Порівняння результатів симуляції із експериментальними даними для N = 2^20, TPB = [32, 1024] Моделі та засоби паралельних і розподілених програм 29 роботи алгоритму при малих розмірах вхідних даних. У цій ситуації величина даного впливу порівняна з обсягом обчи- слень, які виконує алгоритм. Проте, як було відмічено в попередній роботі [1], найбільший інтерес становлять саме великі розміри вхідних даних. Слід зауважити, що основною за- дачею моделі є отримання відповіді на питання «Яку кількість потоків на блок слід використовувати в паралельному алгоритмі обчислення гравітаційної за- дачі взаємодії N тіл?». Зокрема, навіть якщо побудована модель не достатньо то- чно відтворює час виконання для окре- мих значень N та TPB, але дозволяє пра- вильно відповідати на сформульоване питання, вона вже є корисною для вибору оптимальних значень параметрів. Розроблена модель зберігає харак- тер залежності часу виконання обчислень від TPB при незмінному N : для більших N мінімальне значення часу виконання досягається при більших TPB. Іншими словами, точки екстремуму моделі й екс- периментальних даних збігаються. Крім того, час обрахування моделі значно мен- ший за час проведення експерименту на реальній системі: для N = 2^21 та TPB = = [32; 1024] симуляція триває 2,5 хвили- ни, час експерименту на реальній системі при таких вхідних даних становить 8 годин. Таким чином, запропонована мо- дель, попри наявність середньої відносної похибки у 43%, за короткий час (3 хвилини для N = 2^21, TPB = [32; 1024]) дає корек- тне значення оптимального параметра TPB та може використовуватись у подальших дослідженнях. 3.2. Дослідження моделі. Оскільки для роботи алгоритму із розмірами вхідних даних більших за 2^20 тіл, що обрахову- ються, потребується багато ресурсів, то наступним кроком є дослідження моделі при великих N для отримання оптималь- ного значення кількості обчислювальних потоків на блок. На рис. 10 – 12 показані графіки залежності часу виконання від TPB для N більших за 2^20. Рис. 10. Залежність часу виконання від TPB [32; 1024] для N = 2^21 Рис. 11. Залежність часу виконання від TPB[64; 1024] для N = 2^23 Рис. 12. Залежність часу виконання від TPB[128; 1024] для N = 2^24 Моделі та засоби паралельних і розподілених програм 30 Аналізуючи отримані графіки мож- на зробити висновок, що для значень N більших за 2^20 оптимальними будуть на- ступні значення TPB:  якщо 2^20 <= N < 2^22, оптимальне TPB = 256;  якщо 2^22 < N < 2^23, оптимальне TPB = 512;  якщо N > 2^23, оптимальне TPB = = 1024. Слід відмітити, що використання алгоритму для великих значень N потре- буватиме внесення певних змін, щоб не перевантажувати пам’ять GPU. Висновки У роботі проведено дослідження та моделювання виконання паралельного ал- горитму на відеографічному мультипроце- сорі на прикладі гравітаційної задачі взає- модії N тіл. Виявлено, що в залежності від розміру вхідних даних для досягнення мі- німального часу виконання слід обирати різну величину кількості потоків CUDA на блок. Для подальшого дослідження цієї особливості було запропоновано, розроб- лено та налаштовано наближену модель алгоритму і паралельної системи, на якій він виконується для середовища моделю- вання гетерогенних паралельних систем gpusim. Розроблена модель, проте наявність середньої відносної похибки у 43%, за ко- роткий час дає коректну відповідь на пи- тання «Яку кількість потоків на блок слід використовувати в паралельному алгорит- мі обчислення гравітаційної задачі взаємо- дії N тіл?». Моделювання також дозволяє суттєво прискорити процес отримання оп- тимальних значень параметрів: наприклад, для N = 2^21 оптимальне значення TPB = 256 отримане за 3 хвилини, порів- няно з 8 годинами, необхідними для екс- периментального підтвердження цього значення. Експерименти із моделлю для вели- ких значень N (більших за 2^20) дали на- ступні результати:  якщо 2^20 <= N < 2^22, оптимальне TPB = 256;  якщо 2^22 < N < 2^23, оптимальне TPB = 512;  якщо N > 2^23, оптимальне TPB = = 1024. Подальші дослідження в даному напрямку передбачають підвищення точ- ності моделі, оптимізацію симулятора для прискорення моделювання при великій кі- лькості завдань та дослідження можливос- ті використання інтелектуальних алгорит- мів для автоматизації розробки наближе- них моделей для gpusim. 1. Оконський І.В., Дорошенко А.Ю., Жереб К.А. Інструментальні засоби моделювання гетерогенних середовищ заснованих на ві- деографічних прискорювачах // Проблеми програмування. – 2013. – № 1. – С. 107–115. 2. Sulistio A., Cibej U., Venugopal S., et al. A toolkit for modelling and simulating data Grids: an extension to GridSim // Concurren- cy and Computation: Practice & Experience. – 2008. – Vol. 20, N 13. – P. 1591–1609. 3. Sverre J. Aarseth. Gravitational N-body simulations. – Cambridge University Press, 2003. – 413 p. 4. Hamada T., Nitadori K. 190 TFlops Astrophysical N-body Simulation on a Cluster of GPUs // Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, Washington, DC, USA. – 2010. – P. 1–9. 5. Bédorf J., Gaburov E., Zwart S.P.: A sparse octree gravitational N-body code that runs entirely on the GPU processor // Journal of Computational Physics. – 2012. – Vol. 231, N 7. – P. 2825–2839. 6. Belleman R.G., Bédorf J., Portegies Zwart S.F. High performance direct gravitational N-body simulations on graphics processing units II: An implementation in CUDA // New Astronomy– 2008. – Vol. 13, N 2. – P. 103–112. 7. Hamada T., et al. 42 Tflops hierarchical n- body simulations on GPUs with applications in both astrophysics and turbulence // Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. – 2009. – P. 62. 8. Anderson J.A., Lorenz C.D., Travesset A. General purpose molecular dynamics simulations fully implemented on graphics Моделі та засоби паралельних і розподілених програм 31 processing units // Journal of Computational Physics. – 2008. – Vol. 227, N 10. – P. 5342–5359. 9. Makino J., Aarseth S.J. On a Hermite integrator with Ahmad-Cohen // Publications of the Astronomical Society of Japan – 1992. – Vol. 44, N 2. – P. 141–151. 10. GeForce GTX 650 Specifications [Электро- ний ресурс]. – Режим доступу: http://www.geforce.com/hardware/desktop- gpus/geforce-gtx-650/specifications. – 01.11.2012 р. 11. CUDA API REFERENCE MANUAL [Элект- роний ресурс]. – Режим доступу: http://docs.nvidia.com/cuda/pdf/CUDA_Tool kit_Reference_Manual.pdf – 01.11.2012 р. 12. ResourceCharacteristics (GridSim 5.0 beta API Specification) [Электроний ресурс]. – Режим доступу: http://www.buyya.com/gridsim/doc/api/ gridsim/ResourceCharacteristics.html – 01.11.2012 р. 13. First-come, first-served – Wikipedia, the free encyclopedia [Электроний ресурс]. – Режим доступу: http://en.wikipedia. org/wiki/First- come,_first-served. – 01.11.2012 р. 14. Round-robin (алгоритм) – Википедия [Эле- ктроний ресурс]. – Режим доступу: http://ru.wikipedia.org/wiki/Round- robin_(алгоритм). – 01.11.2012 р. Одержано 16.10.2012 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп'ютерних обчислень Інституту програмних систем НАН України, Оконський Ілля В'ячеславович, студент факультету інформатики та обчислювальної техніки, кафедри автоматики i управління в технічних системах НТУУ “КПІ”, Жереб Костянтин Анатолійович, кандидат фізико-математичних наук, науковий співробітник, Бекетов Олексій Геннадійович, аспірант. Місце роботи авторів: Національний технічний університет України "КПІ" 03056, Київ-56, Проспект Перемоги, 37 Тел.: (044) 236 7989, Інститут програмних систем НАН України, 03680, Київ-187, Проспект Академіка Глушкова, 40. Тел.: (044) 526 1538. E-mail: dor@isofts.kiev.ua, logrus.work@gmail.com zhereb@gmail.com beketov.oleksii@gmail.com http://docs.nvidia.com/cuda/pdf/CUDA_Toolkit_Reference_Manual.pdf http://docs.nvidia.com/cuda/pdf/CUDA_Toolkit_Reference_Manual.pdf http://www.buyya.com/gridsim/doc/api/%0bgridsim/ResourceCharacteristics.html http://www.buyya.com/gridsim/doc/api/%0bgridsim/ResourceCharacteristics.html http://en.wikipedia/ mailto:dor@isofts.kiev.ua mailto:logrus.work@gmail.com mailto:zhereb@gmail.com mailto:beketov.oleksii@gmail.com

Usage of modelling tools for determining optimal parameters of programme execution on video graphics accelerators

Institution

Ähnliche Einträge