Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств
Розглянуто розвиток алгеброалгоритмічного інструментарію для конструювання паралельних алгоритмів на основі спільного використання алгеброалгоритмічної методології специфікації і розробки програм та неалгоритмічних (евристичних) методів генерації коду. Евристичною частиною системи є динамічне налашт...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств / А.Е. Дорошенко, Н.В. Котюк, С.С. Николаев, Г.Е. Цейтлин, Е.А. Яценко // Кибернетика и системный анализ. — 2010. — № 4. — С. 151-158. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859500833470676992 |
|---|---|
| author | Дорошенко, А.Е. Котюк, Н.В. Николаев, С.С. Цейтлин, Г.Е. Яценко, Е.А. |
| author_facet | Дорошенко, А.Е. Котюк, Н.В. Николаев, С.С. Цейтлин, Г.Е. Яценко, Е.А. |
| citation_txt | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств / А.Е. Дорошенко, Н.В. Котюк, С.С. Николаев, Г.Е. Цейтлин, Е.А. Яценко // Кибернетика и системный анализ. — 2010. — № 4. — С. 151-158. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто розвиток алгеброалгоритмічного інструментарію для конструювання паралельних алгоритмів на основі спільного використання алгеброалгоритмічної методології специфікації і розробки програм та неалгоритмічних (евристичних) методів генерації коду. Евристичною частиною системи є динамічне налаштування програмного коду на цільову платформу і його оптимізація з використанням генерації коду, що самонавчається, і евристичних технологій.
The paper proposes a new approach and a system to develop parallel algorithms based on the joint use of the algebraic-algorithmic methodology of specification and development and non-algorithmic (heuristic) techniques for code generation. The algebraic part of the methodology provides the formalized process of parallel program design through high-level algebra-algorithmic specifications and automating transformations up to program code in a standard programming language. The heuristic part of the system stands for dynamical adjustment of program code for a target platform and its optimization using self-learning code generation and heuristic technologies.
|
| first_indexed | 2025-11-25T03:38:17Z |
| format | Article |
| fulltext |
ÓÄÊ 681.3
À.Å. ÄÎÐÎØÅÍÊÎ, Í.Â. ÊÎÒÞÊ, Ñ.Ñ. ÍÈÊÎËÀÅÂ, Ã.Å. ÖÅÉÒËÈÍ, Å.À. ßÖÅÍÊÎ
ÐÀÇÂÈÒÈÅ ÈÍÑÒÐÓÌÅÍÒÀÐÈß ÀËÃÅÁÐÛ
ÀËÃÎÐÈÒÌÈÊÈ Ñ ÖÅËÜÞ ÐÀÇÐÀÁÎÒÊÈ ÏÀÐÀËËÅËÜÍÛÕ
ÏÐÎÃÐÀÌÌ Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÝÂÐÈÑÒÈ×ÅÑÊÈÕ ÑÐÅÄÑÒÂ
Êëþ÷åâûå ñëîâà: àëãåáðû àëãîðèòìîâ, ïðîåêòèðîâàíèå ïðîãðàìì, ñèíòåç
ïðîãðàìì, îïòèìèçàöèÿ àëãîðèòìîâ, ýâðèñòèêà, èñêóññòâåííûé èíòåëëåêò .
ÂÂÅÄÅÍÈÅ
Ïðèìåíåíèå àëãåáðàè÷åñêîé ìåòîäîëîãèè â ïðîãðàììèðîâàíèè ÿâëÿåòñÿ îäíîé
èç ñîâðåìåííûõ òåíäåíöèé â èíôîðìàòèêå [1, 2]. Â íàñòîÿùåé ñòàòüå èñïîëüçó-
þòñÿ ìåòîäû, îñíîâàííûå íà àëãåáðå àëãîðèòìèêè (ÀÀ), ðàçâèâàþùåéñÿ â ðàì-
êàõ óêðàèíñêîé àëãåáðî-êèáåðíåòè÷åñêîé øêîëû [3, 4]. ÀÀ áëèçêà ê êîíöåïöèÿì
àëãåáðàè÷åñêîé àëãîðèòìèêè [2] è ïîðîæäàþùåãî ïðîãðàììèðîâàíèÿ [5] è ïðåä-
íàçíà÷åíà äëÿ ôîðìàëèçàöèè çíàíèé î ïðåäìåòíûõ îáëàñòÿõ ñ èñïîëüçîâàíèåì
àëãåáðàè÷åñêèõ ñðåäñòâ. Íà îñíîâå ÀÀ áûëà ðåàëèçîâàíà èíñòðóìåíòàëüíàÿ ñèñ-
òåìà ïðîãðàììèðîâàíèÿ (íàçâàííàÿ èíòåãðèðîâàííûì èíñòðóìåíòàðèåì ïðîåêòè-
ðîâàíèÿ è ñèíòåçà ïðîãðàìì, ÈÏÑ [6, 7]). Â ñèñòåìå ñîâìåùàåòñÿ òðè ôîðìû
ïðåäñòàâëåíèÿ çíàíèé: àíàëèòè÷åñêàÿ (ôîðìóëà â àëãåáðå àëãîðèòìîâ), åñòåñ-
òâåííî-ëèíãâèñòè÷åñêàÿ (òåêñòîâàÿ) è ãðàôîâàÿ (ãðàô-ñõåìû). ÈÏÑ îñíîâàí íà ìå-
òîäå äèàëîãîâîãî êîíñòðóèðîâàíèÿ ñèíòàêñè÷åñêè ïðàâèëüíûõ àëãîðèòìîâ, îðèåí-
òèðîâàííîì íà óñòðàíåíèå ñèíòàêñè÷åñêèõ îøèáîê â ïðîöåññå ïðîåêòèðîâàíèÿ [3].
Äëÿ ÀÀ áûë ðàçðàáîòàí àïïàðàò ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé [3, 4], îáåñïå÷è-
âàþùèé âîçìîæíîñòü óëó÷øåíèÿ îáúåêòîâ ïðîåêòèðîâàíèÿ ïî âûáðàííûì êðèòåðè-
ÿì (íàïðèìåð, ïàìÿòü, áûñòðîäåéñòâèå è ò.ä.).  êà÷åñòâå êîìïîíåíòû ÈÏÑ áûë
ðàçðàáîòàí äèàëîãîâûé òðàíñôîðìàòîð ðåãóëÿðíûõ ñõåì, áàçèðóþùèéñÿ íà èñ-
ïîëüçîâàíèè ñîîòíîøåíèé è òîæäåñòâ àëãåáð àëãîðèòìîâ. Â [7] èññëåäîâàëîñü
ïðèìåíåíèå ñèñòåìû ïåðåïèñûâàíèÿ ïðàâèë TermWare äëÿ ïðåîáðàçîâàíèÿ ñõåì
àëãîðèòìîâ. ÈÏÑ îáåñïå÷èâàåò ïîøàãîâóþ ðàçðàáîòêó ïðîãðàìì ñ èñïîëüçîâàíè-
åì òðàíñôîðìàöèé, íà÷èíàÿ îò ôîðìàëüíîé ñïåöèôèêàöèè è çàêàí÷èâàÿ ïðîãðàì-
ìíûì êîäîì â öåëåâîì ÿçûêå ïðîãðàììèðîâàíèÿ. Îäíàêî ïðè ýòîì îñòàåòñÿ ïðî-
áëåìà ïðîèçâîäèòåëüíîñòè ðàçðàáàòûâàåìûõ ïðîãðàìì, êîòîðàÿ íå ìîæåò áûòü
ïîëíîñòüþ ðåøåíà ââèäó âûñîêîé ñëîæíîñòè ãåíåðàöèè êîäà äëÿ áûñòðî ðàçâè-
âàþùèõñÿ àïïàðàòíûõ ïëàòôîðì. Òàêèì îáðàçîì, çàäà÷à ðàçðàáîòêè ïðîãðàìì
ñîñòîèò â ñîâìåùåíèè òðàíñôîðìàöèîííîé ìîùíîñòè ôîðìàëüíîé àëãåáðàè÷åñ-
êîé ìåòîäîëîãèè ñ àäàïòèâíûìè òåõíîëîãèÿìè ñàìîíàñòðàèâàþùèõñÿ ñèñòåì
ïðîãðàììèðîâàíèÿ.
 íàñòîÿùåé ñòàòüå àëãåáðîàëãîðèòìè÷åñêèå ñðåäñòâà ÈÏÑ èñïîëüçóþòñÿ ñî-
âìåñòíî ñ ñèñòåìîé ïðîãðàììèðîâàíèÿ MySHA [8], êîòîðàÿ îáåñïå÷èâàåò ñàìîîáó-
÷àþùóþñÿ ãåíåðàöèþ êîäà è äèíàìè÷åñêîå íàñòðàèâàíèå ïðîãðàìì íà öåëåâóþ àï-
ïàðàòíóþ è ïðîãðàììíóþ ïëàòôîðìû.  ñëó÷àå èñïîëüçîâàíèÿ MySHA âûñîêî-
óðîâíåâûé êîä, ðàçðàáîòàííûé â ÈÏÑ, ïîäëåæèò äèíàìè÷åñêîìó ïðåîáðàçîâàíèþ
äëÿ íàñòðîéêè íà öåëåâóþ ïëàòôîðìó, â ÷àñòíîñòè íà ìíîãîÿäåðíûé ïðîöåññîð èëè
ãðàôè÷åñêèé àêñåëåðàòîð. MySHA âêëþ÷àåò àâòîìàòèçèðîâàííóþ ñèñòåìó ðàçâåð-
òûâàíèÿ ÏÎ íà âû÷èñëèòåëüíîì êëàñòåðå è òåõíîëîãèþ èíòåëëåêòóàëüíîé îïòèìè-
çàöèè êîäà. Ñèñòåìà óðàâíîâåøèâàåò ïîòåíöèàëüíûå íåäîñòàòêè ðàçðàáîòàííûõ ðà-
íåå ñðåäñòâ òðàíñôîðìàöèè ïðîãðàìì ÈÏÑ (íàïðèìåð, ñëèøêîì áîëüøóþ çàâèñè-
ìîñòü îò ñòðóêòóðû êîíêðåòíîé ïðîãðàììû), èñïîëüçóÿ ýâðèñòè÷åñêîå
ïðîãðàììèðîâàíèå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 151
© À.Å. Äîðîøåíêî, Í.Â. Êîòþê, Ñ.Ñ. Íèêîëàåâ, Ã.Å. Öåéòëèí, Å.À. ßöåíêî, 2010
1. ÔÎÐÌÀËÈÇÎÂÀÍÍÎÅ ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ ÏÐÎÃÐÀÌÌ
 ÈÍÒÅÃÐÈÐÎÂÀÍÍÎÌ ÈÍÑÒÐÓÌÅÍÒÀÐÈÈ
Ðàçðàáîòàííûé ÈÏÑ îñíîâàí íà àëãåáðå àëãîðèòìèêè, êîòîðàÿ ïðåäñòàâëÿåò
ñîáîé äâóõóðîâíåâóþ ñèñòåìó. Â îñíîâó âåðõíåãî óðîâíÿ ïîëîæåíà òåîðèÿ
êëîíîâ (ñåìåéñòâ àëãåáð) [3, 9]. Ïîä êëîíîì ïîíèìàåòñÿ óíèâåðñàëüíàÿ àëãåáðà
C F SUPERk� � �{ }; , ãäå { }Fk — ñîâîêóïíîñòü îñíîâ, k n� 1 2, ,... , . Êàæäàÿ îñíîâà
ñîñòîèò èç ìíîæåñòâà îïåðàöèé îïðåäåëåííûõ òèïîâ (ëîãè÷åñêîãî, îïåðàòîðíî-
ãî, ñòðóêòóð ïàìÿòè è äàííûõ è äð.); SUPER — ñèãíàòóðà êëîíà, ñîäåðæàùàÿ
îïåðàöèþ ñóïåðïîçèöèè îïåðàöèé, ïðèíàäëåæàùèõ îñíîâàì. Êëàññè÷åñêèì
ïðèìåðîì îäíîîñíîâíîãî êëîíà ÿâëÿåòñÿ äâóçíà÷íàÿ àëãåáðà ëîãèêè — àëãåáðà
Ïîñòà (PA) [9]:
PA L SUPER� � �( );2 ,
ãäå L( )2 — ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé.
Ïîä àëãîðèòìè÷åñêèì êëîíîì ( )AC ïîíèìàåòñÿ äâóõîñíîâíàÿ ñèñòåìà
AC OP L SUPER� � �{ , ( )};2 ,
ãäå OP — îïåðàòîðíàÿ îñíîâà, ñîñòîÿùàÿ èç ìíîæåñòâà íåèíòåðïðåòèðîâàííûõ
îïåðàòîðíûõ ñõåì. Âûáîð ñèñòåìû îáðàçóþùèõ AC îïðåäåëÿåò ñèñòåìó àëãîðèò-
ìè÷åñêèõ êîíñòðóêöèé, ïðèñóùóþ òîìó èëè èíîìó ìåòîäó êîíñòðóèðîâàíèÿ àë-
ãîðèòìîâ è ïðîãðàìì (ñòðóêòóðíîìó, íåñòðóêòóðíîìó, îáúåêòíî-îðèåíòèðîâàííî-
ìó).  çàâèñèìîñòè îò ïîñòàâëåííîé çàäà÷è è âûáðàííîãî ìåòîäà ïðîãðàììèðî-
âàíèÿ äàëåå íà îñíîâå AC îñóùåñòâëÿåòñÿ ïîñòðîåíèå è èññëåäîâàíèå òðåáóåìîé
àëãåáðû àëãîðèòìîâ.
Íà íèæíåì óðîâíå àëãåáðû àëãîðèòìèêè îñóùåñòâëÿåòñÿ ïîñòðîåíèå âïîëíå
êîíêðåòíîé ïðèêëàäíîé àëãåáðû àëãîðèòìîâ, îðèåíòèðîâàííîé íà ïðåäñòàâëåíèå
àëãîðèòìè÷åñêèõ çíàíèé î âûáðàííîé ïðåäìåòíîé îáëàñòè. Ñõåìà îáðàçîâàíèÿ ïðè-
êëàäíîé àëãåáðû áàçèðóåòñÿ íà èíòåðïðåòàöèè ýëåìåíòàðíûõ îïåðàòîðíûõ è ïðåäè-
êàòíûõ ïåðåìåííûõ äëÿ àëãåáðû àëãîðèòìîâ, ïîñòðîåííîé íà âåðõíåì óðîâíå.
Ïðèìåðîì àëãåáðû àëãîðèòìîâ ÿâëÿþòñÿ ñèñòåìû àëãîðèòìè÷åñêèõ àëãåáð
(ÑÀÀ) Â.Ì. Ãëóøêîâà [3, 4], ïðåäñòàâëÿþùèå ñîáîé äâóõîñíîâíóþ àëãåáðó
ÑÀÀ � � �U B, ; � , ãäå U — ìíîæåñòâî îïåðàòîðîâ, B — ìíîæåñòâî ëîãè÷åñêèõ
óñëîâèé (ïðåäèêàòîâ).
Îïåðàòîðû ÿâëÿþòñÿ îòîáðàæåíèÿìè èíôîðìàöèîííîãî ìíîæåñòâà (ÈÌ) â ñå-
áÿ, ëîãè÷åñêèå óñëîâèÿ ÿâëÿþòñÿ îòîáðàæåíèÿìè ÈÌ â ìíîæåñòâî çíà÷åíèé
3-çíà÷íîé ëîãèêè E3 0 1� { , , }� , ãäå 0 — ëîæü, 1 — èñòèíà, � — íåîïðåäåëåííîñòü.
Ñèãíàòóðà îïåðàöèé ÑÀÀ � � �� �1 2 ñîñòîèò èç ñèñòåìû �1 ëîãè÷åñêèõ îïåðà-
öèé, ïðèíèìàþùèõ çíà÷åíèÿ â ìíîæåñòâå B, è ñèñòåìû �
2
îïåðàöèé, ïðèíèìàþ-
ùèõ çíà÷åíèÿ â ìíîæåñòâå îïåðàòîðîâ U.  ÑÀÀ � �U B, ; � ôèêñèðóåòñÿ ñèñòåìà
îáðàçóþùèõ � , ïðåäñòàâëÿþùàÿ êîíå÷íóþ ôóíêöèîíàëüíî ïîëíóþ ñîâîêóïíîñòü
îïåðàòîðîâ è ëîãè÷åñêèõ óñëîâèé. Ñ ïîìîùüþ ýòîé ñîâîêóïíîñòè ïîñðåäñòâîì ñó-
ïåðïîçèöèè îïåðàöèé, âõîäÿùèõ â � , ïîðîæäàþòñÿ ïðîèçâîëüíûå îïåðàòîðû è ëî-
ãè÷åñêèå óñëîâèÿ èç ìíîæåñòâ U è B .
Íà ÑÀÀ áàçèðóåòñÿ àëãîðèòìè÷åñêèé ÿçûê ÑÀÀ/1 [3], èñïîëüçóåìûé äëÿ ïðî-
åêòèðîâàíèÿ ïðîãðàìì â ÈÏÑ. Äàííûé ÿçûê ïðåäíàçíà÷åí äëÿ ìíîãîóðîâíåâîãî
ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ è äîêóìåíòèðîâàíèÿ ïîñëåäîâàòåëüíûõ è ïàðàëëåëü-
íûõ àëãîðèòìîâ è ïðîãðàìì. Ïðåèìóùåñòâî åãî èñïîëüçîâàíèÿ çàêëþ÷àåòñÿ â âîç-
ìîæíîñòè îïèñàíèÿ àëãîðèòìîâ â åñòåñòâåííî-ëèíãâèñòè÷åñêîé ôîðìå, óäîáíîé
äëÿ ÷åëîâåêà, ÷òî îáëåã÷àåò äîñòèæåíèå òðåáóåìîãî êà÷åñòâà ïðîãðàìì. Îñíîâíû-
ìè îáúåêòàìè ÿçûêà ÑÀÀ/1 ÿâëÿþòñÿ àáñòðàêöèè îïåðàòîðîâ (ïðåîáðàçîâàòåëåé
äàííûõ) è óñëîâèé (ïðåäèêàòîâ). Óñëîâèÿ è îïåðàòîðû ìîãóò áûòü áàçèñíûìè èëè
ñîñòàâíûìè. Áàçèñíûé îïåðàòîð (óñëîâèå) â ÑÀÀ-ñõåìå ñ÷èòàåòñÿ ïåðâè÷íîé àòî-
ìàðíîé àáñòðàêöèåé.
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Ñîñòàâíûå óñëîâèÿ ñòðîÿòñÿ èç áàçèñíûõ ñ ïîìîùüþ ñëåäóþùèõ ëîãè÷åñêèõ
îïåðàöèé ÑÀÀ:
� äèçúþíêöèÿ: ‘ ’óñëîâèå1 ÈËÈ óñëîâèå‘ ’2 ;
� êîíúþíêöèÿ: ‘ ’ ‘ ’óñëîâèå È óñëîâèå1 2 ;
� îòðèöàíèå: ÍÅ óñëîâèå‘ ’.
Ñîñòàâíûå îïåðàòîðû ñòðîÿòñÿ èç ýëåìåíòàðíûõ ïîñðåäñòâîì îïåðàöèé ïîñëå-
äîâàòåëüíîãî è ïàðàëëåëüíîãî âûïîëíåíèÿ îïåðàòîðîâ:
� “ ” “ ”îïåðàòîð ÇÀÒÅÌ îïåðàòîð1 2 — ïîñëåäîâàòåëüíîå âûïîëíåíèå îïåðàòî-
ðîâ;
� ÅÑËÈ óñëîâèå ÒÎ îïåðàòîð‘ ’ “ ”1 1 ÈÍÀ×Å “ ”îïåðàòîð 2 ÊÎÍÅÖ ÅÑËÈ —
îïåðàòîð âåòâëåíèÿ;
� ÏÎÊÀ ÍÅ óñëîâèå‘ _îêîí÷àíèÿ_ ’ “ ”öèêëà ÖÈÊË îïåðàòîð ÊÎÍÅÖ ÖÈÊËÀ
— îïåðàòîð öèêëà;
� ÏÀÐÀËËÅËÜÍÎ îïåðàòîð(( ) ( ), ... , ( ))(“ ”)i n� 1 — àñèíõðîííîå âûïîëíåíèå
n îïåðàòîðîâ (âåòâåé).
Èäåíòèôèêàòîðû îïåðàòîðîâ â ÑÀÀ-ñõåìàõ çàêëþ÷àþòñÿ â äâîéíûå êàâû÷êè,
à èäåíòèôèêàòîðû óñëîâèé — â îäèíàðíûå. Óðîâíè â ÑÀÀ-ñõåìàõ îïðåäåëÿþòñÿ
ëåâûìè ÷àñòÿìè ðàâåíñòâ, à ñòðóêòóðà êàæäîãî óðîâíÿ êîíêðåòèçèðîâàíà (â òåðìè-
íàõ ÑÀÀ) ïðàâîé ÷àñòüþ ñîîòâåòñòâóþùåãî ðàâåíñòâà. Ëåâàÿ ÷àñòü ðàâåíñòâà
îòäåëÿåòñÿ îò ïðàâîé öåïî÷êîé ñèìâîëîâ � .
ÈÏÑ ïðåäíàçíà÷åí äëÿ ïðîåêòèðîâàíèÿ àëãîðèòìîâ è ãåíåðàöèè ïðîãðàìì
â öåëåâûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ. Ïðîåêòèðîâàíèå àëãîðèòìîâ â ÈÏÑ îñíîâàíî
íà ìåòîäå äèàëîãîâîãî êîíñòðóèðîâàíèÿ ñèíòàêñè÷åñêè ïðàâèëüíûõ ïðîãðàìì
(ÄÑÏ-ìåòîäå), îáåñïå÷èâàþùåì ñèíòàêñè÷åñêóþ ïðàâèëüíîñòü ñõåì [3]. Ïðè ýòîì
èíñòðóìåíòàðèé èñïîëüçóåò óïîìÿíóòûå òðè ðàçëè÷íûå ôîðìû ïðåäñòàâëåíèÿ àë-
ãîðèòìîâ â ïðîöåññå èõ ïðîåêòèðîâàíèÿ – åñòåñòâåííî-ëèíãâèñòè÷åñêóþ (ÑÀÀ-ñõå-
ìû), àëãåáðàè÷åñêóþ (ðåãóëÿðíûå ñõåìû) è ãðàô-ñõåìíóþ. ÈÏÑ ïîääåðæèâàåò ãå-
íåðàöèþ ïîñëåäîâàòåëüíûõ è ìíîãîïîòî÷íûõ ïðîãðàìì íà ÿçûêàõ Java è Ñ++,
à òàêæå MPI ïðîãðàìì íà ÿçûêå C. Äëÿ èíòåãðàöèè ñ ñèñòåìîé MySHA èíñòðóìåí-
òàðèé ÈÏÑ òàêæå áûë íàñòðîåí íà ãåíåðàöèþ ïðîãðàìì â ÿçûêå MySHA Ì10.
Èíòåãðèðîâàííûé èíñòðóìåíòàðèé ñîäåðæèò ñëåäóþùèå êîìïîíåíòû:
� ÄÑÏ-êîíñòðóêòîð, ïðåäíàçíà÷åííûé äëÿ äèàëîãîâîãî ïðîåêòèðîâàíèÿ ñèí-
òàêñè÷åñêè ïðàâèëüíûõ ñõåì ïîñëåäîâàòåëüíûõ è ïàðàëëåëüíûõ àëãîðèòìîâ è ãåíå-
ðàöèè ïðîãðàìì;
� ðåäàêòîð ãðàô-ñõåì;
� òðàíñôîðìàòîð, ïðåäíàçíà÷åííûé äëÿ èíòåðàêòèâíîãî ïðåîáðàçîâàíèÿ ñõåì
àëãîðèòìîâ;
� ãåíåðàòîð ÑÀÀ-ñõåì, áàçèðóþùèéñÿ íà îñíîâå ñõåì áîëåå âûñîêîãî óðîâíÿ —
ãèïåðñõåì [6], ïðåäñòàâëÿþùèõ îáîáùåíèå ãðàììàòèê ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ;
� áàçó äàííûõ, ñîäåðæàùóþ îïèñàíèå êîíñòðóêöèé ÑÀÀ è áàçèñíûõ ïîíÿòèé â òðåõ
óïîìÿíóòûõ âûøå ôîðìàõ, à òàêæå èõ ðåàëèçàöèþ íà öåëåâîì ÿçûêå ïðîãðàììèðîâàíèÿ.
ÄÑÏ-êîíñòðóêòîð ïðåäíàçíà÷åí äëÿ ïîóðîâíåâîãî êîíñòðóèðîâàíèÿ ñõåì àëãî-
ðèòìîâ ñâåðõó-âíèç ñ èñïîëüçîâàíèåì êîíñòðóêöèé ÑÀÀ, âûáèðàåìûõ èç ñïèñêà.
Ïðîöåññ ïîñòðîåíèÿ àëãîðèòìà ñîñòîèò â ïîäñòàíîâêå óïîìÿíóòûõ êîíñòðóêöèé
îäíà â äðóãóþ è èìååò âèä äåðåâà êîíñòðóèðîâàíèÿ àëãîðèòìà. Âûáðàííûå ïîëüçî-
âàòåëåì êîíñòðóêöèè, à òàêæå îïåðàòîðíûå è ëîãè÷åñêèå ïåðåìåííûå, âõîäÿùèå
â íèõ, îòîáðàæàþòñÿ â äåðåâå ñ äàëüíåéøåé äåòàëèçàöèåé ïåðåìåííûõ. Íà êàæäîì
øàãå ïðîåêòèðîâàíèÿ ñèñòåìà â äèàëîãå ñ ïîëüçîâàòåëåì ïðåäîñòàâëÿåò íà âûáîð
ëèøü òå êîíñòðóêöèè, ïîäñòàíîâêà êîòîðûõ â ôîðìèðóåìûé òåêñò íå íàðóøàåò
ñèíòàêñè÷åñêîé ïðàâèëüíîñòè ñõåìû.  çàâèñèìîñòè îò òèïà âûáðàííîé ïåðåìåí-
íîé (îïåðàòîðíîãî èëè ëîãè÷åñêîãî) ñèñòåìà ïðåäëàãàåò ñîîòâåòñòâóþùèé ñïèñîê
îïåðàöèé èëè áàçèñíûõ ïîíÿòèé. Äàëåå äåðåâî êîíñòðóèðîâàíèÿ àëãîðèòìà èñïîëü-
çóåòñÿ äëÿ ãåíåðàöèè òåêñòà ÑÀÀ-ñõåìû, ðåãóëÿðíîé ñõåìû, ãðàô-ñõåìû è êîäà
â öåëåâîì ÿçûêå ïðîãðàììèðîâàíèÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 153
Ïðèìåð 1. Ðàññìîòðèì ïîñëåäîâàòåëüíóþ ÑÀÀ-ñõåìó àëãîðèòìà íàõîæäåíèÿ
ïðîñòûõ ÷èñåë ïî ìåòîäó ðåøåòà Ýðàòîñôåíà, ñêîíñòðóèðîâàííóþ â èíñòðóìåíòà-
ðèè ÈÏÑ.
ÑÕÅÌÀ PRIMES_ERATOSFEN ====
“Íàõîæäåíèå ïðîñòûõ ÷èñåë ìåòîäîì ðåøåòà Ýðàòîñôåíà”
ÊÎÍÅÖ ÊÎÌÌÅÍÒÀÐÈß
“ÎïðåäåëåíèåÃëîáàëüíûõÄàííûõ”
==== “Îïðåäåëèòü ìàññèâ (IS_SIMPL) òèï (bool)”;
“Îïðåäåëèòü ìàññèâ (ALL_NUM ) òèï (int) ñî çíà÷åíèÿìè
([-INF, +INF])”;
“Îïðåäåëèòü ìàññèâ (SIMPL_TAB) òèï (int)”
“program”
==== “Óñòàíîâèòü âñå ýëåìåíòû ìàññèâà (IS_SIMPL) â çíà÷åíèå
(true)”
ÇÀÒÅÌ
“Ïðî÷èòàòü öåëîå (MAX)”
ÇÀÒÅÌ
ÄËß ‘(cnt) îò (1) äî (+INF) ñ øàãîì (2)’
ÖÈÊË
ÅÑËÈ ‘(IS_SIMPL[cnt]) = (true)’
ÒÎ ÄËß ‘(scnt) îò (1) äî (+INF)’
ÖÈÊË
ÅÑËÈ ‘(cnt * scnt) > (MAX)’
ÒÎ “Ïåðåéòè ê ìåòêå (FINISH)”
ÊÎÍÅÖ ÅÑËÈ
ÇÀÒÅÌ
“(IS_SIMPL[cnt * scnt]) := (false)”
ÊÎÍÅÖ ÖÈÊËÀ
ÊÎÍÅÖ ÅÑËÈ
ÊÎÍÅÖ ÖÈÊËÀ
ÇÀÒÅÌ
“Ìåòêà (FINISH)”
ÇÀÒÅÌ
(SIMPLE_TAB := “Âûáðàòü çíà÷åíèÿ èç ìàññèâà (ALL_NUM)
â ñîîòâåòñòâèè ñ ìàñêîé (IS_SIMPL)")
ÇÀÒÅÌ
“Âîçâðàòèòü çíà÷åíèå (SIMPL_TAB)”
ÊÎÍÅÖ ÑÕÅÌÛ PRIMES_ERATOSFEN
Äëÿ äàëüíåéøåãî ïðåîáðàçîâàíèÿ ïðîãðàìì, ñêîíñòðóèðîâàííûõ â ÈÏÑ ñ öåëüþ
èõ íàñòðîéêè íà ïëàòôîðìó è îïòèìèçàöèè, èñïîëüçóåòñÿ ñèñòåìà MySHA.
2. ÐÀÇÐÀÁÎÒÊÀ ÏÐÎÃÐÀÌÌ Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÏËÀÒÔÎÐÌÛ MYSHA
.Ðàññìîòðèì ðåçóëüòàòû ðàñïàðàëëåëèâàíèÿ ïðèâåäåííîãî àëãîðèòìà íàõîæäåíèÿ
ïðîñòûõ ÷èñåë äëÿ âûïîëíåíèÿ íà ìíîãîÿäåðíîé ïðîöåññîðíîé àðõèòåêòóðå.
Ñèñòåìà MySHA — ìíîãîÿçû÷íàÿ êðîññ-ïëàòôîðìåííàÿ òåõíîëîãèÿ, êîòîðàÿ
äàåò âîçìîæíîñòü èíòåãðèðîâàòü êîìïîíåíòû, ñîçäàííûå ñ èñïîëüçîâàíèåì ÿçû-
êîâ ïðîãðàììèðîâàíèÿ ñ ðàçíûìè ïàðàäèãìàìè (èìïåðàòèâíàÿ è äåêëàðàòèâíàÿ)
äëÿ ðåàëèçàöèè ñëîæíûõ íàó÷íî-èññëåäîâàòåëüñêèõ ïðîåêòîâ [8]. Ïëàòôîðìà
MySHA ñîñòîèò èç ñëåäóþùèõ ýëåìåíòîâ:
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
� îïåðàöèîííîé ñèñòåìû ðåàëüíîãî âðåìåíè, êîòîðàÿ ìîæåò èñïîëüçîâàòüñÿ
äëÿ âûïîëíåíèÿ ïðîãðàìì íà îñíîâå ïëàòôîðìû MySHA;
� ñðåäñòâ âûïîëíåíèÿ MySHA-ïðîãðàìì íà ãðàôè÷åñêèõ àêñåëåðàòîðàõ AMD;
� òåõíîëîãèè Universal Binary, îáåñïå÷èâàþùåé âûïîëíåíèå ïðîãðàììû â
îðèãèíàëüíîì ìàøèííîì êîäå áåç èñïîëüçîâàíèÿ èíòåðïðåòàöèè/JIT-êîìïèëÿöèè
ïðîìåæóòî÷íîãî êîäà;
� óíèâåðñàëüíîé ñèñòåìû òèïîâ äàííûõ, îïòèìèçèðîâàííîé äëÿ íàó÷íûõ èñ-
ñëåäîâàíèé;
� âûñîêîóðîâíåâîãî ïðîìåæóòî÷íîãî óíèâåðñàëüíîãî ÿçûêà ïðîãðàììèðîâàíèÿ;
� òåõíîëîãèè ðàñïàðàëëåëèâàíèÿ è îïòèìèçàöèè ïðîãðàìì äëÿ ìíîãîïîòî÷íî-
ãî âûïîëíåíèÿ;
� ñðåäñòâ ðàçðàáîòêè ïðîãðàìì è èõ ðàçâåðòûâàíèÿ íà êëàñòåðíûõ ñèñòåìàõ;
� ïîäñèñòåìû óïðàâëåíèÿ ïàìÿòüþ íà îñíîâå èñïîëüçîâàíèÿ ñèìâîëüíûõ
èìåí;
� àâòîìàòè÷åñêîé ïîäñèñòåìû óïðàâëåíèÿ äèíàìè÷åñêîé ïàìÿòüþ íà îñíîâå
ìãíîâåííîãî îñâîáîæäåíèÿ ïàìÿòè, ãàðàíòèðóþùåãî ìèíèìàëüíûé îáúåì èñïîëü-
çîâàíèÿ ïàìÿòè è îòñóòñòâèå îáúåêòîâ áåç ññûëîê â ëþáîé ìîìåíò âðåìåíè. (Ôèíà-
ëèçàöèÿ îáúåêòîâ â ñèñòåìå MySHA ïðåäñòàâëÿåò äåòåðìèíèðîâàííûé ïðîöåññ
â îòëè÷èå îò ôèíàëèçàöèè â .NET è Java.)
Èäåîëîãèÿ ñîçäàíèÿ ïðîãðàììíûõ ñèñòåì íà áàçå ïëàòôîðìû MySHA ïîëó÷è-
ëà íàçâàíèå àëãîðèòìè÷åñêè-îðèåíòèðîâàííîãî ïðîãðàììèðîâàíèÿ (ÀÎÏ), êîòîðîå
èìååò ìíîãî îáùåãî ñ àëãåáðîàëãîðèòìè÷åñêèì ïîäõîäîì ê ïðîåêòèðîâàíèþ àëãî-
ðèòìîâ, ðàññìîòðåííûì â ðàçä. 1. ÀÎÏ äàåò âîçìîæíîñòü èñïîëüçîâàòü â ëþáîé ñè-
òóàöèè îïòèìàëüíûé ïîäõîä ê ïðîåêòèðîâàíèþ ñèñòåìû èëè îòäåëüíîãî àëãîðèò-
ìà. Òàê, íàïðèìåð, ìîæíî îáúåäèíÿòü òðàäèöèîííóþ ñòðóêòóðíóþ ìîäåëü ÿçûêà
Ïàñêàëü, îáúåêòíî-îðèåíòèðîâàííóþ ìîäåëü â ñòèëå .NET, òåõíîëîãèþ ñòðóêòóðè-
ðîâàíèÿ äàííûõ MySHA, à òàêæå ýâðèñòè÷åñêèå ìåòîäû è äåêëàðàòèâíîå ïðîãðàì-
ìèðîâàíèå.
Âàæíûì ïðåèìóùåñòâîì ïëàòôîðìû MySHA ÿâëÿåòñÿ âûñîêîýôôåêòèâíàÿ ðå-
àëèçàöèÿ áèáëèîòåê è òðàíñëÿòîðà. Òàê, áèáëèîòåêè äëÿ ÝÂÌ àðõèòåêòóð õ86,
AMD FireStream è ÌÏ ðåàëèçîâàíû íà ÿçûêå Àññåìáëåð. Òðàíñëÿòîð äëÿ ïëàòôîð-
ìû MySHA ÿâëÿåòñÿ òðåõóðîâíåâîé ñèñòåìîé, êîòîðàÿ îáåñïå÷èâàåò âûñîêèé óðî-
âåíü òåõíîëîãè÷åñêîé ñîâìåñòèìîñòè è âîçìîæíîñòü ñîçäàíèÿ íîâûõ òðàíñëÿòîðîâ
äëÿ ìíîãèõ ÿçûêîâ ïðîãðàììèðîâàíèÿ. Òåõíîëîãè÷åñêè íà âñåõ óðîâíÿõ òðàíñëÿòîð
ðåàëèçîâàí êàê èíòåëëåêòóàëüíàÿ íåéðîííàÿ ñåòü ñ èñïîëüçîâàíèåì äèíàìè÷åñêè
ãåíåðèðóåìûõ ïðîöåäóð è ýâðèñòèê. Òðàíñëÿòîð ïðåäîñòàâëÿåò ñðåäñòâà ïðîôèëè-
ðîâàíèÿ è èíòåëëåêòóàëüíîé îïòèìèçàöèè ïðîãðàììíîãî êîäà íà óðîâíå èñõîäíûõ
òåêñòîâ è àññåìáëåðíîãî êîäà. Âàæíûì ñâîéñòâîì òðàíñëÿòîðà ÿâëÿåòñÿ âîçìîæ-
íîñòü ïðîãðàììíûõ ñèñòåì äèíàìè÷åñêè èçìåíÿòü ñîáñòâåííûé âûñîêîóðîâíåâûé
êîä; áëàãîäàðÿ ýòîìó ïîÿâëÿþòñÿ øèðîêèå âîçìîæíîñòè äëÿ ñîçäàíèÿ èíòåëëåêòó-
àëüíûõ ïðîãðàììíûõ êîìïëåêñîâ.
Îñíîâó ðàçðàáîòàííîé âåðñèè ÿçûêà MySHA ñîñòàâëÿåò ÿçûê ïðîãðàììèðîâà-
íèÿ Ïàñêàëü. Çíà÷èòåëüíàÿ ÷àñòü ýëåìåíòîâ ÿçûêà MySHA çàèìñòâîâàíà èç Àëãîëà,
Ëèñïà è Ñè. Ôàéë ïðîãðàììû íà ÿçûêå MySHA ñîñòîèò èç äâóõ ÷àñòåé: çîíû îáúÿâ-
ëåíèé è çîíû îïèñàíèÿ ãëàâíîãî òåëà ïðîãðàììû. Â çîíå îáúÿâëåíèé îïèñûâàþòñÿ
ïîäïðîãðàììû, ìîäóëè, òèïû. Ñ ãëàâíîãî òåëà ïðîãðàììû íà÷èíàåòñÿ è çàêàí÷èâà-
åòñÿ åå âûïîëíåíèå. Ïðîãðàììà íàõîæäåíèÿ ïðîñòûõ ÷èñåë, èñïîëüçóþùàÿ ìåòîä
ðåøåòà Ýðàòîñôåíà, ìîæåò áûòü ïðåäñòàâëåíà ÿçûêîì MySHA M10 ñëåäóþùèì îá-
ðàçîì:
// Îáúÿâëåíèå äàííûõ
ar<bool> IS_SIMPL; // Ìàññèâ áóëåâûõ çíà÷åíèé
// Ìàññèâ öåëûõ ÷èñåë çàïîëíÿåòñÿ çíà÷åíèÿìè
ar<int> ALL_NUM = $R<int>([-INF, +INF]);
ar<int> SIMPL_TAB; // Ìàññèâ öåëûõ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 155
// Ãëàâíîå òåëî ïðîãðàììû
program
{
IS_SIMPL.SetAll(true);
int MAX = Console.ReadLn(“Enter MAX value”).ToInt();
forcnt(cnt, 1, +INF, step 2)
if(IS_SIMPL[scnt]==true) forcnt(scnt, 1, +INF)
{
if(cnt*scnt>MAX) goto FINISH;
IS_SIMPL[cnt*scnt] = false;
}
label(FINISH);
SIMPL_TAB = ALL_NUM.SelectByBoolMask(IS_SIMPL);
return SIMPL_TAB;
}
ßçûê MySHA ïðåäëàãàåò ìíîãî ñðåäñòâ ïðîãðàììèðîâàíèÿ àëãîðèòìîâ. Òàê,
ê òðàäèöèîííîé èìïåðàòèâíîé ìîäåëè (ïîäïðîãðàììû è ðóêîâîäÿùèå êîíñòðóêöèè
ÿçûêà Ïàñêàëü) äîáàâëåíî óïðàâëåíèå ïàìÿòüþ ñ ïîìîùüþ ñèìâîëüíûõ èìåí
(â MySHA êàæäàÿ ïåðåìåííàÿ ìîæåò èìåòü ñèìâîëüíîå èìÿ), ýâðèñòè÷åñêîå è äåê-
ëàðàòèâíîå ïðîãðàììèðîâàíèå. Ýâðèñòèêîé ÿâëÿåòñÿ ïðîãðàììà èëè ïîäïðîãðàì-
ìà, êîòîðàÿ ìîæåò îïòèìèçèðîâàòü ñâîå ïîâåäåíèå íà îñíîâå ðàñ÷åòà îïòèìàëüíîé
ñòðàòåãèè ïóòåì èçìåíåíèÿ ïàðàìåòðîâ-êîíñòàíò, çàëîæåííûõ â ñâîåì àëãîðèòìå,
è íà îñíîâå ïîäáîðà îïòèìàëüíûõ ðåøåíèé, âõîäíûõ äàííûõ è ðåçóëüòàòîâ. Ñ ïî-
ìîùüþ ýâðèñòèê ðåàëèçóþòñÿ ñðåäñòâà èíòåëëåêòóàëèçàöèè ïðè ãåíåðàöèè êîäà
è åãî âûïîëíåíèè (â ÷àñòíîñòè, ñðåäñòâà ñ íå÷åòêîé ëîãèêîé), ïðåäóñìàòðèâàþùèå:
� ðåôëåêñèþ MySHA-ïðîãðàììû äëÿ ïåðåñòðîéêè ðåñóðñîåìêèõ áàçîâûõ àë-
ãîðèòìîâ;
� ðåôëåêñèþ è äèíàìè÷åñêîå ãåíåðèðîâàíèå ýâðèñòèê äëÿ ïîñòðîåíèÿ èíòåë-
ëåêòóàëüíûõ ñèñòåì íà îñíîâå íåéðîííûõ ñåòåé è ýâðèñòè÷åñêèõ àëãîðèòìîâ;
� ñèíòàêñè÷åñêèå êîíñòðóêöèè è òåõíîëîãèè äëÿ îïèñàíèÿ è õðàíåíèÿ çíàíèé.
3. ÃÅÍÅÐÀÖÈß ÂÛÑÎÊÎÏÐÎÄÓÊÒÈÂÍÛÕ ÏÐÎÃÐÀÌÌ
Òðàíñëÿòîð ñèñòåìû MySHA ãåíåðèðóåò ýôôåêòèâíûé àññåìáëåðíûé êîä. Èñ-
ïîëüçîâàíèå òåõíîëîãèè ïëàòôîðìåííîãî ïîñòðîåíèÿ äàåò âîçìîæíîñòü ñîçäàâàòü
ïðîãðàììíûå ñðåäñòâà, íå çàâèñèìûå îò òèïà àïïàðàòíîãî îáåñïå÷åíèÿ, à òàêæå
èññëåäîâàòü ïðåèìóùåñòâà è íåäîñòàòêè ðàçëè÷íûõ ïðîöåññîðíûõ àðõèòåêòóð
äëÿ ðàçëè÷íûõ òèïîâ çàäà÷. MySHA ñîäåðæèò êà÷åñòâåííóþ ñèñòåìó èçìåðåíèÿ
ïðîèçâîäèòåëüíîñòè ïðîãðàììû, ïîçâîëÿþùóþ îïðåäåëèòü ñêîðîñòü ïðîãðàììû
â öåëîì è åå îòäåëüíûõ ÷àñòåé, à òàêæå ïîêàçàòåëü èñïîëüçîâàíèÿ ÎÇÓ. Ñèñòåìà
èçìåðåíèÿ ïðîèçâîäèòåëüíîñòè èíòåãðèðîâàíà ñ òðàíñëÿòîðîì, êîòîðûé èñïîëü-
çóåò äàííûå ñèñòåìû â ðåæèìå ñàìîîáó÷åíèÿ äëÿ îïðåäåëåíèÿ íàèëó÷øåé îïòè-
ìèçàöèîííîé ñòðàòåãèè. Ñ öåëüþ îïòèìèçàöèè òðàíñëÿòîð èñïîëüçóåò òðè íàáîðà
äèíàìè÷åñêèõ ýâðèñòèê, ïîçâîëÿþùèõ:
� îïðåäåëÿòü «óçêèå ìåñòà» ïðîãðàììû è ñðàâíèâàòü ïðîèçâîäèòåëüíîñòü ðàç-
íûõ âàðèàíòîâ îäíîãî ôðàãìåíòà êîäà íà ÿçûêå MySHA (îñíîâíûå àíàëèòè÷åñêèå
ýâðèñòèêè);
� ãåíåðèðîâàòü ïðîãðàììó íà Àññåìáëåðå â êîäå ïðîöåññîðà;
� óêàçàòü ïàðàëëåëüíûå ôðàãìåíòû ïðîãðàììû äëÿ ñèíõðîíèçèðîâàííîãî âû-
ïîëíåíèÿ íà ïðîöåññîðå ñ øèðîêèì êîìàíäíûì ñëîâîì;
� âûïîëíÿòü âûáîðêó êîðîòêèõ ïîñëåäîâàòåëüíîñòåé è ñîðòèðîâêó êîìàíä
ñ öåëüþ îïòèìèçàöèè ïðîãðàììû äëÿ ñóïåðñêàëÿðíûõ àðõèòåêòóð (ïîääåðæèâàþò-
ñÿ ìîäåëè SIMD, CISC è EPIC, à òàêæå íàáîðû èíñòðóêöèé MMX, SSE, SSE2,
3DNOW, AMD64, EM64T, PHC è ò.ï.);
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
� îñóùåñòâëÿòü ðàñïàðàëëåëèâàíèå âûñîêîóðîâíåâîãî ïðîãðàììíîãî êîäà íà
äîñòàòî÷íî áîëüøèå àâòîíîìíûå áëîêè ñ öåëüþ óìåíüøåíèÿ íàêëàäíûõ ðàñõîäîâ
íà ïåðåäà÷ó ñîîáùåíèé ìåæäó ïðîöåññàìè;
� ðàñïðåäåëÿòü äàííûå ìåæäó ïîòîêàìè è ïîäðàçäåëÿòü ïîäïðîãðàììû â îò-
äåëüíûå ôóíêöèè, âûïîëíÿåìûå îòäåëüíûìè ïîòîêàìè;
� îñóùåñòâëÿòü îïòèìèçàöèþ ïàìÿòè çà ñ÷åò íåÿâíîãî èñïîëüçîâàíèÿ ïåðåäà-
÷è óêàçàòåëÿ íà ñòðóêòóðó äàííûõ âìåñòî ïåðåäà÷è ñîáñòâåííî ñòðóêòóðû;
� âûïîëíÿòü îïòèìèçàöèþ ïàìÿòè çà ñ÷åò ïîñòðîåíèÿ ñïåöèàëèçèðîâàííûõ ýâ-
ðèñòèê î÷èñòêè äèíàìè÷åñêîé ïàìÿòè. Ýòà ìåòîäèêà äàåò âîçìîæíîñòü èçáåãàòü
òðàäèöèîííûõ íåäîñòàòêîâ òåõíîëîãèè îñâîáîæäåíèÿ ïàìÿòè.
Ñ öåëüþ èññëåäîâàíèÿ ñîâìåñòíîãî èñïîëüçîâàíèÿ ñèñòåìû MySHA è ÈÏÑ
áûë ïðîâåäåí ýêñïåðèìåíò, â êîòîðîì ÈÏÑ áûë íàñòðîåí íà ãåíåðàöèþ ïðîãðàìì
íà ÿçûêå MySHA M10. Ñãåíåðèðîâàííûå òàêèì îáðàçîì ïðîãðàììû ïåðåäàþòñÿ íà
âõîä ñèñòåìû MySHA, êîòîðàÿ îñóùåñòâëÿåò íåîáõîäèìóþ òðàíñôîðìàöèþ äëÿ
îïòèìèçàöèè è ïàðàëëåëèçàöèè ïðîãðàìì.
Ñïåöèàëüíûé íàáîð òåñòîâ íàó÷íûõ çàäà÷ áûë èñïîëüçîâàí äëÿ îïðåäåëåíèÿ
ðåàëüíîé ïðîèçâîäèòåëüíîñòè MySHA â êëàñòåðíîé ñèñòåìå, èìåþùåé ñëåäóþ-
ùóþ êîíôèãóðàöèþ:
� 9: Intel Celeron 3,06 Ghz (512 K L2 cache), 248 MB RAM;
� 2: Intel Celeron 1,7 Ghz (128 K L2 cache). 128 MB RAM;
� 1: Intel Core 2 Duo E6400, 2 GB RAM;
� 8: Intel Celeron 533 MHz (128 K L2 cache), 64 MB RAM;
� 1: AMD Athlon 64 X2 4800+, 8 GB RAM;
� 1: Mobile AMD Turion 64 X2 MT-62, 2 GB RAM.
Òàêèì îáðàçîì, êëàñòåðíàÿ ñèñòåìà èìååò 22 óçëà êëàñòåðà, 25 ïðîöåññîðîâ,
20 âû÷èñëèòåëüíûõ óçëîâ, 2 óïðàâëÿþùèõ óçëà.
Ïðèìåð 2. Ðàññìîòðèì ðåçóëüòàò ðàñïàðàëëåëèâàíèÿ ïðîãðàììû íàõîæäåíèÿ
ïðîñòûõ ÷èñåë, ñãåíåðèðîâàííîé â èíòåãðèðîâàííîì èíñòðóìåíòàðèè (ñì. ïðèìåð 1).
 ñèñòåìå MySHA áûëî ðàñïàðàëëåëåíî òåëî êîíñòðóêöèè IF óïîìÿíóòîé ïðîãðàì-
ìû. Ïðåäñòàâèì èñõîäíóþ êîíñòðóêöèþ â ÿçûêå MySHA Ì10 ñëåäóþùèì îáðàçîì:
if (IS_SIMPL[cnt] == true)
{
forcnt(scnt, 1, +INF)
{
<FOR_LOOP_BODY>
}
}
 ðåçóëüòàòå ðàñïàðàëëåëèâàíèÿ â ñèñòåìå MySHA âìåñòî ïðèâåäåííîé âûøå
êîíñòðóêöèè â ïðîãðàììå äàí ñëåäóþùèé òåêñò:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 157
if(IS_SIMPL[cnt] == true)
{
branch(X000)
{
forcnt(scnt, 1, +INF, step 2)
{
<FOR_LOOP_BODY>
}
}
branch(X001)
{
forcnt(scnt, 2, +INF, step 2)
{
 ðàññìîòðåííîì ôðàãìåíòå òåëî êîíñòðóêöèè IF (êîòîðûì ÿâëÿåòñÿ öèêë
for ), ðàçäåëåíî íà äâà öèêëà, êîòîðûå âûïîëíÿþòñÿ äâóìÿ ïîòîêàìè. Ïàðàìåòðû
öèêëîâ áûëè óñòàíîâëåíû òàêèì îáðàçîì, ÷òîáû ïîòîêè îáðàáàòûâàëè íåçàâèñè-
ìûå ôðàãìåíòû ìàññèâà IS_SIMPL . Òåëî öèêëîâ for â ñðàâíåíèè ñ ïîñëåäîâà-
òåëüíûì âàðèàíòîì îñòàëîñü áåç èçìåíåíèé.
Áûëè ïîëó÷åíû ðåçóëüòàòû âûïîëíåíèÿ ðàñïàðàëëåëåííîé â ñèñòåìå MySHA
ïðîãðàììû íàõîæäåíèÿ ïðîñòûõ ÷èñåë, êîòîðûå ñðàâíèâàëèñü ñ ðåçóëüòàòàìè âû-
ïîëíåíèÿ ïðîãðàììû, ðåàëèçîâàííîé âðó÷íóþ íà äðóãèõ ïëàòôîðìàõ.
Òàêèì îáðàçîì, ñðåäíåå êîëè÷åñòâî íàéäåííûõ ïðîñòûõ ÷èñåë (â ñåêóíäó) äëÿ
ðàçëè÷íûõ ïðîãðàììíûõ ïëàòôîðì ñîñòàâëÿþò 590 000 äëÿ ÿçûêà MySHA Ì10 (àâ-
òîìàòèçèðîâàííîå ðàñïàðàëëåëèâàíèå), 475 000 äëÿ Ñ++ ñ èñïîëüçîâàíèåì MPI 1.1
(ðó÷íîå ðàñïàðàëëåëèâàíèå), 273 000 äëÿ .NET (C#) (ðó÷íîå ðàñïàðàëëåëèâàíèå),
191000 äëÿ ÿçûêà Java (ðó÷íîå ðàñïàðàëëåëèâàíèå). Âî âñåõ ñëó÷àÿõ âû÷èñëÿëèñü
ïåðâûå 1010 ïðîñòûõ ÷èñåë è èñïîëüçîâàëîñü 18 ïîòîêîâ.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå ïîêàçàíî ðàçâèòèå èíñòðóìåíòàðèÿ äëÿ ðàçðàáîòêè ïàðàëëåëü-
íûõ àëãîðèòìîâ íà îñíîâå èíòåãðàöèè àëãåáðîàëãîðèòìè÷åñêèõ ñðåäñòâ è ñàìîîáó-
÷àþùèõñÿ ìåòîäîâ òðàíñëÿöèè. ÈÏÑ îáåñïå÷èâàåò ôîðìàëèçîâàííûå äèàëîãîâûå
ñðåäñòâà êîíñòðóèðîâàíèÿ ïðîãðàìì, õàðàêòåðíûì äëÿ íèõ ÿâëÿþòñÿ ïðîñòîòà
â îáó÷åíèè è èñïîëüçîâàíèè, à òàêæå íåçàâèñèìîñòü îò ÿçûêà ïðîãðàììèðîâàíèÿ
è âîçìîæíîñòü ïåðåâåäåíèÿ â ïðîèçâîëüíûé öåëåâîé ÿçûê. Âûïîëíåíà íàñòðîéêà
àëãåáðîàëãîðèòìè÷åñêîãî èíñòðóìåíòàðèÿ íà ãåíåðàöèþ êîäà â ÿçûêå MySHA M10,
÷òî ïîçâîëÿåò âûïîëíÿòü äàëüíåéøåå àâòîìàòèçèðîâàííîå ïðåîáðàçîâàíèå ïðîãðàìì
â ñèñòåìå MySHA, â ÷àñòíîñòè îñóùåñòâëÿòü èõ ðàñïàðàëëåëèâàíèå. Ïðåèìóùåñ-
òâîì ñèñòåìû MySHA â ñðàâíåíèè ñ ðàçðàáîòàííûìè ðàíåå äëÿ ÈÏÑ ñðåäñòâàìè
òðàíñôîðìàöèè ïðîãðàìì (áàçèðóþùèìèñÿ íà àëãåáðàè÷åñêèõ ðàâåíñòâàõ) ÿâëÿåòñÿ
èñïîëüçîâàíèå ýâðèñòèê è ñàìîîáó÷åíèå. Ðåçóëüòàòû ýêñïåðèìåíòà ïîêàçàëè, ÷òî
ïðîãðàììû, ðåàëèçîâàííûå íà ïëàòôîðìå MySHA ñ èñïîëüçîâàíèåì ýâðèñòè÷åñêèõ
òåõíîëîãèé, èìåþò áîëüøóþ ïðîäóêòèâíîñòü â ñðàâíåíèè ñ ïðîãðàììàìè, ðàçðàáî-
òàííûìè äëÿ äðóãèõ ïëàòôîðì (C++, .NET, J2EE).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A l g e b r a i c methodology to software technology, http://www.amast.org
2. Í î ä å í Ï . , Ê è ò ò å Ê . Àëãåáðàè÷åñêàÿ àëãîðèòìèêà. — Ì.: Ìèð, 1999. — 720 ñ.
3. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í à . Å . , ß ö å í ê î Å . À . Àëãåáðîàëãîðèòìè÷åñ-
êèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Êèåâ: Àêàäåìïåðèîäèêà, 2007. — 631 ñ.
4. Ã ë ó ø ê î â Â . Ì . , Ö å é ò ë è í Ã . Å . , Þ ù å í ê î Å . Ë . Àëãåáðà. ßçûêè. Ïðîãðàììèðîâàíèå. —
3-å èçä. — Ê.: Íàóê. äóìêà, 1989. — 376 ñ.
5. × à ð í å ö ê è Ê . , À é ç å í å ê å ð Ó . Ïîðîæäàþùåå ïðîãðàììèðîâàíèå: ìåòîäû, èíñòðóìåíòû,
ïðèìåíåíèå. — ÑÏá.: Ïèòåð, 2005. — 731 ñ.
6. Y a t s e n k o O . A . Algebras of hyperschemes and integrated tools for synthesis of programs in modern ob-
ject-oriented environments // Cybernetics and Systems Analysis. — 2004. — 40, N 1. — P. 38–42.
7. Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . , ß ö å í ê î Å . À . Ôîðìàëèçîâàííîå ïðîåêòèðîâàíèå ýôôåê-
òèâíûõ ìíîãîïîòî÷íûõ ïðîãðàìì // Ïðîáëåìè ïðîãðàìóâàííÿ. — 2007. — ¹ 1. — Ñ. 17–30.
8. Ä î ð î ø å í ê î À . Þ . , Ê î ò þ ê Ì . Â . , Í ³ ê î ë à º â Ñ . Ñ . Ïðîãðàìíà ïëàòôîðìà äëÿ íàóêîâèõ
äîñë³äæåíü // Òàì æå. — 2007. — ¹ 4. — Ñ. 49–59.
9. D o r o s h e n k o A . , T s e y t l i n G . , Y a t s e n k o O . , Z a c h a r i y a L . A theory of clones and formali-
zed design of programs // Proc. Int. Conf. «Concurrency, Specification, and Programming», 2006. — P. 328–339.
Ïîñòóïèëà 30.04.2009
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
<FOR_LOOP_BODY>
}
}
launch(ar<branch>() << X000 << X001);
meet(ar<branch>() << X000 << X001);
}
|
| id | nasplib_isofts_kiev_ua-123456789-45251 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-25T03:38:17Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Дорошенко, А.Е. Котюк, Н.В. Николаев, С.С. Цейтлин, Г.Е. Яценко, Е.А. 2013-06-10T18:54:34Z 2013-06-10T18:54:34Z 2010 Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств / А.Е. Дорошенко, Н.В. Котюк, С.С. Николаев, Г.Е. Цейтлин, Е.А. Яценко // Кибернетика и системный анализ. — 2010. — № 4. — С. 151-158. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45251 681.3 Розглянуто розвиток алгеброалгоритмічного інструментарію для конструювання паралельних алгоритмів на основі спільного використання алгеброалгоритмічної методології специфікації і розробки програм та неалгоритмічних (евристичних) методів генерації коду. Евристичною частиною системи є динамічне налаштування програмного коду на цільову платформу і його оптимізація з використанням генерації коду, що самонавчається, і евристичних технологій. The paper proposes a new approach and a system to develop parallel algorithms based on the joint use of the algebraic-algorithmic methodology of specification and development and non-algorithmic (heuristic) techniques for code generation. The algebraic part of the methodology provides the formalized process of parallel program design through high-level algebra-algorithmic specifications and automating transformations up to program code in a standard programming language. The heuristic part of the system stands for dynamical adjustment of program code for a target platform and its optimization using self-learning code generation and heuristic technologies. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств Розвиток інструментарію алгебри алгоритміки з метою розробки паралельних програм із використанням евристичних засобів Development of algebra algorithmic tools for designing parallel programs with heuristic facilities Article published earlier |
| spellingShingle | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств Дорошенко, А.Е. Котюк, Н.В. Николаев, С.С. Цейтлин, Г.Е. Яценко, Е.А. Программно-технические комплексы |
| title | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| title_alt | Розвиток інструментарію алгебри алгоритміки з метою розробки паралельних програм із використанням евристичних засобів Development of algebra algorithmic tools for designing parallel programs with heuristic facilities |
| title_full | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| title_fullStr | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| title_full_unstemmed | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| title_short | Развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| title_sort | развитие инструментария алгебры алгоритмики с целью разработки параллельных программ с использованием эвристических средств |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45251 |
| work_keys_str_mv | AT dorošenkoae razvitieinstrumentariâalgebryalgoritmikiscelʹûrazrabotkiparallelʹnyhprogrammsispolʹzovaniemévrističeskihsredstv AT kotûknv razvitieinstrumentariâalgebryalgoritmikiscelʹûrazrabotkiparallelʹnyhprogrammsispolʹzovaniemévrističeskihsredstv AT nikolaevss razvitieinstrumentariâalgebryalgoritmikiscelʹûrazrabotkiparallelʹnyhprogrammsispolʹzovaniemévrističeskihsredstv AT ceitlinge razvitieinstrumentariâalgebryalgoritmikiscelʹûrazrabotkiparallelʹnyhprogrammsispolʹzovaniemévrističeskihsredstv AT âcenkoea razvitieinstrumentariâalgebryalgoritmikiscelʹûrazrabotkiparallelʹnyhprogrammsispolʹzovaniemévrističeskihsredstv AT dorošenkoae rozvitokínstrumentaríûalgebrialgoritmíkizmetoûrozrobkiparalelʹnihprogramízvikoristannâmevrističnihzasobív AT kotûknv rozvitokínstrumentaríûalgebrialgoritmíkizmetoûrozrobkiparalelʹnihprogramízvikoristannâmevrističnihzasobív AT nikolaevss rozvitokínstrumentaríûalgebrialgoritmíkizmetoûrozrobkiparalelʹnihprogramízvikoristannâmevrističnihzasobív AT ceitlinge rozvitokínstrumentaríûalgebrialgoritmíkizmetoûrozrobkiparalelʹnihprogramízvikoristannâmevrističnihzasobív AT âcenkoea rozvitokínstrumentaríûalgebrialgoritmíkizmetoûrozrobkiparalelʹnihprogramízvikoristannâmevrističnihzasobív AT dorošenkoae developmentofalgebraalgorithmictoolsfordesigningparallelprogramswithheuristicfacilities AT kotûknv developmentofalgebraalgorithmictoolsfordesigningparallelprogramswithheuristicfacilities AT nikolaevss developmentofalgebraalgorithmictoolsfordesigningparallelprogramswithheuristicfacilities AT ceitlinge developmentofalgebraalgorithmictoolsfordesigningparallelprogramswithheuristicfacilities AT âcenkoea developmentofalgebraalgorithmictoolsfordesigningparallelprogramswithheuristicfacilities |