Метод автоматической генерации автотюнеров для параллельных программ
Представлена формальная модель метода автоматизированной настройки параллельных приложений (автотюнинга). Описана программная реализация этой модели в виде гибкой системы программных средств для автоматической генерации автотюнеров, которая основана на системе переписывания термов и использовании эк...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/115805 |
| 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: | Метод автоматической генерации автотюнеров для параллельных программ / П.А. Иваненко, А.Е. Дорошенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 161-173. — Бібліогр.: 22 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-115805 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1158052025-06-03T16:25:10Z Метод автоматической генерации автотюнеров для параллельных программ Метод автоматичного породження автотюнерів для паралельних програм Method of automated generation of autotuners for parallel programs Иваненко, П.А. Дорошенко, А.Е. Программно-технические комплексы Представлена формальная модель метода автоматизированной настройки параллельных приложений (автотюнинга). Описана программная реализация этой модели в виде гибкой системы программных средств для автоматической генерации автотюнеров, которая основана на системе переписывания термов и использовании экспертных знаний в качестве источника оптимизационных преобразований. Представлено формальну модель методу автоматичного налаштування паралельних програм (автотюнінгу). Описано програмну реалізацію цієї моделі у вигляді гнучкої системи програмних засобів для автоматичної генерації автотюнерів, яка ґрунтується на системі переписування термів та використанні експертних знань як джерела оптимізаційних перетворень. The paper introduces a formal model of the method of automated adjustment of parallel applications (autotuning). The program implementation of this model is described in the form of a flexible software framework for automatic generation of autotuners, which utilizes term rewriting system and expert knowledge as a source of optimizing transformations. 2014 Article Метод автоматической генерации автотюнеров для параллельных программ / П.А. Иваненко, А.Е. Дорошенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 161-173. — Бібліогр.: 22 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/115805 681.5 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Программно-технические комплексы Программно-технические комплексы |
| spellingShingle |
Программно-технические комплексы Программно-технические комплексы Иваненко, П.А. Дорошенко, А.Е. Метод автоматической генерации автотюнеров для параллельных программ Кибернетика и системный анализ |
| description |
Представлена формальная модель метода автоматизированной настройки параллельных приложений (автотюнинга). Описана программная реализация этой модели в виде гибкой системы программных средств для автоматической генерации автотюнеров, которая основана на системе переписывания термов и использовании экспертных знаний в качестве источника оптимизационных преобразований. |
| format |
Article |
| author |
Иваненко, П.А. Дорошенко, А.Е. |
| author_facet |
Иваненко, П.А. Дорошенко, А.Е. |
| author_sort |
Иваненко, П.А. |
| title |
Метод автоматической генерации автотюнеров для параллельных программ |
| title_short |
Метод автоматической генерации автотюнеров для параллельных программ |
| title_full |
Метод автоматической генерации автотюнеров для параллельных программ |
| title_fullStr |
Метод автоматической генерации автотюнеров для параллельных программ |
| title_full_unstemmed |
Метод автоматической генерации автотюнеров для параллельных программ |
| title_sort |
метод автоматической генерации автотюнеров для параллельных программ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Программно-технические комплексы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/115805 |
| citation_txt |
Метод автоматической генерации автотюнеров для параллельных программ / П.А. Иваненко, А.Е. Дорошенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 161-173. — Бібліогр.: 22 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT ivanenkopa metodavtomatičeskojgeneraciiavtotûnerovdlâparallelʹnyhprogramm AT dorošenkoae metodavtomatičeskojgeneraciiavtotûnerovdlâparallelʹnyhprogramm AT ivanenkopa metodavtomatičnogoporodžennâavtotûnerívdlâparalelʹnihprogram AT dorošenkoae metodavtomatičnogoporodžennâavtotûnerívdlâparalelʹnihprogram AT ivanenkopa methodofautomatedgenerationofautotunersforparallelprograms AT dorošenkoae methodofautomatedgenerationofautotunersforparallelprograms |
| first_indexed |
2025-11-24T10:13:03Z |
| last_indexed |
2025-11-24T10:13:03Z |
| _version_ |
1849666235820670976 |
| fulltext |
ÓÄÊ 681.5
Ï.À. ÈÂÀÍÅÍÊÎ, À.Å. ÄÎÐÎØÅÍÊÎ
ÌÅÒÎÄ ÀÂÒÎÌÀÒÈ×ÅÑÊÎÉ ÃÅÍÅÐÀÖÈÈ ÀÂÒÎÒÞÍÅÐÎÂ
ÄËß ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ
Àííîòàöèÿ. Ïðåäñòàâëåíà ôîðìàëüíàÿ ìîäåëü ìåòîäà àâòîìàòèçèðîâàííîé íàñòðîéêè ïà-
ðàëëåëüíûõ ïðèëîæåíèé (àâòîòþíèíãà). Îïèñàíà ïðîãðàììíàÿ ðåàëèçàöèÿ ýòîé ìîäåëè
â âèäå ãèáêîé ñèñòåìû ïðîãðàììíûõ ñðåäñòâ äëÿ àâòîìàòè÷åñêîé ãåíåðàöèè àâòîòþíå-
ðîâ, êîòîðàÿ îñíîâàíà íà ñèñòåìå ïåðåïèñûâàíèÿ òåðìîâ è èñïîëüçîâàíèè ýêñïåðòíûõ
çíàíèé â êà÷åñòâå èñòî÷íèêà îïòèìèçàöèîííûõ ïðåîáðàçîâàíèé.
Êëþ÷åâûå ñëîâà: àâòîòþíèíã, ïàðàëëåëüíûå âû÷èñëåíèÿ, îïòèìèçàöèÿ ïðîãðàìì, ñèñòå-
ìû ïåðåïèñûâàíèÿ òåðìîâ.
ÂÂÅÄÅÍÈÅ
Äëÿ ðåøåíèÿ ñëîæíûõ íàó÷íî-òåõíè÷åñêèõ çàäà÷ òðåáóþòñÿ áîëüøèå âû÷èñ-
ëèòåëüíûå ìîùíîñòè ïàðàëëåëüíûõ ñèñòåì, ïîýòîìó ýòàï îïòèìèçàöèè ïðè-
êëàäíûõ ïðîãðàìì äëÿ êîíêðåòíîé âûñîêîïðîèçâîäèòåëüíîé ñðåäû âû÷èñëå-
íèé çàíèìàåò çíà÷èòåëüíîå ìåñòî â ïðîöåññå èõ ðàçðàáîòêè. Êëàññè÷åñêîå âû-
ñêàçûâàíèå «ýôôåêòèâíûå àëãîðèòìû âñåãäà ëó÷øå ñóïåðêîìïüþòåðîâ» [1]
òî÷íî îòðàæàåò ïðîáëåìó ýôôåêòèâíîãî èñïîëüçîâàíèÿ âû÷èñëèòåëüíûõ ðå-
ñóðñîâ: íàëè÷èå ìîùíîãî âû÷èñëèòåëÿ íå ãàðàíòèðóåò óñïåøíîãî âûïîëíåíèÿ
çàäà÷è â ïðèåìëåìûõ âðåìåííûõ ðàìêàõ.
Ïðîãðàììèðîâàíèå ýôôåêòèâíûõ àëãîðèòìîâ âñåãäà áûëî íåëåãêîé çàäà÷åé,
êîòîðàÿ åùå áîëåå óñëîæíÿåòñÿ â ñâÿçè ñ ìàññîâûì ïåðåõîäîì ê èñïîëüçîâàíèþ
ìíîãîÿäåðíûõ ìèêðîïðîöåññîðîâ. Äî ýòîãî ïåðåõîäà ìîùíîñòü ïðîöåññîðîâ
óäâàèâàëàñü êàæäûå 18 ìåñÿöåâ (çàêîí Ìóðà), â ðåçóëüòàòå ÷åãî ñòàðûå ïðîãðàì-
ìû ðàáîòàëè â äâà ðàçà áûñòðåå íà íîâûõ ìîäåëÿõ âû÷èñëèòåëåé.  íàñòîÿùåå
âðåìÿ ðîñò ïðîèçâîäèòåëüíîñòè ñèñòåìû âñëåäñòâèå óâåëè÷åíèÿ êîëè÷åñòâà ÿäåð
îäíîãî âû÷èñëèòåëÿ ïðè ïî÷òè íåèçìåííîé òàêòîâîé ÷àñòîòå ÿäðà ìîæåò îãðàíè-
÷èâàòüñÿ çàêîíîì Àìäàëà [2]. Ýôôåêòèâíûé ïàðàëëåëüíûé àëãîðèòì, êðîìå
óäà÷íîé äåêîìïîçèöèè çàäà÷è íà íåçàâèñèìûå ïîäçàäà÷è, äîëæåí ìèíèìèçèðî-
âàòü çàòðàòû íà ñèíõðîíèçàöèþ âû÷èñëåíèé è ïåðåñûëêó äàííûõ, ÷òî âåñüìà
ñëîæíî ñäåëàòü áåç ó÷åòà àðõèòåêòóðû ñðåäû èñïîëíåíèÿ.
Òðàäèöèîííûì ñïîñîáîì àâòîìàòè÷åñêîãî ïîëó÷åíèÿ êîäà ïàðàëëåëüíûõ
ïðîãðàìì ÿâëÿþòñÿ òàê íàçûâàåìûå «ðàñïàðàëëåëèâàþùèå êîìïèëÿòîðû» [3, 4].
Îäíàêî, íåñìîòðÿ íà çíà÷èòåëüíîå óëó÷øåíèå êà÷åñòâà àâòîìàòè÷åñêîãî ðàñïàðàë-
ëåëèâàíèÿ â ïîñëåäíèå ãîäû, äî ñèõ ïîð îáëàñòü åãî ïðèìåíåíèÿ îãðàíè÷èâàåòñÿ
ïðîãðàììàìè ñ äîñòàòî÷íî ïðîñòûìè ñõåìàìè âû÷èñëåíèé. Ðàçâèòèå ýòîãî ïîäõî-
äà çàòðóäíåíî âñëåäñòâèå áîëüøîé ñëîæíîñòè ñòàòè÷åñêîãî àíàëèçà êîäà, ðàçíîîá-
ðàçèÿ àðõèòåêòóð âû÷èñëèòåëüíûõ ñèñòåì, à òàêæå ïîñòîÿííîãî èõ óñëîæíåíèÿ.
Àëüòåðíàòèâîé ðàñïàðàëëåëèâàþùèì êîìïèëÿòîðàì ÿâëÿåòñÿ àâòîòþíèíã
[5] — íîâûé, ãèáêèé è ýôôåêòèâíûé ïîäõîä. Îí ïîçâîëÿåò ýìïèðè÷åñêè â àâòî-
ìàòè÷åñêîì ðåæèìå ïîäîáðàòü íàèëó÷øèé âàðèàíò ïðîãðàììû äëÿ äàííîé öåëå-
âîé ñðåäû âûïîëíåíèÿ. Ãëàâíîå äîñòîèíñòâî ýòîãî ïîäõîäà — àáñòðàãèðîâàíèå
ëîãèêè ïðîãðàììû îò ÷èñëåííûõ õàðàêòåðèñòèê âû÷èñëèòåëüíîé ñèñòåìû òàêèõ,
êàê êîëè÷åñòâî ÿäåð, ðàçìåð êýøà ïðîöåññîðîâ èëè ñêîðîñòü äîñòóïà ê ðàçëè÷-
íûì óðîâíÿì ïàìÿòè. Â ðåçóëüòàòå ïàðàëëåëüíûé àëãîðèòì îïåðèðóåò âûñîêîó-
ðîâíåâûìè ïîíÿòèÿìè èç ïðåäìåòíîé îáëàñòè çàäà÷è (ðàçìåð è êîëè÷åñòâî íåçà-
âèñèìî âûïîëíÿåìûõ ïîäçàäà÷) èëè îñîáåííîñòÿìè ÷èñëåííîãî ìåòîäà ðåøåíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 161
� Ï.À. Èâàíåíêî, À.Å. Äîðîøåíêî, 2014
çàäà÷è (íàïðèìåð, ìåòîä îáõîäà ñòðóêòóðû äàííûõ). Îäíàêî íåäîñòàòêîì àâòî-
òþíèíãà ìîãóò áûòü çíà÷èòåëüíûå (õîòÿ è îäíîêðàòíûå) âðåìåííûå çàòðàòû íà
îïòèìèçàöèþ ïðîãðàìì: åñëè êîëè÷åñòâî ïàðàìåòðîâ, ðåëåâàíòíûõ ïðîèçâîäè-
òåëüíîñòè ïðîãðàììû, âåëèêî, çàòðà÷åííîå âðåìÿ ìîæåò èçìåðÿòüñÿ ÷àñàìè èëè
äàæå äíÿìè. Êðîìå òîãî, âîçíèêàåò íåîáõîäèìîñòü íàïèñàíèÿ äîïîëíèòåëüíîãî
ïðèëîæåíèÿ — íåïîñðåäñòâåííî àâòîòþíåðà.
Õîðîøèì ðåøåíèåì äëÿ óñòðàíåíèÿ îïèñàííûõ íåäîñòàòêîâ àâòîòþíèíãà
ìîæåò áûòü èñïîëüçîâàíèå ñïåöèàëèçèðîâàííûõ èíñòðóìåíòàëüíûõ ñèñòåì, êî-
òîðûå ðàáîòàþò ñ èñõîäíûì êîäîì ïðîãðàììû, îñíîâûâàÿñü íà ýêñïåðòíûõ çíà-
íèÿõ (expert knowledge) ðàçðàáîò÷èêà, ïðåäñòàâëåííûõ â âèäå íåêîòîðûõ ìåòà-
äàííûõ (ïðàãìû, àííîòàöèè è äð.). Ýòî ïîçâîëÿåò ñóùåñòâåííî óìåíüøèòü êîëè-
÷åñòâî èñïûòóåìûõ âàðèàíòîâ ïðîãðàììû è, ñëåäîâàòåëüíî, ñîêðàòèòü âðåìÿ
îïòèìèçàöèè. Ðàáîòà ñèñòåìû ñ èñõîäíûì êîäîì ïðîãðàììû, â ñâîþ î÷åðåäü,
èçáàâëÿåò ðàçðàáîò÷èêà îò çàäà÷è íàïèñàíèÿ äîïîëíèòåëüíîãî ïðèëîæåíèÿ-àâòî-
òþíåðà. Òàêàÿ ñèñòåìà àâòîòþíèíãà â îòëè÷èå îò øèðîêî èçâåñòíûõ áèáëèîòå÷-
íûõ ñèñòåì ATLAS [6] è FFTW [7] íå çàâèñèò îò îáëàñòè ðåøàåìîé çàäà÷è
è óíèâåðñàëüíà â ñâîåì êëàññå.
Ðàññìàòðèâàåìàÿ â íàñòîÿùåé ðàáîòå ñèñòåìà àâòîòþíèíãà TuningGenie èñ-
ïîëüçóåò îïèñàííûé âûøå ïîäõîä è âî ìíîãîì ñõîæà ñ ÿçûêîâûì ðàñøèðåíèåì
äëÿ àâòîòþíèíãà Atune-IL [8]. Ñóùåñòâåííûì îòëè÷èåì TuningGenie ÿâëÿåòñÿ âû-
ïîëíåíèå òðàíñôîðìàöèé èñõîäíîãî êîäà ïðîãðàììû ñ ïîìîùüþ ñèñòåìû îáðà-
áîòêè òåðìîâ, îñíîâàííîé íà òåõíèêå ïåðåïèñûâàþùèõ ïðàâèë. Ïðåäñòàâëåíèå
êîäà ïðîãðàììû â âèäå òåðìà è ìàíèïóëèðîâàíèå èì ñ ïîìîùüþ ïåðåïèñûâàþ-
ùèõ ïðàâèë (TermWare [9, 10]) ïîçâîëÿåò èçìåíåíÿòü êîä è ñòðóêòóðó ïðîãðàììû
â äåêëàðàòèâíîì ñòèëå, ÷òî çíà÷èòåëüíî ðàñøèðÿåò âîçìîæíîñòè ñèñòåìû.
Äàëåå îïèñàíî ïîñòðîåíèå ôîðìàëüíîé ìîäåëè ñèñòåìû àâòîòþíèíãà
TuningGenie, äîêàçàíû îñíîâíûå ñâîéñòâà âûïîëíÿåìûõ ïðåîáðàçîâàíèé, ïðèâå-
äåíû èíñòðóìåíòàðèé ñèñòåìû è ïðèìåðû åå ïðèìåíåíèÿ äëÿ çàäà÷ ïàðàëëåëüíî-
ãî ïðîãðàììèðîâàíèÿ.
ÀÂÒÎÒÞÍÈÍÃ
Ðàññìîòðèì äåòàëüíåå êîíöåïöèþ àâòîìàòè÷åñêîé ïðîãðàììíîé îïòèìèçà-
öèè — àâòîòþíèíãà.
Êëþ÷åâîé îñîáåííîñòüþ äàííîãî ïîäõîäà ÿâëÿåòñÿ òî, ÷òî îïòèìèçàöèÿ âû-
ïîëíÿåòñÿ àâòîìàòèçèðîâàííûì ñïîñîáîì ñ ïîìîùüþ ýìïèðè÷åñêèõ èñïûòàíèé,
ïðîâîäèìûõ ïðîãðàììîé-àâòîòþíåðîì íà òîì æå îáîðóäîâàíèè, íà êîòîðîì äà-
ëåå áóäåò âûïîëíÿòüñÿ îïòèìèçèðóåìàÿ ïðèêëàäíàÿ ïðîãðàììà. Çàòåì íà îñíîâå
àíàëèçà ïðîâåäåííûõ èñïûòàíèé è âûïîëíåíåíèÿ îïòèìèçèðóþùèõ ïðåîáðàçîâà-
íèé íà óðîâíå èñõîäíîãî êîäà ïîëó÷àåòñÿ ðåçóëüòèðóþùàÿ ïðîãðàììà, îöåíêà
ïðîèçâîäèòåëüíîñòè êîòîðîé ìîæåò äàâàòü îùóòèìî ëó÷øèå ðåçóëüòàòû ïî ñðàâ-
íåíèþ ñî ñòàòè÷åñêèì àíàëèçîì èñõîäíîãî êîäà.
Êîíå÷íî, ïîëíîñòüþ àâòîìàòèçèðîâàòü ïðîöåññ íå âîçìîæíî, ýòî
îáúÿñíÿåòñÿ íåñêîëüêèìè ïðè÷èíàìè. Âî-ïåðâûõ, âñå âàðèàíòû îïòèìèçèðóåìîé
ïðèêëàäíîé ïðîãðàììû çàäàþòñÿ ðàçðàáîò÷èêàìè, ïîñêîëüêó îíè èìåþò îïûò
â îáëàñòè ðåøàåìîé çàäà÷è è çíàþò, êàêèå ìîäèôèêàöèè ïðîãðàììû ìîãóò ñó-
ùåñòâåííî ïîâëèÿòü íà ïðîèçâîäèòåëüíîñòü. Âî-âòîðûõ, òîëüêî ðàçðàáîò÷èê ìî-
æåò ïðàâèëüíî îöåíèòü ïðîèçâîäèòåëüíîñòü è ýôôåêòèâíîñòü ïðèêëàäíîé ïðî-
ãðàììû, ïîñêîëüêó ÷àñòî çíà÷èìûìè ÿâëÿþòñÿ íå òîëüêî âðåìåííûå çàòðàòû íà
âûïîëíåíèå, à è êà÷åñòâî ïîëó÷àåìîãî ðåçóëüòàòà âû÷èñëåíèé.
Ñëåäîâàòåëüíî, ãëàâíàÿ çàäà÷à ëþáîé ñèñòåìû àâòîòþíèíãà çàêëþ÷àåòñÿ
â ìèíèìèçàöèè âçàèìîäåéñòâèÿ ñ ðàçðàáîò÷èêîì íà ýòàïå îïòèìèçàöèè ïðèêëàä-
íîé ïðîãðàììû, à òàêæå â ñîêðàùåíèè âðåìåíè ðàçðàáîòêè ýòîé ïðîãðàììû ïðè
äîñòèæåíèè äîñòàòî÷íîãî óðîâíÿ ïðîèçâîäèòåëüíîñòè ðåçóëüòèðóþùåãî êîäà.
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ïðåäëàãàåìàÿ â íàñòîÿùåé ðàáîòå ñèñòåìà àâòîòþíèíãà â ïîëíîé ìåðå ðåøàåò
ýòó çàäà÷ó çà ñ÷åò èíêàïñóëÿöèè ýêñïåðòíûõ çíàíèé ðàçðàáîò÷èêà â èñõîäíîì
êîäå ïðîãðàììû â âèäå ñïåöèàëüíûõ ìåòàäàííûõ. Òàêîé ïîäõîä ïîçâîëÿåò àâòî-
ìàòè÷åñêè ãåíåðèðîâàòü ïðîãðàììó-àâòîòþíåð, ñîêðàùàåò çàòðà÷åííîå íà ýêñïå-
ðèìåíò âðåìÿ çà ñ÷åò ìèíèìèçàöèè êîëè÷åñòâà èñïûòóåìûõ âàðèàöèé èñõîäíîãî
êîäà è òðåáóåò ìèíèìàëüíûõ èçìåíåíèé èñõîäíîãî êîäà ïðîãðàììû. Ðàçðàáîò-
÷èê äîëæåí äîïîëíèòåëüíî çàäàòü ìåòðèêó ýôôåêòèâíîñòè ïîëó÷åííîãî êîäà.
Ëþáîé ìåõàíèçì àâòîòþíèíãà âûïîëíÿåò çàäà÷ó àäàïòàöèè îïòèìèçèðóåìî-
ãî ïðîãðàììíîãî îáåñïå÷åíèÿ (ÏÎ) ê óñëîâèÿì åãî âûïîëíåíèÿ, êîòîðûå ìîæíî
ðàçäåëèòü íà ÷åòûðå ãðóïïû:
� îñîáåííîñòè âõîäíûõ äàííûõ, íàïðèìåð, èõ ðàçìåð;
� ñâîéñòâà àðõèòåêòóðû ïðîöåññîðîâ, ðàçìåð êýøåé è ò.ï.;
� óñëîâèÿ âû÷èñëèòåëüíîé ñðåäû, íàïðèìåð, íàëè÷èå äðóãèõ çàäà÷, âûïîë-
íÿåìûõ îäíîâðåìåííî ñ îïòèìèçèðóåìûì ÏÎ;
� ñâîéñòâà óñòàíîâëåííîãî â îïåðàöèîííîé ñèñòåìå ÏÎ (èñïîëüçóåìûå áèá-
ëèîòåêè, îïòèìèçàöèÿ, âûïîëíÿåìàÿ êîìïèëÿòîðîì è ò.ï.).
 äàííîé ðàáîòå íå ðàññìàòðèâàåòñÿ çàäà÷à àäàïòàöèè ÏÎ ê äèíàìè÷åñêè
èçìåíÿåìûì õàðàêòåðèñòèêàì âû÷èñëèòåëüíîé ñðåäû. Ñâîéñòâà äîñòóïíûõ ïðî-
ãðàììå ðåñóðñîâ (êîëè÷åñòâî ïðîöåññîðîâ, òàêòîâàÿ ÷àñòîòà, ñêîðîñòü äîñòóïà
ê îïåðàòèâíîé ïàìÿòè è ò.ï.) ñ÷èòàþòñÿ íåèçìåííûìè êàê äëÿ ýòàïà îïòèìèçà-
öèè, òàê è äëÿ ïîñëåäóþùåãî âûïîëíåíèÿ ïðîãðàììû. Âî âðåìÿ îïòèìèçàöèè
îñóùåñòâëÿåòñÿ íàáëþäåíèå çà ïðîèçâîäèòåëüíîñòüþ ÏÎ â çàâèñèìîñòè îò åãî
êîíôèãóðèðóåìûõ ïàðàìåòðîâ. Â ðåçóëüòàòå âûáèðàåòñÿ íàèëó÷øàÿ êîíôèãóðà-
öèÿ, êîòîðàÿ èñïîëüçóåòñÿ äî òåõ ïîð, ïîêà íå èçìåíÿòñÿ õàðàêòåðèñòèêè
âû÷èñëèòåëüíîé ñðåäû (â òàêîì ñëó÷àå ïðèäåòñÿ çàíîâî ïðîâåñòè îïòèìèçàöèþ).
Äëÿ îïòèìèçàöèè ÏÎ ñ ó÷åòîì èçìåíÿåìûõ â ðåàëüíîì âðåìåíè óñëîâèé
îáû÷íî âûäåëÿþò êëþ÷åâûå õàðàêòåðèñòèêè ñðåäû âûïîëíåíèÿ (ÑÂ), çíà÷åíèÿ
êîòîðûõ ëåãêî îöåíèòü. Äàëåå ïðîâîäèòñÿ àíàëèç ïðîèçâîäèòåëüíîñòè ÏÎ â çà-
âèñèìîñòè îò åãî êîíôèãóðàöèè ïðè ðàçëè÷íûõ ñîñòîÿíèÿõ ÑÂ. Ñèñòåìà óïðàâ-
ëåíèÿ, êîòîðîé ìîæåò áûòü àâòîòþíåð, èñõîäÿ èç ïîëó÷åííûõ ðåçóëüòàòîâ, âûáè-
ðàåò íàèëó÷øóþ êîíôèãóðàöèþ äëÿ òåêóùåãî ñîñòîÿíèÿ ÑÂ âî âðåìÿ âûïîëíå-
íèÿ ïðèêëàäíîé ïðîãðàììû.
Ãëàâíîå ïðåèìóùåñòâî ðàññìàòðèâàåìîãî ïîäõîäà — ýòî àäàïòàöèÿ ÏÎ ê íå-
ÿâíûì îñîáåííîñòÿì óñëîâèé âûïîëíåíèÿ. Ýòîò ïîäõîä ïîçâîëÿåò àáñòðàãèðîâàòü-
ñÿ îò êîíêðåòíûõ õàðàêòåðèñòèê Ñ è äîñòàòî÷íî ëåãêî ïîäáèðàòü îïòèìàëüíûé
âàðèàíò ÏÎ äëÿ äàííûõ óñëîâèé. Èìåííî âñëåäñòâèå ýòîãî ñâîéñòâà ýìïèðè÷åñêàÿ
àäàïòàöèÿ, íåñìîòðÿ íà áîëüøóþ ñëîæíîñòü àäàïòàöèè ÏÎ ê äèíàìè÷åñêè-èçìåíÿ-
åìûì óñëîâèÿì, ñòàëà äîìèíèðóþùåé ìåòîäîëîãèåé àâòîòþíèíãà.
Íà ðèñ. 1 ïðåäñòàâëåíà îáùàÿ ñõåìà èòåðàòèâíîãî ïðîöåññà àâòîòþíèíãà, âû-
ïîëíÿåìîãî ñèñòåìîé TuningGenie.
Âíà÷àëå èçâëåêàåòñÿ è àíàëè-
çèðóåòñÿ ìåòàèíôîðìàöèÿ èñõîä-
íîãî êîäà, â ðåçóëüòàòå ôîðìèðó-
åòñÿ ìíîæåñòâî êîíôèãóðàöèé
îïòèìèçèðóåìîé ïðîãðàììû, êî-
òîðîå ïðåäñòàâëÿåò ñîâîêóïíîñòü
õàðàêòåðèñòèê âû÷èñëèòåëüíîãî
ìåòîäà, âëèÿþùèõ íà ïðîèçâîäè-
òåëüíîñòü è/èëè òî÷íîñòü âû÷èñ-
ëåíèé (íàïðèìåð, çåðíèñòîñòü ïà-
ðàëëåëèçìà). Îáîçíà÷èì ýòî ìíî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 163
Èñõîäíûé êîä
Îïòèìàëüíàÿ
ïðîãðàììàÈçâëå÷åíèå
ýêñïåðòíûõ äàííûõ
Ìíîæåñòâî
êîíôèãóðàöèé
Àíàëèç
ïðîèçâîäèòåëüíîñòè
Îöåíêà
ýôôåêòèâíîñòè
Âûïîëíåíèå
Ïðåîáðàçîâàíèå
ïðîãðàììû
Êîíôèãóðàöèÿ
Íîâàÿ
ïðîãðàììà
Ðèñ. 1
æåñòâî C. Ïîèñê íàèáîëåå ýôôåêòèâíîé âàðèàöèè âûïîëíÿåòñÿ â ïðåäåëàõ ýòîãî
ìíîæåñòâà. Êàæäàÿ êîíôèãóðàöèÿ çàäàåò óíèêàëüíóþ òðàíñôîðìàöèþ êîäà, â ðå-
çóëüòàòå êîòîðîé ãåíåðèðóåòñÿ íîâûé âàðèàíò ïðîãðàììû. Äàëåå âûïîëíÿåòñÿ
ýìïèðè÷åñêàÿ îöåíêà ýôôåêòèâíîñòè. Ðåçóëüòàò ïåðåäàåòñÿ àâòîòüþíåðó, êîòî-
ðûé àññîöèèðóåò åãî ñ òåêóùåé êîíôèãóðàöèåé, íà ýòîì èòåðàöèÿ òüþíèíãà çà-
êàí÷èâàåòñÿ. Ìíîæåñòâî êîíôèãóðàöèé, äëÿ êîòîðûõ áûëà ïðîâåäåíà ýìïèðè-
÷åñêàÿ îöåíêà, îáîçíà÷èì C Cexp � . Ïî îêîí÷àíèè âñåõ èòåðàöèé òüþíèíãà (èõ
êîëè÷åñòâî â îáùåì ñëó÷àå ðàâíî ìîùíîñòè | |C ìíîæåñòâà êîíôèãóðàöèé)
TuningGenie âûáèðàåò îïòèìàëüíóþ êîíôèãóðàöèþ ñðåäè ýëåìåíòîâ Cexp è ãåíå-
ðèðóåò ïî íåé òîò âàðèàíò èñõîäíîé ïðîãðàììû, êîòîðûé äàëåå áóäåò
âûïîëíÿòüñÿ â öåëåâîé ÑÂ.
Êàê óæå îòìå÷àëîñü, çàòðà÷åííîå íà àâòîòþíèíã âðåìÿ ïðÿìî ïðîïîðöèî-
íàëüíî ìîùíîñòè ìíîæåñòâà | |Cexp . Èíîãäà äëÿ ïðàâèëüíîé îöåíêè ïðîèçâîäè-
òåëüíîñòè îïòèìèçèðóåìîé ïðîãðàììû íåîáõîäèìî äëÿ êàæäîé èòåðàöèè òþ-
íèíãà ïîëíîñòüþ âûïîëíèòü ïîñëåäîâàòåëüíîñòü âû÷èñëåíèé, ïðîèçâîäèìûõ
ïðîãðàììîé, ÷òî çíà÷èòåëüíî óâåëè÷èâàåò âðåìåííûå çàòðàòû.  òàêîì ñëó÷àå
ðàöèîíàëüíî ââåäåíèå äîïîëíèòåëüíîãî âðåìåííîãî îãðàíè÷åíèÿ.  ñëó÷àå, êîã-
äà ìíîæåñòâî C ÷åðåñ÷óð âåëèêî, âîçìîæíî èñïîëüçîâàíèå îïòèìèçàöèîííûõ
ïîèñêîâûõ àëãîðèòìîâ äëÿ âûáîðà ñëåäóþùåé èñïûòóåìîé êîíôèãóðàöèè [11].
Îáà ïîäõîäà ñóùåñòâåííî óìåíüøàþò ìîùíîñòü | |Cexp , íî íå ãàðàíòèðóþò
íàõîæäåíèå ãëîáàëüíîãî ìàêñèìóìà äëÿ ìíîæåñòâà C.
 êà÷åñòâå àëüòåðíàòèâíîãî ïîäõîäà ê óìåíüøåíèþ âðåìåíè âûïîëíåíèÿ
àâòîòþíèíãà ìîæíî ðàññìîòðåòü íàïèñàíèå íåáîëüøîé è, ñëåäîâàòåëüíî, áûñ-
òðîé òåñòîâîé çàäà÷è, ðåçóëüòàòû âûïîëíåíèÿ êîòîðûé çàäàäóò áîëåå óçêîå èñ-
õîäíîå ìíîæåñòâî êîíôèãóðàöèé C. Ïîäîáíîå ðåøåíèå äëÿ îïòèìèçàöèè âû÷èñ-
ëåíèé, âûïîëíÿåìûõ íà ãðàôè÷åñêîì óñêîðèòåëå, ðàññìîòðåíî â [12]. Äàëåå
ïðåäëîæåí èíñòðóìåíòàðèé, ïîçâîëÿþùèé èíòåãðèðîâàòü âûïîëíåíèå òàêîé òåñ-
òîâîé çàäà÷è â ïðîöåññ àâòîòþíèíãà. Îòìåòèì ÷òî, íåñìîòðÿ íà òî, ÷òî ýòà êîí-
öåïöèÿ íå èìååò íåäîñòàòêîâ äâóõ ïðåäûäóùèõ ïîäõîäîâ, òàêîå ðåøåíèå òðåáó-
åò äîïîëíèòåëüíûõ ðåñóðñîâ è ñóùåñòâåííîé ìîäèôèêàöèè èñõîäíîãî êîäà
îïòèìèçèðóåìîé ïðîãðàììû.
ÐÀÑØÈÐÅÍÍÀß ÌÎÄÅËÜ PRAM
Äëÿ áîëåå äåòàëüíîãî ôîðìàëüíîãî îïèñàíèÿ âñåãî ïðîöåññà îïòèìèçàöèè, âû-
ïîëíÿåìîãî àâòîòþíåðîì (ñì. ðèñ. 1), âîçüìåì çà îñíîâó êëàññè÷åñêóþ
àáñòðàêòíóþ ìîäåëü PRAM [13] è äîïîëíèì åå ñëåäóþùèìè îãðàíè÷åíèÿìè:
� ïðåäïîëîæèì, ÷òî âû÷èñëåíèÿ ïðîâîäÿòñÿ íà ïàðàëëåëüíîé ñèñòåìå, ãäå
åäèíèöåé îáîðóäîâàíèÿ âû÷èñëèòåëÿ ÿâëÿåòñÿ «ïðîöåññîð» (ñîîòâåòñòâóåò ïîíÿ-
òèþ ÿäðà â ñîâðåìåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ), ÷òî êîëè÷åñòâî ïðîöåññî-
ðîâ íå îãðàíè÷åíî, íî ôèêñèðîâàíî â êàæäîì êîíêðåòíîì ñëó÷àå (îáîçíà÷èì
÷èñëîì N ), à òàêæå, ÷òî âñå ïðîöåññîðû îäíîðîäíû;
� ðàçìåð ëîêàëüíîé ïàìÿòè (ðåãèñòðîâ) êàæäîãî ïðîöåññîðà îãðàíè÷åí ÷èñ-
ëîì M loc, äàííûå, íå ïîìåùàþùèåñÿ â ëîêàëüíîé ïàìÿòè, õðàíÿòñÿ â îáùåé ïà-
ìÿòè M shar , âðåìåíà äîñòóïà ê ëîêàëüíîé Tloc è îáùåé ïàìÿòè Tshar ðàçëè÷íû,
ïðè÷åì T Tloc shar�� ;
� îäíîâðåìåííûé äîñòóï ê îáùåé ïàìÿòè ðåãóëèðóåòñÿ ñòðàòåãèåé
Concurrent Read Exclusive Write (CREW), äîïóñêàåòñÿ ïàðàëëåëüíîå ÷òåíèå èç
îäíîé ÿ÷åéêè ïàìÿòè, íî òîëüêî îäèí ïðîöåññîð ìîæåò çàïèñûâàòü äàííûå
â êîíêðåòíóþ ÿ÷åéêó ïàìÿòè â åäèíèöó âðåìåíè, îñòàëüíûå ïðîöåññîðû â ýòî
âðåìÿ íàõîäÿòñÿ â ñîñòîÿíèè îæèäàíèÿ.
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Îáîçíà÷èì TN ew
îáùåå âðåìÿ, çàòðà÷åííîå ïðîöåññîðàìè íà îæèäàíèå ðàç-
áëîêèðîâêè îáùåé ïàìÿòè äëÿ çàïèñè.
Äàëåå òàêóþ ðàñøèðåííóþ ìîäåëü áóäåì íàçûâàòü PRAM *.
Èíñòðóêöèè ýòîé ìîäåëè âûïîëíÿþòñÿ â òðè ýòàïà:
1) ÷òåíèå äàííûõ èç îáùåé ïàìÿòè, åñëè îíè íå íàõîäÿòñÿ â ðåãèñòðàõ ïðî-
öåññîðà (è åñëè îíè íóæíû äëÿ âûïîëíåíèÿ èíñòðóêöèè);
2) ëîêàëüíûå âû÷èñëåíèÿ;
3) çàïèñü äàííûõ â îáùóþ ïàìÿòü (åñëè òðåáóåòñÿ).
Âðåìÿ, çàòðà÷èâàåìîå i-ì ïðîöåññîðîì íà äîñòóï ê ïàìÿòè (ýòàïû 1 è 3 ïðè
óñëîâèè îòñóòñòâèÿ áëîêèðîâîê âî âðåìÿ çàïèñè), âû÷èñëÿåòñÿ ñëåäóþùèì îáðà-
çîì: T T Ti i imem loc shar
� � . Êàê âèäíî èç ôîðìóëû, îíî ñîñòîèò èç çàòðàò íà äîñ-
òóï ê ëîêàëüíîé è ãëîáàëüíîé ïàìÿòè.
Ââåäåì ïîíÿòèå ñèíõðîíèçàöèè ëîêàëüíûõ âû÷èñëåíèé è ñîîòâåòñòâóþùèõ
âðåìåííûõ çàòðàò. Åñëè âûïîëíÿåòñÿ êðèòè÷åñêàÿ ñåêöèÿ, òî âñå ïðîöåññîðû,
êðîìå àêòèâíîãî, íàõîäÿòñÿ â ðåæèìå îæèäàíèÿ è âûïîëíåíèå òàêèõ ñåêöèé àíà-
ëîãè÷íî ïîñëåäîâàòåëüíîé âåðñèè ïðîãðàììû â ìîäåëè RAM. Îáîçíà÷èì TN seq
âðåìåííûå çàòðàòû íà òàêèå êðèòè÷åñêèå ñåêöèè è TN par
— âðåìÿ «÷èñòûõ» ïà-
ðàëëåëüíûõ âû÷èñëåíèé.
Ââåäåííûå îãðàíè÷åíèÿ ïîçâîëÿþò áîëåå òî÷íî îõàðàêòåðèçîâàòü àðõèòåê-
òóðó ñðåäû âû÷èñëåíèÿ, à òàêæå âûïîëíÿåìûõ àâòîòþíåðîì îïòèìèçèðóþùèõ
ïðåîáðàçîâàíèé.
Îáùåå âðåìÿ âû÷èñëåíèé ïàðàëëåëüíîé ïðîãðàììû îïèñûâàåò ôîðìóëà
T T T TN N N N� � �
par seq ew
.
Çàäà÷à àâòîòþíåðà çàêëþ÷àåòñÿ â ìèíèìèçàöèè âðåìåííûõ çàòðàò íà ñèí-
õðîíèçàöèþ T TN Nseq ew
� , à òàêæå ñîêðàùåíèè âðåìåíè TN par
.
Âðåìåííûå ïîòåðè íà ñèíõðîíèçàöèþ ìîæíî ñîêðàòèòü çà ñ÷åò îïòèìàëüíîãî
ðàñïðåäåëåíèÿ âû÷èñëèòåëüíûõ çàäà÷ ìåæäó ïðîöåññîðàìè, íàïðèìåð, èñïîëüçóÿ
òðàäèöèîííóþ ñõåìó êðóïíîáëî÷íîãî ðàñïàðàëëåëèâàíèÿ, ïðè êîòîðîé âõîäÿùèå
äàííûå ðàñïðåäåëÿþòñÿ òàêèì îáðàçîì, ÷òîáû êàæäûé ïðîöåññîð âûïîëíÿë íåçà-
âèñèìî ìàêñèìàëüíî êðóïíûé áëîê âû÷èñëåíèé è ïðè ýòîì âñå ïðîöåññîðû áûëè
áû ðàâíîìåðíî çàãðóæåííûìè. Âîçìîæíà òàêæå ñòðóêòóðíàÿ ìîäèôèêàöèÿ âûïîë-
íÿåìûõ ïðîãðàììîé âû÷èñëåíèé. Äàëåå ïðèâåäåí ïðèìåð òàêîãî ïðåîáðàçîâàíèÿ
äëÿ ñïåöèôè÷åñêîãî êëàññà èòåðàòèâíûõ àëãîðèòìîâ ñ áàðüåðíîé ñèíõðîíèçàöè-
åé â êîíöå êàæäîé èòåðàöèè. Ýòè ïðåîáðàçîâàíèÿ íàïðàâëåíû íà óëó÷øåíèå
ïðîãðàììíîé ðåàëèçàöèè òàêîé ïàðàäèãìû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ, êàê
ïàðàëëåëèçì ïî äàííûì (ãåîìåòðè÷åñêèé ïàðàëëåëèçì) [14].
Äëÿ ñîêðàùåíèÿ âðåìåíè ïàðàëëåëüíîãî âûïîëíåíèÿ TN par
ïðåäñòàâëåííàÿ
â ðàáîòå ñèñòåìà àâòîòþíèíãà îñóùåñòâëÿåò ïðåîáðàçîâàíèÿ, íàïðàâëåííûå íà
îïòèìèçàöèþ èñïîëüçîâàíèÿ ëîêàëüíîé ïàìÿòè, ò.å., âû÷èñëåíèÿ ðàñïðåäåëÿþò-
ñÿ ìåæäó ïðîöåññîðàìè òàê, ÷òîáû îíè ïîìåùàëèñü â ëîêàëüíóþ ïàìÿòü, äîñòóï
ê êîòîðîé íà ïîðÿäîê áûñòðåå, ÷åì ÷òåíèå/çàïèñü â ãëîáàëüíóþ ïàìÿòü. Òàêèì
îáðàçîì, äëÿ êàæäîãî ïðîöåññîðà Tishar
� 0. Ñèñòåìà TuningGenie ïîçâîëÿåò ëåã-
êî ïðîåêòèðîâàòü ýôôåêòèâíî ðàáîòàþùèå ñ êýøåì àëãîðèòìû áåç ÿâíîãî èñ-
ïîëüçîâàíèÿ èíôîðìàöèè î åãî àðõèòåêòóðå. Íàïðèìåð, ðàññìîòðåííàÿ â [15] ìî-
äèôèêàöèÿ àëãîðèòìà ñîðòèðîâêè QuickSort èìååò ïàðàìåòð, âëèÿþùèé íà ýô-
ôåêòèâíîñòü èñïîëüçîâàíèÿ êýøà è, ñëåäîâàòåëüíî, êëàññèôèöèðóåòñÿ êàê
îñâåäîìëåííûé î êýøå àëãîðèòì (Cache-aware Algorithm [16]), íî â òî æå âðåìÿ
çíà÷åíèå ýòîãî ïàðàìåòðà ïðèíàäëåæèò ïðåäìåòíîé îáëàñòè çàäà÷è, çà ñ÷åò ÷åãî
âåñü àëãîðèòì àáñòðàãèðîâàí îò ñâîéñòâ àðõèòåêòóðû ñðåäû âûïîëíåíèÿ.
Îáà ïðåäëîæåííûõ ïîäõîäà ê îïòèìèçàöèè ïàðàëëåëüíûõ àëãîðèòìîâ ñâî-
äÿòñÿ ê ïðîòèâîïîëîæíûì ïî ñâîåìó õàðàêòåðó ñòðàòåãèÿì ðàñïðåäåëåíèÿ âû-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 165
÷èñëåíèé, ýôôåêòèâíîñòü êîòîðûõ íàïðÿìóþ çàâèñèò îò òàêèõ õàðàêòåðèñòèê
âû÷èñëèòåëüíîé ñðåäû, êàê îáúåì è ñêîðîñòü äîñòóïà ê îáùåé ïàìÿòè è êýøó
ïðîöåññîðà. Î÷åâèäíî, ÷òî îïòèìàëüíûå ñòðàòåãèè äëÿ ðàçëè÷íûõ àðõèòåêòóð
îòëè÷àþòñÿ, è ìîùíîñòü ïðåäëàãàåìîé ìåòîäîëîãèè àâòîòüþíèíãà çàêëþ÷àåòñÿ
â òîì, ÷òî ïîèñê ñòðàòåãèè âûïîëíÿåòñÿ â àâòîìàòè÷åñêîì ðåæèìå.
ÀÂÒÎÒÞÍÅÐ ÊÀÊ ÄÈÑÊÐÅÒÍÀß ÄÈÍÀÌÈ×ÅÑÊÀß ÑÈÑÒÅÌÀ
 äàííîé ðàáîòå ââîäèòñÿ ðàñøèðåííîå ïîíÿòèå äèñêðåòíîé äèíàìè÷åñêîé
ñèñòåìû [14] êàê ñðåäñòâà äëÿ ïîñòðîåíèÿ ôîðìàëüíîé ìîäåëè àâòîòþíèíãà.
Ñóòü ñîñòîèò â òîì, ÷òî ïðè ìîäåëèðîâàíèè ïàðàëëåëüíîãî âûïîëíåíèÿ ïðè-
êëàäíûõ çàäà÷ ó÷èòûâàþòñÿ äâå ãëàâíûå õàðàêòåðèñòèêè àëãîðèòìà: ïðîèçâî-
äèòåëüíîñòü è êà÷åñòâî [17, 18]. Ïåðâàÿ ÿâëÿåòñÿ òðàäèöèîííûì ïðèîðèòåòîì
ïðè ðàçðàáîòêå ïàðàëëåëüíûõ àëãîðèòìîâ, à âòîðàÿ — â ðàçëè÷íûõ ïðåäìåò-
íûõ îáëàñòÿõ ïðåäñòàâëÿåò ðàçíûå àñïåêòû âû÷èñëåíèé (íàïðèìåð, â âû÷èñëè-
òåëüíûõ çàäà÷àõ ýòî òî÷íîñòü âû÷èñëåíèé, â àëãîðèòìàõ ñîõðàíåíèÿ äàí-
íûõ — ñòåïåíü ñæàòèÿ äàííûõ). Ïðàêòè÷åñêè âñåãäà îêàçûâàåòñÿ, ÷òî îáåñïå-
÷åíèå êà÷åñòâà ïðåäïîëàãàåò âûïîëíåíèå äîïîëíèòåëüíûõ âû÷èñëåíèé, ÷òî
âëèÿåò íà ïðîèçâîäèòåëüíîñòü. Òàêèì îáðàçîì, îäíîâðåìåííîå äîñòèæåíèå âû-
ñîêèõ ïîêàçàòåëåé ïðîèçâîäèòåëüíîñòè è êà÷åñòâà âîçìîæíî òîëüêî â ðåçóëü-
òàòå íå êîòîðîãî êîìïðîìèññà èëè îïòèìèçàöèè ïî çàäàííîìó êðèòåðèþ.
Äàëåå îãðàíè÷èìñÿ ðàññìîòðåíèåì êëàññà âû÷èñëèòåëüíûõ çàäà÷, ãäå
îñíîâíîé õàðàêòåðèñòèêîé êà÷åñòâà ÿâëÿåòñÿ òðåáîâàíèå òî÷íîñòè âû÷èñëåíèé.
Èñïîëüçóåì ïîíÿòèå -îòêëîíåíèÿ, êîòîðîå îáîçíà÷àåò âåëè÷èíó îòêëîíåíèÿ ðå-
çóëüòàòà âû÷èñëåíèé ïàðàëëåëüíîãî àëãîðèòìà îò íåêîòîðîãî «ýòàëîííîãî» çíà-
÷åíèÿ, ïîëó÷åííîãî íà PRAM *-ìàøèíå ñ îäíèì ïðîöåññîðîì.
Âûïîëíåíèå ëþáîé ïàðàëëåëüíîé ïðîãðàììû ìîæíî ñìîäåëèðîâàòü ñ èñïîëü-
çîâàíèåì òåîðèè äèñêðåòíûõ äèíàìè÷åñêèõ ñèñòåì (ÄÄÑ) [14], îïðåäåëÿåìîé òðîé-
êîé ( , , )S S d0 , ãäå S — ìíîæåñòâî, íàçûâàåìîå ïðîñòðàíñòâîì ñîñòîÿíèé; S S0
—
ìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé; d S S� � — áèíàðíîå îòíîøåíèå ïåðåõîäîâ
â ïðîñòðàíñòâå ñîñòîÿíèé. Ñèñòåìà ìîæåò ïåðåéòè èç ñîñòîÿíèÿ si â ñîñòîÿíèå s j ,
åñëè ( , )s s di j � . Ñîñòîÿíèå ïàìÿòè ñèñòåìû õàðàêòåðèçóåòñÿ îòîáðàæåíèåì
b X D: � , ãäå Õ — ìíîæåñòâî ïåðåìåííûõ ïðîãðàììû, D — îáëàñòü çíà÷åíèé.
Äàëåå ðàññìîòðèì àâòîòþíåð êàê èòåðàòèâíîå ðàñøèðåíèå ÄÄÑ äëÿ ìíîãî-
ïîòî÷íûõ ïðîãðàìì S mt , ïðåäñòàâëåííîå â [19].  îïèñàííîé ìîäåëè ÄÄÑ ïåðå-
ìåííûå S tune íå èìåþò òèïà è ïðèíèìàþò çíà÷åíèÿ â íåêîòîðîì óíèâåðñàëüíîì
ìíîæåñòâå D èç íîðìèðîâàííîãî ïðîñòðàíñòâà [20].
Ðàñïðîñòðàíåííûìè ïðèìåðàìè íîðì, êîòîðûå ìîæíî èñïîëüçîâàòü â S tune,
ÿâëÿþòñÿ ñëåäóþùèå:
� åâêëèäîâà íîðìà — ýòî ÷èñëî | |x x
kk
n�
�
2
1
, íàçûâàåìîå äëèíîé èëè íîð-
ìîé n-ìåðíîãî âåêòîðà x x xn� ( , , )1 � â ïðîñòðàíñòâå R n . Ðàññòîÿíèå ìåæäó âåê-
òîðàìè x x xn� ( , , )1 � è y y yn� ( , , )1 � äåéñòâèòåëüíîãî ïðîñòðàíñòâà R n îïðå-
äåëÿåòñÿ ïî ôîðìóëå | | ( )x y x yk kk
n� � �
�
2
1
;
� ÷åáûøåâñêàÿ (ðàâíîìåðíàÿ) íîðìà [20] | | | | max | ( )|[ , ] [ , ]x x ta b t a b� � , ãäå x —
íåïðåðûâíàÿ íà îòðåçêå [ , ]a b ôóíêöèÿ (ýòà íîðìà èñïîëüçîâàíà â [15] äëÿ îöåíêè
ðàñõîæäåíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ èòåðàöèé äëÿ çàäà÷è ïðîãíîçèðîâàíèÿ
ìåòåîðîëîãè÷åñêèõ óñëîâèé).
Ôîðìàëèçóåì ïîíÿòèå -îòêëîíåíèÿ êàê õàðàêòåðèñòèêó êà÷åñòâà ðåçóëüòà-
òîâ âû÷èñëåíèé. Ïóñòü âûäåëåí âåêòîð x V� ðåçóëüòèðóþùèõ ïåðåìåííûõ ïðî-
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
ãðàììû. Ôèíàëüíîå ñîñòîÿíèå ïàìÿòè ïðîãðàìì P è P * îáîçíà÷èì b x( ) è b x* ( )
ñîîòâåòñòâåííî. Ðàññòîÿíèå ìåæäó çíà÷åíèÿìè ðåçóëüòèðóþùèõ ïåðåìåííûìè
ýòèõ ïðîãðàìì îáîçíà÷èì r b x b x( ( ), ( ))* . Ïóñòü èìååòñÿ èñõîäíàÿ ïðîãðàììà P
è ïðåîáðàçîâàííàÿ àâòîòþíåðîì åå âåðñèÿ P * . Ñ÷èòàåì, ÷òî ðåçóëüòàò âû÷èñëå-
íèé ïðîãðàììû P * îòêëîíÿåòñÿ íà âåëè÷èíó , åñëè ïðîãðàììû P è P * ñ îäèíà-
êîâûìè íà÷àëüíûìè äàííûìè b0 îäíîâðåìåííî ïðèõîäÿò (èëè íå ïðèõîäÿò)
â ôèíàëüíûå ñîñòîÿíèÿ ñîîòâåòñòâåííî s bf � ( , , )� � è s bf
* *( , , )� � � , äëÿ êîòîðûõ
r b x b x( ( ), ( ))* � (ïðè ïóñòîé îñòàòî÷íîé ïðîãðàììå � è ïóñòîì çàêëþ÷èòåëüíîì
îòíîøåíèè ïåðåõîäîâ �).
Ðàññìàòðèâàåìàÿ ñèñòåìà àâòîòþíèíãà — ýòî òðîéêà � �PRAM ÎÔ OUT*, ( ),P ,
ãäå P — èñõîäíûé êîä ïðîãðàììû; PRAM * — ðàññìîòðåííàÿ ðàíåå àáñòðàêòíàÿ
ìîäåëü âû÷èñëèòåëÿ; OUT — «ýòàëîííûé» ðåçóëüòàò âû÷èñëåíèÿ èñõîäíîãî âà-
ðèàíòà ïàðàëëåëüíîé ïðîãðàììû íà îäíîì ïðîöåññîðå, èñïîëüçóåìûé äëÿ àíàëè-
çà òî÷íîñòè îïòèìèçèðóåìîé ïðîãðàììû; ÎÔ( ) * *P T kN� — ôóíêöèÿ ýìïè-
ðè÷åñêîé ÷èñëîâîé îöåíêè ïðîäóêòèâíîñòè âûïîëíåíèÿ ïðîãðàììû, ó÷èòûâàþ-
ùàÿ òî÷íîñòü ïîëó÷åííûõ ðåçóëüòàòîâ âû÷èñëåíèé.
Çàäà÷à òþíèíãà çàêëþ÷àåòñÿ â ìèíèìèçàöèè çíà÷åíèÿ ÎÔ. Êîýôôèöèåíò k
èñïîëüçóåòñÿ äëÿ çàäà÷, êîòîðûå èìåþò ÷åòêîå òðåáîâàíèå ê òî÷íîñòè ïîëó÷åííûõ
ðåçóëüòàòîâ è âðåìåíè âûïîëíåíèÿ âû÷èñëåíèé (çàäà÷è ðåàëüíîãî âðåìåíè).
Îáîçíà÷èì max ìàêñèìàëüíî äîïóñòèìîå -îòêëîíåíèå. Äëÿ òîãî ÷òîáû èñ-
êëþ÷èòü áûñòðûé, íî íåòî÷íûé âàðèàíò îïòèìèçèðóåìîé ïðîãðàììû, ïðèìåì
k � 1ïðè �[ , ]max0 è k �1000000 (äîñòàòî÷íî áîëüøîå ÷èñëî) ïðè �� max .
Êàæäàÿ èòåðàöèÿ òþíèíãà êà÷åñòâåííî îöåíèâàåò ñãåíåðèðîâàííûé âàðèàíò
ïðîãðàììû
� � �P C Pi i, ,* ÎÔ ,
ãäå P * — íîâûé âàðèàíò èñõîäíîé ïðîãðàììû, ÎÔ i — îöåíêà ïðîäóêòèâíîñ-
òè âûïîëíåíèÿ ïðîãðàììû èç i-é èòåðàöèè.
Ïðåîáðàçîâàíèå, ïðîâåäåííîå âî âðåìÿ èòåðàöèè àâòîòþíåðà, áóäåì ñ÷èòàòü
ðåçóëüòàòèâíûì, åñëè ÎÔ ÎÔ opt( ) ( )*P P� , ò.å., ñòîèìîñòíàÿ îöåíêà èíòåðïðåòà-
öèè ïðîãðàììû ñòðîãî óìåíüøèëàñü. Åñëè âûïîëíåííîå â ïðåäåëàõ èòåðàöèè
òþíèíãà ïðåîáðàçîâàíèå îêàçàëîñü ðåçóëüòàòèâíûì, ïîëó÷åííûé âàðèàíò èñõîä-
íîé ïðîãðàììû ñ÷èòàåòñÿ óëó÷øåííûì è ïðèíèìàåòñÿ â îáùåì ñëó÷àå êàê èñ-
õîäíûé äëÿ ñëåäóþùåé èòåðàöèè àâòîòþíåðà.
 ïðîñòåéøåì ñëó÷àå àâòîòþíåð îñóùåñòâëÿåò èòåðàöèþ ïî âñåìó ìíîæåñ-
òâó C.  áîëåå ñëîæíûõ ñëó÷àÿõ ðåøåíèå î ïðîäîëæåíèè è/èëè îêîí÷àíèè ïðî-
öåññà òþíèíãà ïðèíèìàåò ýêñïåðò-ðàçðàáîò÷èê. Ïîñëå îêîí÷àíèÿ âñåõ èòåðàöèé
òþíèíãà ïîëó÷åííàÿ ïðîãðàììà P opt ñ÷èòàåòñÿ îïòèìàëüíîé è ñîõðàíÿåòñÿ äëÿ
äàëüíåéøåãî âûïîëíåíèÿ.
ÎÏÒÈÌÈÇÀÖÈß ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ Â ÌÎÄÅËÈ ÀÂÒÎÒÞÍÈÍÃÀ
Áîëüøèíñòâî ïàðàëëåëüíûõ àëãîðèòìîâ, îðèåíòèðîâàííûõ íà ãåîìåòðè÷åñêèé
ïàðàëëåëèçì [2], èìåþò èòåðàòèâíóþ ñõåìó îðãàíèçàöèé âû÷èñëåíèé. Íà
ðèñ. 2 ïîêàçàíà òàêàÿ äèàãðàììà âû÷èñëåíèé, ãäå tsplit , tparallel è tmerge — âðå-
ìÿ, çàòðà÷åííîå íà äåêîìïîçèöèþ äàííûõ, âûïîëíåíèå ïàðàëëåëüíîé ñåêöèè è
îáðàáîòêó ðåçóëüòàòîâ âû÷èñëåíèé ñîîòâåòñòâåííî. Âî ìíîãèõ ñëó÷àÿõ äëÿ
óñêîðåíèÿ âû÷èñëåíèé òàêèå àëãîðèòìû ïîçâîëÿþò âûïîëíÿòü «ñêëåéêó» íå-
ñêîëüêèõ èòåðàöèé öèêëà â îäíó (ðèñ. 3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 167
Îáîçíà÷èì m êîëè÷åñòâî îáúåäèíåííûõ
ïàðàëëåëüíûõ ñåêöèé. Áóäåì ñ÷èòàòü, ÷òî ñõåìà
âû÷èñëåíèé, ïîçâîëÿþùàÿ âûïîëíÿòü òàêóþ
ñêëåéêó (ñì. ðèñ. 3), èìååò ñâîéñòâî àñèíõðîí-
íîãî öèêëà ñî ñòåïåíüþ ñâîáîäû m. Äëÿ ìíîãèõ
çàäà÷ òàêîå èçìåíåíèå ñòðóêòóðû âû÷èñëåíèé
ïðèâîäèò ê èçìåíåíèþ ðåçóëüòàòà âû÷èñëåíèé.
Äàëåå ýòî èçìåíåíèå áóäåì õàðàêòåðèçîâàòü
ââåäåííûì ðàíüøå ïîíÿòèåì -îòêëîíåíèÿ.
Îòìåòèì, ÷òî çàìåíà ñõåìû âû÷èñëåíèé íà àñèíõðîííûé öèêë óâåëè÷èâàåò
ïðîèçâîäèòåëüíîñòü ïàðàëëåëüíîãî àëãîðèòìà çà ñ÷åò ñîêðàùåíèÿ âðåìåíè íà äå-
êîìïîçèöèþ äàííûõ è ñèíõðîíèçàöèþ ðåçóëüòàòîâ ïðîìåæóòî÷íûõ âû÷èñëåíèé.
Ïîêàæåì ýòî ôîðìàëüíî, à òàê æå îöåíèì ãðàíèöû óñêîðåíèÿ ïîëó÷åííîãî
àëãîðèòìà S tuned .
Ïóñòü n — êîëè÷åñòâî èòåðàöèé â èñõîäíîé ïðîãðàììå. Òîãäà îáùåå âðåìÿ
âûïîëíåíèÿ èñõîäíîé ïàðàëëåëüíîé ïðîãðàììû âû÷èñëÿåòñÿ
T n t t tp � � � �( )split parallel merge .
Äîïóñòèì, ÷òî m — äåëèòåëü n, m n�[ , ]1 . Òîãäà âðåìÿ âûïîëíåíèÿ ïðîãðàììû
ñ èñïîëüçîâàíèåì àñèíõðîííîãî öèêëà îïðåäåëÿåòñÿ
T
n
m
t t n tpm � � � �( )split merge parallel .
Ïóñòü t t texchange split merge� � , òîãäà
S
T
T
t t
m
t t
p
pm
tuned
parallel exchange
exchange paral
� �
�
�
1
lel
,
lim
m n
S
t t
t
t
� ��
�
�
� �tuned
parallel exchange
parallel
exc
1
hange
parallelt
.
Ïðè m �1 èìååì íèæíþþ îöåíêó ãðàíèöû óñêîðåíèÿ
S
t t
t t
tuned
parallel exchange
parallel exchange
�
�
�
�1 .
Òàêèì îáðàçîì, ïîëó÷åííîå â ðåçóëüòàòå ïðèìåíåíèÿ àñèíõðîííîãî öèêëà
óñêîðåíèå ëåæèò â ñëåäóþùèõ ãðàíèöàõ:
S
t
t
tuned exchange
parallel
� �
�
�
�
�
�
�
�
�
1 1, .
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ðèñ. 3
tsplit tparallel tmerge tmergetparallel����
Ðèñ. 2
tsplit tparallel
tmerge
Îïèñàííàÿ îïòèìèçàöèÿ èìååò ñìûñë, êîãäà êîëè÷åñòâî èòåðàöèé n äîñòà-
òî÷íî âåëèêî, à âðåìÿ âûïîëíåíèÿ ïàðàëëåëüíîé ñåêöèè è âðåìÿ îáìåíà äàííû-
ìè — âåëè÷èíû îäíîãî ïîðÿäêà. Ëåãêî âèäåòü, ÷òî ñ óâåëè÷åíèåì ïàðàìåòðà m
çíà÷åíèå S tuned óâåëè÷èâàåòñÿ, êàê è çíà÷åíèå -îòêëîíåíèÿ äëÿ áîëüøèíñòâà
çàäà÷. Âåðõíåå çíà÷åíèå m îãðàíè÷èâàåòñÿ òîëüêî îæèäàåìîé òî÷íîñòüþ âû÷èñ-
ëåíèé è íåîáõîäèìîñòüþ ïîëó÷åíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ (íàïðèìåð, äëÿ
âèçóàëèçàöèè). Ïîýòîìó èìååì äâîéñòâåííóþ çàäà÷ó îïòèìèçàöèè ïðîèçâîäè-
òåëüíîñòè è êà÷åñòâà ïîëó÷åííîãî ðåçóëüòàòà, ýìïèðè÷åñêîå ðåøåíèå êîòîðîé
âîçëàãàåòñÿ íà ñèñòåìó TuningGenie. Äàëåå ïðåäñòàâëåíû ïðèìåðû îïòèìèçàöèè
äâóõ çàäà÷ ñ ïîìîùüþ àñèíõðîííîãî öèêëà.
ÈÍÑÒÐÓÌÅÍÒÀËÜÍÀß ÑÈÑÒÅÌÀ ÄËß ÐÅÀËÈÇÀÖÈÈ ÀÂÒÎÒÞÍÅÐÎÂ TUNINGGENIE
Ïðîãðàììíàÿ ðåàëèçàöèÿ ðàññìàòðèâàåìîé ñèñòåìû àâòîòþíèíãà îñíîâàíà íà
ñèñòåìå îáðàáîòêè òåðìîâ TermWare [9, 10]. Â TermWare ðåàëèçîâàíà êîíöåï-
öèÿ òåðìèíàëüíûõ ñèñòåì — îáúåêòíûõ ñòðóêòóð è ïðàâèë ïåðåïèñûâàíèÿ
c ÿâíûìè àêöèÿìè âçàèìîäåéñòâèÿ ñ áàçîé çíàíèé. Ñ åå ïîìîùüþ TuningGenie
èçâëåêàåò ýêñïåðòíûå çíàíèÿ èç èñõîäíîãî êîäà ïðîãðàììû è ãåíåðèðóåò íî-
âûé âàðèàíò ïðîãðàììû íà êàæäîé èòåðàöèè òþíèíãà. Ñèñòåìà TermWare
òðàíñëèðóåò èñõîäíûé êîä ïðîãðàììû â òåðì è ïðåäîñòàâëÿåò èíñòðóìåíòà-
ðèé äëÿ åãî ïðåîáðàçîâàíèÿ ñ ïîìîùüþ ïåðåïèñûâàþùèõ ïðàâèë, ÷òî ïîçâî-
ëÿåò TuningGenie âûïîëíÿòü ñòðóêòóðíûå èçìåíåíèÿ ïðîâîäèìûõ ïðîãðàììîé
âû÷èñëåíèé â äåêëàðàòèâíîì ñòèëå (áåç èçìåíåíèé èñõîäíîãî êîäà). Ïîñëåä-
íåå ñâîéñòâî êà÷åñòâåííî îòëè÷àåò TuningGenie îò ïîõîæèõ ñèñòåì, íàïðèìåð
AtuneIL [8], è îñîáåííî óäîáíî, êîãäà íóæíî îïòèìèçèðîâàòü óæå íàïèñàííóþ
è âåñüìà áîëüøóþ ïàðàëëåëüíóþ ïðîãðàììó.
Ñèñòåìà TermWare ñîäåðæèò ìîäóëü äëÿ ðàáîòû ñ JAVA è C#-êîäîì. Äëÿ
ðàáîòû ñ äðóãèìè ÿçûêàìè ïðîãðàììèðîâàíèÿ íåîáõîäèìî íàïèñàòü ïàðñåð äëÿ
òðàíñëèðîâàíèÿ èñõîäíîãî êîäà â ÿçûê TermWare è ïðèíòåð äëÿ îáðàòíîãî ïðå-
îáðàçîâàíèÿ. Â íàñòîÿùåå âðåìÿ âåðñèÿ TuningGenie ðàáîòàåò ñ ïðîãðàììàìè,
íàïèñàííûìè íà JAVA.
Íà ýòàïå «Àíàëèç» àâòîòþíåð, èñõîäÿ èç ýêñïåðòíûõ äàííûõ, ñòðîèò ìíî-
æåñòâî êîíôèãóðàöèé ïðîãðàììû, êîòîðûå àäàïòèðóþò åå ïîä öåëåâóþ ñðåäó
âûïîëíåíèÿ. Êàæäàÿ êîíôèãóðàöèÿ òðàíñëèðóåòñÿ â íàáîð ïåðåïèñûâàþùèõ
ïðàâèë, êîòîðûå âûïîëíÿþòñÿ äëÿ èñõîäíîãî òåðìà ïàðàëëåëüíîé ïðîãðàììû.
Ïîñëå ïðåîáðàçîâàíèÿ ïîëó÷åííûé òåðì òðàíñëèðóåòñÿ â êîä JAVA è êîìïèëè-
ðóåòñÿ, â ðåçóëüòàòå ÷åãî ïîëó÷àåòñÿ ãîòîâàÿ äëÿ ýìïèðè÷åñêîé îöåíêè íîâàÿ
âåðñèÿ îïòèìèçèðóåìîé ïðîãðàììû.
Ðàíåå îòìå÷àëîñü, ÷òî ýêñïåðòíûå çíàíèÿ ðàçðàáîò÷èêà ñîõðàíÿþòñÿ â èñ-
õîäíîì êîäå ïðîãðàììû â âèäå ñïåöèàëüíûõ äèðåêòèâ — ïðàãì. Ñèíòàêñè÷åñêè
ïîñëåäíèå ÿâëÿþòñÿ êîììåíòàðèÿìè, ïîýòîìó èõ äîáàâëåíèå íå ìåíÿåò ñòðóê-
òóðû âû÷èñëåíèé ïàðàëëåëüíîé ïðîãðàììû è åå èñõîäíûé êîä âñå òàêæå êîìïè-
ëèðóåòñÿ ëþáûì êîìïèëÿòîðîì ÿçûêà JAVA.
Èíñòðóìåíòàðèé TuningGenie ñîñòîèò èç òðåõ ïðàãì.
Ïåðâàÿ ïðàãìà tuneAbleParam çàäàåò îáëàñòü çíà÷åíèé ÷èñëåííîé ïåðåìåí-
íîé. Íàïðèìåð, äëÿ ïåðåìåííîé numTasks ãðàíèöû âûáîðà çíà÷åíèé [1...10]
ñ øàãîì 2 çàäàþòñÿ ñëåäóþùèì îáðàçîì:
//tuneAbleParam name=numTasks start=1 stop=10 step=2
int numTasks = 1;
Ýòó ïðàãìó ïðåæäå âñåãî ïðèìåíÿþò ê àëãîðèòìàì, èñïîëüçóþùèì ãåîìåò-
ðè÷åñêèé ïàðàëëåëèçì (ïàðàäèãìà ïðîãðàììèðîâàíèÿ «ïàðàëëåëèçì ïî äàííûì»
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 169
[14]), ïîñêîëüêó îíà ïîçâîëÿåò ëåãêî ïîäîáðàòü îïòèìàëüíóþ äåêîìïîçèöèþ îá-
ëàñòè âû÷èñëåíèé, ò.å. «çåðíèñòîñòü» àëãîðèòìà. Ñ ïîìîùüþ ýòîé ïðàãìû ìîæíî
òàêæå ïîäîáðàòü íåêîòîðîå ïîðîãîâîå çíà÷åíèå äëÿ èçìåíåíèÿ ñõåìû âû÷èñëå-
íèé ïðîãðàììû. Ïðèìåð èñïîëüçîâàíèÿ ýòîé ïðàãìû äëÿ îïòèìèçàöèè êëàññè-
÷åñêîãî àëãîðèòìà ñîðòèðîâêè QuickSort ðàññìîòðåí äàëåå.
Âòîðàÿ ïðàãìà calculatedValue èíèöèàëèçèðóåò ïåðåìåííóþ çíà÷åíèåì, êî-
òîðîå âû÷èñëÿåòñÿ â öåëåâîé ÑÂ. Ýòîò òèï ïðàãì ñîçäàí äëÿ àëãîðèòìîâ, êîòî-
ðûì íåîáõîäèìà èíôîðìàöèÿ î ÑÂ, íàïðèìåð, î ñêîðîñòè äîñòóïà ê ðàçëè÷íûì
óðîâíÿì ïàìÿòè èëè ñêîðîñòè âûïîëíåíèÿ áàçîâûõ àðèôìåòè÷åñêèõ îïåðàöèé.
Âñå çíà÷åíèÿ òàêèõ ïåðåìåííûõ âû÷èñëÿþòñÿ äî âûïîëíåíèÿ èòåðàöèé òþíèíãà
è ñîõðàíÿþòñÿ â áàçå çíàíèé TermWare. Âñëåäñòâèå òîãî, ÷òî èíôîðìàöèÿ èç
áàçû çíàíèé äîñòóïíà ïåðåïèñûâàþùèì ïðàâèëàì, ïðàãìà calculatedValue ïîçâî-
ëÿåò òàêæå çàäàòü îáëàñòü çíà÷åíèé äëÿ ïåðåìåííûõ ïðåäûäóùåé ïðàãìû
tuneAbleParam. Òàêèì îáðàçîì, ìîæíî âûïîëíèòü íåáîëüøóþ òåñòîâóþ çàäà÷ó,
ðåçóëüòàòû êîòîðîé ñóçÿò îáëàñòü ïîèñêà îïòèìàëüíîé êîíôèãóðàöèè è, ñëåäîâà-
òåëüíî, ñîêðàòÿò âðåìåííûå çàòðàòû íà àâòîòþíèíã. Ïîõîæèé ïîäõîä äëÿ âû÷èñ-
ëåíèé íà GPU ðàññìîòðåí â [12]. Ïðèìåð èñïîëüçîâàíèÿ ïðàãìû:
//calculatedValue name=hdReadSpeed method=
//"org.org.tuning.EnvironmUtils.getHDReadSpeed()"
int hdKbPerSec = 1;
Òðåòüÿ ïðàãìà bidirectionalCycle èäåíòèôèöèðóåò öèêëû, âû÷èñëåíèÿ âíóòðè
êîòîðûõ íå çàâèñÿò îò ïîðÿäêà èòåðàöèé öèêëà. Íàïðèìåð, TuningGenie ýìïèðè-
÷åñêè îïðîáóåò èíêðåìåíòíóþ è äåêðåìåíòíóþ âåðñèè äëÿ ñëåäóþùåãî öèêëà:
int[] data = new int[SIZE];
//bidirectionalCycle
for (int i=0; i < SIZE; i++) {
doSomethingWith(data[i]);
}
Èçìåíåíèå íàïðàâëåíèÿ îáõîäà äàííûõ âëèÿåò íà ýôôåêòèâíîñòü èñïîëüçî-
âàíèÿ ïðîöåññîðíîãî êýøà è, ñëåäîâàòåëüíî, íà îáùåå âðåìÿ âûïîëíåíèÿ ïàðàë-
ëåëüíîé ïðîãðàììû (äëÿ çàäà÷è [15] ðàçíîñòü ìåæäó íàèõóäøèì è íàèëó÷øèì
âàðèàíòàìè ñîñòàâèëà ïðèáëèçèòåëüíî 15%).
ÑÂÎÉÑÒÂÎ ÊÎÌÌÓÒÀÒÈÂÍÎÑÒÈ ÏÐÀÃÌ
Âàæíî, ÷òî ïåðåïèñûâàþùèå ïðàâèëà, â êîòîðûå òðàíñëèðóþòñÿ ïðàãìû
TuningGenie, èìåþò ñâîéñòâî êîììóòàòèâíîñòè (êîíôëþýíòíîñòè [21]), ïîçâî-
ëÿþùåå ïðèìåíÿòü ïðàâèëà ïðåîáðàçîâàíèÿ êîäà íàñòðàèâàåìîé ïðîãðàììû
â ïðîèçâîëüíîì ïîðÿäêå.
Ðàçëè÷èå ìåæäó ïðàãìàìè calculatedValue è tuneAbleParam çàêëþ÷àåòñÿ
â òîì, ÷òî äëÿ ïåðâîé ïðàãìû ïîäñòàíîâî÷íîå çíà÷åíèå âû÷èñëÿåòñÿ äî âûïîëíå-
íèÿ èòåðàöèé òþíèíãà, à íå çàäàåòñÿ â ïàðàìåòðàõ, êàê äëÿ tuneAbleParam. Îáå
ïðàãìû òðàíñëèðóþòñÿ â ïåðåïèñûâàþùèå ïðàâèëà ÿçûêà TermWare îäèíàêîâî-
ãî ñèíòàêñèñà. Ñâîéñòâî êîììóòàòèâíîñòè ýòèõ ïðàâèë ñëåäóåò èç òðåáîâàíèÿ
ê ñåìàíòè÷åñêîé ïðàâèëüíîñòè èñïîëüçîâàíèÿ ïðàãì � � �b R Rb! , ãäå R — ìíî-
æåñòâî ïåðåïèñûâàþùèõ ïðàâèë ïðîãðàììû; b — íåêîòîðàÿ ïåðåìåííàÿ èç ìíî-
æåñòâà ïåðåìåííûõ ïðîãðàììû V ; Rb — ïåðåïèñûâàþùåå ïðàâèëî, êîòîðîå èíè-
öèàëèçèðóåò çíà÷åíèå ïåðåìåííîé b.
Ñëåäîâàòåëüíî, äîñòàòî÷íî ïîêàçàòü êîììóòàòèâíîñòü ïåðåïèñûâàþùèõ ïðà-
âèë, îòíîñÿùèõñÿ ê ïðàãìàì bidirectionalCycle (ÏÏ1) è tuneAbleParam (ÏÏ2). Äîêà-
æåì ýòî ñâîéñòâî â òåðìèíàõ ÄÄÑ, äëÿ ÷åãî ââåäåì ñëåäóþùèå óòî÷íåííûå îïåðà-
òîðû ïðèñâàèâàíèÿ çíà÷åíèÿ ïåðåìåííîé è óñëîâèÿ ïðîäîëæåíèÿ âåòâëåíèÿ öèêëà.
Îáîçíà÷èì l, z, y — ëèòåðàëû; A b l( , ) — îïåðàòîð ïðèñâàèâàíèÿ ïåðåìåííîé
b çíà÷åíèÿ l; B b z B b z( , ), ( , )� — óñëîâíûå îïåðàòîðû; C b( ), �C b( ) — îïåðàòîðû èç-
ìåíåíèÿ çíà÷åíèÿ ïåðåìåííîé, íàïðèìåð èíêðåìåíò.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ïåðåïèñûâàþùåå ïðàâèëî, â êîòîðîå òðàíñëèðóåòñÿ ïðàãìà
bidirectionalCycle, ìåíÿåò óïðàâëåíèå ïðîãðàììû ñëåäóþùèì îáðàçîì:
A b l while B b z C b P A b z while B b l C( , ); ( ( , ), ( ), ) ( , ); ( ' ( , ),� ( ), )b P . (1)
Ìàíèïóëÿöèè ñ ëèòåðàëàìè ÏÏ2 âûïîëíÿåò, íå èçìåíÿÿ îïåðàòîðû
A b A b y( , ?) ( , )� , (2)
ãäå ñèìâîë ? îáîçíà÷àåò óíèâåðñàëüíûé ëèòåðàë.
Î÷åâèäíî, ÷òî ïðåîáðàçîâàíèÿ (1) è (2) êîììóòàòèâíû è, ñëåäîâàòåëüíî, êîì-
ìóòàòèâíû ïðàãìû bidirectionalCycle è tuneAbleParam, ïîðîæäàþùèå ÏÏ1 è ÏÏ2.
Èç ïðåäñòàâëåíèÿ ÏÏ1 è ÏÏ2 òàêæå âèäíî, ÷òî îíè òðàíñôîðìèðóþò (íî íå ïî-
ðîæäàþò) ðàçëè÷íûå îïåðàòîðû, è, ñëåäîâàòåëüíî, âñÿ ôàçà òðàíñôîðìàöèè èñõîä-
íîãî êîäà ïðîãðàììû èìååò ñâîéñòâî êîíå÷íîñòè äëÿ êîíå÷íûõ âõîäÿùèõ äàííûõ.
ÏÐÀÊÒÈ×ÅÑÊÎÅ ÏÐÈÌÅÍÅÍÈÅ
Ïðèìåð 1. Ðàññìîòðèì êëàññè÷åñêèé àëãîðèòì ñîðòèðîâêè QuickSort, â êîòî-
ðîì èñïîëüçóåòñÿ ôðåéìâîðê TuningGenie äëÿ îïòèìèçàöèè ïðîãðàìì. Äàííûé
àëãîðèòì ìîæíî çíà÷èòåëüíî óëó÷øèòü, ïðèìåíÿÿ äëÿ ïîäçàäà÷ (ìàññèâîâ) íå-
áîëüøîãî ðàçìåðà áîëåå ýôôåêòèâíûé àëãîðèòì «âíóòðåííåé ñîðòèðîâêè» (áåç
èñïîëüçîâàíèÿ äîïîëíèòåëüíîé ïàìÿòè è, ñëåäîâàòåëüíî, ñ áîëåå ýôôåêòèâ-
íûì èñïîëüçîâàíèåì åå êåøèðîâàíèÿ). Ïðàãìà tuneAbleParam ïîçâîëÿåò ëåãêî
äëÿ ëþáîé âû÷èñëèòåëüíîé ñðåäû ïîäîáðàòü ýòî îïòèìàëüíîå ïîðîãîâîå çíà-
÷åíèå. Ïîñêîëüêó çàìåíà àëãîðèòìà ñîðòèðîâêè íå ìåíÿåò êîíå÷íîãî ðåçóëüòà-
òà, åäèíñòâåííûì êðèòåðèåì îöåíêè êà÷åñòâà âûïîëíåííîé îïòèìèçàöèè áóäåò
çàòðà÷åííîå íà ñîðòèðîâêó âðåìÿ.
Èñõîäíûé êîä èìååò âèä
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
//tuneAbleParam name=threshold start=10 stop=1500 step=10
int threshold = 1;
if (high – low < threshold) {
insertionsort (array, low, high);
} else {
addPartitionForQuickSort (array, low, high)
}
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ýêñïåðèìåíò ïðîâîäèëñÿ íà ïåðñîíàëüíîì êîìïüþòåðå ñî ñëåäóþùåé êîí-
ôèãóðàöèåé:
� Intel® Core™ i5-2410M Processor (3M Cache, up to 2.90 GHz);
� 4 GB DDR2 RAM.
Ãðàôèê çàâèñèìîñòè âðåìåíè ñîðòèðîâêè ìàññèâà ñ äâóìÿ ìèëëèîíàìè ýëå-
ìåíòîâ îò çíà÷åíèÿ ïåðåìåííîé threshold ïðèâåäåí íà ðèñ. 4.
Ñèñòåìà TuningGenie ïîäîáðàëà îïòèìàëüíîå çíà÷åíèå threshold = 90,
ïðè êîòîðîì ðàññìàòðèâàåìàÿ ìîäèôèêàöèÿ QuickSort îêàçàëàñü ïðèáëèçèòåëüíî
íà 30% áûñòðåå êëàññè÷åñêîé âåðñèè.
Ïðèìåð 2. Ðàññìîòðèì çàäà÷ó ìîäåëèðîâàíèÿ áðîóíîâñêîãî äâèæåíèÿ
â èäåàëüíîì ãàçå.  ýòîé ìîäåëè íå áóäåì ðàçëè÷àòü ÷àñòèöû, ÷òî ïîçâîëèò çà
ñ÷åò àáñîëþòíî óïðóãîãî ñòîëêíîâåíèÿ ÷àñòèö ìåæäó ñîáîé èãíîðèðîâàòü ýòîò
ïðîöåññ, ïîñêîëüêó âñëåäñòâèå îäèíàêîâîé ñêîðîñòè è ìàññû â ìîìåíò ñòîëêíî-
âåíèÿ ÷àñòèöû êàê áû ìåíÿþòñÿ ìåñòàìè, ïðîäîëæàÿ òðàåêòîðèþ äâèæåíèÿ äî
ñòîëêíîâåíèÿ. Èíûìè ñëîâàìè, ó÷èòûâàåì òîëüêî ñòîëêíîâåíèÿ ìîëåêóë ñî
ñòåíêàìè ñîñóäà è ìîæåì ìîäåëèðîâàòü äâèæåíèå êàæäîé ÷àñòèöû íåçàâèñèìî
îò äðóãèõ. Ïóñòü íåîáõîäèìî ñìîäåëèðîâàòü ïîëîæåíèå ÷àñòèö ÷åðåç íåêîòîðûé
èíòåðâàë âðåìåíè t. Ðàçîáüåì ýòîò èíòåðâàë íà y ðàâíûõ èíòåðâàëîâ è áóäåì
ñ÷èòàòü, ÷òî êàæäàÿ ÷àñòèöà çà îäèí èíòåðâàë äåëàåò îäèí øàã — ïåðåìåùåíèå íà
åäèíèöó ðàññòîÿíèÿ. Òàêèì îáðàçîì, çàäà÷à ñâîäèòñÿ ê ìîäåëèðîâàíèþ ïîëîæåíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 171
÷àñòèö èäåàëüíîãî ãàçà âíóòðè ñî-
ñóäà ÷åðåç ó øàãîâ.
Ïàðàëëåëüíàÿ ñõåìà âû÷èñëå-
íèé ýòîé çàäà÷è èìååò ñâîéñòâî
àñèíõðîííîãî öèêëà ñî ñòåïåíüþ
ñâîáîäû z, çíà÷åíèå êîòîðîé
îïðåäåëÿåòñÿ íåîáõîäèìîñòüþ
ïîëó÷åíèÿ ïðîìåæóòî÷íûõ ðå-
çóëüòàòîâ âû÷èñëåíèé. Åñëè îíè
íå íóæíû (íàïðèìåð, íåò íåîá-
õîäèìîñòè âèçóàëèçèðîâàòü ïðî-
öåññ), òî m n� .
Êàê è â ïðèìåðå 1, åäèí-
ñòâåííûì êðèòåðèåì îöåíêè êà-
÷åñòâà âûïîëíåííîé îïòèìèçà-
öèè áóäåò çàòðà÷åííîå íà âû÷èñ-
ëåíèå âðåìÿ. Âëèÿíèå çíà÷åíèÿ
ïàðàìåòðà m íà îáùóþ ïðîèçâî-
äèòåëüíîñòü î÷åâèäíî: ÷åì áîëü-
øå êîëè÷åñòâî íåçàâèñèìûõ èòå-
ðàöèé, òåì ìåíüøå çàòðàò íà
ñèíõðîíèçàöèþ è îáùåå âðåìÿ
âû÷èñëåíèé. Ýòîò ôàêò ïîäòâåðæ-
äàåò ïðîâåäåííûé ýêñïåðèìåíò.
Êîíôèãóðàöèÿ òåñòîâîé ïëî-
ùàäêè òàêîâà:
� 2 õ Quad Core Intel Xeon E5405 2 GHz Intel EM64T;
� 16 GB DDR3 1066 Mhz RAM;
� n � 300000.
Ãðàôèê çàâèñèìîñòè ìóëüòèïðîöåññîðíîãî óñêîðåíèÿ S îò çíà÷åíèÿ ïàðà-
ìåòðà z ïðèâåäåí íà ðèñ. 5.
Êàê âèäíî èç ãðàôèêà, ïðè áîëüøîì çíà÷åíèè z ìóëüòèïðîöåññîðíîå óñêîðå-
íèå äîñòèãàëî çíà÷åíèÿ S � 7 5. , ÷òî ñîãëàñíî çàêîíó Àìäàëà áëèçêî ê òåîðåòè-
÷åñêîìó ïðåäåëó (âû÷èñëèòåëüíàÿ ñèñòåìà ñîñòîÿëà èç âîñüìè ÿäåð).
Ïðèâåäåííûå ïðèìåðû äàþò îáùåå ïðåäñòàâëåíèå î êëàññàõ çàäà÷, êîòîðûå
ìîæíî îïòèìèçèðîâàòü ñ ïîìîùüþ TuningGenie. Ïðèìåíåíèå ìåòîäîëîãèè àâòî-
òþíèíãà ê ñëîæíîé âû÷èñëèòåëüíîé çàäà÷å ñî ñâîéñòâîì àñèíõðîííîãî öèêëà,
à òàêæå ñ æåñòêèìè îãðàíè÷åíèÿìè ïî âðåìåíè è òî÷íîñòè âû÷èñëåíèé äåòàëüíî
ðàññìîòðåíî â [15].
ÇÀÊËÞ×ÅÍÈÅ
Èçâåñòíîå óòâåðæäåíèå «àëãîðèòìû + ñòðóêòóðû äàííûõ = ïðîãðàììû» [22]
âåðíî è äëÿ ïàðàëëåëüíûõ ïðîãðàìì. Îäíàêî çàäà÷à ïîñòðîåíèÿ ýôôåêòèâíîãî
ïàðàëëåëüíîãî àëãîðèòìà è âûáîðà ïîäõîäÿùåé ñòðóêòóðû äàííûõ äëÿ íåãî
îêàçûâàåòñÿ íàìíîãî ñëîæíåå. Äëÿ äîñòèæåíèÿ âûñîêèõ ïîêàçàòåëåé ïðîèçâî-
äèòåëüíîñòè ïðîãðàììû îíà äîëæíà ìàêñèìàëüíî ýôôåêòèâíî èñïîëüçîâàòü
ðåñóðñû âû÷èñëèòåëüíî ñðåäû, à ñëîæíîñòü è ðàçíîîáðàçèå ñîâðåìåííûõ ïà-
ðàëëåëüíûõ àðõèòåêòóð äåëàåò ïðàêòè÷åñêè íåâîçìîæíûì ñîçäàíèå ïðîãðàì-
ìû, ýôôåêòèâíîé â ëþáîé âû÷èñëèòåëüíîé ñðåäå, áåç äëèòåëüíîãî ïðîöåññà åå
êîíôèãóðèðîâàíèÿ è íàñòðîéêè. Ìåòîäîëîãèÿ àâòîòþíèíãà ïîçâîëÿåò ñóùåñ-
òâåííî ñîêðàòèòü ðåñóðñîåìêèé è ðóòèííûé ýòàï îïòèìèçàöèè ïàðàëëåëüíûõ
ïðîãðàìì çà ñ÷åò àâòîìàòèçàöèè ïðîöåññà èõ ýìïèðè÷åñêîé àäàïòàöèè ê öåëå-
âîé âû÷èñëèòåëüíîé ñðåäå.
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3
Ðèñ. 4
Ïåðåìåííàÿ
threshold
T �10 ìñ2 ,
Ðèñ. 5
m �102
S
Ðàññìàòðèâàåìàÿ â ðàáîòå ìîäåëü è ñèñòåìà ãåíåðàöèè àâòîòþíåðîâ
TuningGenie ïîçâîëÿåò îïòèìèçèðîâàòü îáå ñîñòàâëÿþùèå ïàðàëëåëüíîé ïðî-
ãðàììû: àëãîðèòìû è ñòðóêòóðû äàííûõ. Îñíîâûâàÿñü íà ñèñòåìå ïåðåïèñûâàþ-
ùèõ ïðàâèë, TuningGenie àâòîìàòè÷åñêè ãåíåðèðóåò àâòîòþíåð äëÿ îïòèìèçèðó-
åìîé ïðîãðàììû è òðåáóåò äëÿ ýòîãî ìèíèìàëüíûõ èçìåíåíèé â èñõîäíîì êîäå.
Èñïîëüçîâàíèå ýêñïåðòíûõ çíàíèé, â ñâîþ î÷åðåäü, ìàêñèìàëüíî ñîêðàùàåò ïðî-
öåññ îïòèìèçàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. S e d g e w i c k R . , W a y n e K . Algorithms (4th ed.). — Boston: Addison-Wesley Profess., 2011.
— 976 p.
2. Ä î ð î ø å í ê î À . Þ . Êóðñ ëåêö³é «Ïàðàëåëüí³ îá÷èñëþâàëüí³ ñèñòåìè». — Ê.: Âèä. ä³ì
ÊÌÀ, 2003. — 42 ñ.
3. h t t p ://www.oracle.com/technetwork/server-storage/solarisstudio/overview/index.html
4. h t t p ://software.intel.com/en-us/articles/automatic-parallelization-with-intel-compilers
5. N a o n o K . , T e r a n i s h i K . , C a v a z o s J . , S u d a R . Software automatic tuning from
concepts to state-of-the-art results. — New York: Springer, 2010. — 240 p.
6. W h a l e y R . , P e t i t e t A . , D o n g a r r a J . J . Automated em-pirical optimizations of software
and the ATLAS project // Parallel Comput. — 2001. — 27(1-2). — P. 3–35.
7. F r i g o M . a n d J o h n s o n S . FFTW: An adaptive software architecture for the FF // Acoustics,
Speech and Signal Processing. — 1998. — 3. — P. 1381–1384.
8. S c h a e f e r C . A . , P a n k r a t i u s V . , a n d T i c h y W . F . Atune-IL: An instrumentation
language for auto-tuning parallel applications // Euro-Par‘09 Proc. 15th Int. Euro-Par Conf. on
Parallel Processing. — Berlin; Heidelberg: Springer-Verlag, 2009. — P. 9–20.
9. h t t p ://www.gradsoft.ua/products/termware sub rus.html
10. Ä î ð î ø å í ê î À . Å . , Ø å â ÷ å í ê î Ð . Ñ . Ñèñòåìà ñèìâîëüíûõ âû÷èñëåíèé äëÿ ïðîãðàììè-
ðîâàíèÿ äèíàìè÷åñêèõ ïðèëîæåíèé // Ïðîáëåìû ïðîãðàììèðîâàíèÿ. — 2005. — ¹ 4. — Ñ. 718–727.
11. ² â à í å í ê î Ï . À . Çàñòîñóâàííÿ ð³çíèõ àëãîðèòì³â ïîøóêó îïòèìàëüíî¿ êîíô³ãóðàö³¿ äëÿ ïà-
ðàëåëüíîãî àëãîðèòìó ÷èñåëüíîãî ðîçâ’ÿçàííÿ áàãàòîâèì³ðíî¿ çàäà÷³ ìîäåëþâàííÿ íàâêîëèø-
íüîãî ñåðåäîâèùà // Theoretical and Applied Aspects of Cybernetics: Proc. of the Intern. Sci. Conf.
of Students and Young Scientists. — Kyiv: Bukrek, 2011. — 352 p.
12. K r i s h n a m o o r t h y M a W . , A g r a w a l S . G . Parameterized micro-benchmarking: An
auto-tuning approach for complex applications // Proc. of the 9th Conf. on Comput. Frontiers. —
2012. — P. 213–222.
13. E p p s t e i n D . , G a l i l Z . Parallel algorithmic techniques for combinatorial computation // Ann.
Rev. Comput. — 1988. — N 3. — P. 233–283.
14. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í Ã . Å . , ß ö å í ê î Å . À . Àëãåáðî-
àëãîðèòìè÷åñêèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Êèåâ:
Àêàäåìïåðèîäèêà, 2007. — 631 ñ.
15. ² â à í å í ê î Ï . À . , Ä î ð î ø å í ê î À . Þ . Àâòîìàòè÷íà îïòèì³çàö³ÿ âèêîíàííÿ äëÿ çàäà÷³
ìåòåîðîëîã³÷íîãî ïðîãíîçóâàííÿ // Ïðîáë. ïðîãðàìóâàííÿ. — 2012. — ¹ 2–3. — Ñ. 426–434.
16. P r o k o p H . Cache-oblivious algorithms // FOCS‘99 Proc. of the 40th Ann. Symp. on Foundations
of Comput. Sci. — 1999. — N 40. — P. 285–299.
17. A k l S . Superlinear performance in real-time parallel computation // The Journal of Supercomp. —
2004. — N 29. — P. 89–111
18. Ò ð à ó á Ä æ . , Â à ñ è ë ü ê î â ñ ê è é Ã . , Â î æ ü í ÿ ê î â ñ ê è é Õ . Èíôîðìàöèÿ, íåîïðå-
äåëåííîñòü, ñëîæíîñòü. — Ì.: Ìèð, 1988. — 184 ñ.
19. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . Àëãåáðî-äèíàìè÷åñêèå ìîäåëè äëÿ ðàñïàðàëëåëèâà-
íèÿ ïðîãðàìì // Ïðîáë. ïðîãðàìóâàííÿ. — 2010. — ¹ 1. — Ñ. 39–55.
20. Ê î ë ì î ã î ð î â À . Í . , Ô î ì è í Ñ . È . Ýëåìåíòû òåîðèè ôóíêöèé è ôóíêöèîíàëüíîãî àíà-
ëèçà. — Ì.: Íàóêà, 1976. — 544 ñ.
21. B e z e m M . , K l o p J . W . , V r i j e r R . Term rewriting systems. — New York: Cambridge
Univ. Press, 2003. — 908 p.
22. Â è ð ò Í . Àëãîðèòìû è ñòðóêòóðû äàííûõ. — Ì.: Ìèð, 1989. — 360 ñ.
Ïîñòóïèëà 04.07.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 3 173
|