Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей
У статті проведено оцінку ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей. Проведено порівняння часу виконання паралельної програми в залежності від порядку моделі, кількості дискрет, кількості потоків та блоків графічного процесора. The evaluation of effi...
Збережено в:
| Опубліковано в: : | Індуктивне моделювання складних систем |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83682 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей / І.П. Струбицька // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 288-296. — Бібліогр.: 16 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860248520805580800 |
|---|---|
| author | Струбицька, І.П. |
| author_facet | Струбицька, І.П. |
| citation_txt | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей / І.П. Струбицька // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 288-296. — Бібліогр.: 16 назв. — укр. |
| collection | DSpace DC |
| container_title | Індуктивне моделювання складних систем |
| description | У статті проведено оцінку ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей. Проведено порівняння часу виконання паралельної програми в залежності від порядку моделі, кількості дискрет, кількості потоків та блоків графічного процесора.
The evaluation of efficiency of parallelization of optimization procedure of constructing of dis-crete dynamical models was conducted in this paper. Comparison of the execution time of parallel program depending on the order of model, the number of discretes, the number of threads and blocks of GPU was conducted.
В статье проведена оценка эффективности распараллеливания оптимизационной процедуры построения дискретных динамических моделей. Проведено сравнение времени выполнения параллельной программы в зависимости от порядка модели, количества дискрет, количества потоков и блоков графического процессора.
|
| first_indexed | 2025-12-07T18:39:58Z |
| format | Article |
| fulltext |
Оцінка ефективності розпаралелення оптимізаційної процедури
УДК 519.688
ОЦІНКА ЕФЕКТИВНОСТІ РОЗПАРАЛЕЛЕННЯ ОПТИМІЗАЦІЙНОЇ
ПРОЦЕДУРИ ПОБУДОВИ ДИСКРЕТНИХ ДИНАМІЧНИХ МОДЕЛЕЙ
І.П. Струбицька
Тернопільський національний економічний університет
iryna.str@gmail.com
У статті проведено оцінку ефективності розпаралелення оптимізаційної процедури
побудови дискретних динамічних моделей. Проведено порівняння часу виконання
паралельної програми в залежності від порядку моделі, кількості дискрет, кількості потоків
та блоків графічного процесора.
Ключові слова: дискретні динамічні моделі, метод оптимізації, паралельні обчислення,
розпаралелення, графічні процесори.
The evaluation of efficiency of parallelization of optimization procedure of constructing of dis-
crete dynamical models was conducted in this paper. Comparison of the execution time of parallel
program depending on the order of model, the number of discretes, the number of threads and
blocks of GPU was conducted.
Keywords: discrete dynamic models, optimization methods, parallel computing, parallelization,
GPU.
В статье проведена оценка эффективности распараллеливания оптимизационной процеду-
ры построения дискретных динамических моделей. Проведено сравнение времени выполне-
ния параллельной программы в зависимости от порядка модели, количества дискрет, количе-
ства потоков и блоков графического процессора.
Ключевые слова: дискретные динамические модели, метод оптимизации, параллельные
вычисления, распараллеливания, графические процессоры.
Вступ
Методи побудови дискретних динамічних моделей різноманітних систем
є достатньо розроблені та широко використовуються. Задачі параметричної
ідентифікації дискретних моделей описані в працях Л. Люнга [1], Л. Заде,
Ч. Дезоера [2], В. Стрейца [3], В. М. Кунцевича [4]. З точки зору комп'ютерного
моделювання найбільш перспективним є метод моделювання на основі
дискретних рівнянь стану [5-8]. З математичної точки зору цей підхід є
найбільш формалізованим і має практичне застосування в різних галузях.
У працях П. Г. Стахіва та Ю. Я. Козака [9-10] побудова динамічних
моделей електричних та електронних кіл здійснюється з використанням
оптимізаційного підходу. Такий підхід дає можливість зробити універсальною
побудову моделей. Однак, така універсалізація призводить до появи складних
оптимізаційних задач, які важко розв’язати за прийнятний час навіть з
використанням сучасних засобів обчислювальної техніки.
Актуальним є створення таких методів побудови моделей, які б
піддавалися реалізації на доступних засобах обчислювальної техніки і водночас
забезпечували необхідну швидкодію.
Індуктивне моделювання складних систем, випуск 5, 2013 288
Струбицька І.П.
Тому існує потреба в розробці достатньо універсальних алгоритмів
побудови дискретних динамічних моделей з використанням розпаралелення, за
допомогою яких можна буде ефективно будувати моделі екологічних,
електроенергетичних та інших складних систем.
1. Метод розпаралелення оптимізаційної процедури побудови
дискретних динамічних моделей
Розглянемо узагальнену математичну модель у формі рівнянь стану (1):
( 1) ( ) ( ) ( ) ( )
( 1) ( 1) ( 1)
( ,
,
k k k k
k k k
x Fx Gv x v
y Cx Dv
+
+ + +
мп = + + Fпнп = +по
),k
rr r r r r
r r r (1)
де – вектор змінних стану; ( )kvr – вектор вхідних значень; ( 1)ky +r – вектор
вихідних значень; – матриці, з невідомими коефіцієнтами, які
необхідно знайти при побудові моделі;
, , ,F G C D
– деяка нелінійна вектор-функція
багатьох змінних, форму і коефіцієнти якої також потрібно знайти.
Така форма моделі (1) характеризується деяким вектором невідомих
параметрів
r
λ . Для даної моделі цей вектор складається з елементів матриць
і коефіцієнтів вектор-функції , , ,F G C D ( ) ( )( ,k k )x yF
r r r
.
Введемо деякий критерій для точності моделі , який позначає
відхилення поведінки моделі від поведінки модельованого об’єкту для відомих
проміжків часу. Функція
( ) 0Q λ >
r
( )Q λ
r
, яка називається функцією мети, розраховується
як середньоквадратична похибка значень моделі від значень модельованої
системи:
2*( ) ( ( )) ,Q y y= −∑
r rr rλ λ
де – відомі характеристики модельованого об'єкта, yr *( )y
rr λ – перехідні
характеристики розраховані за допомогою моделі.
Тому побудову моделі можна звести до знаходження значень вектора
r
λ ,
при яких функція мети буде мінімальною. Ця задача розв’язується за
допомогою алгоритму оптимізації.
Задача знаходження мінімальної точки нелінійної функції ( )Q λ
r
багатьох
змінних є складним завданням. При побудові дискретних динамічних моделей
функція мети має чітко виражений яровий характер з великою кількістю
локальних мінімумів. Для розв’язку таких задач найкращими характеристиками
володіє метод напрямного конуса Растригіна [11]. За допомогою цього підходу
Індуктивне моделювання складних систем, випуск 5, 2013 289
Оцінка ефективності розпаралелення оптимізаційної процедури
можна провести цілеспрямований перебір локальних мінімумів, що прискорює
знаходження глобального мінімуму цільової функції. Але обчислювальна
складність такої задачі буде досить велика. Також для побудови якісної моделі
використовується значна кількість вхідних даних. Отже, значними будуть і
затрати машинного часу на реалізацію оптимізаційних процедур.
У праці [12] запропоновано розпаралелення даної задачі з використанням
SIMD-архітектури, яка дозволяє виконати один і той самий потік команд для
багатьох потоків даних.
З практично доступних сьогодні пристроїв з SIMD-архітектурою та за
критерієм ціна/продуктивність є GPU (Graphics Proccesing Unit) [13-14]. Тому
пропонований алгоритм адаптовано саме для цих акселераторів обчислень.
З програмної точки зору реалізація даного розпаралелення не вимагає
великих затрат завдяки програмній архітектурі графічного процесора. Для всіх
потоків пересилається ідентичний програмний код. Вхідними даними для
кожного потоку виступають параметри моделі. Вони для всіх потоків однакові.
На виході кожного потоку отримується значення функції мети. Для кожного
потоку це значення своє. Усі вихідні дані зберігаються у спільній пам’яті
потоків для подальшого обчислення мінімуму. Схематично порівняння
процесів виконання обчислювального алгоритму на центральному та
графічному процесорах представлено на рис. 1.
3λ
r
1λ
r
2λ
r
nλ
r
( )Q λ
r
1( )Q λ
r
2( )Q λ
r
3( )Q λ
r
( )nQ λ
r
iλ
r
Рис. 1. Схема обчислювального алгоритму на CPU та GPU
Для програмної реалізації розпаралеленого алгоритму використано
технологію CUDA (Compute Unified Device Architecture). На даний час
обчислення на графічних процесорах з технологією CUDA — це інноваційне
поєднання обчислювальних особливостей нового покоління графічних
процесорів NVIDIA, що обробляють відразу тисячі потоків з високим рівнем
інформаційного завантаження, які доступні через стандартну мову
програмування С [13].
Індуктивне моделювання складних систем, випуск 5, 2013 290
Струбицька І.П.
2. Дослідження ефективності розпаралелення оптимізаційної
процедури побудови дискретних динамічних моделей
Для того, що оцінити ефективність розпаралелення оптимізаційної
процедури побудови дискретних динамічних моделей проведено власне
тестування розробленого програмного забезпечення. Оскільки обчислення
функції мети в різних точках проводилось у різних потоках графічного
процесора, то досліджено саме цю частину програми. Послідовна частина коду
і так виконується на центральному процесорі, тобто час буде практично
незмінним.
Для проведення тестування швидкодії паралельної програми розрахунку
функції мети побудуємо автономну дискретну динамічну модель третього
порядку, яка матиме наступний вигляд:
( )
,
,
k k
k k
k k
kk
k k
k k
x xF F F
x F F F x
F F Fx x
xy
y C C C x
y x
+
+
+
++
+ +
+ +
мж ц ж цп ж цч чпз зчзч чпз зчч чзз зп чч чзз зч=ч чзз зчч чз чз зч чз чз зч ччзч чи шз зи ш и
н ж цж ц чзчз чзчз чч зз чч з=з чч з чз ч з чз ч з чз ччз чзи ш и ш
1
1 111 12 13
1
2 21 22 23
1
31 32 333 3
11
11
1 1
1 1 2 3 2
1 1
1 3
ппппппп
пппппппппппо
ш
2
де 1,...,52.k =
Входом моделі є середні значення потижневих викидів (двоокису
сульфуру) в атмосферу в м. Живєц (Польща) за 2011 р., а виходом – середні
значення потижневих викидів в 2013 р. [15].
2SO
Функція мети матиме наступний вигляд:
2*
11 11
*
21 21
*
31 31
( ) .i
i
y y
Q y y
y y
λ
⎛ ⎞⎛ ⎞
⎜ ⎟⎜ ⎟= − ⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
∑
r
Проведемо тестування програми обчислення функції мети. Для цього
використано наступне апаратне та системне забезпечення:
− графічний процесор NVIDIA GeForce GTS250 (16 мультипроцесорів по 8
ядер);
− оперативна пам’ять 1024 Мб;
− центральний процесор Core2Duo E8400, 3 ГГц;
Індуктивне моделювання складних систем, випуск 5, 2013 291
Оцінка ефективності розпаралелення оптимізаційної процедури
− материнська плата ASRock G41M-S3;
− операційна система Windows XP.
Для цієї моделі дослідимо час виконання паралельної програми
розрахунку функції мети на 128 ядрах графічного процесора. При 100 запусках
середній час паралельного обчислення функції мети – 2,74 мс.
Дослідимо зміну часу виконання програми в залежності від зміни порядку
моделі, для якої проводиться оптимізація (рис. 2). Очевидно, що час виконання
паралельного розрахунку функцій мети буде поступово збільшуватись із
збільшенням порядку побудованої моделі.
Рис. 2. Залежність часу виконання паралельної програми
від порядку моделі
При збільшенні кількості дискет час виконання паралельного обчислення
функції мети також буде поступово зростати (рис. 3).
Рис. 3. Залежність часу виконання паралельної програми
від кількості дискрет моделі
Цікаво також порівняти залежність часу, що необхідний для всіх
розрахунків функцій мети, від кількості обчислень цільової функції. Тобто, при
різній кількості потоків на графічному процесорі. Очевидно, що для
Індуктивне моделювання складних систем, випуск 5, 2013 292
Струбицька І.П.
послідовного обчислення така залежність має лінійний характер. Для
паралельних обчислень ця залежність показана на рис. 4.
Рис. 4. Залежність часу виконання паралельної програми
від кількості потоків
При цьому випадкових значень чи похибок при замірі часу виконання
паралельної програми не може бути, оскільки всі дані усереднювались по 100
значеннях.
Як видно з рис. 4, така залежність має періодичний характер. Оскільки
час програми обчислювався разом із пересилкою даних, то на кожному циклі є
постійні затримки виконання оптимізаційного алгоритму. Якщо відкинути ці
затримки, то побачимо, що періодичність повторюється через 128 потоків.
Тому доцільно використовувати розпаралелення при кількості потоків кратній
кількості ядер графічного процесора. У нашому випадку це 128 ядер. У такому
разі розпаралелення буде найефективнішим.
Для кращого уявлення побудуємо 3D-графік залежності часу виконання
паралельної програми від кількості потоків і кількості блоків графічного
процесора (рис. 5).
Запропонований підхід паралельних обчислень може використовуватись з
різними оптимізаційними алгоритмами. Тому до уваги не береться час
розрахунку, який необхідний для самого алгоритму. На практиці час обчислень
самого алгоритму є меншим ніж час, який необхідний для розрахунку функції
мети.
Очевидно, що продуктивність центрального процесора значно вища, ніж
продуктивність одного ядра графічного процесора. Проте, паралельна
реалізація буде ефективнішою при одночасному обчисленні функції мети для
багатьох наборів коефіцієнтів моделі [16]. Тобто чим більше проводиться
Індуктивне моделювання складних систем, випуск 5, 2013 293
Оцінка ефективності розпаралелення оптимізаційної процедури
обчислень цільової функції, тим ефективнішим буде розпаралелення процесу
побудови дискретних динамічних моделей.
Рис. 5. Залежність часу виконання паралельної програми
від кількості потоків і кількості блоків
Для оцінювання ефективності запропонованого підходу розпаралелення
порівняємо час, що необхідний для розрахунку функції мети з використанням
розпаралелення та без нього. Обчислимо прискорення паралельної програми за
такою формулою:
,посл
пар
tS
t
=
де – прискорення; – час виконання послідовної програми; – час вико-S послt парt
нання паралельної програми.
Залежність такого прискорення від кількості паралельних обчислень
цільової функції на графічному процесорі показана на рис. 6.
Як бачимо, для великої кількості паралельних потоків обчислення
функції мети досягло прискорення в 5 разів у порівнянні з центральним
процесором. Хоча для тестування використовували один із найпростіших
графічних процесорів із підтримкою технології CUDA.
Додаткові обмеження накладаються для обчислювальної точності.
Сучасні графічні процесори можуть виконувати обчислення з подвійною
Індуктивне моделювання складних систем, випуск 5, 2013 294
Струбицька І.П.
точністю, але в цьому випадку швидкість розрахунків значно знижується.
Проте GPU швидко прогресує, так що ця проблема буде вирішена в
найближчому майбутньому.
Рис. 6. Ефективність розпаралелення з використанням GPU
порівняно з центральним процесором
Висновки
У результаті цього дослідження проведено оцінку ефективності
розпаралелення оптимізаційної процедури побудови дискретних динамічних
моделей. Проведено порівняння часу виконання паралельної програми в
залежності від порядку моделі, кількості дискрет, кількості потоків та блоків
графічного процесора. Також досліджено прискорення виконання паралельної
програми на графічному процесорі порівняно з послідовною на центральному
процесорі. Обчислене прискорення показало ефективність розпаралелення
обчислювального процесу побудови дискретних динамічних моделей.
Література
1. Люнг Л. Идентификация систем. Теория для пользователя / Л. Люнг;
[пер. с англ. под ред. Я.З. Цыпкина]. – М.: Наука. Гл. ред. физ.-мат. лит, 1991. –
432 с.
2. Заде Л. Теория линейных систем. Метод пространства состояний / Л. За-
де, Ч. Дезоер – М.: Наука, 1970. – 704 c.
3. Стрейц В. Метод пространства состояний в теории дискретних линейных
систем управления/ В. Стрейц [Пер. с англ. под ред. Я.З. Цыпкина] – М.: наука.
Главная редакция физико-математической литературы, 1985. – 296 с.
Індуктивне моделювання складних систем, випуск 5, 2013 295
Оцінка ефективності розпаралелення оптимізаційної процедури
4. Кунцевич Р.М. О редуцированных моделях дискретных динамических
объектов и их гарантированных оценках в задачах управления / Р.М. Кунце-
вич // Проблемы управления и информатики. – 2001. – № 1. – С. 42-50.
5. Стахив П.Г. Анализ динамических режимов в электронных схемах с мно-
гополюсниками / П.Г. Стахив – Львов: Высш. школа, 1988. – 154 с.
6. Hinamoto T. Approximation of polynomial state-affine discrete-time systems /
T. Hinamoto, S. Mackava – IEEE Trans. Circ. and Syst. – 1984. – Vol. 33, № 8. –
P. 713-721.
7. Isidori A. Direct Construction of minimal bilinear realization from nonlinear
input-output maps / A. Isidori – IEEE. – 1973. – vol. AC-18, № 6. – P. 626-631.
8. Мельник Б.К. Алгоритм побудови білінійних макромоделей багатополю-
сних елементів електронних схем / Б.К. Мельник, П.Г. Стахів // Теоретична
електротехніка. – 1995. – № 52 – С. 94-98.
9. Стахів П.Г, Побудова макромоделей електромеханічних компонент із ви-
користанням оптимізації / П.Г. Стахів, Ю.Я. Козак // Технічна електродинамі-
ка. – 2001. – №4. – С. 33-36.
10. Стахів П.Г. Побудова математичної макромоделі електромеханічного пе-
ретворювача вентильного двигуна з використанням оптимізації / П.Г. Стахів,
Ю.Я. Козак, В.Г. Гайдук // Електроенергетичні та електромеханічні системи, ві-
сник національного університету «Львівська політехніка». – 2001. – №418. – С.
159-164.
11. Растригин Л.А. Адаптация сложных систем / Л.А. Растригин - Рига: Зина-
тне, 1981. – 375 с.
12. Козак Ю.Я. Розпаралелення алгоритму оптимізації параметрів дискрет-
них динамічних моделей на масивно-паралельних процесорах / Ю.Я., П.Г. Ста-
хів, І.П. Струбицька // Відбір і обробка інформації. - 2010. – Вип. 32 (108). – С.
126-130.
13. Боресков А. В. Параллельные вычисления на GPU. Архитектура и про-
граммная модель CUDA/ А. В. Боресков, А. А. Харламов и др.. – М.: Издатель-
ство Московского университет, 2012. – 336 с.
14. Струбицька І.П. Аналіз сучасних графічних процесорів з підтримкою
CUDA / І.П. Струбицька, А.І. Цигипало // Матеріали ІIІ Всеукраїнської школи-
семінару молодих вчених і студентів «Сучасні комп’ютерні інформаційні тех-
нології”. – Тернопіль: ТНЕУ, 2013. – С. 162-163.
15. Śląski Monitoring Powietrza [Electronic Resource]. – Mode of access:
http://stacje.katowice.pios.gov.pl/iseo/.
16. Stakhiv P. Parallelization of calculations using GPU in optimization approach
for macromodels construction / Petro Stakhiv, Iryna Strubytska, Yuriy Kozak //
Przegląd elektrotechniczny. – 2012. – № 3a. – P. 7-9.
Індуктивне моделювання складних систем, випуск 5, 2013 296
http://stacje.katowice.pios.gov.pl/iseo/
|
| id | nasplib_isofts_kiev_ua-123456789-83682 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0044 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:39:58Z |
| publishDate | 2013 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Струбицька, І.П. 2015-06-21T18:02:11Z 2015-06-21T18:02:11Z 2013 Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей / І.П. Струбицька // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 288-296. — Бібліогр.: 16 назв. — укр. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/83682 519.688 У статті проведено оцінку ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей. Проведено порівняння часу виконання паралельної програми в залежності від порядку моделі, кількості дискрет, кількості потоків та блоків графічного процесора. The evaluation of efficiency of parallelization of optimization procedure of constructing of dis-crete dynamical models was conducted in this paper. Comparison of the execution time of parallel program depending on the order of model, the number of discretes, the number of threads and blocks of GPU was conducted. В статье проведена оценка эффективности распараллеливания оптимизационной процедуры построения дискретных динамических моделей. Проведено сравнение времени выполнения параллельной программы в зависимости от порядка модели, количества дискрет, количества потоков и блоков графического процессора. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Індуктивне моделювання складних систем Наукові статті Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей Article published earlier |
| spellingShingle | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей Струбицька, І.П. Наукові статті |
| title | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| title_full | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| title_fullStr | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| title_full_unstemmed | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| title_short | Оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| title_sort | оцінка ефективності розпаралелення оптимізаційної процедури побудови дискретних динамічних моделей |
| topic | Наукові статті |
| topic_facet | Наукові статті |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83682 |
| work_keys_str_mv | AT strubicʹkaíp ocínkaefektivnostírozparalelennâoptimízacíinoíproceduripobudovidiskretnihdinamíčnihmodelei |