Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов
Предложено развитие алгеброалгоритмической методологии и инструментария для автоматизированного проектирования и генерации программ для графических ускорителей. Особенностью предложенного подхода является использование языковых конструкций, близких к естественному языку, а также применение метода, к...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2015 |
| Автори: | , , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/124768 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов / Ф.И. Андон, А.Е. Дорошенко, А.Г. Бекетов, В.А. Иовчев, Е.А. Яценко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 162-170. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124768 |
|---|---|
| record_format |
dspace |
| spelling |
Андон, Ф.И. Дорошенко, А.Е. Бекетов, А.Г. Иовчев, В.А. Яценко, Е.А. 2017-10-04T19:50:29Z 2017-10-04T19:50:29Z 2015 Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов / Ф.И. Андон, А.Е. Дорошенко, А.Г. Бекетов, В.А. Иовчев, Е.А. Яценко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 162-170. — Бібліогр.: 20 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124768 681.3 Предложено развитие алгеброалгоритмической методологии и инструментария для автоматизированного проектирования и генерации программ для графических ускорителей. Особенностью предложенного подхода является использование языковых конструкций, близких к естественному языку, а также применение метода, который обеспечивает синтаксическую правильность проектируемых алгоритмов и программ. Подход реализован в инструментальной системе, предназначенной для диалогового конструирования схем алгоритмов и генерации программ. Применение инструментария проиллюстрировано на примере разработки параллельной программы из области метеорологии. Запропоновано розвиток алгеброалгоритмічної методології та інструментарію для автоматизованого проектування і генерації програм для графічних прискорювачів. Особливістю підходу є застосування високорівневих специфікацій, поданих в алгебрі алгоритмів, а також використання методу, який забезпечує синтаксичну правильність проектованих алгоритмів та програм. Підхід реалізовано в інструментальній системі, призначеній для діалогового конструювання схем алгоритмів і генерації програм. Застосування інструментарію проілюстровано на прикладі розробки паралельної програми для задачі з області метеорології. The development of the algebra-algorithmic methodology and tools for automated design and generation of programs for graphics processor units is proposed. A particular feature of the proposed approach is the use of high-level specifications that are close to natural language and application of the method that ensures the syntactical regularity of the algorithms and programs being designed. The approach was implemented in the toolkit for interactive design of algorithm schemes and generation of programs. The use of the toolkit is illustrated on the development of a parallel program in meteorology. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов Інструментальні засоби автоматизації паралельного програмування на основі алгебри алгоритмів Software tools for automation of parallel programming on the basis of the algebra of algorithms Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| spellingShingle |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов Андон, Ф.И. Дорошенко, А.Е. Бекетов, А.Г. Иовчев, В.А. Яценко, Е.А. Программно-технические комплексы |
| title_short |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| title_full |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| title_fullStr |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| title_full_unstemmed |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| title_sort |
инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов |
| author |
Андон, Ф.И. Дорошенко, А.Е. Бекетов, А.Г. Иовчев, В.А. Яценко, Е.А. |
| author_facet |
Андон, Ф.И. Дорошенко, А.Е. Бекетов, А.Г. Иовчев, В.А. Яценко, Е.А. |
| topic |
Программно-технические комплексы |
| topic_facet |
Программно-технические комплексы |
| publishDate |
2015 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Інструментальні засоби автоматизації паралельного програмування на основі алгебри алгоритмів Software tools for automation of parallel programming on the basis of the algebra of algorithms |
| description |
Предложено развитие алгеброалгоритмической методологии и инструментария для автоматизированного проектирования и генерации программ для графических ускорителей. Особенностью предложенного подхода является использование языковых конструкций, близких к естественному языку, а также применение метода, который обеспечивает синтаксическую правильность проектируемых алгоритмов и программ. Подход реализован в инструментальной системе, предназначенной для диалогового конструирования схем алгоритмов и генерации программ. Применение инструментария проиллюстрировано на примере разработки параллельной программы из области метеорологии.
Запропоновано розвиток алгеброалгоритмічної методології та інструментарію для автоматизованого проектування і генерації програм для графічних прискорювачів. Особливістю підходу є застосування високорівневих специфікацій, поданих в алгебрі алгоритмів, а також використання методу, який забезпечує синтаксичну правильність проектованих алгоритмів та програм. Підхід реалізовано в інструментальній системі, призначеній для діалогового конструювання схем алгоритмів і генерації програм. Застосування інструментарію проілюстровано на прикладі розробки паралельної програми для задачі з області метеорології.
The development of the algebra-algorithmic methodology and tools for automated design and generation of programs for graphics processor units is proposed. A particular feature of the proposed approach is the use of high-level specifications that are close to natural language and application of the method that ensures the syntactical regularity of the algorithms and programs being designed. The approach was implemented in the toolkit for interactive design of algorithm schemes and generation of programs. The use of the toolkit is illustrated on the development of a parallel program in meteorology.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124768 |
| citation_txt |
Инструментальные средства автоматизации параллельного программирования на основе алгебры алгоритмов / Ф.И. Андон, А.Е. Дорошенко, А.Г. Бекетов, В.А. Иовчев, Е.А. Яценко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 162-170. — Бібліогр.: 20 назв. — рос. |
| work_keys_str_mv |
AT andonfi instrumentalʹnyesredstvaavtomatizaciiparallelʹnogoprogrammirovaniânaosnovealgebryalgoritmov AT dorošenkoae instrumentalʹnyesredstvaavtomatizaciiparallelʹnogoprogrammirovaniânaosnovealgebryalgoritmov AT beketovag instrumentalʹnyesredstvaavtomatizaciiparallelʹnogoprogrammirovaniânaosnovealgebryalgoritmov AT iovčevva instrumentalʹnyesredstvaavtomatizaciiparallelʹnogoprogrammirovaniânaosnovealgebryalgoritmov AT âcenkoea instrumentalʹnyesredstvaavtomatizaciiparallelʹnogoprogrammirovaniânaosnovealgebryalgoritmov AT andonfi ínstrumentalʹnízasobiavtomatizacííparalelʹnogoprogramuvannânaosnovíalgebrialgoritmív AT dorošenkoae ínstrumentalʹnízasobiavtomatizacííparalelʹnogoprogramuvannânaosnovíalgebrialgoritmív AT beketovag ínstrumentalʹnízasobiavtomatizacííparalelʹnogoprogramuvannânaosnovíalgebrialgoritmív AT iovčevva ínstrumentalʹnízasobiavtomatizacííparalelʹnogoprogramuvannânaosnovíalgebrialgoritmív AT âcenkoea ínstrumentalʹnízasobiavtomatizacííparalelʹnogoprogramuvannânaosnovíalgebrialgoritmív AT andonfi softwaretoolsforautomationofparallelprogrammingonthebasisofthealgebraofalgorithms AT dorošenkoae softwaretoolsforautomationofparallelprogrammingonthebasisofthealgebraofalgorithms AT beketovag softwaretoolsforautomationofparallelprogrammingonthebasisofthealgebraofalgorithms AT iovčevva softwaretoolsforautomationofparallelprogrammingonthebasisofthealgebraofalgorithms AT âcenkoea softwaretoolsforautomationofparallelprogrammingonthebasisofthealgebraofalgorithms |
| first_indexed |
2025-11-25T22:43:40Z |
| last_indexed |
2025-11-25T22:43:40Z |
| _version_ |
1850570102701817856 |
| fulltext |
Ô.È. ÀÍÄÎÍ, À.Å. ÄÎÐÎØÅÍÊÎ, À.Ã. ÁÅÊÅÒÎÂ, Â.À. ÈÎÂ×ÅÂ, Å.À. ßÖÅÍÊÎ
ÓÄÊ 681.3 ÈÍÑÒÐÓÌÅÍÒÀËÜÍÛÅ ÑÐÅÄÑÒÂÀ
ÀÂÒÎÌÀÒÈÇÀÖÈÈ ÏÀÐÀËËÅËÜÍÎÃÎ
ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
ÍÀ ÎÑÍÎÂÅ ÀËÃÅÁÐÛ ÀËÃÎÐÈÒÌÎÂ
Àííîòàöèÿ. Ïðåäëîæåíî ðàçâèòèå àëãåáðîàëãîðèòìè÷åñêîé ìåòîäîëîãèè è èíñòðóìåíòà-
ðèÿ äëÿ àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ è ãåíåðàöèè ïðîãðàìì äëÿ ãðàôè÷åñêèõ
óñêîðèòåëåé. Îñîáåííîñòüþ ïðåäëîæåííîãî ïîäõîäà ÿâëÿåòñÿ èñïîëüçîâàíèå ÿçûêîâûõ
êîíñòðóêöèé, áëèçêèõ ê åñòåñòâåííîìó ÿçûêó, à òàêæå ïðèìåíåíèå ìåòîäà, êîòîðûé îáåñ-
ïå÷èâàåò ñèíòàêñè÷åñêóþ ïðàâèëüíîñòü ïðîåêòèðóåìûõ àëãîðèòìîâ è ïðîãðàìì. Ïîäõîä
ðåàëèçîâàí â èíñòðóìåíòàëüíîé ñèñòåìå, ïðåäíàçíà÷åííîé äëÿ äèàëîãîâîãî êîíñòðóèðîâà-
íèÿ ñõåì àëãîðèòìîâ è ãåíåðàöèè ïðîãðàìì. Ïðèìåíåíèå èíñòðóìåíòàðèÿ ïðîèëëþñòðè-
ðîâàíî íà ïðèìåðå ðàçðàáîòêè ïàðàëëåëüíîé ïðîãðàììû èç îáëàñòè ìåòåîðîëîãèè.
Êëþ÷åâûå ñëîâà: àëãåáðà àëãîðèòìîâ, àâòîìàòèçàöèÿ ïðîåêòèðîâàíèÿ è ãåíåðàöèè ïðî-
ãðàìì, ãðàôè÷åñêèå óñêîðèòåëè, ïàðàëëåëüíîå ïðîãðàììèðîâàíèå, ñõåìà àëãîðèòìà.
ÂÂÅÄÅÍÈÅ
 ñâÿçè ñ øèðîêèì ðàñïðîñòðàíåíèåì ìíîãîÿäåðíûõ ïðîöåññîðîâ â ñîâðåìåííûõ
âû÷èñëèòåëüíûõ ñèñòåìàõ àêòóàëüíîé ïðîáëåìîé ÿâëÿåòñÿ ñîçäàíèå ñïåöèàëüíûõ
ñðåäñòâ äëÿ ðàçðàáîòêè è ðåèíæåíåðèè ïàðàëëåëüíîãî ïðîãðàììíîãî îáåñïå÷åíèÿ,
êîòîðûå èñïîëüçîâàëèñü áû íà âñåõ ýòàïàõ æèçíåííîãî öèêëà ïðîãðàìì.
 Èíñòèòóòå ïðîãðàììíûõ ñèñòåì ÍÀÍ Óêðàèíû íà ïðîòÿæåíèè äëèòåëüíî-
ãî ïåðèîäà ðàçâèâàþòñÿ òåîðèÿ, ìåòîäîëîãèÿ è èíñòðóìåíòàðèé äëÿ àâòîìàòèçè-
ðîâàííîãî ïðîåêòèðîâàíèÿ ïàðàëëåëüíûõ ïðîãðàìì, îñíîâàííûå íà ñðåäñòâàõ
àëãåáðû àëãîðèòìèêè [1]. Ïîñëåäíÿÿ ïðåäñòàâëÿåò ñîáîé ñîâðåìåííîå íàïðàâëå-
íèå êîìïüþòåðíîé íàóêè, âîñõîäÿùåå ê ôóíäàìåíòàëüíûì ðàáîòàì àêàäåìèêà
Â.Ì. Ãëóøêîâà ïî òåîðèè ñèñòåì àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ). Îáúåêòîì èñ-
ñëåäîâàíèÿ â íåé ÿâëÿþòñÿ âûñîêîóðîâíåâûå ìîäåëè àëãîðèòìîâ, ïðåäñòàâëåí-
íûå â âèäå ñõåì. Â [1–9] ïðåäëîæåíû ôîðìàëüíûå ñðåäñòâà äëÿ ðàçðàáîòêè ýô-
ôåêòèâíûõ ïàðàëëåëüíûõ ïðîãðàìì äëÿ ìíîãîÿäåðíûõ öåíòðàëüíûõ ïðîöåññî-
ðîâ, ãðàôè÷åñêèõ óñêîðèòåëåé è ñèñòåì ñ ðàñïðåäåëåííîé ïàìÿòüþ. Äàííûå
ñðåäñòâà îñíîâàíû íà èñïîëüçîâàíèè ÑÀÀ [1, 2], îíòîëîãèé [3], àëãåáðîäèíà-
ìè÷åñêèõ ìîäåëåé è äèñêðåòíûõ äèíàìè÷åñêèõ ñèñòåì [4, 5], ìåòîäà ïàðàìåòðè-
÷åñêè óïðàâëÿåìîé ãåíåðàöèè ñõåì àëãîðèòìîâ [6], à òàêæå òåõíèêè ïåðåïèñûâà-
íèÿ òåðìîâ [7–9]. Ñ ó÷åòîì ðàçðàáîòàííîé òåîðèè è ìåòîäîëîãèè ñîçäàí èíòåãðè-
ðîâàííûé èíñòðóìåíòàðèé ïðîåêòèðîâàíèÿ è ñèíòåçà ïðîãðàìì (ÈÏÑ) [2, 6–8],
à òàêæå ñèñòåìà ñèìâîëüíûõ âû÷èñëåíèé TermWare [9].
Ñèñòåìà ÈÏÑ áàçèðóåòñÿ íà ïðåäñòàâëåíèè ñïåöèôèêàöèé àëãîðèòìîâ
â ÑÀÀ è âûïîëíÿåò ãåíåðàöèþ ïîñëåäîâàòåëüíûõ è ïàðàëëåëüíûõ ïðîãðàìì íà
ÿçûêàõ ïðîãðàììèðîâàíèÿ Java è C++. Ñèñòåìà TermWare, îñíîâàííàÿ íà ïàðà-
äèãìå ïåðåïèñûâàþùèõ ïðàâèë, äîïîëíÿåò âîçìîæíîñòè ñèñòåìû ÈÏÑ è èñïîëü-
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1
� Ô.È. Àíäîí, À.Å. Äîðîøåíêî, À.Ã. Áåêåòîâ, Â.À. Èîâ÷åâ, Å.À. ßöåíêî, 2014
çóåòñÿ äëÿ àâòîìàòèçàöèè âûïîëíåíèÿ ôîðìàëüíûõ òðàíñôîðìàöèé àëãîðèòìîâ
â öåëÿõ îïòèìèçàöèè èõ ïðîèçâîäèòåëüíîñòè ïî çàäàííûì êðèòåðèÿì (ïàìÿòü,
áûñòðîäåéñòâèå, çàãðóçêà îáîðóäîâàíèÿ è äð.). Ðàçðàáîòàíà òàêæå íîâàÿ âåðñèÿ
ÈÏÑ — îíëàéíîâûé äèàëîãîâûé êîíñòðóêòîð ñèíòàêñè÷åñêè ïðàâèëüíûõ
ïðîãðàìì (ÎÄÑÏ).
 íàñòîÿùåé ñòàòüå ïðåäëîæåíî äàëüíåéøåå ðàçâèòèå àëãåáðîàëãîðèòìè÷åñ-
êîé ìåòîäîëîãèè è èíñòðóìåíòàðèÿ äëÿ àâòîìàòèçàöèè êîíñòðóèðîâàíèÿ ïàðàë-
ëåëüíûõ ïðîãðàìì äëÿ ãðàôè÷åñêèõ óñêîðèòåëåé (Graphics Processing Units,
GPU), ïîçâîëÿþùèõ çíà÷èòåëüíî ïîâûñèòü ïðîèçâîäèòåëüíîñòü âû÷èñëåíèé ïî
ñðàâíåíèþ ñ îáû÷íûìè ïðîöåññîðàìè. Ðàññìîòðåíà ïðîáëåìà àâòîìàòèçèðîâàí-
íîãî ïðîåêòèðîâàíèÿ è ãåíåðàöèè ïàðàëëåëüíûõ ïðîãðàìì äëÿ ïëàòôîðìû
NVIDIA CUDA [10] ñ èñïîëüçîâàíèåì ñðåäñòâ ÑÀÀ è ñèñòåìû ÎÄÑÏ.
Ïðåäëàãàåìûé ïîäõîä ïîäîáåí îïèñàííîìó â ðàáîòàõ îá àëãåáðàè÷åñêîì ïðî-
ãðàììèðîâàíèè [11] è ñèíòåçå ïðîãðàìì íà îñíîâå ñïåöèôèêàöèé [12, 13], à òàêæå
î ïðîáëåìå ãåíåðàöèè êîäà äëÿ ãðàôè÷åñêèõ ïðîöåññîðîâ. Ñóùåñòâóþùèå ïîäõî-
äû ê ñèíòåçó ïðîãðàìì äëÿ GPU îñíîâàíû, â ÷àñòíîñòè, íà àííîòàöèÿõ äëÿ îïèñà-
íèÿ ñâîéñòâ ñòðóêòóð äàííûõ è îáëàñòåé êîäà [14], ñåòÿõ ïðîöåññîâ Êàíà [15], äè-
ðåêòèâàõ êîìïèëÿòîðà [16], ãðàôàõ ïîòîêà äàííûõ [17], âûñîêîóðîâíåâûõ àáñòðàê-
öèÿõ ñòðóêòóð äàííûõ, çàäà÷ è êîììóíèêàöèîííûõ îïåðàòîðîâ [18].
Îòëè÷èå ïðèâåäåííîãî äàëåå ïîäõîäà ñîñòîèò â èñïîëüçîâàíèè ñïåöèôèêàöèé
àëãåáðû Ãëóøêîâà, ïðåäñòàâëåííûõ â åñòåñòâåííî-ëèíãâèñòè÷åñêîé ôîðìå, îáëåã-
÷àþùåé ïîíèìàíèå àëãîðèòìîâ è äîñòèæåíèå íåîáõîäèìîãî êà÷åñòâà ïðîãðàìì.
Ïðåèìóùåñòâîì ðàçðàáîòàííûõ ñðåäñòâ ÿâëÿåòñÿ ïðèìåíåíèå ìåòîäà äèàëîãîâîãî
êîíñòðóèðîâàíèÿ ñèíòàêñè÷åñêè ïðàâèëüíûõ ïðîãðàìì, èñêëþ÷àþùåãî âîçìîæ-
íîñòü âîçíèêíîâåíèÿ ñèíòàêñè÷åñêèõ îøèáîê â ïðîöåññå ïðîåêòèðîâàíèÿ ñõåì.
Ïðèìåíåíèå ïîäõîäà ïðîèëëþñòðèðîâàíî íà ïðèìåðå ïðîåêòèðîâàíèÿ ïà-
ðàëëåëüíîé ïðîãðàììû èç îáëàñòè ìåòåîðîëîãèè.
ÔÎÐÌÀËÈÇÎÂÀÍÍÎÅ ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÀËÃÅÁÐÛ ÀËÃÎÐÈÒÌÎÂ È ÏÅÐÅÏÈÑÛÂÀÞÙÈÕ ÏÐÀÂÈË
 îñíîâó ïðåäëàãàåìîãî ïîäõîäà ê ïðîåêòèðîâàíèþ ïàðàëëåëüíûõ ïðîãðàìì
ïîëîæåí àïïàðàò ÑÀÀ è èõ ìîäèôèêàöèé [1]. Ìîäèôèöèðîâàííûå ÑÀÀ
(ÑÀÀ-Ì) ïðåäíàçíà÷åíû äëÿ ôîðìàëèçàöèè ïðîöåññîâ ìóëüòèîáðàáîòêè, êîòî-
ðûå âîçíèêàþò ïðè êîíñòðóèðîâàíèè ïðîãðàììíîãî îáåñïå÷åíèÿ â ìóëüòèïðî-
öåññîðíûõ ñèñòåìàõ. Îïèñàííûå ÑÀÀ-Ì ÿâëÿþòñÿ äâóõîñíîâíîé àëãåáðîé
� �U B, ;� , ãäå U — ìíîæåñòâî îïåðàòîðîâ, B — ìíîæåñòâî ëîãè÷åñêèõ óñëî-
âèé (ïðåäèêàòîâ), � — ñèãíàòóðà îïåðàöèé. Îïåðàòîðû ïðåäñòàâëÿþò ñîáîé
îòîáðàæåíèÿ èíôîðìàöèîííîãî ìíîæåñòâà (ÈÌ) â ñåáÿ, ëîãè÷åñêèå óñëîâèÿ
ÿâëÿþòñÿ îòîáðàæåíèÿìè ÈÌ âî ìíîæåñòâî çíà÷åíèé òðåõçíà÷íîé ëîãèêè
E3 0 1� { }, , � , ãäå 0 — ëîæü, 1 — èñòèíà, � — íåîïðåäåëåííîñòü. Ñèãíàòóðà
� � �� �1 2 ñîñòîèò èç ñèñòåìû �1 ëîãè÷åñêèõ îïåðàöèé, ïðèíèìàþùèõ çíà-
÷åíèÿ âî ìíîæåñòâå B, è ñèñòåìû � 2 îïåðàöèé, ïðèíèìàþùèõ çíà÷åíèÿ âî
ìíîæåñòâå îïåðàòîðîâ U . Îïåðàòîðû è ïðåäèêàòû ìîãóò áûòü áàçèñíûìè èëè
ñîñòàâíûìè. Îïåðàöèè, âõîäÿùèå â ñèãíàòóðó �, ðàññìîòðåíû äàëåå.
Íà ÑÀÀ-Ì áàçèðóåòñÿ àëãîðèòìè÷åñêèé ÿçûê ÑÀÀ/1 [1], ïðåäíàçíà÷åííûé
äëÿ ìíîãîóðîâíåâîãî ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ è äîêóìåíòèðîâàíèÿ ïîñëå-
äîâàòåëüíûõ è ïàðàëëåëüíûõ àëãîðèòìîâ è ïðîãðàìì. Ïðåèìóùåñòâîì åãî èñ-
ïîëüçîâàíèÿ ÿâëÿåòñÿ âîçìîæíîñòü îïèñàíèÿ àëãîðèòìîâ â åñòåñòâåííî-ëèíãâèñ-
òè÷åñêîé ôîðìå, óäîáíîé äëÿ ïîëüçîâàòåëÿ, ÷òî îáëåã÷àåò äîñòèæåíèå òðåáóåìî-
ãî êà÷åñòâà ïðîãðàìì. Ïðåäñòàâëåíèÿ îïåðàòîðîâ â ÿçûêå ÑÀÀ/1 íàçûâàþòñÿ
ÑÀÀ-ñõåìàìè.
Ñîñòàâíûå ïðåäèêàòû ÿçûêà ÑÀÀ/1 ñòðîÿòñÿ èç áàçèñíûõ ñ ïîìîùüþ ëîãè-
÷åñêèõ îïåðàöèé ÑÀÀ-Ì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1 163
— äèçúþíêöèÿ predicate predicate1 2OR ;
— êîíúþíêöèÿ predicate predicate1 2AND ;
— îòðèöàíèå NOT predicate.
Ñîñòàâíûå îïåðàòîðû ñòðîÿòñÿ èç ýëåìåíòàðíûõ íà îñíîâå èñïîëüçîâàíèÿ
ñëåäóþùèõ îñíîâíûõ îïåðàöèé:
— ïîñëåäîâàòåëüíîå âûïîëíåíèå îïåðàòîðîâ (êîìïîçèöèÿ) operator1;
operator2;
— îïåðàòîð âåòâëåíèÿ IF ( )THEN ELSE END IF;predicate operator operator1 2
— îïåðàòîð öèêëà WHILE ( ) END OF LOOPpredicate operator .
 ðàáîòàõ [2, 7, 8] ïðèâåäåíû ñïåöèôèêàöèè äîïîëíèòåëüíûõ îïåðàöèé
ÑÀÀ-Ì, ïðåäíàçíà÷åííûõ äëÿ ôîðìàëèçàöèè ìíîãîïîòî÷íûõ âû÷èñëåíèé äëÿ
ìíîãîÿäåðíûõ öåíòðàëüíûõ ïðîöåññîðîâ.
Äàëåå â ñèãíàòóðó � âêëþ÷åíû íîâûå îïåðàöèè, îðèåíòèðîâàííûå íà ïðîåê-
òèðîâàíèå ïàðàëëåëüíûõ ïðîãðàìì äëÿ ïëàòôîðìû NVIDIA CUDA [10]. Îòìå-
òèì, ÷òî òåõíîëîãèÿ CUDA ïðåäñòàâëÿåò ñîáîé ïðîãðàììíî-àïïàðàòíûé êîì-
ïëåêñ, ïîçâîëÿþùèé ðàçðàáàòûâàòü ïðîãðàììû äëÿ ãðàôè÷åñêèõ óñêîðèòåëåé
GPU. Ïîñëåäíèé ÿâëÿåòñÿ âû÷èñëèòåëüíûì óñòðîéñòâîì, ñîïðîöåññîðîì äëÿ
öåíòðàëüíîãî ïðîöåññîðà, èìåþùèì ñîáñòâåííóþ ïàìÿòü è îáðàáàòûâàþùèì ïà-
ðàëëåëüíî îïðåäåëåííîå êîëè÷åñòâî ïîòîêîâ (threads). ßäðîì (kernel) íàçûâàåòñÿ
ôóíêöèÿ äëÿ GPU, âûïîëíÿåìàÿ ïîòîêàìè. Ìîäåëü ïðîãðàììèðîâàíèÿ â CUDA
ïðåäïîëàãàåò ãðóïïèðîâàíèå ïîòîêîâ â áëîêè. Êàæäûé áëîê ïðåäñòàâëÿåò ñîáîé
ìàññèâ ïîòîêîâ, âçàèìîäåéñòâóþùèõ ñ ïîìîùüþ ðàçäåëÿåìîé ïàìÿòè è òî÷åê
ñèíõðîíèçàöèè. Áëîêè, â ñâîþ î÷åðåäü, îáúåäèíÿþòñÿ â ñåòêó áëîêîâ.
Íîâûìè êîíñòðóêöèÿìè ÑÀÀ-Ì äëÿ ïðîåêòèðîâàíèÿ ïðîãðàìì äëÿ ãðàôè-
÷åñêèõ óñêîðèòåëåé ÿâëÿþòñÿ ñëåäóþùèå:
— îïðåäåëåíèå ôóíêöèè-ÿäðà
KERNEL ( )fname param list function body_ _� ,
ãäå fname — íàçâàíèå ôóíêöèè, param list_ — ñïèñîê ôîðìàëüíûõ ïàðàìåò-
ðîâ, function body_ — ðåàëèçàöèÿ ôóíêöèè, ïðåäñòàâëåííàÿ â ÑÀÀ;
— îïåðàöèÿ âûçîâà ôóíêöèè-ÿäðà
fname N N arg listb th( ), , _ ,
ãäå N b — êîëè÷åñòâî áëîêîâ â ñåòêå, N th — êîëè÷åñòâî ïîòîêîâ â êàæäîì
áëîêå, arg list_ — ñïèñîê ôàêòè÷åñêèõ ïàðàìåòðîâ ôóíêöèè;
— îïåðàòîðû, ïîëó÷àþùèå çíà÷åíèÿ ãëîáàëüíîãî (óíèêàëüíîãî) è â ãðàíè-
öàõ áëîêà ëîêàëüíîãî èíäåêñîâ ïîòîêà, à òàêæå ïðèñâàèâàþùèå ïîëó÷åííîå çíà-
÷åíèå öåëî÷èñëåííîé ïåðåìåííîé i:
Get global index of the thread( )i ,
Get local index of the thread( )i ;
— ñèíõðîíèçàòîð — îïåðàöèÿ îæèäàíèÿ çàâåðøåíèÿ âû÷èñëåíèé âñåìè ïîòîêàìè
Synchronizer (all threads completed work);
— îïåðàöèè âûäåëåíèÿ è îñâîáîæäåíèÿ ïàìÿòè ãðàôè÷åñêîãî ïðîöåññîðà
äëÿ íåêîòîðîé ïåðåìåííîé
Allocate the memory for variable on GPU ( )var name size_ , ,
Free the memory for variable on GPU (var name_ ),
ãäå var_ name — íàçâàíèå ïåðåìåííîé, size — îáúåì íåîáõîäèìîé ïàìÿòè
(â áàéòàõ);
— îïåðàöèÿ êîïèðîâàíèÿ äàííûõ èç ïàìÿòè öåíòðàëüíîãî ïðîöåññîðà â ïà-
ìÿòü ãðàôè÷åñêîãî ïðîöåññîðà è â îáðàòíîì íàïðàâëåíèè
Copy data from CPU to GPU ( , , )dest src count ,
Copy data from GPU to CPU ( , , )dest src count ,
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1
ãäå dest — ïåðåìåííàÿ êîïèðîâàíèÿ, src — ïåðåìåííàÿ, çíà÷åíèå êîòîðîé íå-
îáõîäèìî ñêîïèðîâàòü, count — îáúåì êîïèðóåìûõ äàííûõ (â áàéòàõ).
Ïðèìåð 1. Ïðîèëëþñòðèðóåì èñïîëüçîâàíèå íåêîòîðûõ èç îïèñàííûõ âûøå
îïåðàöèé ÑÀÀ-Ì äëÿ ïîñòðîåíèÿ ïðîñòîãî àëãîðèòìà, ïðåäíàçíà÷åííîãî äëÿ âû-
ïîëíåíèÿ íà GPU. Äàëåå ïðèâåäåíà ÑÀÀ-ñõåìà àëãîðèòìà ïàðàëëåëüíîãî çàïîë-
íåíèÿ çíà÷åíèÿìè ýëåìåíòîâ ÷èñëîâîãî ìàññèâà.
SCHEME Parallel algorithm for GPU, assigning values to array elements;
KERNEL Set array values ( , , )A N val �
Get global index of the thread ( )i ;
Assign value ( , )A i i val[ ] � ;
main function =
Declare integer array ( _ , )h A N ;
Declare integer array ( _ )d A ;
Allocate the memory for variable on GPU ( _ , _ )d A A size ;
Set array values ( , , _ ,N N d A Nb th , 10);
Copy data from GPU to CPU ( _ , _ , _ )h A d A A size ;
Free the memory for variable on GPU ( _ )d A ;
Print array ( _ , )h A N ;
Ñõåìà âêëþ÷àåò ðåàëèçàöèþ ôóíêöèè-ÿäðà è îñíîâíîé ôóíêöèè ñõåìû.
Ôóíêöèÿ-ÿäðî Set array values ( , , )A N val âûïîëíÿåò ïðèñâàèâàíèå çíà÷åíèÿ
i val� ýëåìåíòó A i[ ] îäíîìåðíîãî öåëî÷èñëåííîãî ìàññèâà A äëèíû N , ãäå i —
èíäåêñ òåêóùåãî ïîòîêà, val — ïàðàìåòð ôóíêöèè. Â ðåàëèçàöèè îñíîâíîé ôóíê-
öèè (main) ïðèâåäåíû îïåðàòîðû îïðåäåëåíèÿ ïîäëåæàùåãî îáðàáîòêå ìàññèâà
h A_ , êîòîðûé õðàíèòñÿ â ïàìÿòè öåíòðàëüíîãî ïðîöåññîðà, à òàêæå îïåðàòîðû
îïðåäåëåíèÿ è ðåçåðâèðîâàíèÿ ïàìÿòè äëÿ ñîîòâåòñòâóþùåãî ìàññèâà d A_ â ïà-
ìÿòè GPU. Äàëåå âûïîëíÿåòñÿ âûçîâ îïèñàííîé ðàíåå ôóíêöèè-ÿäðà, â ðåçóëüòà-
òå êîòîðîãî îñóùåñòâëÿåòñÿ ïàðàëëåëüíîå çàïîëíåíèå çíà÷åíèÿìè ýëåìåíòîâ
ìàññèâà d A_ . Çíà÷åíèÿ ïàðàìåòðîâ N b è N th (êîëè÷åñòâî áëîêîâ â ñåòêå è ïîòî-
êîâ â êàæäîì áëîêå) âûáèðàþòñÿ òàêèì îáðàçîì, ÷òî N N Nb th* � . Ïîñëå ýòîãî
äàííûå èç ìàññèâà d A_ êîïèðóþòñÿ â ìàññèâ h A_ è âûïîëíÿåòñÿ îïåðàòîð îñâî-
áîæäåíèÿ çàðåçåðâèðîâàííîé ïàìÿòè äëÿ ìàññèâà d A_ . Ïîñëåäíèé îïåðàòîð
â ôóíêöèè main âûâîäèò íà ýêðàí çíà÷åíèå ðåçóëüòèðóþùåãî ìàññèâà h A_ .
 ïðîöåññå ïðîåêòèðîâàíèÿ ñõåì àëãîðèòìîâ äëÿ âûïîëíåíèÿ èõ àâòîìàòè-
çèðîâàííûõ ïðåîáðàçîâàíèé ñîâìåñòíî ñ ÑÀÀ-Ì ïðèìåíÿþòñÿ ïåðåïèñûâàþùèå
ïðàâèëà c èñïîëüçîâàíèåì ðàçðàáîòàííîé ñèñòåìû ñèìâîëüíûõ âû÷èñëåíèé
TermWare [9]. Òðàíñôîðìàöèÿ îñíîâàíà íà ïðèìåíåíèè ê àëãîðèòìó, ïðåäñòàâ-
ëåííîìó â âèäå òåðìà, ñèñòåì ïðàâèë f x x g x xn n( , ..., ) ( , ..., )1 1 , ãäå f è g —
òåðìû, xi — ïåðåìåííûå òåðìîâ.
Ïðèìåð 2. Ïðèìåíèì òåõíèêó ïåðåïèñûâàþùèõ ïðàâèë äëÿ ïðåîáðàçîâàíèÿ
ôóíêöèè-ÿäðà Set array values èç ïðèìåðà 1. Âíà÷àëå ïðåäñòàâèì äàííóþ ôóíê-
öèþ â âèäå òåðìà
set_ array_ values (params ( ),A N val, ,
get_ global_ thread_ index( ),i
assign_ value (arr_ elem( ), summ( ))A i i val, ,
) .
Ïóñòü îïåðàòîð assign_ value, ïðèâåäåííûé â ðåàëèçàöèè äàííîé ôóíêöèè,
íåîáõîäèìî âêëþ÷èòü â áëîê îïåðàòîðà âåòâëåíèÿ IF òàêèì îáðàçîì, ÷òîáû îí
âûïîëíÿëñÿ òîëüêî ïðè óñëîâèè i N� . Äëÿ ýòîãî ê îïèñàííîìó ðàíåå òåðìó ïðè-
ìåíèì ïðàâèëî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1 165
set_ array_ values($ $ assign_ value($ $ ))x x x x1 2 3 4, , ,
set_ array_ values($ $ IF(LESS( ), assign_ valuex x i N1 2, , , ($ $ ))),x x3 4,
ãäå $ $ $ $x x x x1 2 3 4, , , — ïåðåìåííûå. Â ðåçóëüòàòå, èñõîäíûé òåðì ïðåîáðàçó-
åòñÿ â ñëåäóþùèé:
set_ array_ values (params ( ),A N val, ,
get_ global_ thread_ index( ),i
IF (LESS( ), assign_ value (arr_ elem( ), summ (i N A i i val, , , )))
) .
Èñïîëüçîâàíèå îïåðàöèé ÑÀÀ-Ì äëÿ ïðîåêòèðîâàíèÿ ïàðàëëåëüíîãî àëãî-
ðèòìà äëÿ ðåøåíèÿ çàäà÷è èç îáëàñòè ìåòåîðîëîãèè ðàññìîòðåíî äàëåå.
ÈÍÑÒÐÓÌÅÍÒÀËÜÍÛÅ ÑÐÅÄÑÒÂÀ ÀÂÒÎÌÀÒÈÇÈÐÎÂÀÍÍÎÉ
ÐÀÇÐÀÁÎÒÊÈ ÏÐÎÃÐÀÌÌ
Ðàçðàáîòàííûå èíñòðóìåíòàëüíûå ñðåäñòâà àâòîìàòèçèðîâàííîãî ïðîåêòèðîâà-
íèÿ è ãåíåðàöèè ïðîãðàìì îñíîâàíû íà èñïîëüçîâàíèè ÑÀÀ è ìåòîäå äèàëîãî-
âîãî êîíñòðóèðîâàíèÿ ñèíòàêñè÷åñêè ïðàâèëüíûõ ïðîãðàìì (ÄÑÏ-ìåòîäå) [1].
 îòëè÷èå îò òðàäèöèîííûõ ñèíòàêñè÷åñêèõ àíàëèçàòîðîâ ÄÑÏ-ìåòîä îðèåíòè-
ðîâàí íå íà ïîèñê è èñïðàâëåíèå ñèíòàêñè÷åñêèõ îøèáîê, à íà èñêëþ÷åíèå âîç-
ìîæíîñòè èõ ïîÿâëåíèÿ â ïðîöåññå ïîñòðîåíèÿ àëãîðèòìà. Ñóòü ìåòîäà çàêëþ-
÷àåòñÿ â ïîóðîâíåâîì êîíñòðóèðîâàíèè ñõåì ñâåðõó âíèç ïóòåì ñóïåðïîçèöèè
ÿçûêîâûõ êîíñòðóêöèé ÑÀÀ-Ì. Íà êàæäîì øàãå êîíñòðóèðîâàíèÿ ñèñòåìà
â äèàëîãå ñ ïîëüçîâàòåëåì ïðåäîñòàâëÿåò íà âûáîð ëèøü òå êîíñòðóêöèè, ïîäñòà-
íîâêà êîòîðûõ â ôîðìèðóåìûé òåêñò íå íàðóøàåò ñèíòàêñè÷åñêîé ïðàâèëüíîñòè
ñõåìû. Íà îñíîâå ïîñòðîåííîé ñõåìû àëãîðèòìà âûïîëíÿåòñÿ àâòîìàòè÷åñêàÿ ãå-
íåðàöèÿ òåêñòà ïðîãðàììû. Îòîáðàæåíèå îïåðàöèé ÑÀÀ-Ì â òåêñò íà ÿçûêå ïðî-
ãðàììèðîâàíèÿ ïðåäñòàâëåíî â âèäå øàáëîíîâ è õðàíèòñÿ â áàçå äàííûõ.
Îïèñàííûé ïîäõîä ðåàëèçîâàí â ñèñòåìå ÈÏÑ [2, 6–8]. Äëÿ àâòîìàòèçàöèè
âûïîëíåíèÿ òðàíñôîðìàöèé àëãîðèòìîâ ñèñòåìà ÈÏÑ ïðèìåíÿåòñÿ ñîâìåñòíî
ñ ñèñòåìîé TermWare [9], îñíîâàííîé íà ïàðàäèãìå ïåðåïèñûâàþùèõ ïðàâèë.
Ðàññìîòðèì íîâóþ âåðñèþ ñèñòåìû ÈÏÑ — ñèñòåìó ÎÄÑÏ, ïðåäíàçíà÷åí-
íóþ äëÿ äèàëîãîâîãî ïðîåêòèðîâàíèÿ, ãåíåðàöèè è çàïóñêà ïðîãðàìì. Îñîáåí-
íîñòüþ èíñòðóìåíòàðèÿ ÎÄÑÏ ïî ñðàâíåíèþ ñ ÈÏÑ ÿâëÿåòñÿ ìíîãîïîëüçîâà-
òåëüñêîå èñïîëüçîâàíèå ñèñòåìû ÷åðåç Èíòåðíåò è ðàñïðåäåëåííàÿ àðõèòåêòóðà
ñèñòåìû. Îòìåòèì, ÷òî êîìïîíåíòû èíñòðóìåíòàðèÿ ÎÄÑÏ àâòîíîìíû, ãèáêî
ñâÿçàíû è èìåþò ñîãëàñîâàííûé ïðîòîêîë îáìåíà äàííûìè, ò.å. îïèñàííàÿ ìî-
äåëü ïî ñóòè ÿâëÿåòñÿ ñåðâèñíî-îðèåíòèðîâàííîé.
Ñèñòåìà ÎÄÑÏ ñîñòîèò èç ñëåäóþùèõ êîìïîíåíòîâ (ðèñ. 1). Êëèåíò —
âåá-èíòåðôåéñ äëÿ äèàëîãîâîãî âçàèìîäåéñòâèÿ ïîëüçîâàòåëÿ ñ ñèñòåìîé è åå ðå-
ñóðñàìè. Îí ïðåäîñòàâëÿåò âîç-
ìîæíîñòü êîíñòðóèðîâàòü ñõåìû
àëãîðèòìîâ, âûáèðàÿ íåîáõîäè-
ìûå ýëåìåíòû áàçû äàííûõ, îñó-
ùåñòâëÿòü ãåíåðàöèþ êîäà íà
öåëåâîì ÿçûêå ïðîãðàììèðîâàíèÿ
(Java èëè C++) è âûïîëíÿòü çà-
ïóñê ïðîãðàìì â âû÷èñëèòåëüíîé
ñðåäå. Â îñíîâó ïðîåêòèðîâàíèÿ
àëãîðèòìîâ â ñèñòåìå ïîëîæåí
äèàëîãîâûé ðåæèì ñ èñïîëüçîâà-
íèåì ñïèñêà êîíñòðóêöèé è äåðå-
âà àëãîðèòìà. Ñïåöèôèêàöèè ÿçû-
êîâûõ êîíñòðóêöèé îñíîâàíû íà
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1
Ãåíåðàòîð
ïðîãðàìì
Äèñïåò÷åð
Ñõåìà àëãîðèòìà
Êëèåíò
Øëþç
Ñðåäà
âûïîëíåíèÿ
Áàçà
äàííûõ
Ðèñ. 1. Àðõèòåêòóðà ñèñòåìû ÎÄÑÏ
àíãëîÿçû÷íîé âåðñèè ÿçûêà ÑÀÀ/1. Ïîñòðîåíèå ñõåì îñóùåñòâëÿåòñÿ ñâåðõó
âíèç ïóòåì äåòàëèçàöèè àëãîðèòìè÷åñêèõ êîíñòðóêöèé.  ïðîöåññå êîíñòðóèðî-
âàíèÿ ñõåìû ïîëüçîâàòåëü ïîî÷åðåäíî âûáèðàåò íåîáõîäèìûå êîíñòðóêöèè èç
ñïèñêà è äîáàâëÿåò èõ â äåðåâî.
Äèñïåò÷åð ÿâëÿåòñÿ ÿäðîì èíñòðóìåíòàðèÿ è îðãàíèçóåò ñâÿçü ìåæäó êëèåí-
òîì, ãåíåðàòîðîì ïðîãðàìì, øëþçîì è áàçîé äàííûõ. Ãåíåðàòîð ïðîãðàìì âû-
ïîëíÿåò ãåíåðàöèþ òåêñòà ïðîãðàììû íà îñíîâå ñõåìû àëãîðèòìà, ïîñòðîåííîé
ñ ïîìîùüþ èíòåðôåéñà (êëèåíòà). Øëþç îáåñïå÷èâàåò çàïóñê, àíàëèç è ïîëó÷å-
íèå ðåçóëüòàòîâ ðàáîòû ïðîãðàìì â ñðåäå âûïîëíåíèÿ. Ïîñëåäíÿÿ ïðåäñòàâëÿåò
ñîáîé ïðîãðàììíóþ ïëàòôîðìó, óñòàíîâëåííóþ íà ñòîðîíå ñåðâåðà ñèñòåìû
ÎÄÑÏ, âêëþ÷àåò îïåðàöèîííóþ ñèñòåìó è ïðîãðàììíîå îáåñïå÷åíèå, íåîáõîäè-
ìîå äëÿ êîìïèëÿöèè è çàïóñêà ïðîãðàìì.
 áàçå äàííûõ ñèñòåìû ÎÄÑÏ õðàíÿòñÿ ðàçðàáîòàííûå ïðîåêòû àëãîðèòìîâ,
îïèñàíèå ÿçûêîâûõ êîíñòðóêöèé ÑÀÀ-Ì, êàðêàñîâ ïðîåêòîâ íà ÿçûêå ïðîãðàì-
ìèðîâàíèÿ, èíôîðìàöèÿ î íàñòðîéêàõ çàïóñêà ïðîãðàìì. Îïèñàíèå êàæäîé ÿçû-
êîâîé êîíñòðóêöèè ÑÀÀ-Ì â áàçå äàííûõ âêëþ÷àåò åå ïðåäñòàâëåíèå â åñòåñ-
òâåííî-ëèíãâèñòè÷åñêîé ôîðìå, èíôîðìàöèþ î òèïå êîíñòðóêöèè, ðåàëèçàöèþ
(øàáëîí) íà âûáðàííîì ÿçûêå ïðîãðàììèðîâàíèÿ, íàçâàíèÿ ïåðåìåííûõ è
ñïèñîê ôîðìàëüíûõ ïàðàìåòðîâ.
Ðàíåå ñèñòåìà ÎÄÑÏ â îñíîâíîì èñïîëüçîâàëàñü äëÿ ðàçðàáîòêè ïàðàëëåëü-
íûõ ïðîãðàìì ñîðòèðîâêè äëÿ ìíîãîÿäåðíûõ öåíòðàëüíûõ ïðîöåññîðîâ. Â äàí-
íîé ðàáîòå áàçà äàííûõ ñèñòåìû äîïîëíåíà îïåðàöèÿìè, îðèåíòèðîâàííûìè íà
ïðîåêòèðîâàíèå ïðîãðàìì äëÿ ãðàôè÷åñêèõ óñêîðèòåëåé.
ÏÐÈÌÅÐ ÏÐÈÌÅÍÅÍÈß ÀËÃÅÁÐÎÀËÃÎÐÈÒÌÈ×ÅÑÊÎÃÎ ÈÍÑÒÐÓÌÅÍÒÀÐÈß
ÄËß ÏÐÎÅÊÒÈÐÎÂÀÍÈß ÏÐÈÊËÀÄÍÎÉ ÏÀÐÀËËÅËÜÍÎÉ ÏÐÎÃÐÀÌÌÛ
Ðàññìîòðèì èñïîëüçîâàíèå àïïàðàòà ÑÀÀ-Ì è ñèñòåìû ÎÄÑÏ íà ïðèìåðå
ðàçðàáîòêè CUDA-ïðîãðàììû äëÿ ðåøåíèÿ äâóìåðíîé çàäà÷è êîíâåêòèâíîé
äèôôóçèè, êîòîðàÿ âîçíèêàåò ïðè ìàòåìàòè÷åñêîì ìîäåëèðîâàíèè öèðêóëÿöèè
àòìîñôåðû â ìåòåîðîëîãèè. Äàííàÿ òåñòîâàÿ çàäà÷à ñîñòîèò â ðåøåíèè ñîâî-
êóïíîñòè óðàâíåíèé êîíâåêòèâíîé äèôôóçèè:
�
�
�
�
�
�
�
�� �
u
t
v
u
x
v
u
x x
u
x x
u
1
1
2
2 1
1
1 2
2� �
x
f
2
�
�
�
�
�� � (1)
ïðè ( , ) , [ ; ],x x t1 2 0 10� ��
u x x x x( ) sin( )0 1 2 1 2, , � � (2)
ïðè ( , ) ,x x t1 2 0� �� ,
u t x x u t x xA( ) ( ), , , ,1 2 1 2� (3)
ïðè ( , ) , [ ; ]x x t1 2 0 10�
�� ,
ãäå
� � �[ ] [ ];0 1 0 1, , v x xk k kk
� � � �sin ( ); � 0 001 0 1 02. . *sin ( ) ;
f t x x v v x x( ) ( ( (sin (2 ) sin (2 )))), , . * *1 2 1 2 1 21 0 1� � � � �
* *cos ( ) ( ) sin ( ).1 2x x t x x t1 2 1 2� � � � � �� �
Çäåñü u u t x x� ( ), ,1 2 — çàâèñèìàÿ ôóíêöèÿ (íàïðèìåð, ñêîðîñòü âåòðà); t —
âðåìÿ; x1, x2 — êîîðäèíàòû; � — äâóìåðíàÿ ïðîñòðàíñòâåííàÿ îáëàñòü îïðå-
äåëåíèÿ çàäà÷è; f f t x x� ( ), ,1 2 — ñâîáîäíûé ÷ëåí óðàâíåíèÿ; vk — êîýôôè-
öèåíò êîíâåêöèè; �k – êîýôôèöèåíò äèôôóçèè. Äàëåå äëÿ êîîðäèíàò x1 è x2
èñïîëüçîâàíû îáîçíà÷åíèÿ x è y ñîîòâåòñòâåííî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1 167
Äëÿ ðåøåíèÿ çàäà÷è (1)–(3) â ÑUDÀ-ïðîãðàììå ïðèìåíÿåòñÿ êîíå÷íî-ðàç-
íîñòíûé ÷èñëåííûé ìåòîä, èçëîæåííûé â [19].  ïðîöåññå ðåøåíèÿ îáëàñòü �
ðàçáèâàåòñÿ íà S x è S y ðàâíîìåðíûõ øàãîâ (óçëîâ) ïî îñÿì x è y ñîîòâåòñòâåííî.
Òàêèì îáðàçîì, îáùåå êîëè÷åñòâî óçëîâ ñîñòàâëÿåò S Sx y� . Ðàñïàðàëëåëèâàíèå
âû÷èñëåíèé äëÿ äàííîé çàäà÷è çàêëþ÷àåòñÿ â ðàçáèåíèè îáëàñòè ðàçìåðîì
S Sx y� íà ïîäìíîæåñòâà è ïàðàëëåëüíîì ðåøåíèè ñîâîêóïíîñòè ïîäçàäà÷, îïðå-
äåëåííûõ íà ýòèõ ïîäìíîæåñòâàõ.
Äàëåå ïðèâåäåíà îáùàÿ ÑÀÀ-ñõåìà ðàçðàáîòàííîãî ïàðàëëåëüíîãî GPU-àë-
ãîðèòìà äëÿ çàäà÷è êîíâåêòèâíîé äèôôóçèè. Ñõåìà ïîñòðîåíà â ñèñòåìå ÎÄÑÏ
â ñîîòâåòñòâèè ñ ðàññìîòðåííûì ðàíåå ìåòîäîì äèàëîãîâîãî êîíñòðóèðîâàíèÿ.
Êðîìå îïèñàííûõ ïåðåìåííûõ S x è S y àëãîðèòì ñîäåðæèò òàêèå îñíîâíûå ïåðå-
ìåííûå: N b — êîëè÷åñòâî áëîêîâ â ñåòêå CUDA; N th — êîëè÷åñòâî ïîòîêîâ
â êàæäîì áëîêå; Time � 0 — íà÷àëüíîå çíà÷åíèå âðåìåíè; T �10 — êîíå÷íîå çíà-
÷åíèå âðåìåíè; dT � 0 001. — âðåìåííîé øàã; t — âðåìÿ; m — êîëè÷åñòâî âû÷èñ-
ëèòåëüíûõ øàãîâ; h pX_ , d pX_ , h pY_ , d pY_ — ìàññèâû àðãóìåíòîâ; ux è u y —
ìàññèâû äëÿ õðàíåíèÿ çíà÷åíèé ôóíêöèè u.
SCHEME Parallel algorithm for convection-diffusion problem for GPU;
main function �
Get command line arguments ( , )S Sx y ;
Initialize the data for convection-diffusion problem;
Start the timer;
Input of initial data ( , )N Nb th ;
Fill the arrays of equation coefficients ( , , * )N N Time m dTb th � ;
Fill the array for function u with initial values ( , )N Nb th ;
Synchronizer (all threads completed work);
Copy data from GPU to CPU ( _ , _ , _ _ )h pX d pX d pX size ;
Copy data from GPU to CPU ( _ , _ , _ _ )h pY d pY d pY size ;
Synchronizer (all threads completed work );
Declare integer variable ( , )t 0 ;
WHILE ( * * )m dT t T�
Fill the arrays of equation coefficients ( , , * )N N Time m dTb th � ;
Fill the border conditions with zero values ( , )N Nb th ;
Fill the border conditions ( , )N Nb th ;
Fill the arrays of equation coefficients ( ,N Nb th , Time) ;
Fill arrays ux and u y with initial values ( , )N Nb th ;
Synchronizer (all threads completed work) ;
Compute ux ( , )N Nb th ;
Synchronizer (all threads completed work);
Compute u y ( , )N Nb th ;
Synchronizer (all threads completed work);
Compute average value on the basis of ux and u y ( , )N Nb th ;
Synchronizer (all threads completed work);
Increment (Time, m dT* ) ;
Increment (t, 1);
END OF LOOP;
Stop the timer and print the execution time;
Copy data from GPU to CPU for convection-diffusion problem;
Compare computed function values with real values and compute an error;
Write the obtained results for function u to files;
Deallocate memory for variables of convection-diffusion problem;
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1
Ðåàëèçàöèÿ îñíîâíîé ôóíêöèè ïðèâåäåííîé ÑÀÀ-ñõåìû íà÷èíàåòñÿ ñ îïå-
ðàòîðà, êîòîðûé ñ÷èòûâàåò çíà÷åíèå äâóõ ïàðàìåòðîâ êîìàíäíîé ñòðîêè è ïðè-
ñâàèâàåò ñîîòâåòñòâóþùèå çíà÷åíèÿ ïåðåìåííûì S x è S y . Äàëåå âûïîëíÿåòñÿ
èíèöèàëèçàöèÿ äàííûõ è íà÷èíàåòñÿ îòñ÷åò âðåìåíè. Ïîñëå ýòîãî îïåðàöèè ñ àð-
ãóìåíòàìè N b è N th îñóùåñòâëÿþò âûçîâû ôóíêöèé-ÿäåð. Ïîñëåäíèå ââîäÿò íà-
÷àëüíûå äàííûå, çàïîëíÿþò ìàññèâû êîýôôèöèåíòîâ óðàâíåíèé è ìàññèâ äëÿ
ôóíêöèè u. Ñèíõðîíèçàòîð, ïðèâåäåííûé ïîñëå âûçîâîâ ôóíêöèé, âûïîëíÿåò çà-
äåðæêó âû÷èñëåíèé äî òåõ ïîð, ïîêà âñå ïîòîêè íå çàâåðøàò ðàáîòû. Îòìåòèì,
÷òî àëãîðèòì ñîäåðæèò öèêë WHILE, â òåëå êîòîðîãî íàõîäÿòñÿ âûçîâû äîïîë-
íèòåëüíûõ ôóíêöèé-ÿäåð, çàïîëíÿþùèõ ìàññèâû êîýôôèöèåíòîâ, ãðàíè÷íûõ
óñëîâèé, à òàêæå âû÷èñëÿþùèõ çíà÷åíèÿ ux , u y è ñðåäíåå çíà÷åíèå. Àëãîðèòìû
ôóíêöèé-ÿäåð ïðåäñòàâëÿþòñÿ â îòäåëüíûõ ÑÀÀ-ñõåìàõ.
Îáùèì ðåçóëüòàòîì âûïîëíåíèÿ àëãîðèòìà ÿâëÿåòñÿ ñîâîêóïíîñòü âû÷èñ-
ëåííûõ çíà÷åíèé ôóíêöèè u äëÿ êîîðäèíàò x è y, ãäå ( , )x y ��.  êîíöå ïðîãðàì-
ìû âûïîëíÿåòñÿ ñðàâíåíèå ïîëó÷åííûõ çíà÷åíèé ôóíêöèè u ñ ðåàëüíûìè è âû-
÷èñëÿåòñÿ ïîãðåøíîñòü. Ïîñëå ýòîãî çíà÷åíèÿ êîîðäèíàò è ôóíêöèè u
çàïèñûâàþòñÿ â ôàéëû.
Ñ èñïîëüçîâàíèåì ñèñòåìû ÎÄÑÏ íà îñíîâå ïîñòðîåííîé ñõåìû àëãîðèòìà
àâòîìàòè÷åñêè ñãåíåðèðîâàí òåêñò ïðîãðàììû íà ÿçûêå CUDA C. Ïðîâåäåí
ýêñïåðèìåíò ïî âûïîëíåíèþ ðàçðàáîòàííîé ïàðàëëåëüíîé ïðîãðàììû è ñîîò-
âåòñòâóþùåé ïîñëåäîâàòåëüíîé ïðîãðàììû íà îäíîì èç óçëîâ ðàçäåëà ÑÊÈÒ-4
êëàñòåðà Èíñòèòóòà êèáåðíåòèêè ÍÀÍ Óêðàèíû [20]. Äàííûé óçåë ñîäåðæèò ãðà-
ôè÷åñêèé óñêîðèòåëü NVIDIA Tesla M2075 (448 âû÷èñëèòåëüíûõ ÿäåð) è öåí-
òðàëüíûé ïðîöåññîð Intel Xeon E5-2670. ×èñëåííûå ýêñïåðèìåíòû âûïîëíåíû
äëÿ çíà÷åíèé ðàçìåðà çàäà÷è îò S Sx y� � �64 64 äî S Sx y� � �2048 2048. Ïîëó-
÷åíû çíà÷åíèÿ ìóëüòèïðîöåññîðíîãî óñêîðåíèÿ T Ts p/ , ãäå Ts è Tp — âðåìÿ âû-
ïîëíåíèÿ ïîñëåäîâàòåëüíîé è ïàðàëëåëüíîé ïðîãðàììû ñîîòâåòñòâåííî. Ìàêñè-
ìàëüíîå çíà÷åíèå óñêîðåíèÿ ïðè S Sx y� � �2048 2048 ñîñòàâèëî 69 ðàç.
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåíî ðàçâèòèå àëãåáðîàëãîðèòìè÷åñêîé ìåòîäîëîãèè è èíñòðóìåíòàðèÿ
äëÿ àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ è ãåíåðàöèè ïðîãðàìì äëÿ ãðàôè-
÷åñêèõ óñêîðèòåëåé. Ïðåèìóùåñòâî îïèñàííîãî ïîäõîäà ñîñòîèò â èñïîëüçîâà-
íèè ÿçûêîâûõ êîíñòðóêöèé, áëèçêèõ ê åñòåñòâåííîìó ÿçûêó, à òàêæå â ïðèìå-
íåíèè ìåòîäà, êîòîðûé îáåñïå÷èâàåò ñèíòàêñè÷åñêóþ ïðàâèëüíîñòü ïðîåêòè-
ðóåìûõ àëãîðèòìîâ è ïðîãðàìì. Ïîäõîä ðåàëèçîâàí â èíñòðóìåíòàëüíîé
ñèñòåìå, ïðåäíàçíà÷åííîé äëÿ äèàëîãîâîãî êîíñòðóèðîâàíèÿ ñõåì àëãîðèòìîâ
è ãåíåðàöèè ïðîãðàìì íà îñíîâå êîìïîíåíòîâ ïîâòîðíîãî èñïîëüçîâàíèÿ, ò.å.
îïåðàöèé àëãåáðû àëãîðèòìîâ. Ïðèìåíåíèå èíñòðóìåíòàðèÿ ïðîèëëþñòðèðîâà-
íî íà ïðèìåðå ðàçðàáîòêè ïàðàëëåëüíîé ïðîãðàììû äëÿ çàäà÷è êîíâåêòèâíîé
äèôôóçèè. Ïðîâåäåí ýêñïåðèìåíò ïî âûïîëíåíèþ ðàçðàáîòàííîé ïðîãðàììû
íà ãðàôè÷åñêîì óñêîðèòåëå, â ðåçóëüòàòå êîòîðîãî ïîëó÷åí õîðîøèé
ïîêàçàòåëü ðàñïàðàëëåëèâàåìîñòè âû÷èñëåíèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í Ã . Å . , ß ö å í ê î Å . À .
Àëãåáðîàëãîðèòìè÷åñêèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Êèåâ:
Àêàäåìïåðèîäèêà, 2007. — 631 ñ.
2. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . , ß ö å í ê î Å . À . Ôîðìàëèçîâàííîå ïðîåêòèðîâàíèå
ýôôåêòèâíûõ ìíîãîïîòî÷íûõ ïðîãðàìì // Ïðîáëåìû ïðîãðàììèðîâàíèÿ. — 2007. — ¹ 1. —
Ñ. 17–30.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1 169
3. D o r o s h e n k o A . , Y a t s e n k o O . Using ontologies and algebra of algorithms for formalized
development of parallel programs // Fundamenta Inform. — 2009. — 93, N 1–3. — P. 111–125.
4. D o r o s h e n k o A . , Z h e r e b K . , Y a t s e n k o O . Formal facilities for designing efficient
GPU programs // Proc. Int. Workshop “Concurrency, Specification, and Programming”
(CS&P’2010). (Bernau, 27–29 Sept., 2010). — Berlin: Humboldt University, 2010. — P. 142–153.
5. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . Ïðîãðàììèðîâàíèå âûñîêîïðîèçâî-
äèòåëüíûõ ïàðàëëåëüíûõ âû÷èñëåíèé: ôîðìàëüíûå ìîäåëè è ãðàôè÷åñêèå óñêîðèòåëè // Êè-
áåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011. — ¹ 4. — Ñ. 176–187.
6. Y a t s e n k o O . On parameter-driven generation of algorithm schemes // Proc. Intern. Workshop
“Concurrency, Specification, and Programming” (CS&P’2012). (Berlin, 26–28 Sept., 2012). —
Berlin: Humboldt University, 2012. — P. 428–438.
7. D o r o s h e n k o A . , Z h e r e b K . , Y a t s e n k o O . Developing and optimizing parallel
programs with algebra-algorithmic and term rewriting tools // Proc. Intern. Conf. “Information and
Communication Technologies in Education, Research, and Industrial Applications” (ICTERI’2013).
(Kherson, 19–22 June, 2013), Revised Selected Papers. — Berlin: Springer-Verlag. — 2013. — 412.
— P. 70–92.
8. ß ö å í ê î Å . À . Èíòåãðàöèÿ èíñòðóìåíòàëüíûõ ñðåäñòâ àëãåáðû àëãîðèòìîâ è ïåðåïèñûâà-
íèÿ òåðìîâ äëÿ ðàçðàáîòêè ýôôåêòèâíûõ ïàðàëëåëüíûõ ïðîãðàìì // Ïðîáëåìû ïðîãðàììèðî-
âàíèÿ. — 2013. — ¹ 2. — Ñ. 62–70.
9. D o r o s h e n k o A . , S h e v c h e n k o R . A Rewriting framework for rule-based programming
dynamic applications // Fundamenta Inform. — 2006. — 72, N 1–3. — P. 95–108.
10. W i l t N . The CUDA handbook. A Comprehensive guide to GPU programming. — Boston:
Addison-Wesley, 2013. — 528 p.
11. S a n n e l l a D . , T a r l e c k i A . Foundations of algebraic specification and formal software
development. — Berlin: Springer-Verlag, 2012. — 594 p.
12. F l e n e r P . Achievements and prospects of program synthesis // Lecture Notes in Artificial
Intelligence. — 2002. — 2407. — P. 310–346.
13. G u l w a n i S . Dimensions in program synthesis // Proc. 12th Intern. ACM SIGPLAN symposium
on Principles and practice of declarative programming. (Hagenberg, 26–28 July, 2010). — New
York: ACM, 2010. — P. 13–24.
14. U e n g S . , L a t h a r a M . , B a g h s o r k h i S . S . , H w u W . W . C U D A - l i t e : r e d u c i n g
G P U p r o g r a m m i n g c o m p l e x i t y CUDA-lite: reducing GPU programming complexity //
Proc. 21st Intern. Workshop on Languages and Compilers for Parallel Computing (LCPC’2008).
(Edmonton, 31 July–2 Aug, 2008). — Berlin: Springer-Verlag, 2008. — P. 1–15.
15. H a i d W . , S c h o r L . , H u a n g K . , B a c i v a r o v I . , T h i e l e L . Efficient execution of
Kahn process networks on multi-processor systems using protothreads and windowed FIFOs // Proc.
Workshop on Embedded Systems for Real-Time Multimedia (ESTImedia’09). (Grenoble, 15–16
Oct., 2009). — Los Alamitos: IEEE Computer Society Press, 2009. — P. 35–44.
16. H a n T . D . , A b d e l r a h m a n T . S . hiCUDA: A High-level language for GPU programming //
IEEE Transactions on Parallel and Distributed systems. — 2011. — 22, N 1. — P. 78–90.
17. J u n g H . , Y i Y . , H a S . Automatic CUDA code synthesis framework for multicore CPU and
GPU architectures // Lecture Notes in Comp. Sci. — 2012. — 7203. — P. 579–588.
18. D u b a c h C . , C h e n g P . , R a b b a h R . , B a c o n D . F . , F i n k S . J . Compiling
a high-level language for GPUs (via language support for architectures and compilers) // Proc. 33rd
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’12).
(Beijing, 11–16 June, 2012). — New York: ACM, 20112 — P. 1–12.
19. Ï ð ó ñ î â  . À . , Ä î ð î ø å í ê î À . Å . , × å ð í û ø Ð . È . Ìåòîä ÷èñëåííîãî ðåøåíèÿ ìíî-
ãîìåðíîé çàäà÷è êîíâåêòèâíîé äèôôóçèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. —
¹ 1. — Ñ. 100–107.
20. Ñ ó ï å ð ê î ì ï ü þ ò å ð Èíñòèòóòà êèáåðíåòèêè ÍÀÍ Óêðàèíû — http: // icybcluster.org.ua
Ïîñòóïèëà 12.09.2014
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 50, ¹ 1
|