Программирование высокопроизводительных параллельных вычислений: формальные модели и графические ускорители
Запропоновано розвиток формальних методів проектування, заснований на концепціях алгебраїчного програмування і алгебро-динамічних моделей програм з використанням техніки пере писувальних правил, для автоматизованої розробки ефективних програм для графічних прискорю вачів. Розроблені формальні засоби...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84226 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Программирование высокопроизводительных параллельных вычислений: формальные модели и графические ускорители / Ф.И. Андон, А.Е. Дорошенко, К.А. Жереб // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 176-187. — Бібліогр.: 23 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84226 |
|---|---|
| record_format |
dspace |
| spelling |
Андон, Ф.И. Дорошенко, А.Е. Жереб, К.А. 2015-07-03T18:41:42Z 2015-07-03T18:41:42Z 2011 Программирование высокопроизводительных параллельных вычислений: формальные модели и графические ускорители / Ф.И. Андон, А.Е. Дорошенко, К.А. Жереб // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 176-187. — Бібліогр.: 23 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84226 681.3 Запропоновано розвиток формальних методів проектування, заснований на концепціях алгебраїчного програмування і алгебро-динамічних моделей програм з використанням техніки пере писувальних правил, для автоматизованої розробки ефективних програм для графічних прискорю вачів. Розроблені формальні засоби проілюстровано на конкретних задачах, що демонструють ви соку ефективність перетворень. We present the development of formal design methods based on the concepts of algebraic programming and algebraic dynamic models of programs using rewriting rules technique for the automated development of efficient programs for graphical processing units. The developed formal methods are illustrated by specific problems that demonstrate high performance of transformations. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Программирование высокопроизводительных параллельных вычислений: формальные модели и графические ускорители Програмування високопродуктивних паралельних обчислень: формальні моделі та графічні прискорювачі Programming high-performance parallel computations: formal models and graphical processing units 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 |
2011 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Програмування високопродуктивних паралельних обчислень: формальні моделі та графічні прискорювачі Programming high-performance parallel computations: formal models and graphical processing units |
| description |
Запропоновано розвиток формальних методів проектування, заснований на концепціях алгебраїчного програмування і алгебро-динамічних моделей програм з використанням техніки пере писувальних правил, для автоматизованої розробки ефективних програм для графічних прискорю вачів. Розроблені формальні засоби проілюстровано на конкретних задачах, що демонструють ви соку ефективність перетворень.
We present the development of formal design methods based on the concepts of algebraic programming and algebraic dynamic models of programs using rewriting rules technique for the automated development of efficient programs for graphical processing units. The developed formal methods are illustrated by specific problems that demonstrate high performance of transformations.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84226 |
| citation_txt |
Программирование высокопроизводительных параллельных вычислений: формальные модели и графические ускорители / Ф.И. Андон, А.Е. Дорошенко, К.А. Жереб // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 176-187. — Бібліогр.: 23 назв. — рос. |
| work_keys_str_mv |
AT andonfi programmirovanievysokoproizvoditelʹnyhparallelʹnyhvyčisleniiformalʹnyemodeliigrafičeskieuskoriteli AT dorošenkoae programmirovanievysokoproizvoditelʹnyhparallelʹnyhvyčisleniiformalʹnyemodeliigrafičeskieuskoriteli AT žerebka programmirovanievysokoproizvoditelʹnyhparallelʹnyhvyčisleniiformalʹnyemodeliigrafičeskieuskoriteli AT andonfi programuvannâvisokoproduktivnihparalelʹnihobčislenʹformalʹnímodelítagrafíčnípriskorûvačí AT dorošenkoae programuvannâvisokoproduktivnihparalelʹnihobčislenʹformalʹnímodelítagrafíčnípriskorûvačí AT žerebka programuvannâvisokoproduktivnihparalelʹnihobčislenʹformalʹnímodelítagrafíčnípriskorûvačí AT andonfi programminghighperformanceparallelcomputationsformalmodelsandgraphicalprocessingunits AT dorošenkoae programminghighperformanceparallelcomputationsformalmodelsandgraphicalprocessingunits AT žerebka programminghighperformanceparallelcomputationsformalmodelsandgraphicalprocessingunits |
| first_indexed |
2025-11-25T23:32:44Z |
| last_indexed |
2025-11-25T23:32:44Z |
| _version_ |
1850583155978797056 |
| fulltext |
Ô.È. ÀÍÄÎÍ, À.Å. ÄÎÐÎØÅÍÊÎ, Ê.À. ÆÅÐÅÁ
ÓÄÊ 681.3 ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈÅ
ÂÛÑÎÊÎÏÐÎÈÇÂÎÄÈÒÅËÜÍÛÕ ÏÀÐÀËËÅËÜÍÛÕ
ÂÛ×ÈÑËÅÍÈÉ: ÔÎÐÌÀËÜÍÛÅ ÌÎÄÅËÈ
È ÃÐÀÔÈ×ÅÑÊÈÅ ÓÑÊÎÐÈÒÅËÈ
Êëþ÷åâûå ñëîâà: âûñîêîïðîèçâîäèòåëüíûå ïàðàëëåëüíûå âû÷èñëåíèÿ, ôîð-
ìàëüíûå ìåòîäû ïðîãðàììèðîâàíèÿ, àëãåáðî-äèíàìè÷åñêèå ìîäåëè ïðîãðàìì,
ïåðåïèñûâàþùèå ïðàâèëà, ãðàôè÷åñêèå óñêîðèòåëè.
ÂÂÅÄÅÍÈÅ
Ðàçâèòèå àðõèòåêòóðû è ìåòîäîâ ïðîãðàììèðîâàíèÿ âûñîêîïðîèçâîäèòåëüíûõ
ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåì â ïîñëåäíåå äåñÿòèëåòèå ïðåòåðïåëî
âàæíûå èçìåíåíèÿ. Äî ñðåäèíû 2000-õ ãîäîâ ïîâûøåíèå ïðîèçâîäèòåëüíîñòè
êîìïüþòåðîâ ìîãëî îñóùåñòâëÿòüñÿ êàê çà ñ÷åò ðîñòà òàêòîâîé ÷àñòîòû ïðî-
öåññîðîâ, òàê è óâåëè÷åíèÿ êîëè÷åñòâà ïðîöåññîðîâ. Îäíàêî âî âòîðîé ïîëî-
âèíå ïðîøåäøåãî äåñÿòèëåòèÿ â ñâÿçè ñ îòêàçîì ïðîèçâîäèòåëåé îò äàëüíåé-
øåãî íàðàùèâàíèÿ òàêòîâîé ÷àñòîòû èç-çà òðóäíîñòåé ðåøåíèÿ ïðîáëåìû òåï-
ëîîòâîäà è ïîÿâëåíèåì ìíîãîÿäåðíûõ àðõèòåêòóð [1] ïðàêòè÷åñêè îñòàëàñü
òîëüêî ïîñëåäíÿÿ èç íàçâàííûõ âîçìîæíîñòåé. Äëÿ ïðîãðàììèñòîâ è èññëåäî-
âàòåëåé òàêîé ïîâîðîò îçíà÷àë òîëüêî îäíî — ñìåíó ïàðàäèãìû è íåîáõîäè-
ìîñòü ñîçäàíèÿ íîâûõ ìîäåëåé ïðîãðàììèðîâàíèÿ ïàðàëëåëüíûõ âû÷èñëåíèé,
ñîîòâåòñòâóþùèõ íîâûì ðåàëèÿì â ðàçâèòèè âû÷èñëèòåëüíîé òåõíèêè. Ïåðâûå
ïîïûòêè ðàäèêàëüíîãî ðåøåíèÿ ïðîáëåìû íà îñíîâå êàêîé-ëèáî îòäåëüíîé
òåõíîëîãèè (òàêèå êàê êîíöåïöèÿ òðàíçàêöèîííîé ïàìÿòè, ïðåäëîæåííàÿ
Intel [2], è êîîðäèíàöèîííàÿ áèáëèîòåêà CCR, ðàçðàáîòàííàÿ Microsoft [3])
óñïåõà íå èìåëè. Ýòî ëèøíèé ðàç ïîêàçàëî, ÷òî ðàçðàáîòêà ýôôåêòèâíûõ ïðî-
ãðàìì äëÿ íîâîãî êëàññà ìíîãîÿäåðíûõ àðõèòåêòóð — ìàñøòàáíàÿ íàó÷íî-òåõ-
íè÷åñêàÿ ïðîáëåìà, óñïåøíîå ðåøåíèå êîòîðîé ìîæåò áûòü îáåñïå÷åíî ïî-
ýòàïíî, ïóòåì êîìïëåêñíîãî ó÷åòà ñïåöèôèêè ïðåäìåòíûõ îáëàñòåé è ãëóáî-
êîãî îõâàòà ýòàïîâ æèçíåííîãî öèêëà ðàçðàáàòûâàåìûõ ïðîãðàìì ñ ïðèìåíå-
íèåì ñðåäñòâ àâòîìàòèçàöèè ïðîåêòèðîâàíèÿ è ïðîãðàììèðîâàíèÿ — îò íàïè-
ñàíèÿ ïåðâîíà÷àëüíûõ ñïåöèôèêàöèé äî ãåíåðàöèè âûïîëíÿåìîãî êîäà.
Îñíîâîé äëÿ òàêîé àâòîìàòèçàöèè ÿâëÿåòñÿ, ïðåæäå âñåãî, âûñîêîóðîâíåâàÿ
ôîðìàëèçàöèÿ êîíñòðóèðîâàíèÿ ìíîãîïîòî÷íûõ ïðîãðàìì è àâòîìàòèçàöèÿ ôîð-
ìàëüíûõ òðàíñôîðìàöèé ïðîãðàìì äëÿ îïòèìèçàöèè èõ ïðîèçâîäèòåëüíîñòè ïî
çàäàííûì êðèòåðèÿì (ïàìÿòü, áûñòðîäåéñòâèå, çàãðóçêà îáîðóäîâàíèÿ è äð.).
 äàííîé ðàáîòå ïðåäëîæåíû ôîðìàëüíûå àëãåáðî-äèíàìè÷åñêèå ìîäåëè ïàðàë-
ëåëüíûõ âû÷èñëåíèé, ïðåäíàçíà÷åííûå äëÿ àâòîìàòèçàöèè ïðîãðàììèðîâàíèÿ
ñðàâíèòåëüíî íîâîãî êëàññà ìóëüòèïðîöåññîðíûõ ñèñòåì — âèäåîãðàôè÷åñêèõ
óñêîðèòåëåé îáùåãî íàçíà÷åíèÿ (GPGPU). Îïûò ïðèìåíåíèÿ òàêèõ ìîäåëåé äëÿ
àâòîìàòèçàöèè ïðîåêòèðîâàíèÿ è ïðîãðàììèðîâàíèÿ ïàðàëëåëüíûõ âû÷èñëåíèé
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
© Ô.È. Àíäîí, À.Å. Äîðîøåíêî, Ê.À. Æåðåá, 2011
áåðåò íà÷àëî îò ïðîåêòà ìàêðîêîíâåéåðíîãî âû÷èñëèòåëüíîãî êîìïëåêñà [4], êîòî-
ðûé ðàçðàáàòûâàëñÿ â Èíñòèòóòå êèáåðíåòèêè ÍÀÍ Óêðàèíû â 80–90-å ãîäû. Íå-
ñìîòðÿ íà îòëè÷èÿ ýòèõ ïðîåêòîâ, èõ îáúåäèíÿþò îáùèå ïðîáëåìû ýôôåêòèâíîãî
óïðàâëåíèÿ ìíîãîóðîâíåâîé ïàìÿòüþ ìíîãîïðîöåññîðíîé ñèñòåìû äëÿ ïîëó÷åíèÿ
âûñîêîé ïðîèçâîäèòåëüíîñòè âû÷èñëåíèé.
 ðàçä. 1 êðàòêî îïèñàíû îñîáåííîñòè àðõèòåêòóðû âèäåîãðàôè÷åñêèõ óñêî-
ðèòåëåé ñ òî÷êè çðåíèÿ ïðîãðàììèðîâàíèÿ ïàðàëëåëüíûõ âû÷èñëåíèé. Ðàçä. 2 ñî-
äåðæèò îïèñàíèå àëãåáðî-äèíàìè÷åñêèõ ìîäåëåé ïðîãðàìì äëÿ îáû÷íîãî óíè-
âåðñàëüíîãî ïðîöåññîðà (CPU) è ãðàôè÷åñêîãî óñêîðèòåëÿ (GPU).  ðàçä. 3 îïè-
ñàíî ïðèìåíåíèå ïåðåïèñûâàþùèõ ïðàâèë äëÿ ïðåîáðàçîâàíèÿ ïðîãðàìì,
à òàêæå íàìå÷åí ïåðåõîä ê âûñîêîóðîâíåâûì ìîäåëÿì ïðîãðàìì.
1. ÃÐÀÔÈ×ÅÑÊÈÅ ÓÑÊÎÐÈÒÅËÈ ÊÀÊ ÌÓËÜÒÈÏÐÎÖÅÑÑÎÐÍÛÅ ÑÈÑÒÅÌÛ
Ìíîãîïîòî÷íîå ïðîãðàììèðîâàíèå â íàñòîÿùåå âðåìÿ àññîöèèðóåòñÿ â îñíîâ-
íîì ñ ìíîãîÿäåðíûìè ïðîöåññîðàìè îáùåãî íàçíà÷åíèÿ (multi-core CPUs [1]).
Íî ñóùåñòâóåò åùå îäíî àêòèâíî ðàçâèâàþùååñÿ íàïðàâëåíèå ïàðàëëåëüíîãî
ìíîãîïîòî÷íîãî ïðîãðàììèðîâàíèÿ — ïðîãðàììèðîâàíèå îáùåöåëåâûõ çàäà÷
äëÿ GPU [5]. Ðûíî÷íûå òðåáîâàíèÿ ñïîñîáñòâîâàëè áóðíîìó ðàçâèòèþ GPU,
â ðåçóëüòàòå èõ âû÷èñëèòåëüíàÿ ìîùíîñòü íà äàííûé ìîìåíò çíà÷èòåëüíî
ïðåâûøàåò âîçìîæíîñòè îáû÷íûõ ïðîöåññîðîâ. Ïîýòîìó âîçíèê èíòåðåñ ê èñ-
ïîëüçîâàíèþ GPU äëÿ ðåøåíèÿ çàäà÷, íå ñâÿçàííûõ íàïðÿìóþ ñ îáðàáîòêîé
ãðàôèêè. Òàêîé èíòåðåñ ïîääåðæèâàåòñÿ ðàçðàáîò÷èêàìè ãðàôè÷åñêèõ óñêîðè-
òåëåé: â ÷àñòíîñòè, êîìïàíèÿ NVidia ïðåäñòàâëÿåò ïëàòôîðìó CUDA [6] äëÿ
âû÷èñëåíèé íà ãðàôè÷åñêîì óñêîðèòåëå.
Ñõåìà óñòðîéñòâà GPU ïîêàçà-
íà íà ðèñ. 1 (ðèñóíîê âçÿò èç äîêó-
ìåíòàöèè ïëàòôîðìû CUDA [6]).
Ãðàôè÷åñêîå óñòðîéñòâî (device)
ñîäåðæèò íåñêîëüêî ìóëüòèïðîöåñ-
ñîðîâ, à òàêæå îáùóþ äëÿ íèõ ãðà-
ôè÷åñêóþ ïàìÿòü. Êàæäûé ìóëü-
òèïðîöåññîð ñîäåðæèò íåñêîëüêî
âû÷èñëèòåëüíûõ ÿäåð (ñêàëÿðíûõ
ïðîöåññîðîâ) è îäèí óïðàâëÿþùèé
áëîê, ïîääåðæèâàþùèé ìíîãîïî-
òî÷íîå èñïîëíåíèå.  ðåçóëüòàòå
êîëè÷åñòâî âû÷èñëèòåëüíûõ ÿäåð
(à çíà÷èò, è ñòåïåíü âîçìîæíîãî ïà-
ðàëëåëèçìà) ñóùåñòâåííî âûøå,
÷åì ó îáùåöåëåâûõ ìíîãîÿäåðíûõ
ïðîöåññîðîâ.
GPU ïîääåðæèâàþò íåñêîëüêî
ðàçíûõ âèäîâ ïàìÿòè, îòëè÷àþ-
ùèõñÿ ïî îáúåìó, ñêîðîñòè äîñòó-
ïà è îñîáåííîñòÿì ðåàëèçàöèè. Ñà-
ìàÿ áûñòðàÿ ïàìÿòü — ðåãèñòðû
âû÷èñëèòåëüíûõ ÿäåð; îäíàêî èõ
êîëè÷åñòâî â êàæäîì ÿäðå îãðàíè-
÷åíî. Êåø äàííûõ, èëè ðàçäåëÿå-
ìàÿ ïàìÿòü (shared memory), ïîääåðæèâàåò ïðîèçâîëüíûé äîñòóï èç ëþáîãî âû-
÷èñëèòåëüíîãî áëîêà, íî èìååò îãðàíè÷åííûé ðàçìåð è òðåáóåò ÿâíîé ñèíõðîíè-
çàöèè äîñòóïà. Èìååòñÿ òàêæå äâà ñïåöèôè÷åñêèõ âèäà ïàìÿòè — êåø êîíñòàíò è
êåø òåêñòóð. Îíè ïîääåðæèâàþò òîëüêî ÷òåíèå, íî èìåþò áîëüøèé îáúåì ïî
ñðàâíåíèþ ñ ðàçäåëÿåìîé ïàìÿòüþ. Ðàçíèöà ìåæäó òåêñòóðíîé è êîíñòàíòíîé ïà-
ìÿòüþ çàêëþ÷àåòñÿ â òîì, ÷òî òåêñòóðíàÿ ïàìÿòü ïîääåðæèâàåò ñïåöèàëüíûå ðå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 177
Ðèñ. 1. Îáùàÿ ñõåìà îñíîâíûõ àïïàðàòíûõ êîìïî-
íåíòîâ GPU
Device
Multiprocessor N
Multiprocessor 2
Multiprocessor 1
Processor MProcessor 2Processor 1
Shared Memory
Registers Registers Registers Instruction
Unit
Constant
Cache
Texture
Cache
Device Memory
æèìû äîñòóïà, ïîëåçíûå äëÿ ãðàôè÷åñêèõ çàäà÷. Âñåì ìóëüòèïðîöåññîðàì
äîñòóïíà òàêæå ãðàôè÷åñêàÿ ïàìÿòü óñòðîéñòâ, ñàìàÿ áîëüøàÿ ïî îáúåìó è ñàìàÿ
ìåäëåííàÿ äëÿ GPU.
Ïàðàëëåëüíàÿ ïðîãðàììà äëÿ GPU ñîñòîèò èç áîëüøîãî êîëè÷åñòâà ïîòîêîâ.
Îñîáåííîñòè àïïàðàòíîãî îáåñïå÷åíèÿ, à èìåííî áîëüøîå êîëè÷åñòâî âû÷èñëè-
òåëüíûõ ÿäåð, ïîçâîëÿþò èñïîëüçîâàòü î÷åíü ìåëêîçåðíèñòûé ïàðàëëåëèçì,
âïëîòü äî âûäåëåíèÿ îòäåëüíîãî ïîòîêà äëÿ êàæäîãî ýëåìåíòà äàííûõ.
Äëÿ èñïîëíåíèÿ íà GPU ïîòîêè îáúåäèíÿþòñÿ â áëîêè. Êàæäûé áëîê âû-
ïîëíÿåòñÿ íà îäíîì ìóëüòèïðîöåññîðå. Ðàçëè÷íûå áëîêè, ñîîòâåòñòâóþùèå îä-
íîé èëè íåñêîëüêèì ïðîãðàììàì, ïî âîçìîæíîñòè ðàñïðåäåëÿþòñÿ ðàâíîìåðíî
ïî äîñòóïíûì ìóëüòèïðîöåññîðàì. Ñëåäóåò îòìåòèòü, ÷òî íàëè÷èå âåòâëåíèé
â ïîòîêàõ îäíîãî áëîêà ïîíèæàåò ïðîèçâîäèòåëüíîñòü, ïîñêîëüêó êàæäûé èç âà-
ðèàíòîâ èñïîëíåíèÿ â òàêèõ ñëó÷àÿõ âûïîëíÿåòñÿ ïîñëåäîâàòåëüíî, à îñòàëüíûå
ïîòîêè îæèäàþò âûïîëíåíèÿ.
Íåñìîòðÿ íà íàëè÷èå ñïåöèàëèçèðîâàííûõ ñðåäñòâ CUDA, ðàçðàáîòêà ïðî-
ãðàìì äëÿ GPU îñòàåòñÿ òðóäîåìêîé, òðåáóþùåé îò ðàçðàáîò÷èêà çíàíèÿ íèçêîó-
ðîâíåâûõ äåòàëåé àïïàðàòíîé è ïðîãðàììíîé ïëàòôîðìû. Ïîýòîìó àêòóàëüíîé ÿâ-
ëÿåòñÿ çàäà÷à àâòîìàòèçàöèè ïðîöåññà ðàçðàáîòêè.  äàííîé ñòàòüå ïðåäëîæåíî ðàç-
âèòèå ôîðìàëüíûõ ìåòîäîâ ïðîåêòèðîâàíèÿ, îñíîâàííîå íà êîíöåïöèÿõ
àëãåáðàè÷åñêîãî ïðîãðàììèðîâàíèÿ [7] è àëãåáðî-äèíàìè÷åñêèõ ìîäåëåé ïðî-
ãðàìì [8] ñ èñïîëüçîâàíèåì òåõíèêè ïåðåïèñûâàþùèõ ïðàâèë [9–11] äëÿ àâòîìàòè-
çèðîâàííîé ðàçðàáîòêè ýôôåêòèâíûõ ïðîãðàìì äëÿ GPU. Ðàçðàáîòàíû âûñîêîóðîâ-
íåâûå ìîäåëè ïðîãðàìì è ìîäåëè èñïîëíåíèÿ ïðîãðàìì äëÿ CPU è GPU. Îïèñàíî
èñïîëüçîâàíèå ïåðåïèñûâàþùèõ ïðàâèë è âûñîêîóðîâíåâûõ ìîäåëåé äëÿ àâòîìàòè-
çèðîâàííîãî ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè ïðîãðàìì äëÿ GPU. Ïðåäëîæåí ìå-
òîä àâòîìàòèçèðîâàííîãî ïåðåõîäà ìåæäó âûñîêîóðîâíåâîé ìîäåëüþ ïðîãðàììû è
èñõîäíûì êîäîì, îñíîâàííûé íà èñïîëüçîâàíèè ïåðåïèñûâàþùèõ ïðàâèë ñïåöèàëü-
íîãî âèäà. Ðàçðàáîòàííûå ôîðìàëüíûå ñðåäñòâà ïðîèëëþñòðèðîâàíû íà êîíêðåòíûõ
çàäà÷àõ, êîòîðûå ïîêàçûâàþò âûñîêóþ ýôôåêòèâíîñòü ïðåîáðàçîâàíèé.
Íàñòîÿùàÿ ðàáîòà ïðîäîëæàåò èññëåäîâàíèÿ, íà÷àòûå â [12–14], ïî àâòîìà-
òèçàöèè ïðîöåññà ïðîåêòèðîâàíèÿ è ðàçðàáîòêè ýôôåêòèâíûõ ïàðàëëåëüíûõ ïðî-
ãðàìì. Îñîáåííîñòü äàííîé ïóáëèêàöèè — èñïîëüçîâàíèå íîâîé àïïàðàòíîé
ïëàòôîðìû äëÿ ïàðàëëåëüíûõ âû÷èñëåíèé, GPU, ÷òî ïîçâîëÿåò äîáèòüñÿ çíà÷è-
òåëüíîãî ïîâûøåíèÿ ïðîèçâîäèòåëüíîñòè ïî ñðàâíåíèþ ñ ïðèìåíåíèåì ìíîãîÿ-
äåðíûõ ïðîöåññîðîâ îáùåãî íàçíà÷åíèÿ. Äàííàÿ ïëàòôîðìà èññëåäîâàëàñü
â [15], îäíàêî îòëè÷èå íàñòîÿùåé ðàáîòû ñîñòîèò â èñïîëüçîâàíèè áîëåå ôîðìà-
ëèçîâàííûõ ìåòîäîâ è âûñîêîóðîâíåâûõ ïðåäñòàâëåíèé ïðîãðàìì. Ýòî ïîçâîëÿ-
åò óïðîñòèòü çàïèñü ïðåîáðàçîâàíèé, à òàêæå ïðèìåíèòü îäíè âûñîêîóðîâíåâûå
ïðåîáðàçîâàíèÿ äëÿ ïðîãðàìì íà ðàçíûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ.
Îáëàñòü èññëåäîâàíèé, ñâÿçàííàÿ ñ àâòîìàòèçàöèåé ðàçðàáîòêè ïðèëîæåíèé
äëÿ ãðàôè÷åñêèõ ïðîöåññîðîâ, â íàñòîÿùåå âðåìÿ àêòèâíî ðàçâèâàåòñÿ. Ïðè ýòîì
ðàññìàòðèâàþòñÿ êàê çàäà÷è ïåðåõîäà îò ïîñëåäîâàòåëüíûõ ê ïàðàëëåëüíûì ïðî-
ãðàììàì, òàê è çàäà÷è îïòèìèçàöèè ñóùåñòâóþùèõ ïàðàëëåëüíûõ ïðîãðàìì ñ èñ-
ïîëüçîâàíèåì âîçìîæíîñòåé GPU. Òàê, â ðàáîòå [16] ðàññìîòðåí àâòîìàòè÷åñêèé
ïåðåõîä îò ìíîãîïîòî÷íîé ïðîãðàììû, ðåàëèçîâàííîé ñ èñïîëüçîâàíèåì òåõíîëî-
ãèè OpenMP [17], ê ðåàëèçàöèè äàííîé ïðîãðàììû íà ïëàòôîðìå CUDA. Â [18]
îïèñàíà ïëàòôîðìà äëÿ îïòèìèçàöèè öèêëîâ â ïðîãðàììàõ äëÿ GPU. Ðàçðàáîòàíû
ñèñòåìû äëÿ àâòîìàòè÷åñêîãî ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè ïðîãðàìì èç êîí-
êðåòíîé ïðåäìåòíîé îáëàñòè, íàïðèìåð data mining [19] èëè îáðàáîòêà èçîáðàæå-
íèé [20]. Àâòîðû ðàáîòû [21] îïèñûâàþò áèáëèîòåêó âûñîêîóðîâíåâûõ ñòðóêòóð
äàííûõ äëÿ GPU. Òàêæå ðàçðàáàòûâàþòñÿ ïëàòôîðìû èõ ïðîãðàììèðîâàíèÿ, ïðåä-
îñòàâëÿþùèå áîëåå âûñîêîóðîâíåâûå ñðåäñòâà ïî ñðàâíåíèþ ñ CUDA, òàêèå êàê
hiCUDA [22] è BSGP [23]. Îòëè÷èå äàííîé ïóáëèêàöèè çàêëþ÷àåòñÿ â èñïîëüçî-
âàíèè ôîðìàëüíûõ ìîäåëåé è ìåòîäîâ, ÷òî ïîçâîëÿåò ñîâìåñòèòü êðàòêîñòü îïè-
ñàíèÿ è ýôôåêòèâíîñòü ðåàëèçàöèè ïðåîáðàçîâàíèé.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
2. ÀËÃÅÁÐÎ-ÄÈÍÀÌÈ×ÅÑÊÈÅ ÌÎÄÅËÈ ÏÐÎÃÐÀÌÌ
2.1. Ìîäåëü èñõîäíîãî êîäà ïðîãðàììû. Àëãåáðî-äèíàìè÷åñêèå ìîäåëè ïðî-
ãðàìì ñîñòîÿò èç äâóõ ÷àñòåé: ìîäåëü èñõîäíîãî êîäà ïðîãðàììû è ìîäåëü
èñïîëíåíèÿ ïðîãðàììû. Â äàííîì ðàçäåëå ðàññìîòðèì ñëåäóþùóþ ìîäåëü èñ-
õîäíîãî êîäà. Ïðîãðàììà ñîñòîèò èç ìíîæåñòâà ïðîöåäóð, ñîîòâåòñòâóþùèõ
îòäåëüíûì ìåòîäàì (ôóíêöèÿì) ÿçûêà ïðîãðàììèðîâàíèÿ: P P Pk� { }1, ,� . Áó-
äåì ñ÷èòàòü, ÷òî ïðîöåäóðà îïèñûâàåòñÿ èäåíòèôèêàòîðîì (èìåíåì, óíèêàëü-
íûì â ïðåäåëàõ ïðîãðàììû), à òàêæå ìîäåëüþ êîäà: P name codei i i� ( , ).
 äàëüíåéøåì äëÿ ñîêðàùåíèÿ çàïèñè áóäåì îòîæäåñòâëÿòü îáîçíà÷åíèå äëÿ
ïðîöåäóðû â öåëîì Pi è åå èìåíè namei .
Äëÿ ìîäåëèðîâàíèÿ êîäà èñïîëüçóåì àëãåáðó àëãîðèòìîâ Ãëóøêîâà. Ïðîöå-
äóðíûé êîä áóäåì ïðåäñòàâëÿòü â âèäå âûðàæåíèÿ ýòîé àëãåáðû. Àëãåáðà Ãëóø-
êîâà (ÀÃ) ÿâëÿåòñÿ äâóõîñíîâíîé àëãåáðîé A Y U( , ) , ñîäåðæàùåé ìíîæåñòâà îïå-
ðàòîðîâ Y è óñëîâèé (ïðåäèêàòîâ) U . Â àëãåáðå îïðåäåëåíû ñòàíäàðòíûå îïåðà-
öèè: ëîãè÷åñêèå îïåðàöèè êîíúþíêöèè AND, äèçúþíêöèè OR è îòðèöàíèÿ NOT ,
ïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ THEN , âåòâëåíèå IF , èòåðàöèÿ (öèêë) WHILE.
Íà ìíîæåñòâàõ îïåðàòîðîâ è óñëîâèé ââîäÿòñÿ áàçîâûå ýëåìåíòû, ÷òî äàåò
âîçìîæíîñòü ñòðîèòü ðàçëè÷íûå âûðàæåíèÿ àëãåáðû, êîòîðûå áóäóò îïèñûâàòü
ñëîæíûå îïåðàòîðû è óñëîâèÿ. Áàçîâûå îïåðàòîðû è óñëîâèÿ îáû÷íî çàâèñÿò îò
ïðåäìåòíîé îáëàñòè. Âûäåëèì îäèí áàçîâûé îïåðàòîð, îáùèé äëÿ âñåõ ïðåäìåò-
íûõ îáëàñòåé: âûçîâ ïðîöåäóðû call Pi( ) .
Îñîáåííîñòüþ ïðîãðàìì äëÿ GPU ÿâëÿåòñÿ èõ ðàçäåëåíèå íà äâå ÷àñòè: êîä,
êîòîðûé èñïîëíÿåòñÿ íà CPU, è ñïåöèàëèçèðîâàííûé êîä äëÿ GPU. Ýòè ÷àñòè
ìîãóò áûòü ðåàëèçîâàíû íà ðàçíûõ ÿçûêàõ. Íàïðèìåð, â [15] ðàññìàòðèâàëèñü
ïðîãðàììû, â êîòîðûõ CPU-êîä ðåàëèçîâàí íà C#, òîãäà êàê GPU-êîä — íà C for
CUDA, ñïåöèàëüíîì ðàñøèðåíèè ÿçûêà Ñ.
 ìîäåëè ïðîãðàììû ýòó îñîáåííîñòü áóäåì ó÷èòûâàòü ñëåäóþùèì îáðà-
çîì: ñ÷èòàòü, ÷òî êàæäàÿ ïðîöåäóðà îòíîñèòñÿ ëèáî ê CPU-, ëèáî ê GPU-êîäó.
Ïðè ýòîì äëÿ CPU è GPU íàáîðû áàçîâûõ îïåðàòîðîâ ìîãóò ðàçëè÷àòüñÿ.
2.2. Ìîäåëü èñïîëíåíèÿ ïîñëåäîâàòåëüíîé ïðîãðàììû. Äëÿ îïèñàíèÿ èñ-
ïîëíåíèÿ ïðîãðàìì èñïîëüçóåì îáùèå ïîíÿòèÿ òåîðèè äèñêðåòíûõ äèíàìè÷åñ-
êèõ ñèñòåì (transition systems) [8]. Äèñêðåòíàÿ äèíàìè÷åñêàÿ ñèñòåìà (ÄÄÑ)
îïðåäåëÿåòñÿ êàê òðîéêà ( , , )S S d0 , ãäå S — ìíîæåñòâî, íàçûâàåìîå ïðîñòðàí-
ñòâîì ñîñòîÿíèé; S S0 � — ìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé; d S S� � — áè-
íàðíîå îòíîøåíèå ïåðåõîäîâ â ïðîñòðàíñòâå ñîñòîÿíèé. Ñèñòåìà ìîæåò ïåðåéòè
èç ñîñòîÿíèÿ si â ñîñòîÿíèå s j , åñëè ( , )s s di j � .
Äëÿ ïîñòðîåíèÿ ìîäåëè èñïîëíåíèÿ íåîáõîäèìî îïðåäåëèòü èíòåðïðåòàöèþ
âûðàæåíèé ÀÃ, èç êîòîðûõ ñîñòîèò ïðîãðàììà. Ïóñòü V — ìíîæåñòâî ïåðåìåí-
íûõ ïðîãðàììû. Äëÿ ïðîñòîòû áóäåì ñ÷èòàòü, ÷òî ïåðåìåííûå íå èìåþò òèïà è
ïðèíèìàþò çíà÷åíèÿ â íåêîòîðîì óíèâåðñàëüíîì ìíîæåñòâå D. ×àñòè÷íûå îòî-
áðàæåíèÿ b V D: � ïåðåìåííûõ íà èõ çíà÷åíèÿ áóäåì íàçûâàòü ñîñòîÿíèÿìè ïà-
ìÿòè. Èíôîðìàöèîííîé ñðåäîé ÿâëÿåòñÿ ìíîæåñòâî ñîñòîÿíèé ïàìÿòè:
B b V D� �{ }: . Òîãäà îïåðàòîðû àëãåáðû àëãîðèòìîâ èíòåðïðåòèðóþòñÿ êàê
ôóíêöèè íà ìíîæåñòâå B, à óñëîâèÿ — êàê ïðåäèêàòû íà òîì æå ìíîæåñòâå.
Èíòåðïðåòàöèÿ áàçîâûõ îïåðàòîðîâ è óñëîâèé îïðåäåëÿåòñÿ â ðàìêàõ
ñîîòâåòñòâóþùåé ïðåäìåòíîé îáëàñòè.
Òåïåðü îïðåäåëèì ÄÄÑ, êîòîðàÿ îïèñûâàåò èñïîëíåíèå ïîñëåäîâàòåëüíîé
ïðîãðàììû. Ñîñòîÿíèÿ ÄÄÑ èìåþò âèä s b R F� ( , , ) , ãäå b B� — òåêóùåå ñîñòîÿ-
íèå ïàìÿòè, R Y� — òåêóùåå ñîñòîÿíèå óïðàâëåíèÿ, ïðåäñòàâëåííîå â âèäå îñòà-
òî÷íîé ïðîãðàììû, F P Y� �( )* — ñòåê âûçîâîâ ïðîöåäóð, ò.å. ïîñëåäîâàòåëü-
íîñòü èäåíòèôèêàòîðîâ ïðîöåäóð è îïåðàòîðîâ ÀÃ, îïèñûâàþùèõ ñîñòîÿíèå
óïðàâëåíèÿ äàííîé ïðîöåäóðû. Íà÷àëüíîå ñîñòîÿíèå äëÿ çàäàííîé ïðîãðàììû
èìååò âèä s b Y P Pm m0 0� � �( , ( ), ( )) , ãäå Pm — îñíîâíàÿ ïðîöåäóðà (òî÷êà âõî-
äà â ïðîãðàììó). Îòíîøåíèå ïåðåõîäà çàäàåòñÿ ñëåäóþùèìè ïðàâèëàìè ïåðåõîäà:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 179
1) ( , , ) ( ( ), , )b yR F y b R F� , ãäå y Y� — áàçîâûé îïåðàòîð;
2) ( , ( , , ) , )
( , , ), ( ) ,
( , , ), ( ) ;
b if u P Q R F
b PR F u b
b QR F u b
�
�
�
1
0
�
3) ( , ( , ) , )
( , ( , ) , ), ( ) ,
( , ,
b while u P R F
b Pwhile u P R F u b
b R F
�
�1
), ( ) ;u b �
� 0
4) ( , ( ) , (..., )) ( , ( ), (..., , ))b call P R P b Y P P R Pj i j i j� � � � � � ;
5) ( , , (..., , )) ( , , (..., ))b P R P b R Pi j i� � � � � � � .
Ïðàâèëî 1 îïðåäåëÿåò âûïîëíåíèå áàçîâûõ îïåðàòîðîâ. Ïðàâèëà 2 è 3 îïèñûâà-
þò âåòâëåíèå è öèêëè÷åñêóþ êîíñòðóêöèþ. Ðàáîòà ñ ïðîöåäóðàìè îïèñàíà ïðàâèëà-
ìè 4 (âûçîâ ïðîöåäóðû) è 5 (âîçâðàò èç ïðîöåäóðû). Ôèíàëüíûå ñîñòîÿíèÿ (èç êîòî-
ðûõ íåâîçìîæåí ïåðåõîä íè â êàêîå äðóãîå ñîñòîÿíèå) èìåþò âèä s bf � �( , , )� .
Îïðåäåëåííóþ òàêèì îáðàçîì ÄÄÑ îáîçíà÷èì S ser . Îíà ìîäåëèðóåò èñïîëíå-
íèå çàäàííîé ïîñëåäîâàòåëüíîé ïðîãðàììû. Îòìåòèì, ÷òî ñèñòåìà S ser äåòåðìèíè-
ðîâàííàÿ, ïîñêîëüêó äëÿ êàæäîãî ñîñòîÿíèÿ ïåðåõîä îïðåäåëåí îäíîçíà÷íî.
2.3. CPU-ïðîãðàììà. Îïèðàÿñü íà ïîñòðîåííóþ ìîäåëü äëÿ ïîñëåäîâàòåëü-
íûõ ïðîãðàìì, îïèøåì àíàëîãè÷íóþ ìîäåëü äëÿ ïàðàëëåëüíûõ ïðîãðàìì, èñïîë-
íÿåìûõ íà ãðàôè÷åñêèõ GPU. Ïðè ïîñòðîåíèè ìîäåëè èñïîëíåíèÿ ïðîãðàìì äëÿ
äàííûõ óñêîðèòåëåé áóäåì îòäåëüíî ðàññìàòðèâàòü èñïîëíåíèå íà CPU è íà GPU.
Äëÿ êàæäîãî ðåæèìà ïîñòðîèì ñîîòâåòñòâóþùóþ ìîäåëü â âèäå ÄÄÑ. Ìîäåëü èñ-
ïîëíåíèÿ ïðîãðàììû â öåëîì, S gc, ñòðîèòñÿ êàê îáúåäèíåíèå ýòèõ äâóõ ÄÄÑ.
Êîä, îòíîñÿùèéñÿ ê CPU, èñïîëíÿåòñÿ òàê æå, êàê è ëþáàÿ îáû÷íàÿ ïðî-
ãðàììà, ïîýòîìó äëÿ ìîäåëèðîâàíèÿ ýòîé ÷àñòè ìîæíî èñïîëüçîâàòü ìîäåëü
S ser , â êîòîðóþ íóæíî äîáàâèòü ñðåäñòâà âçàèìîäåéñòâèÿ ñ GPU. Ðàññìîòðèì
ñëåäóþùèå íîâûå îïåðàòîðû: init gpu_ — èíèöèàëèçàöèÿ GPU,
copy gpu m mG C_ ( , ) — êîïèðîâàíèå äàííûõ â âèäåîïàìÿòü, copy back m mC G_ ( , )
— êîïèðîâàíèå ðåçóëüòàòîâ èç âèäåîïàìÿòè è call gpu P block gridi_ ( , , ) — çàïóñê
êîäà (ÿäðà CUDA) íà GPU. Ñîîòâåòñòâåííî ïîòðåáóåòñÿ äîáàâèòü ïðàâèëà ïåðå-
õîäîâ, êîòîðûå áóäóò ìåíÿòü ñîñòîÿíèå ÄÄÑ S gc â öåëîì, à íå òîëüêî îäèí èç åå
êîìïîíåíòîâ. Ôîðìàëüíîå îïèñàíèå ýòèõ ïðàâèë ïðèâåäåíî â ï. 2.6.
2.4. GPU-ïðîãðàììà: óðîâåíü áëîêîâ. Ìîäåëü S gpu èñïîëíåíèÿ êîäà íà
GPU ñòðîèòñÿ ïî ìíîãîóðîâíåâîìó ïðèíöèïó [8]: ñîñòîÿíèÿ áîëåå âûñîêèõ
óðîâíåé ÄÄÑ ÿâëÿþòñÿ êîìáèíàöèåé ñîñòîÿíèé áîëåå íèçêèõ óðîâíåé. Íà íèç-
øåì óðîâíå ìîäåëèðóåòñÿ èñïîëíåíèå îòäåëüíûõ ïîòîêîâ; äëÿ ýòîãî èñïîëüçóåò-
ñÿ ìîäèôèöèðîâàííàÿ ÄÄÑ S ser . Ïåðåõîäû ÄÄÑ îòäåëüíûõ ïîòîêîâ îáúåäèíÿ-
þòñÿ â ïåðåõîä ÄÄÑ áîëåå âûñîêîãî óðîâíÿ.
Ìîäåëü S gpu ñîäåðæèò òðè óðîâíÿ âëîæåííîñòè ñîñòîÿíèé: ïîòîêîâ, áëîêîâ
è ïðîãðàììû â öåëîì. Îòäåëüíûå ïîòîêè (ïåðâûé óðîâåíü) îáúåäèíÿþòñÿ â áëî-
êè (âòîðîé óðîâåíü), êîòîðûå, â ñâîþ î÷åðåäü, ôîðìèðóþò GPU-ïðîãðàììó
â öåëîì (òðåòèé óðîâåíü).
Âàæíîé îñîáåííîñòüþ ìîäåëè S gpu ïî ñðàâíåíèþ ñ ïîñëåäîâàòåëüíîé ìî-
äåëüþ S ser ÿâëÿåòñÿ íàëè÷èå èåðàðõèè ïàìÿòè.  CUDA èñïîëüçóåòñÿ ïÿòü âèäîâ
ïàìÿòè: ðåãèñòðû, ðàçäåëÿåìàÿ (shared) ïàìÿòü, êåø êîíñòàíò, êåø òåêñòóð è ãëî-
áàëüíàÿ ïàìÿòü.  ðàìêàõ ìîäåëè îãðàíè÷èìñÿ ðàññìîòðåíèåì äâóõ íàèáîëåå
÷àñòî èñïîëüçóåìûõ âèäîâ ïàìÿòè, à èìåííî shared-ïàìÿòü è ãëîáàëüíàÿ ïàìÿòü.
Ðàçëè÷íûå âèäû ïàìÿòè â ìîäåëè ïðîÿâëÿþòñÿ â âèäå äîïîëíèòåëüíûõ êîì-
ïîíåíòîâ ñîñòîÿíèÿ. Äëÿ íèçøåãî óðîâíÿ (ïîòîêîâ) ñîñòîÿíèå èìååò âèä
s b b R Fg s� ( , , , ), ãäå b Bg g� — ñîñòîÿíèå ãëîáàëüíîé ïàìÿòè, b Bs s� — ñîñòîÿ-
íèå shared-ïàìÿòè. Îäíàêî äëÿ óïðîùåíèÿ ìîäåëè áóäåì îáúåäèíÿòü ñîñòîÿíèÿ
ðàçëè÷íûõ âèäîâ ïàìÿòè â îáùåå ñîñòîÿíèå b b bg s� � , b B B Bg s� � � , ñ÷èòàÿ,
÷òî âñå îïåðàòîðû è ïðåäèêàòû ÀÃ òàêæå äåéñòâóþò íà îáúåäèíåííîì
ìíîæåñòâå B.
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
Íà óðîâíå ïîòîêîâ äåéñòâóþò ïðàâèëà ïåðåõîäà 1–5 (ïðàâèëî 4) èìååò äî-
ïîëíèòåëüíîå îãðàíè÷åíèå — âûçûâàåìàÿ ôóíêöèÿ äîëæíà ðàáîòàòü íà GPU, ÷òî
îïèñûâàåòñÿ ìîäèôèêàòîðîì __device__ â C for CUDA.
Íà óðîâíå áëîêîâ ñîñòîÿíèåì ÿâëÿåòñÿ ìíîæåñòâî ïîòîêîâ, êàæäûé ñî ñâî-
èì ñîñòîÿíèåì s T si i
2 1� �{ }. Ïåðåõîäû íà óðîâíå áëîêîâ îáúåäèíÿþòñÿ èç ïå-
ðåõîäîâ íà óðîâíå ïîòîêîâ. Ýòà ïðîöåäóðà ïðîâîäèòñÿ ñëåäóþùèì îáðàçîì: âû-
áèðàåòñÿ íåêîòîðîå ïîäìíîæåñòâî ïîòîêîâ; äëÿ êàæäîãî èç íèõ îñóùåñòâëÿåòñÿ
ïåðåõîä â ñîîòâåòñòâèè ñ îòíîøåíèåì d gpu1, è íîâîå ñîñòîÿíèå ïðîãðàììû ïîëó-
÷àåòñÿ îáúåäèíåíèåì ñîñòîÿíèé îòäåëüíûõ ïîòîêîâ. Íîâûå ñîñòîÿíèÿ îòäåëüíûõ
ïîòîêîâ èñïîëüçóþò ñîñòîÿíèå óïðàâëåíèÿ, îïðåäåëåííîå îòíîøåíèåì ïåðåõîäîâ
äëÿ S ser . Ñîñòîÿíèå îáùåé ïàìÿòè îïðåäåëÿåòñÿ ôóíêöèåé merge B B B: .*� � Ýòà
ôóíêöèÿ ìåíÿåò ñîñòîÿíèå êàæäîé ïåðåìåííîé, êîòîðàÿ áûëà èçìåíåíà õîòÿ áû â
îäíîì èç ïîòîêîâ. Ôîðìàëüíî
merge b b b
b b b j k
k i
j i j i i( , , , )
! ( )| ( ) ( ), ,
0 1
0 1
� � �
�
�
� � �{ }
b i0 ( )�
�
�
��
�
�
�
��
(çäåñü èñïîëüçîâàíî îáîçíà÷åíèå ! A äëÿ ïðîèçâîëüíîãî ýëåìåíòà ìíîæåñòâà A).
Ôóíêöèÿ merge ïðèìåíÿåòñÿ ê îáîèì âèäàì ïàìÿòè: b bg s, (èëè ê îáúåäèíåí-
íîé ïàìÿòè b).
Ñëåäóåò îòìåòèòü âàæíîå îãðàíè÷åíèå íà äîïóñòèìûå ïåðåõîäû: âñå îäíî-
âðåìåííî ñðàáàòûâàþùèå ïîòîêè äîëæíû èñïîëíÿòü îäèíàêîâûå îïåðàòîðû. Ýòî
îáúÿñíÿåòñÿ òåì, ÷òî â àðõèòåêòóðå GPU íà êàæäûé áëîê âûäåëÿåòñÿ òîëüêî îäíî
óïðàâëÿþùåå óñòðîéñòâî [6]. Ïîýòîìó ïîòîêè ìîãóò ðàáîòàòü îäíîâðåìåííî,
òîëüêî åñëè îíè èñïîëíÿþò îäíó èíñòðóêöèþ.
Äëÿ ñèíõðîíèçàöèè ïîòîêîâ äîáàâèì îïåðàòîð _ Barrier. Îí èñïîëüçóåòñÿ äëÿ
ñèíõðîíèçàöèè ñîñòîÿíèÿ ïîòîêîâ â ïðåäåëàõ áëîêà: êàæäûé ïîòîê, äîñòèãøèé
äàííîãî îïåðàòîðà, îæèäàåò, ïîêà âñå îñòàëüíûå ïîòîêè òàêæå äîñòèãíóò åãî. Äåé-
ñòâèå îïåðàòîðà _ Barrier îïèñûâàåòñÿ ñëåäóþùèìè ïðàâèëàìè ïåðåõîäà:
6) ( , _ ; , ) ( ( ), _ ; , )b Barrier R F inc b waiting Barrier R F� ;
7) ( , _ ; , ) ( ( ), , )b waiting Barrier R F zero b R F� ïðè óñëîâèè bc threads� .
Èñïîëüçóåòñÿ äîïîëíèòåëüíàÿ ïåðåìåííàÿ bc, îïèñûâàþùàÿ êîëè÷åñòâî ïîòîêîâ,
îæèäàþùèõ èñïîëíåíèÿ. Îïåðàòîðû inc b bc bc( ): � �1 è zero b bc( ): � 0 ñîîòâå-
òñòâåííî äîáàâëÿþò íîâûé ïîòîê ê êîëè÷åñòâó îæèäàþùèõ è î÷èùàþò ñïèñîê îæè-
äàíèÿ. Â C for CUDA îïåðàòîð _ Barrier ðåàëèçîâàí ïðèìèòèâîì __syncthreads().
2.5. GPU-ïðîãðàììà: óðîâåíü ïðîãðàììû. Óðîâåíü ïðîãðàììû â öåëîì
ñòðîèòñÿ èç óðîâíÿ áëîêîâ òàêèì æå îáðàçîì, êàê óðîâåíü áëîêîâ ñòðîèëñÿ èç
óðîâíÿ ïîòîêîâ. Ñîñòîÿíèÿìè ïðîãðàììû ÿâëÿþòñÿ îòîáðàæåíèÿ èç ìíîæåñòâà
áëîêîâ âî ìíîæåñòâî ñîñòîÿíèé óðîâíÿ áëîêîâ: s B sj j
3 2� �{ }. Êàê è íà âòîðîì
óðîâíå, êîëè÷åñòâî áëîêîâ ïîñòîÿííî è îïðåäåëÿåòñÿ ïàðàìåòðàìè çàïóñêà ÿäðà.
 îòëè÷èå îò óðîâíÿ áëîêîâ, shared-ïàìÿòü óíèêàëüíàÿ äëÿ êàæäîãî áëîêà,
à íå îáùàÿ, êàê ãëîáàëüíàÿ ïàìÿòü. Ïîýòîìó îáúåäèíåíèå ðåçóëüòàòîâ ôóíêöèåé
merge íà äàííîì óðîâíå èñïîëüçóåòñÿ òîëüêî äëÿ ãëîáàëüíîé ïàìÿòè bg .
Åùå îäíîé îñîáåííîñòüþ îáúåäèíåííûõ ïåðåõîäîâ íà óðîâíå âñåé ïðîãðàì-
ìû ÿâëÿåòñÿ ñëåäóþùåå îãðàíè÷åíèå: íå ìîæåò íà÷àòüñÿ èñïîëíåíèå íîâîãî áëî-
êà (êîòîðûé íàõîäèòñÿ â íà÷àëüíîì ñîñòîÿíèè óðîâíÿ áëîêîâ), åñëè ñóùåñòâóåò
õîòÿ áû îäèí áëîê, êîòîðûé íà÷àë èñïîëíÿòüñÿ, íî íå çàäåéñòâîâàí â äàííîì ïå-
ðåõîäå. Èíûìè ñëîâàìè, íå ïðîèñõîäèò ïåðåêëþ÷åíèå ìåæäó ðàçíûìè îäíîâðå-
ìåííî èñïîëíÿåìûìè áëîêàìè; êàæäûé áëîê, íà÷àâøèé èñïîëíÿòüñÿ,
èñïîëíÿåòñÿ äî êîíöà.
Íà óðîâíå ïðîãðàììû ñóùåñòâóþò ñâîè ñðåäñòâà ñèíõðîíèçàöèè (íàïðèìåð,
àòîìàðíûå îïåðàöèè [6]). Îäíàêî îíè äîñòóïíû íå âî âñåõ óñòðîéñòâàõ, ñèëüíî
çàìåäëÿþò âûïîëíåíèå ïðîãðàììû, ê òîìó æå ïðîòèâîðå÷àò èäåîëîãèè CUDA,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 181
ñîãëàñíî êîòîðîé áëîêè äîëæíû èñïîëíÿòüñÿ íåçàâèñèìî è ïðîèçâîëüíî, ïîýòî-
ìó ýòè ñðåäñòâà â ìîäåëü íå âêëþ÷àþòñÿ.
2.6. Âçàèìîäåéñòâèå CPU è GPU. Ñîâìåñòíàÿ ðàáîòà äâóõ ÷àñòåé ïðîãðàì-
ìû êîîðäèíèðóåòñÿ èç CPU-êîäà ñ èñïîëüçîâàíèåì îïåðàòîðîâ copy gpu_ ,
copy back_ è call gpu_ (îïåðàòîð init gpu_ èñïîëüçóåòñÿ îäíîêðàòíî â íà÷àëå ïðî-
ãðàììû è íå âëèÿåò íà äàëüíåéøåå èñïîëíåíèå). Ïåðâûå äâà îïåðàòîðà êîïèðó-
þò äàííûå ìåæäó CPU è GPU. Ôîðìàëüíî ýòî ñâîäèòñÿ ê òîìó, ÷òî íåêîòîðîå
ìíîæåñòâî ïåðåìåííûõ (îáû÷íî ìàññèâ) â ñîñòîÿíèè îäíîãî óñòðîéñòâà ïðèíè-
ìàþò òå æå çíà÷åíèÿ, ÷òî è ñîîòâåòñòâóþùèå ïåðåìåííûå â ñîñòîÿíèè äðóãîãî.
Îïåðàòîð call gpu_ ñîáñòâåííî çàïóñêàåò êîä äëÿ èñïîëíåíèÿ íà ãðàôè÷åñ-
êîì óñêîðèòåëå. Åãî ðàáîòà îïèñûâàåòñÿ äâóìÿ ïðàâèëàìè:
8) ( , ( , )) ( , ( , , ))s b s s P block gridc
g
c g
i� �
0
;
9) ( , ) (( , , ), ( , ))s s b R F bc
f
g
g� � � .
Çäåñü èñïîëüçîâàíî îáîçíà÷åíèå s b call gpu P block grid R Fc
i� ( , _ ( , , ) , ). Ïðà-
âèëî 8 îïèñûâàåò ñîçäàíèå íà÷àëüíîãî ñîñòîÿíèÿ ÄÄÑ S gpu ïðè èñïîëíåíèè îïå-
ðàòîðà call gpu_ . Ïàðàìåòðû ýòîãî ñîñòîÿíèÿ — êîëè÷åñòâî áëîêîâ, ïîòîêîâ, èñ-
ïîëíÿåìûé ìîäóëü, êîòîðûå èçâëåêàþòñÿ èç ïàðàìåòðîâ îïåðàòîðà. Îòìåòèì,
÷òî îïåðàòîð íå óäàëÿåòñÿ èç ñîñòîÿíèÿ óïðàâëåíèÿ: ñ òî÷êè çðåíèÿ CPU, ýòîò
îïåðàòîð âûïîëíÿåòñÿ âñå âðåìÿ, ïîêà èäóò âû÷èñëåíèÿ íà GPU. Ïðàâèëî 9
âûïîëíÿåòñÿ, êîãäà âû÷èñëåíèÿ íà GPU îêîí÷åíû. Îíî î÷èùàåò ñîñòîÿíèå
óïðàâëåíèÿ GPU è çàâåðøàåò âûïîëíåíèå îïåðàòîðà call gpu_ . Ñîñòîÿíèå ïàìÿòè
CPU â ïðîöåññå âû÷èñëåíèé íà GPU íå ìåíÿåòñÿ: òðåáóåòñÿ ÿâíîå êîïèðîâàíèå
ðåçóëüòàòîâ âû÷èñëåíèé îïåðàòîðîì copy back_ .
2.7. Ïðèìåíåíèå àëãåáðî-äèíàìè÷åñêèõ ìîäåëåé. Ïîñòðîåííûå àëãåá-
ðî-äèíàìè÷åñêèå ìîäåëè èñïîëíåíèÿ ïðîãðàìì äëÿ GPU ïîçâîëÿþò ïðîâîäèòü
ôîðìàëüíûé àíàëèç ðàáîòû òàêèõ ïðîãðàìì, ïîýòîìó òàêèå ìîäåëè ïîëåçíû ïðè
ðàçðàáîòêå ïðîãðàìì.  ÷àñòíîñòè, â ðàáîòå [14] àâòîðû ïðåäëîæèëè èñïîëüçî-
âàòü àëãåáðî-äèíàìè÷åñêèå ìîäåëè äëÿ äîêàçàòåëüñòâà êîððåêòíîñòè ïðåîáðàçî-
âàíèé ìíîãîïîòî÷íûõ ïðîãðàìì. Ïðè ýòîì ôîðìóëèðóþòñÿ íåêîòîðûå ñâîéñòâà
ïðîãðàìì (íàïðèìåð, îòñóòñòâèå òóïèêîâ èëè êîíôëèêòíûõ ñèòóàöèé) è äîêàçû-
âàåòñÿ êîððåêòíîñòü îïðåäåëåííîãî êëàññà ïðåîáðàçîâàíèé ïðè íàëè÷èè îïðåäå-
ëåííûõ ñâîéñòâ ïðîãðàìì. Òàêîé æå ïîäõîä ïðèìåíèì è ê ïðîãðàììàì äëÿ GPU.
Åùå îäíèì íàïðàâëåíèåì èñïîëüçîâàíèÿ àëãåáðî-äèíàìè÷åñêèõ ìîäåëåé èñ-
ïîëíåíèÿ ïðîãðàìì ìîæåò áûòü îöåíêà âðåìåíè âûïîëíåíèÿ ïðîãðàììû. Â ðàáîòå
[13] îïèñàí îáùèé ïîäõîä ê îöåíêå ñëîæíîñòè àëãîðèòìà, ïðåäñòàâëåííîãî â âèäå
âûðàæåíèÿ ÀÃ; îäíàêî òàì èñïîëüçîâàíà àáñòðàêòíàÿ ìîäåëü âû÷èñëèòåëÿ, êîòî-
ðàÿ íå ïîçâîëÿåò ó÷åñòü àïïàðàòíûå îñîáåííîñòè GPU. Ïðåäëîæåííûå â äàííîé
ðàáîòå àëãåáðî-äèíàìè÷åñêèå ìîäåëè äîñòàòî÷íî ïîäðîáíî îïèñûâàþò ïðîöåññ
èñïîëíåíèÿ ïðîãðàììû íà GPU, ïîýòîìó ïîÿâëÿåòñÿ âîçìîæíîñòü áîëåå òî÷íîé
îöåíêè âðåìåíè èñïîëíåíèÿ.  ÷àñòíîñòè, ìîæíî îïèñàòü âëèÿíèå íà ïðîèçâîäè-
òåëüíîñòü ïðîãðàììû ñïîñîáîâ äîñòóïà ê ïàìÿòè è âåòâëåíèé â áëèçêèõ ïîòîêàõ.
3. ÏÅÐÅÏÈÑÛÂÀÞÙÈÅ ÏÐÀÂÈËÀ È ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÏÐÎÃÐÀÌÌ
3.1. Ñèñòåìà Termware. Äëÿ àâòîìàòèçàöèè ïðåîáðàçîâàíèé ïðîãðàìì èñ-
ïîëüçóåì ñèñòåìó ïåðåïèñûâàþùèõ ïðàâèë Termware [9, 10]. Îíà ïðåäíàçíà-
÷åíà äëÿ îïèñàíèÿ ïðåîáðàçîâàíèÿ íàä òåðìàìè, ò.å. âûðàæåíèÿìè âèäà
f t tn( , , )1 � . Äëÿ çàäàíèÿ ïðåîáðàçîâàíèé èñïîëüçóþòñÿ ïðàâèëà Termware,
ò.å. êîíñòðóêöèè âèäà
source [condition] -> destination [action].
Çäåñü source — èñõîäíûé òåðì (îáðàçåö äëÿ ïîèñêà), condition — óñëîâèå
ïðèìåíåíèÿ ïðàâèëà, destination — ïðåîáðàçîâàííûé òåðì, action — äîïîë-
íèòåëüíîå äåéñòâèå ïðè ñðàáàòûâàíèè ïðàâèëà. Êàæäûé èç ÷åòûðåõ êîìïîíåíòîâ
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
ïðàâèëà ìîæåò ñîäåðæàòü ïåðåìåííûå (êîòîðûå çàïèñûâàþòñÿ â âèäå $var), ÷òî
îáåñïå÷èâàåò îáùíîñòü ïðàâèë. Êîìïîíåíòû condition è action íåîáÿçàòåëü-
íû. Îíè ìîãóò èñïîëíÿòü ïðîèçâîëüíûé ïðîöåäóðíûé êîä, â ÷àñòíîñòè èñïîëü-
çîâàòü äîïîëíèòåëüíûå äàííûå î ïðîãðàììå.
3.2. Ïåðåõîä îò ïîñëåäîâàòåëüíîé ïðîãðàììû ê ïðîãðàììå äëÿ GPU.
Ïåðåïèñûâàþùèå ïðàâèëà ïîçâîëÿþò àâòîìàòèçèðîâàòü ïðåîáðàçîâàíèÿ ïðî-
ãðàìì, â ÷àñòíîñòè ïåðåõîä îò ïîñëåäîâàòåëüíîé ïðîãðàììû äëÿ CPU ê ïàðàë-
ëåëüíîé ïðîãðàììå, èñïîëíÿþùåéñÿ íà GPU. Äëÿ ýòîãî ïðîãðàììà ïðåäñòàâëÿåò-
ñÿ â âèäå âûñîêîóðîâíåâîé ìîäåëè, îïèñàííîé â ï. 2.1. Êîä êàæäîé ïðîöåäóðû
codei ìîäåëèðóåòñÿ â âèäå âûðàæåíèÿ ÀÃ, êîòîðîå åñòåñòâåííûì îáðàçîì ïðåä-
ñòàâëÿåòñÿ â âèäå òåðìà. Ê ýòèì òåðìàì ïðèìåíÿþòñÿ ïåðåïèñûâàþùèå ïðàâèëà
Termware, êîòîðûå ïåðåâîäÿò èñõîäíóþ ïðîãðàììó â ïðåîáðàçîâàííóþ âåðñèþ.
Ðàññìîòðèì ðàñïàðàëëåëèâàþùèå ïðåîáðàçîâàíèÿ äëÿ îïðåäåëåííûõ öèêëè-
÷åñêèõ êîíñòðóêöèé. Ïóñòü ôðàãìåíò èñõîäíîé ïðîãðàììû èìååò ñëåäóþùèé âèä:
Ser for i m body i1 � ( , , , ( ))0 . (1)
Çäåñü èñïîëüçîâàí îïåðàòîð öèêëà ñî ñ÷åò÷èêîì for var min max body( , , , ), êîòî-
ðûé âûðàæàåòñÿ îáùèì îïåðàòîðîì öèêëà while. Îïåðàòîð body i( ) îïèñûâàåò
òåëî öèêëà; â îáùåì ñëó÷àå ýòî äîñòàòî÷íî ñëîæíûé îïåðàòîð, â ÷àñòíîñòè,
îí ìîæåò ñîäåðæàòü âëîæåííûå öèêëè÷åñêèå êîíñòðóêöèè. Ðàññìîòðèì ñëåäó-
þùåå ïðåîáðàçîâàíèå: äàííûé ó÷àñòîê ïðîãðàììû ïåðåõîäèò â ïàðàëëåëüíûé
ýêâèâàëåíò:
Gpu init gpu copy gpu call gpu gbody block d gri1 1 1� _ ; _ ; _ ( , , d d copy back1 ); _ . (2)
Çäåñü èñïîëüçîâàíû îïåðàòîðû âçàèìîäåéñòâèÿ ñ GPU, îïèñàííûå â ï. 2.3.
Ñîáñòâåííî òåëî öèêëî ïåðåìåùàåòñÿ â íîâóþ ïðîöåäóðó gbody1 , èñïîëíÿþ-
ùóþñÿ íà GPU. Ýòà ïðîöåäóðà èìååò ñëåäóþùèé âèä:
gbody assign i GetCoor x CpuToGpu body i1 � ( , _ ( )); _ ( ( )). (3)
Ñíà÷àëà âû÷èñëÿåòñÿ íîìåð èñõîäíîé èòåðàöèè i, äëÿ ýòîãî èñïîëüçóþòñÿ
ïàðàìåòðû òåêóùåãî ïîòîêà (ôóíêöèÿ _ ( )GetCoor x , êîòîðàÿ âû÷èñëÿåò íîìåð
èòåðàöèè ïî ïîëîæåíèþ òåêóùåãî ïîòîêà â áëîêå è òåêóùåãî áëîêà â ðåøåòêå).
Çàòåì èñïîëíÿåòñÿ òåëî öèêëà äëÿ ýòîãî çíà÷åíèÿ. Ïðè ýòîì èñïîëüçóåòñÿ ôóíê-
öèÿ _ CpuToGpu äëÿ ïðåîáðàçîâàíèÿ ìåæäó îïåðàòîðàìè CPU- è GPU-ïðîãðàìì.
Ïðåîáðàçîâàíèå ïîñëåäîâàòåëüíîé ïðîãðàììû Ser1 â ïàðàëëåëüíóþ âåðñèþ
äëÿ ãðàôè÷åñêèõ óñêîðèòåëåé Gpu1 îïèñûâàåòñÿ ñëåäóþùèìè ïåðåïèñûâàþùèìè
ïðàâèëàìè.
1. for iter itlm body($ , ,$ ,$ )0 �
[ _ ; _ ; _ ( , , (init gpu copy gpu call gpu gbody block d grid d1 1 1 $ )); _ ]itlm copy back
[_ ( , _ ($ ,$ )]AddMethod gbody CreateKernel d iter body1 1 .
2. _ ($ ,$ ) ($ , _CreateKernel d iter body assign iter GetCoor1 � ( )); _ ($ )x CpuToGpu body .
3. grid d itlm itlm block d block d1 1 1($ ) ($ ) /� � �1 .
Ïðàâèëî 1 îïèñûâàåò ïåðåõîä ôðàãìåíòà ïðîãðàììû îò Ser1 ê Gpu1. Ïðè
ýòîì ïðàâèëî ñîäåðæèò äåéñòâèå _ AddMethod, êîòîðîå ñîçäàåò íîâóþ ïðîöåäó-
ðó. Ïðàâèëî 2 ãåíåðèðóåò òåëî íîâîé ïðîöåäóðû gbody1. Ïðàâèëî 3 çàäàåò ðàçìå-
ðû âû÷èñëèòåëüíîé ðåøåòêè äëÿ çàïóñêà ÿäðà íà îñíîâàíèè êîëè÷åñòâà èòåðàöèé
èñõîäíîãî öèêëà $itlm.
Çàìåòèì, ÷òî ïåðåïèñûâàþùèå ïðàâèëà, çàäàþùèå ïåðåõîä, èìåþò äîñòàòî÷-
íî ïðîñòîé âèä è áëàãîäàðÿ èñïîëüçîâàíèþ âûñîêîóðîâíåâûõ ìîäåëåé ïðîãðàìì
íåïîñðåäñòâåííî ñëåäóþò èç àëãåáðàè÷åñêèõ ðàâåíñòâ (1)–(3). Äëÿ ñðàâíåíèÿ ïðè-
âåäåì àíàëîãè÷íûå ïðåîáðàçîâàíèÿ, îïèñàííûå â [15], êîòîðûå èñïîëüçîâàëè íèç-
êîóðîâíåâóþ ìîäåëü ïðîãðàììû (äåðåâî ñèíòàêñè÷åñêîãî ðàçáîðà) è ïîýòîìó
áûëè áîëåå ãðîìîçäêèìè è ñîäåðæàëè áîëüøîå êîëè÷åñòâî òåõíè÷åñêèõ äåòàëåé.
3.3. Îïòèìèçàöèÿ ïðîãðàìì äëÿ GPU. Ïåðåïèñûâàþùèå ïðàâèëà ìîãóò
èñïîëüçîâàòüñÿ òàêæå äëÿ âûïîëíåíèÿ îïòèìèçèðóþùèõ ïðåîáðàçîâàíèé. Â ýòîì
ñëó÷àå ïåðåïèñûâàþùèå ïðàâèëà ïðèìåíÿþòñÿ òàêèì æå îáðàçîì, êàê è ïðè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 183
ðàñïàðàëëåëèâàíèè, îïèñàííîì â ïðåäûäóùåì ïóíêòå. Åäèíñòâåííîå îòëè÷èå çà-
êëþ÷àåòñÿ â òîì, ÷òî èñõîäíîé ïðîãðàììîé ÿâëÿåòñÿ ïàðàëëåëüíàÿ ïðîãðàììà äëÿ
GPU, êîòîðàÿ ìîæåò áûòü ñîçäàíà âðó÷íóþ èëè ïîëó÷åíà ïóòåì ïðåîáðàçîâàíèé.
 êà÷åñòâå ïðèìåðà îïòèìèçèðóþùåãî ïðåîáðàçîâàíèÿ ðàññìîòðèì ïåðåõîä
îò ïðèìåíåíèÿ ãëîáàëüíîé ïàìÿòè GPU ê èñïîëüçîâàíèþ shared-ïàìÿòè. Òàêîå
ïðåîáðàçîâàíèå ïîçâîëÿåò ñóùåñòâåííî ïîâûñèòü áûñòðîäåéñòâèå ïðîãðàììû,
ïîñêîëüêó çàäåðæêè ïðè äîñòóïå ê shared-ïàìÿòè íàìíîãî ìåíüøå, ÷åì â ñëó÷àå
ãëîáàëüíîé ïàìÿòè.
Ïðåîáðàçîâàíèå òàêîãî òèïà íå çàòðàãèâàåò CPU-÷àñòü ïðîãðàììû è ìåíÿåò
òîëüêî ñîîòâåòñòâóþùåå GPU-ÿäðî.  êà÷åñòâå èñõîäíîé ïðîãðàììû ðàññìîò-
ðèì ÿäðî gbody1èç ïðåäûäóùåãî ïóíêòà. Ïðåîáðàçîâàííîå ÿäðî áóäåò èìåòü âèä
gbody assign i GetCoor x copy shared i Bar11. ( , _ ( )); _ ( ); _� rier;
_ ( ( )); _ ; _ ( )GlobalToShared gbody i Barrier copy global i .
Çäåñü èñïîëüçîâàíî îáîçíà÷åíèå gbody i CpuToGpu body i( ) _ ( ( ))� , ïîä÷åðêèâàþùåå,
÷òî òåëî èñõîäíîãî ÿäðà íå îáÿçàòåëüíî äîëæíî áûòü ïîëó÷åíî ïðåîáðàçîâàíèåì
ïîñëåäîâàòåëüíîé ïðîãðàììû. Íîâîå ÿäðî èñïîëüçóåò äâà îïåðàòîðà:
copy shared i_ ( ) è copy global i_ ( ), äëÿ êîïèðîâàíèÿ äàííûõ èç ãëîáàëüíîé
â shared-ïàìÿòü è â îáðàòíîì íàïðàâëåíèè. Ýòè îïåðàòîðû àíàëîãè÷íû îïåðàòîðàì
copy gpu_ è copy back_ äëÿ êîïèðîâàíèÿ äàííûõ ìåæäó ïàìÿòüþ CPU è GPU.
Îñíîâíîå îòëè÷èå çàêëþ÷àåòñÿ â òîì, ÷òî îïåðàòîðû copy gpu_ è copy back_ êî-
ïèðóþò ñðàçó âñå äàííûå, òîãäà êàê ïðè èñïîëüçîâàíèè copy shared i_ ( ) è
copy global i_ ( ) êàæäûé ïîòîê êîïèðóåò ñâîþ ÷àñòü äàííûõ. Ïîýòîìó íåîáõîäèìà
ñèíõðîíèçàöèÿè ïîòîêîâ ñ èñïîëüçîâàíèåì îïåðàòîðà _ Barrier. Ïðåîáðàçîâàíèå
òàêæå èñïîëüçóåò îïåðàòîð _ GlobalToShared äëÿ ïåðåõîäà îò îïåðàòîðîâ, äåéñòâó-
þùèõ íàä ãëîáàëüíîé ïàìÿòüþ Bg , ê îïåðàòîðàì íàä shared-ïàìÿòüþ Bs.
Ïðàâèëà, ðåàëèçóþùèå äàííîå ïðåîáðàçîâàíèå, àíàëîãè÷íû ðàññìîòðåííûì
â ï. 3.2 è íå ïðèâîäÿòñÿ èç-çà îãðàíè÷åííîãî îáúåìà ñòàòüè.
3.4. Ïåðåõîä ìåæäó âûñîêîóðîâíåâûìè è íèçêîóðîâíåâûìè ìîäåëÿìè
ïðîãðàììû. Êàê óæå óïîìèíàëîñü, ïðåèìóùåñòâî èñïîëüçîâàíèÿ âûñîêîóðîâ-
íåâûõ ìîäåëåé ïðîãðàìì çàêëþ÷àåòñÿ â âîçìîæíîñòè áîëåå êðàòêîé è âûðàçè-
òåëüíîé çàïèñè ïðåîáðàçîâàíèé ïðîãðàììû. Îäíàêî ïðè ýòîì âîçíèêàåò íåîáõî-
äèìîñòü ïåðåõîäà îò ìîäåëè ïðîãðàììû ê èñõîäíîìó êîäó.
Äëÿ áîëåå íèçêîóðîâíåâûõ ìîäåëåé, ôàêòè÷åñêè ñîîòâåòñòâóþùèõ äåðåâó
ñèíòàêñè÷åñêîãî ðàçáîðà, òàêîå ïðåîáðàçîâàíèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ñèí-
òàêñè÷åñêîãî àíàëèçàòîðà è ãåíåðàòîðà äëÿ äàííîãî ÿçûêà ïðîãðàììèðîâàíèÿ.
Ýòîò ïîäõîä èñïîëüçîâàëñÿ, íàïðèìåð, â [15]. Îäíàêî äëÿ ïîñòðîåíèÿ áîëåå âûñî-
êîóðîâíåâûõ ìîäåëåé íåîáõîäèìû äîïîëíèòåëüíûå çíàíèÿ î ïðåäìåòíîé îáëàñòè,
êîòîðûå ìîæíî âûðàçèòü â âèäå íàáîðîâ áàçîâûõ îïåðàòîðîâ è ïðåäèêàòîâ ÀÃ.
 äàííîé ðàáîòå äëÿ ïåðåõîäà îò èñõîäíîãî êîäà ê âûñîêîóðîâíåâîé ìîäåëè
ïðîãðàììû è â îáðàòíîì íàïðàâëåíèè òàêæå èñïîëüçóþòñÿ ïåðåïèñûâàþùèå
ïðàâèëà. Ïåðåõîä ïðîâîäèòñÿ â äâà ýòàïà: ìåæäó èñõîäíûì êîäîì è íèçêîóðîâ-
íåâîé ìîäåëüþ (äåðåâîì ñèíòàêñè÷åñêîãî ðàçáîðà), à çàòåì ìåæäó íèçêîóðîâíå-
âîé è âûñîêîóðîâíåâîé ìîäåëüþ (îïåðàòîðàìè ÀÃ). Íà ïåðâîì ýòàïå èñïîëüçó-
þòñÿ ñèíòàêñè÷åñêèé àíàëèçàòîð è ãåíåðàòîð äàííîãî ÿçûêà. Âòîðîé ýòàï îñóùå-
ñòâëÿåòñÿ ñ ïîìîùüþ ïåðåïèñûâàþùèõ ïðàâèë: ïîñêîëüêó îáà âèäà ìîäåëåé
ïðåäñòàâèìû â âèäå òåðìîâ, ïðåîáðàçîâàíèÿ ìåæäó íèìè çàïèñûâàþòñÿ â âèäå
ïðàâèë. Ïðè ýòîì ïðàâèëà ïðåäñòàâëåíû â âèäå ïàòòåðíîâ Termware (áîëåå ïîä-
ðîáíî îïèñàííûõ â [14]).  îáùåì ñëó÷àå ïàòòåðí îïðåäåëÿåòñÿ äâóìÿ ñèñòåìàìè
ïðàâèë: R p — ñèñòåìà ïðàâèë äëÿ âûäåëåíèÿ ïàòòåðíà èç ïðîèçâîëüíîãî òåðìà,
Rg — ñèñòåìà ïðàâèë äëÿ ðàñøèôðîâêè ïàòòåðíà.  áîëåå ÷àñòíîì ñëó÷àå ïàò-
òåðí çàäàåòñÿ ïàðîé òåðìîâ: t p — îáîçíà÷åíèå ïàòòåðíà (ýëåìåíò ìîäåëè âûñî-
êîãî óðîâíÿ) è tg — îáðàçåö, çàäàþùèé ïàòòåðí (ýëåìåíò ìîäåëè íèçêîãî
óðîâíÿ).  ýòîì ñëó÷àå R t tp g p� �{ } è R t tg p g� �{ }.
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
Òàêîãî ðîäà ïàòòåðíû çàäàþòñÿ äëÿ êàæäîãî âûñîêîóðîâíåâîãî îïåðàòîðà.
Ïîñëåäîâàòåëüíîå ïðèìåíåíèå ïðàâèë R p äëÿ âñåõ îïåðàòîðîâ ïîçâîëÿåò ïåðåé-
òè îò íèçêîóðîâíåâîé ê âûñîêîóðîâíåâîé ìîäåëè. Àíàëîãè÷íî ïðàâèëà Rg îñó-
ùåñòâëÿþò îáðàòíûé ïåðåõîä.  êà÷åñòâå ïðèìåðà ïàòòåðíîâ ðàññìîòðèì
ôóíêöèþ _ GetCoor, êîòîðàÿ èñïîëüçóåòñÿ äëÿ âû÷èñëåíèÿ íîìåðà èñõîäíîé èòåðà-
öèè öèêëà ïî ïàðàìåòðàì ïîòîêà è áëîêà.  ýòîì ñëó÷àå t GetCoor cp �_ ($ ),
t Dot blockIdx c Dot blockDim c Dot threadIdxg � �( ,$ )* ( ,$ ) ( ,$ )c . Òàêèì îáðàçîì, âîç-
ìîæíî ïðåîáðàçîâàíèå ýëåìåíòà âûñîêîóðîâíåâîé ìîäåëè _ ( )GetCoor x â ýëåìåíò
íèçêîóðîâíåâîé ìîäåëè Dot blockIdx x Dot blockDim x Dot threadIdx x( , )* ( , ) ( , )� , êî-
òîðûé çàòåì ïðåîáðàçóåòñÿ â ôðàãìåíò èñõîäíîãî êîäà blockIdx.x * blockDim.x +
+ threadIdx.x. Âîçìîæíî ïðåîáðàçîâàíèå è â îáðàòíîì íàïðàâëåíèè, êîãäà
ôðàãìåíò èñõîäíîãî êîäà ïåðåõîäèò â ýëåìåíò íèçêîóðîâíåâîé ìîäåëè ñ èñïîëü-
çîâàíèåì ñèíòàêñè÷åñêîãî àíàëèçàòîðà, à çàòåì ïðèìåíÿåòñÿ ïðàâèëî R p ïàòòåð-
íà äëÿ âûäåëåíèÿ ýëåìåíòà âûñîêîóðîâíåâîé ìîäåëè.
Åùå îäíà âàæíàÿ îñîáåííîñòü âûñîêîóðîâíåâûõ ìîäåëåé — íåçàâèñèìîñòü îò
ÿçûêà ðåàëèçàöèè. Îäíà âûñîêîóðîâíåâàÿ ìîäåëü ïðîãðàììû ìîæåò ñîîòâåòñòâî-
âàòü íèçêîóðîâíåâûì ïðîãðàììàì íà ðàçëè÷íûõ ÿçûêàõ (èëè ñ èñïîëüçîâàíèåì ðàç-
ëè÷íûõ ïëàòôîðì). Äëÿ ïîääåðæêè ðàçðàáîòêè ïðîãðàìì íà ðàçëè÷íûõ ÿçûêàõ íå-
îáõîäèìà ïîääåðæêà íèçêîóðîâíåâîé ìîäåëè (ò.å. íàëè÷èå àíàëèçàòîðà è ãåíåðàòî-
ðà) äëÿ êàæäîãî ÿçûêà, à òàêæå íàáîð ïàòòåðíîâ, ïîääåðæèâàþùèõ äàííûé ÿçûê.
Ðàññìîòðèì, êàê îäèí îïåðàòîð âûñîêîóðîâíåâîé ìîäåëè ïî-ðàçíîìó âûãëÿäèò
â ðàçëè÷íûõ ÿçûêàõ (ðåàëèçàöèÿ îïåðàòîðà init gpu_ äëÿ C è C#).  ïåðâîì ñëó÷àå
ýòîò îïåðàòîð ñâîäèòñÿ ê âûçîâó îäíîé ôóíêöèè: t FunctionCall InitCUDA NILg
c � ( , ).
 ðåçóëüòàòå ãåíåðèðóåòñÿ ôðàãìåíò êîäà InitCUDA(). Äëÿ C# òîò æå îïåðàòîð ïðè-
âîäèò ê ñîçäàíèþ îáúåêòà ñïåöèàëüíîãî òèïà: t DeclarationAssignment cudag
cs � ( ,
CUDA New CUDA true, ( , [ , ]))0 . Ñîîòâåòñòâóþùèé êîä èìååò âèä CUDA cuda = new
CUDA(0, true).
Òàêèì îáðàçîì, èñïîëüçîâàíèå âûñîêîóðîâíåâûõ ìîäåëåé ïîçâîëÿåò îïèñû-
âàòü ïðåîáðàçîâàíèÿ ïðîãðàìì íåçàâèñèìî îò êîíêðåòíîãî ÿçûêà ðåàëèçàöèè.
3.5. Ïðèìåð èñïîëüçîâàíèÿ ïðåîáðàçîâàíèé. Ðàññìîòðèì èñïîëüçîâàíèå
îïèñàííûõ ïðåîáðàçîâàíèé íà ïðèìåðå çàäà÷è óìíîæåíèÿ ìàòðèö. Èñõîäíàÿ ïðî-
ãðàììà ðåàëèçîâàíà íà ÿçûêå C#. Ïî ýòîé ïðîãðàììå ïîñòðîåíà ñíà÷àëà íèçêîó-
ðîâíåâàÿ ìîäåëü (ñ èñïîëüçîâàíèåì ñèíòàêñè÷åñêîãî àíàëèçàòîðà ÿçûêà C#), à çà-
òåì è âûñîêîóðîâíåâàÿ ìîäåëü (ñ èñïîëüçîâàíèåì ïàòòåðíîâ äëÿ îïåðàòîðîâ àðèô-
ìåòè÷åñêèõ äåéñòâèé è ðàáîòû ñ äâóìåðíûìè ìàññèâàìè). Ê âûñîêîóðîâíåâîé
ìîäåëè ñíà÷àëà ïðèìåíÿëèñü ðàñïàðàëëåëèâàþùåå, à çàòåì îïòèìèçèðóþùåå ïðå-
îáðàçîâàíèÿ, îïèñàííûå â ïï. 3.2 è 3.3. Äàëåå ê ïîëó÷åííîé âûñîêîóðîâíåâîé ìî-
äåëè ðàñïàðàëëåëåííîé è îïòèìèçèðîâàííîé ïðîãðàììû ïðèìåíÿëñÿ îáðàòíûé
ïðîöåññ: ñíà÷àëà èñïîëüçîâàëèñü ïàòòåðíû äëÿ ïåðåõîäà ê íèçêîóðîâíåâîé ìîäå-
ëè, êîòîðàÿ çàòåì ïåðåâîäèëàñü â èñõîäíûé êîä ñ ïðèìåíåíèåì ãåíåðàòîðà êîäà.
Ýòîò ïðîöåññ ïðîâîäèëñÿ äëÿ äâóõ ÿçûêîâ: C# è C. (Ðàçëè÷èÿ ìåæäó ïîëó÷åííû-
ìè ïðîãðàììàìè çàêëþ÷àëîñü òîëüêî â CPU-÷àñòè ïðîãðàììû: GPU-ïðîãðàììà
â îáîèõ ñëó÷àÿõ áûëà îäèíàêîâîé è ðåàëèçîâàííîé íà ÿçûêå C for CUDA.)
Ðåçóëüòàòû èçìåðåíèÿ
ïðîèçâîäèòåëüíîñòè ðàçëè÷-
íûõ âàðèàíòîâ ïðîãðàìì
ïðèâåäåíû â òàáë. 1. Êàê âèä-
íî èç òàáëèöû, äëÿ äàííîé
çàäà÷è äàæå íåîïòèìèçèðî-
âàííûé âàðèàíò äàåò ÷åòû-
ðåõêðàòíîå óñêîðåíèå, à îïòè-
ìèçèðîâàííûé ïîçâîëÿåò
óìåíüøèòü âðåìÿ ðàáîòû áî-
ëåå ÷åì â 20 ðàç. Çàìåòèì,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 185
Âåðñèÿ ïðîãðàììû
Âðåìÿ
èñïîëíåíèÿ, ñ
Êîýôôèöèåíò
óñêîðåíèÿ
Ïîñëåäîâàòåëüíàÿ, C# 4,02 1
Ïàðàëëåëüíàÿ, C# 0,97 4,1
Îïòèìèçèðîâàííàÿ, C# 0,19 21,4
Ïîñëåäîâàòåëüíàÿ, C 3,58 1
Ïàðàëëåëüíàÿ, C 0,96 3,7
Îïòèìèçèðîâàííàÿ, C 0,15 23,2
Ò à á ë è ö à 1
÷òî îñíîâíîå âðåìÿ èñïîëíåíèÿ GPU-ïðîãðàììû çàíèìàþò íå ñàìè âû÷èñëåíèÿ,
à êîïèðîâàíèå äàííûõ è ðåçóëüòàòîâ. Åñëè äàííûå óæå èìåþòñÿ â âèäåîïàìÿòè è
ðåçóëüòàò íåîáõîäèìî ïîìåñòèòü òàì æå, îïòèìèçèðîâàííàÿ âåðñèÿ äàñò óñêîðå-
íèå â 124 ðàçà, ÷òî áëèçêî ê êîëè÷åñòâó âû÷èñëèòåëüíûõ ÿäåð GPU (128 ÿäåð).
Çàäà÷à óìíîæåíèÿ ìàòðèö õîðîøî ïîäõîäèò äëÿ ïàðàëëåëüíîé ðåàëèçàöèè
(õîòÿ, êàê âèäíî èç òàáë. 1, äëÿ äîñòèæåíèÿ ïðîèçâîäèòåëüíîñòè íåîáõîäèìî
ïðèìåíèòü îïòèìèçèðóþùèå ïðåîáðàçîâàíèÿ). Äëÿ ñðàâíåíèÿ ðàññìîòðèì çàäà÷ó
ñëîæåíèÿ ýëåìåíòîâ ÷èñëîâîãî ìàññèâà, ïîäðîáíî îïèñàííóþ â [15]. Ýòà çàäà÷à
èñïîëüçóåò ïîõîæèå îïåðàòîðû àðèôìåòè÷åñêèõ äåéñòâèé è ðàáîòû ñ ìàññèâàìè,
îäíàêî îïåðàòîðû â ðàçëè÷íûõ ïîòîêàõ èñïîëíÿþòñÿ â ðàçëè÷íîì ïîðÿäêå è äîñ-
òóï ê ïàìÿòè îñóùåñòâëÿåòñÿ íåðåãóëÿðíî. Â ðåçóëüòàòå ïðèìåíåíèå ðàñïàðàëëå-
ëèâàþùåãî ïðåîáðàçîâàíèÿ äàæå ïîíèæàåò ïðîèçâîäèòåëüíîñòü ïðîãðàììû, òîã-
äà êàê èñïîëüçîâàíèå îïòèìèçèðóþùåãî ïðåîáðàçîâàíèÿ èç ï. 3.3 ïîâûøàåò ïðî-
èçâîäèòåëüíîñòü âñåãî â äâà ðàçà ïî ñðàâíåíèþ ñ ïîñëåäîâàòåëüíîé ïðîãðàììîé.
Ýòî ïîäòâåðæäàåò òîò ôàêò, ÷òî ðàçðàáîòêà ïðîãðàìì äëÿ GPU — ñëîæíàÿ çàäà÷à,
òðåáóþùàÿ ó÷åòà ñïåöèôèêè çàäà÷è. Èñïîëüçîâàíèå ïåðåïèñûâàþùèõ ïðàâèë è âû-
ñîêîóðîâíåâûõ ìîäåëåé â äàííîì ñëó÷àå ïîçâîëÿåò ïðèìåíèòü ñòàíäàðòíûå ïðåîá-
ðàçîâàíèÿ, ïðåæäå ÷åì êîíöåíòðèðîâàòüñÿ íà áîëåå òîíêèõ äåòàëÿõ îïòèìèçàöèè,
ñïåöèôè÷åñêèõ äëÿ êîíêðåòíîé çàäà÷è.  ðàáîòå [15] îïèñàíî, êàê ïðèìåíåíèå ïåðå-
ïèñûâàþùèõ ïðàâèë äëÿ ðåàëèçàöèè ñïåöèôè÷åñêèõ ïðåîáðàçîâàíèé ïîçâîëÿåò ïî-
ëó÷èòü óñêîðåíèå â 20 ðàç ïî ñðàâíåíèþ ñ ïîñëåäîâàòåëüíîé ïðîãðàììîé; ïðè ýòîì
ñïåöèôè÷åñêèå ïðåîáðàçîâàíèÿ ìîãóò ïðèìåíÿòüñÿ òîëüêî ïîñëå èñïîëüçîâàíèÿ
óíèâåðñàëüíûõ ïðåîáðàçîâàíèé äëÿ ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå ðàññìîòðåíû ïðîáëåìû ïðîãðàììèðîâàíèÿ âûñîêîïðîèçâî-
äèòåëüíûõ âû÷èñëåíèé è èõ ïðåëîìëåíèå, â ÷àñòíîñòè, äëÿ àðõèòåêòóðû âèäå-
îãðàôè÷åñêèõ óñêîðèòåëåé. Ïðåäëîæåíû ôîðìàëüíûå ìåòîäû äëÿ ðàçðàáîòêè
ýôôåêòèâíûõ ïàðàëëåëüíûõ ïðîãðàìì äëÿ GPU. Àëãåáðî-äèíàìè÷åñêèå ìîäåëè
èñïîëíåíèÿ ïðîãðàìì ïîçâîëÿþò äîêàçûâàòü êîððåêòíîñòü ïðåîáðàçîâàíèé è
îöåíèâàòü âðåìÿ èñïîëíåíèÿ ïðîãðàìì. Ïåðåïèñûâàþùèå ïðàâèëà ñïîñîáñòâó-
þò àâòîìàòèçàöèè ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè ïðîãðàìì. Èñïîëüçîâà-
íèå âûñîêîóðîâíåâûõ ìîäåëåé ïðîãðàìì ïîçâîëÿåò ñîêðàòèòü ðàçìåð ïðàâèë
äëÿ ïðåîáðàçîâàíèÿ, à òàêæå ïðèìåíèòü îäíè è òå æå ïðàâèëà äëÿ îïèñàíèÿ
ïðåîáðàçîâàíèé íà ðàçíûõ ÿçûêàõ. Ýêñïåðèìåíòàëüíûå äàííûå ïîäòâåðäèëè
âûñîêóþ ýôôåêòèâíîñòü ïðåîáðàçîâàíèé: äîñòèãíóòî óñêîðåíèå áîëåå ÷åì
â 20 ðàç ïî ñðàâíåíèþ ñ ïîñëåäîâàòåëüíîé ïðîãðàììîé.
Äàëüíåéøèå èññëåäîâàíèÿ â äàííîì íàïðàâëåíèè ïðåäïîëàãàþò ðàçðàáîòêó äî-
ïîëíèòåëüíûõ ïðåîáðàçîâàíèé äëÿ ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè êîäà äëÿ GPU
è îöåíêó èõ ýôôåêòèâíîñòè íà ðàçëè÷íûõ ïðèìåðàõ. Êðîìå òîãî, âîçìîæíî óòî÷íå-
íèå ïîñòðîåííûõ ìîäåëåé äëÿ ó÷åòà äîïîëíèòåëüíûõ àïïàðàòíûõ è ïðîãðàììíûõ
âîçìîæíîñòåé ïëàòôîðìû CUDA; ïðåäïîëàãàåòñÿ òàêæå ïîääåðæêà äðóãèõ òåõíîëî-
ãèé ïðîãðàììèðîâàíèÿ äëÿ ãðàôè÷åñêèõ óñêîðèòåëåé, òàêèõ êàê OpenCL.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A k h t e r S . , R o b e r t s J . Multi-core programming. Increasing performance through software
multi-threading. — Hillsboro: Intel Press, 2006. — 336 p.
2. A d l - T a b a t a b a i A . - R . , K o z y r a k i s C . , S a h a B . Unlocking concurrency // Comput.
Architect. — Dec. 2006 / Jan. 2007. — 4, N 10. — P. 24–33.
3. C h r y s a n t h a k o p o u l o s G . , S i n g h S . An asynchronous messaging library for C#. —
http://research.microsoft.com/~tharris/scool/papers/sing.pdf.
4. Ä î ð î ø å í ê î À . Å . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû îðãàíèçàöèè âûñîêîïðîèçâîäèòåëüíûõ
ïàðàëëåëüíûõ âû÷èñëåíèé. Àëãåáðî-äèíàìè÷åñêèé ïîäõîä. — Êèåâ: Íàóê. äóìêà, 2000. — 177 ñ.
5. G e n e r a l - p u r p o s e computation using graphics hardware. — http://www.gpgpu.org.
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
6. N V i d i a CUDA technology. — http://www.nvidia.com/cuda.
7. L e t i c h e v s k y A . A . , K a p i t o n o v a J . V . , K o n o z e n k o S . V . Computations in APS //
Theoret. Comput. Sci. — 1993. — 119. — P. 145–171.
8. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í Ã . Å . , ß ö å í ê î Å . À . Àëãåáðîàëãî-
ðèòìè÷åñêèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Êèåâ: Àêàäåìïåðèîäèêà,
2007. — 631 ñ.
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 // Fund. Inform. — 2006. — 72, N 1–3. — P. 95–108.
10. T e r m W a r e . — http://www.gradsoft.com.ua/products/termware_rus.html.
11. Ë å ò è ÷ å â ñ ê è é À . À . , Õ î ì å í ê î Â . Â . Ïåðåïèñûâàþùàÿ ìàøèíà è îïòèìèçàöèÿ
ñòðàòåãèé ïåðåïèñûâàíèÿ òåðìîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2002. — ¹ 5. — Ñ. 3–17.
12. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . , ß ö å í ê î Å . À . Ôîðìàëèçîâàííîå ïðîåêòèðîâàíèå
ýôôåêòèâíûõ ìíîãîïîòî÷íûõ ïðîãðàìì // Ïðîáë. ïðîãðàììèðîâàíèÿ. — 2007. — ¹ 1. —
Ñ. 17–30.
13. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . , ß ö å í ê î Å . À . Îá îöåíêå ñëîæíîñòè è êîîð-
äèíàöèè âû÷èñëåíèé â ìíîãîïîòî÷íûõ ïðîãðàììàõ // Òàì æå. — 2007. — ¹ 2. — Ñ. 41–55.
14. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . Àëãåáðî-äèíàìè÷åñêèå ìîäåëè äëÿ ðàñïàðàëëåëè-
âàíèÿ ïðîãðàìì // Òàì æå. — 2010. — ¹ 1. — Ñ. 39–55.
15. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . Ðàçðàáîòêà âûñîêîïàðàëëåëüíûõ ïðèëîæåíèé äëÿ
ãðàôè÷åñêèõ óñêîðèòåëåé ñ èñïîëüçîâàíèåì ïåðåïèñûâàþùèõ ïðàâèë // Òàì æå. — 2009. —
¹ 3. — Ñ. 3–18.
16. L e e S . , M i n S . , a n d E i g e n m a n n R . OpenMP to GPGPU: a compiler framework for auto-
matic translation and optimization // Proc. of the 14th ACM SIGPLAN Symp. on Principles and Practice of
Parallel Program. (PPoPP’9), Raleigh, NC (USA) Febr. 14–18, 2009. — P. 101–110.
17. O p e n M P specification. — http://openmp.org/wp/.
18. A c o m p i l e r framework for optimization of affine loop nests for gpgpus / M. Baskaran,
U. Bondhugula, S. Krishnamoorthy, et al. // Proc. of the 22nd Ann. Intern. Conf. on Supercom.
(ICS’08), Island of Kos (Greece), June 07–12, 2008. — New York: ACM, 2008. — P. 225–234.
19. M a W . a n d A g r a w a l G . A compiler and runtime system for enabling data mining applica-
tions on gpus // Proc. of the 14th ACM SIGPLAN Symp. on Principles and Practice of Parallel Pro-
gram (PPoPP’09), Raleigh, NC (USA), Febr. 14–18, 2009. — New York: ACM, 2009. —
P. 287–288.
20. A l l u s s e Y . , H o r a i n P . , A g a r w a l A . , a n d S a i p r i y a d a r s h a n C . GpuCV: an open
source GPU-accelerated framework for image processing and computer vision // Proc. of the 16th
ACM Intern.Conf. on Multimedia (MM’08), Vancouver, British Columbia (Canada), Oct. 26–31,
2008. — New York: ACM, 2008. — P. 1089–1092.
21. G l i f t : Generic, efficient, random-access GPU data structures / A.E. Lefohn, S. Sengupta, J. Kniss,
et al. // ACM Trans. Graph. — 2006. — 25, N 1. — P. 60–99.
22. H a n T . D . a n d A b d e l r a h m a n T . S . hiCUDA: a high-level directive-based language for
GPU programming // Proc. of 2nd Workshop on General Purpose Processing on Graphics Processing
Units (GPGPU-2), Washington, D.C., March 08, 2009. — New York: ACM, 2009. — 383. —
P. 52–61.
23. H o u Q . , Z h o u K . , G u o B . BSGP: bulk-synchronous GPU programming // ACM
SIGGRAPH 2008 Papers, Los Angeles, Aug. 11–15, 2008. — New York: ACM, 2008. — P. 1–12.
Ïîñòóïèëà 24.02.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 187
|