Применение суперкомпьютеров СКИТ для разработки и выполнения параллельных геофизических программ
Описано досвід розробки паралельних програм для сейсморозвідки. Сейсмічні дані зазвичай дуже великі і їх легко декомпозувати. Ці властивості призводять до аналогічних технологій розпаралелювання для таких різних завдань, як потрасна обробка, міграції й кінцево-різницеве моделювання. Розробка проекту...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/44484 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Применение суперкомпьютеров СКИТ для разработки и выполнения параллельных геофизических программ / В.Г. Тульчинский, П.Г. Тульчинский // Кибернетика и системный анализ. — 2009. — № 6. — С. 64-78. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44484 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-444842013-06-03T03:06:57Z Применение суперкомпьютеров СКИТ для разработки и выполнения параллельных геофизических программ Тульчинский, В.Г. Тульчинский, П.Г. Системный анализ Описано досвід розробки паралельних програм для сейсморозвідки. Сейсмічні дані зазвичай дуже великі і їх легко декомпозувати. Ці властивості призводять до аналогічних технологій розпаралелювання для таких різних завдань, як потрасна обробка, міграції й кінцево-різницеве моделювання. Розробка проекту розпаралелювання описана в термінах мови шаблонів паралельного програмування й методу аналізу ієрархій Т. Сааті. Досліджено питання ефективності паралельної обробки даних. The development of parallel programs for seismic exploration is described. Seismic datasets are usually extensive and have easily decomposable structure. These features result in similar paralleling techniques for different problems such as trace-by-trace processing, migrations and finite-difference modeling. The paralleling project development is described in terms of Pattern Language for Parallel Programming and Analytic Hierarchy Process. The parallel data processing is analyzed for efficiency. 2009 Article Применение суперкомпьютеров СКИТ для разработки и выполнения параллельных геофизических программ / В.Г. Тульчинский, П.Г. Тульчинский // Кибернетика и системный анализ. — 2009. — № 6. — С. 64-78. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44484 681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2009 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44484 |
| citation_txt |
Применение суперкомпьютеров СКИТ для разработки и выполнения параллельных геофизических программ / В.Г. Тульчинский, П.Г. Тульчинский // Кибернетика и системный анализ. — 2009. — № 6. — С. 64-78. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT tulʹčinskijvg primeneniesuperkompʹûterovskitdlârazrabotkiivypolneniâparallelʹnyhgeofizičeskihprogramm AT tulʹčinskijpg primeneniesuperkompʹûterovskitdlârazrabotkiivypolneniâparallelʹnyhgeofizičeskihprogramm |
| first_indexed |
2025-07-04T02:58:34Z |
| last_indexed |
2025-07-04T02:58:34Z |
| _version_ |
1836683535439626240 |
| fulltext |
ÓÄÊ 681.3
Â.Ã. ÒÓËÜ×ÈÍÑÊÈÉ, Ï.Ã. ÒÓËÜ×ÈÍÑÊÈÉ
ÏÐÈÌÅÍÅÍÈÅ ÑÓÏÅÐÊÎÌÏÜÞÒÅÐÎÂ ÑÊÈÒ ÄËß ÐÀÇÐÀÁÎÒÊÈ
È ÂÛÏÎËÍÅÍÈß ÏÀÐÀËËÅËÜÍÛÕ ÃÅÎÔÈÇÈ×ÅÑÊÈÕ ÏÐÎÃÐÀÌÌ
Êëþ÷åâûå ñëîâà: ïàðàëëåëüíîå ïðîãðàììèðîâàíèå, îáðàáîòêà ñåéñìè÷åñêèõ
äàííûõ, îïòèìèçàöèÿ êëàñòåðíûõ âû÷èñëåíèé, áîëüøèå íàáîðû äàííûõ.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìàòèêà ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ äîñòàòî÷íî õîðîøî ðàçðàáîòàíà
åùå â 1970–1980 ãã. Íàñòîÿùèé âçðûâ ïàðàëëåëüíûõ âû÷èñëåíèé íà÷àëñÿ â ïîñëåä-
íèå ãîäû â ñâÿçè ñ íåïðåðûâíûì íàêîïëåíèåì äàííûõ è óâåëè÷åíèåì ðàçìåðîâ çà-
äà÷ â óñëîâèÿõ òåõíîëîãè÷åñêèõ îãðàíè÷åíèé äàëüíåéøåãî ðîñòà òàêòîâîé ÷àñòîòû
ïðîöåññîðîâ. Íà àïïàðàòíîì óðîâíå ýòà òåíäåíöèÿ ïðîÿâèëàñü â ïåðåõîäå íà ìíî-
ãîÿäåðíûå êîìïüþòåðû, ðàñïðîñòðàíåíèè ìíîãîìàøèííûõ êëàñòåðîâ, ïîÿâëåíèè ïà-
ðàëëåëüíûõ âû÷èñëèòåëåé íà îñíîâå âèäåîêàðò. Êîñâåííî îíà ïðèâåëà ê ñêà÷êó
ïðîèçâîäèòåëüíîñòè ëîêàëüíûõ ñåòåé è äèñêîâûõ õðàíèëèù. Íà îáùåñèñòåìíîì
óðîâíå êîíöåïöèè êëàñòåðíûõ âû÷èñëèòåëåé (high performance computing, HPC),
ðàñïðåäåëåííûõ â Èíòåðíåòå âû÷èñëèòåëåé ïåðåìåííîãî ñîñòàâà (grid), è îïåðàòèâ-
íîé àðåíäû óäàëåííûõ âû÷èñëèòåëüíûõ ðåñóðñîâ (cloud computing) êîñâåííî ñïî-
ñîáñòâóþò ïðîãðàììèðîâàíèþ â îòêðûòûõ êîäàõ è ïðîäâèæåíèþ Linux, íåñìîòðÿ
íà âûñîêîå êà÷åñòâî ÏÎ äëÿ Windows-êëàñòåðîâ.
Óêðàèíà íå îñòàëàñü â ñòîðîíå îò ýòèõ òåíäåíöèé áëàãîäàðÿ ñî÷åòàíèþ èíèöèàòè-
âû ó÷åíûõ è ïîÿâèâøèõñÿ â ïåðèîä ýêîíîìè÷åñêîãî ðîñòà ôèíàíñîâûõ âîçìîæíîñòåé
ãîñóäàðñòâà. Óêðàèíñêèé êëàñòåð ÑÊÈÒ íà ïðîòÿæåíèè ïîñëåäíèõ ëåò ïîñòîÿííî çà-
íèìàë ïåðåäîâûå ïîçèöèè â ðåéòèíãå ïðîèçâîäèòåëüíîñòè [1], èíòåíñèâíî èñïîëüçî-
âàëñÿ óäàëåííûìè ïîëüçîâàòåëÿìè è íåñêîëüêèìè grid-ñèñòåìàìè. Áîëüøîå ÷èñëî
êëàñòåðîâ ìåíüøåãî ðàçìåðà çàêóïëåíî ó êîììåð÷åñêèõ ïîñòàâùèêîâ èëè ïîñòðîåíî
ñèëàìè óêðàèíñêèõ ïðåäïðèÿòèé äëÿ ñîáñòâåííûõ ïîòðåáíîñòåé. Â ñâÿçè ñ ýêîíîìè-
÷åñêîé ðåöåññèåé â áëèæàéøåå âðåìÿ ìàëîâåðîÿòíû çíà÷èòåëüíûå èíâåñòèöèè â âû-
÷èñëèòåëüíóþ òåõíèêó. Ïîýòîìó ïîâûøàåòñÿ àêòóàëüíîñòü óâåëè÷åíèÿ ïðîèçâîäèòåëü-
íîñòè è ýôôåêòèâíîãî èñïîëüçîâàíèÿ ñóùåñòâóþùèõ âû÷èñëèòåëåé.
Îäíîé èç îáëàñòåé ïðèìåíåíèÿ ñóïåðêîìïüþòåðîâ ÿâëÿåòñÿ îáðàáîòêà äàííûõ
ñåéñìîðàçâåäêè.
1. ÎÁÐÀÁÎÒÊÀ ÄÀÍÍÛÕ ÑÅÉÑÌÎÐÀÇÂÅÄÊÈ
Èçëîæèì òèïè÷íóþ ñõåìó ñåéñìè÷åñêîãî èññëåäîâàíèÿ çåìíîé êîðû [2]. Íà ïî-
âåðõíîñòè âäîëü ïëàíîâîãî ñåéñìè÷åñêîãî ïðîôèëÿ ðàçìåùàþò ïðèåìíèêè (ãåî-
ôîíû), ñïîñîáíûå ðåãèñòðèðîâàòü ñâîè ïåðåìåùåíèÿ â ïðîñòðàíñòâå. Âäîëü òîãî
æå ïðîôèëÿ ïîìåùàþò èñòî÷íèê ñåéñìè÷åñêîãî ñèãíàëà: çàêîïàííûé âçðûâïàêåò
èëè ãðóïïó âèáðàòîðîâ — ìàøèí, ñèíõðîííî óäàðÿþùèõ â çåìëþ òÿæåëûìè ìî-
ëîòàìè.  ðåçóëüòàòå âîçäåéñòâèÿ èñòî÷íèêà â çåìíîé êîðå âîçáóæäàåòñÿ àêóñòè-
÷åñêàÿ âîëíà, êîòîðàÿ ñî ñêîðîñòüþ çâóêà â ñðåäå ðàñïðîñòðàíÿåòñÿ âíèç è
â ñòîðîíû îò èñòî÷íèêà. Íà ñåéñìè÷åñêîé ãðàíèöå, ò.å. ãðàíèöå ïåðåïàäà ñêî-
ðîñòè çâóêà â ïîðîäå, ïðîèñõîäèò ïðåëîìëåíèå è îòðàæåíèå âîëí. Îòðàæåííàÿ
âîëíà ðàñïðîñòðàíÿåòñÿ â îáðàòíîì íàïðàâëåíèè, äîñòèãàåò ïîâåðõíîñòè è ðå-
ãèñòðèðóåòñÿ ãåîôîíàìè (ðèñ. 1).  êàæäîì ãåîôîíå çàïèñûâàåòñÿ ñåéñìè÷åñêàÿ
òðàññà, ïðåäñòàâëÿþùàÿ ñîáîé çàâèñèìîñòü çàðåãèñòðèðîâàííîé ñêîðîñòè âåðòè-
êàëüíîãî ñìåùåíèÿ ïðèáîðà îò âðåìåíè. Ñîâîêóïíîñòü ñåéñìè÷åñêèõ òðàññ îáðà-
çóåò ñåéñìîãðàììó. Ïîñëå ðåãèñòðàöèè ñåéñìîèñòî÷íèê è ïðèåìíèêè ïåðåìåùà-
þò âäîëü ïðîôèëÿ è ïîâòîðÿþò îïåðàöèþ. Äëÿ ïîëó÷åíèÿ ìîäåëè ðàéîíà ñåé-
ñìè÷åñêèå èññëåäîâàíèÿ ïðîâîäÿò âäîëü ñåòè ïðîôèëåé. Øèðîêî èñïîëüçóåòñÿ
3D-ñåéñìîðàçâåäêà, â êîòîðîé âîëíó ðåãèñòðèðóþò ïðèåìíèêè, ðàñïîëîæåííûå
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
© Â.Ã. Òóëü÷èíñêèé, Ï.Ã. Òóëü÷èíñêèé, 2009
âäîëü íåñêîëüêèõ ïàðàëëåëüíûõ ëèíèé ïðèåìà, êàê ïðàâèëî, â êðåñò ñ ïðîôèëÿ-
ìè âîçáóæäåíèÿ. Ñåòêó íàáëþäåíèé ñòàðàþòñÿ ñîõðàíÿòü ðåãóëÿðíîé. Ðàñïðîñ-
òðàíÿåòñÿ ìíîãîêîìïîíåíòíàÿ ñåéñìîðàçâåäêà 3Ñ, ïðè êîòîðîé ãåîôîí îòäåëüíî
ðåãèñòðèðóåò ñêîðîñòè ñìåùåíèÿ âäîëü òðåõ ïðîñòðàíñòâåííûõ îñåé, è ñåéñìî-
ðàçâåäêè 9Ñ, ïðè êîòîðîé òðåõêîìïîíåíòíûé ïðèåì ñî÷åòàåòñÿ ñ ïîî÷åðåäíûì
âîçáóæäåíèåì òðåõ íàïðàâëåííûõ âîëí â êàæäîé òî÷êå.
Ñåéñìîãðàììû íåñóò âàæíóþ èíôîðìàöèþ î ñòðóêòóðíîì ñòðîåíèè çåìíîé
êîðû.  ÷àñòíîñòè, íåôòü è ãàç íàõîäÿòñÿ â ïîðèñòûõ ïîðîäàõ-êîëëåêòîðàõ (ïåñ÷à-
íèêàõ, òðåùèíîâàòûõ èçâåñòíÿêàõ), îãðàíè÷åííûõ ïëîòíûìè ïîêðûøêàìè. Çíà÷è-
òåëüíàÿ ðàçíèöà ïëîòíîñòè è ñîîòâåòñòâåííî ñêîðîñòè çâóêà ìåæäó êîëëåêòîðîì è
ïëîòíîé ïîêðûøêîé ñîçäàåò ðåçêèå ãðàíèöû, êîòîðûå îòîáðàæàþòñÿ íà
ñåéñìîãðàììàõ âûñîêèìè àìïëèòóäàìè ñèãíàëà (ÿðêèìè ïîëîñêàìè íà ðèñ. 2).
Åñëè èñòî÷íèê è ïðèåìíèê ðàñïîëîæåíû íà ïëîñêîé ïîâåðõíîñòè çåìëè, âîëíà
ðàñïðîñòðàíÿåòñÿ â îäíîðîäíîé ñðåäå ñî ñêîðîñòüþ çâóêà V è îòðàæàåòñÿ îò ãîðè-
çîíòàëüíîé ãðàíèöû, ðàñïîëîæåííîé íà ãëóáèíå z , à ðàññòîÿíèå ìåæäó èñòî÷íè-
êîì è ïðèåìíèêîì — x , îòðàæåííûé ñèãíàë äîñòèãíåò ïðèåìíèêà ÷åðåç âðåìÿ
t
V
x
z� �
�
�
�
�
�
2
2
2
2 . (1)
Ôîðìóëà (1) ïîëó÷åíà ñîãëàñíî çàêîíó îïòèêè î ðàâåíñòâå óãëîâ ïàäåíèÿ è îò-
ðàæåíèÿ. Åå ïðåîáðàçîâàíèå ïîçâîëÿåò îöåíèòü ãëóáèíó z ãîðèçîíòàëüíîé ãðàíèöû
ïî âðåìåíè ðåãèñòðàöèè:
z
V t x
�
2 2 2
2
. (2)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 65
Ðèñ. 1. Ñõåìà ðàñïðîñòðàíåíèÿ âîëíû è åå îòðàæåíèÿ îò ñåéñìè÷åñêîé ãðàíèöû
Ñîãëàñíî ôîðìóëå (2) ñèãíàë, çàðåãèñòðèðîâàííûé ãåîôîíàìè, ðàñïîëîæåííû-
ìè âäîëü ïðîôèëÿ íà ãîðèçîíòàëüíîé ïîâåðõíîñòè, áóäåò â òàêîé ñðåäå èìåòü ôîð-
ìó âåðõíåãî êóïîëà ýëëèïñà (â ñëó÷àå 3D-íàáëþäåíèé — ýëëèïñîèäà âðàùåíèÿ).
Îò äâóõ èëè áîëüøåãî ÷èñëà ãîðèçîíòàëüíûõ ãðàíèö ïîëó÷èì êîíöåíòðè÷åñêèå ýë-
ëèïñû. Óñëîæíåíèå ìîäåëè (íàêëîí ãðàíèö, àíèçîòðîïèÿ, îãðàíè÷åííûå ïî ðàçìå-
ðó âêðàïëåíèÿ) ïðèâîäèò ê èñêàæåíèþ ýëëèïòè÷åñêîé ôîðìû ñèãíàëà (ðèñ. 2, 3).
Âàæíîå ñëåäñòâèå ôîðìóëû (2) — âîçìîæíîñòü îäíîâðåìåííîãî ïîäáîðà V è z
ïðè íàëè÷èè çàìåðîâ âðåìåíè ïðèõîäà ñèãíàëà t äëÿ ðàçíûõ çíà÷åíèé ðàññòîÿíèÿ x
â ñëó÷àå ãîðèçîíòàëüíîé ãðàíèöû è îäíîðîäíîé ñðåäû íàä ãðàíèöåé. À èìåííî,
äîñòàòî÷íî ïåðåáðàòü âîçìîæíûå çíà÷åíèÿ V è äëÿ êàæäîãî x âû÷èñëèòü z . Åñëè
ñêîðîñòü ïîäîáðàíà âåðíî, âñå ãëóáèíû ñîâïàäóò. Åñëè îíà çàâûøåíà, z áóäåò óâå-
ëè÷èâàòüñÿ ñ ðîñòîì x , åñëè çàíèæåíà — òî óìåíüøàòüñÿ ñ ðîñòîì x . Íà ýòîì ïðè-
íöèïå ïîñòðîåíû àëãîðèòìû âîññòàíîâëåíèÿ ñêîðîñòíîé ìîäåëè ñðåäû ïî
ñåéñìè÷åñêèì äàííûì:
– èñõîäèì èç êàêîé-òî ìîäåëè, âàðüèðóåì åå ïàðàìåòðû è ïîëó÷àåì ðÿä
ìîäåëåé;
– ðàññ÷èòûâàåì äëÿ êàæäîãî âàðèàíòà ìîäåëè êàæäîé òðàññû ïîëîæåíèå
ãðàíèö;
– âûáèðàåì òîò âàðèàíò, â êîòîðîì íàáëþäàåòñÿ íàèëó÷øåå ñîâïàäåíèå ïîëî-
æåíèÿ ãðàíèö ïî ðàçíûì òðàññàì ñ ãðàíèöàìè, çàäàííûìè â ìîäåëè.
Îáû÷íî ìîäåëü ñòðîÿò ñâåðõó âíèç, ïîî÷åðåäíî ïîäáèðàÿ ãðàíèöû è ñêîðîñòè
íàä íèìè. Ïîñëå ïåðâîíà÷àëüíîãî îïðåäåëåíèÿ ñêîðîñòíîé ìîäåëè â íåêîòîðûõ
òî÷êàõ ïîâåðõíîñòè íà îñíîâå îïèñàííîãî ãðóáîãî ãîðèçîíòàëüíî-ñëîèñòîãî ïðè-
áëèæåíèÿ ãðàíèöû è ñêîðîñòè ìåæäó íèìè èíòåðïîëèðóþò, ôîðìèðóÿ òàêèì îáðà-
çîì ãëóáèííóþ ñêîðîñòíóþ ìîäåëü. Çàòåì äëÿ êàæäîé òðàññû âû÷èñëÿþò âðåìåíà
ðàñïðîñòðàíåíèÿ âîëíû îò èñòî÷íèêà è îò ïðèåìíèêà äî êàæäîé òî÷êè ñðåäû. Ñóì-
ìà ýòèõ âðåìåí çàäàåò ïîçèöèþ íà òðàññå, îòêóäà ïåðåíîñÿò (äîáàâëÿþò) çíà÷åíèå â
ñîîòâåòñòâóþùóþ ïîçèöèþ âûõîäíîãî èçîáðàæåíèÿ. Ïîäîáíûå ïðîöåäóðû íàçûâà-
þòñÿ ïðå-ñòåê ìèãðàöèÿìè. ßðêèå, êîíòðàñòíûå èçîáðàæåíèÿ ãðàíèö ìèãðèðîâàí-
íîãî ðàçðåçà èëè êóáà, ñîâïàäàþùèå ñ ãðàíèöàìè èñõîäíîé ìîäåëè, îçíà÷àþò, ÷òî
ìîäåëü ïîñòðîåíà õîðîøî. Äëÿ äîñòèæåíèÿ òàêîãî ðåçóëüòàòà ãðàíèöû ìîäåëè ïðè-
õîäèòñÿ èòåðàòèâíî êîððåêòèðîâàòü â ñòîðîíó èçîáðàæåíèé ãðàíèö íà
ìèãðèðîâàííîì ðàçðåçå èëè êóáå.  ïðîöåññå óòî÷íåíèÿ ìîäåëè ìèãðàöèè
âûïîëíÿþòñÿ íåîäíîêðàòíî. Àëãîðèòìû ìèãðàöèé ðàçëè÷àþòñÿ ãëàâíûì îáðàçîì
ïî ñïîñîáó ðàñ÷åòà âðåìåí.
Çàäà÷è äëÿ ðàñïàðàëëåëèâàíèÿ.  êà÷åñòâå ïðèìåðà ðàñïàðàëëåëèâàíèÿ
ðàññìîòðèì òðè õàðàêòåðíûå çàäà÷è, çíà÷èòåëüíî ðàçëè÷àþùèåñÿ ïî ñîîòíîøåíèþ
ïîòðåáíîñòåé â ïðîöåññîðíîì ðåñóðñå, îïåðàòèâíîé ïàìÿòè è íàãðóçêå íà ñèñòåìó
õðàíåíèÿ ôàéëîâ.
Ïåðâàÿ çàäà÷à — 3D ïðå-ñòåê ìèãðàöèÿ äâàæäû îòðàæåííûõ (äóïëåêñíûõ)
âîëí (ÌÄÂ) [2]. Ïî ñâîéñòâàì àëãîðèòìà ýòî òèïè÷íàÿ ìèãðàöèîííàÿ ïðîöåäóðà.
Íî â îòëè÷èå îò îáû÷íîé ìèãðàöèè ÌÄ ðåãèñòðèðóåò íå ãîðèçîíòàëüíûå, à âåðòè-
êàëüíûå ãðàíèöû (ðàçëîìû, çîíû òðåùèíîâàòîñòè, ãðàíèöû ñîëÿíûõ øòîêîâ è ò.ï.).
66 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ðèñ. 2. Òðè ñåéñìîãðàììû îäíîãî ïðîôèëÿ (2D) Ðèñ. 3. Ñêîðîñòíàÿ ìîäåëü ïðîôèëÿ äëÿ ðèñ. 2
Íà âõîä ÌÄÂ ïîìèìî ñêîðîñòíîé ìîäåëè ñðåäû è ñåéñìîãðàììû ïîäàåòñÿ êàðòà
îòðàæàþùåãî ãîðèçîíòà. Ðàçëè÷àþò äâà òèïà äóïëåêñíûõ âîëí â çàâèñèìîñòè îò
ïîðÿäêà îòðàæåíèé: ñíà÷àëà îò çàäàííîé ãîðèçîíòàëüíîé ãðàíèöû, çàòåì — îò âåð-
òèêàëüíîé (ÌÄÂ-Ï), è â îáðàòíîì ïîðÿäêå (ÌÄÂ-È). Àëãîðèòì ÌÄÂ äëÿ îäíîé
òðàññû ñîñòîèò èç òðåõ øàãîâ:
1) ðàñ÷åò àëãîðèòìîì ýéêîíàëà âðåìåíè ðàñïðîñòðàíåíèÿ óïðóãîé âîëíû îò
èñòî÷íèêà (äëÿ ÌÄÂ-È) èëè äî ïðèåìíèêà (ÌÄÂ-Ï) äëÿ êàæäîé òî÷êè ñðåäû;
2) ðàñ÷åò àëãîðèòìîì ýéêîíàëà âðåìåíè ðàñïðîñòðàíåíèÿ óïðóãîé âîëíû, îò-
ðàæåííîé îò çàäàííîãî îòðàæàþùåãî ãîðèçîíòà, îò ïðèåìíèêà (ÌÄÂ-È) èëè äî
èñòî÷íèêà (ÌÄÂ-Ï);
3) âû÷èñëåíèå äëÿ êàæäîé òî÷êè ñðåäû ñóììàðíîãî âðåìåíè è ïðèáàâëåíèå â
ñîîòâåòñòâóþùóþ òî÷êó ìèãðèðîâàííîãî êóáà çíà÷åíèÿ òðàññû, çàïèñàííîãî â ýòî
ñóììàðíîå âðåìÿ (ïðè óñëîâèè âûïîëíåíèÿ àïåðòóðíûõ îãðàíè÷åíèé, îãðàíè÷åíèé
ïî çíà÷åíèÿì âðåìåí è èõ ïðîèçâîäíûõ).
Âòîðàÿ çàäà÷à — ñèíòåç 3D-ñåéñìîãðàìì ïî ãåîëîãè÷åñêîé ìîäåëè ñðåäû ìåòîäîì
êîíå÷íî-ðàçíîñòíîãî ýëàñòè÷åñêîãî àíèçîòðîïíîãî ìîäåëèðîâàíèÿ 2,5D (Ì2,5D) [3].  îò-
ëè÷èå îò àëüòåðíàòèâíûõ ìåòîäîâ ïîëó÷åíèÿ ñèíòåòè÷åñêèõ 3D-ñåéñìîãðàìì — ëó÷åâîãî
ìîäåëèðîâàíèÿ è êîíå÷íî-ðàçíîñòíîãî àêóñòè÷åñêîãî ìîäåëèðîâàíèÿ — Ì2,5D ïîçâîëÿåò
ó÷èòûâàòü òîíêîñëîèñòîñòü, ïðîñòðàíñòâåííóþ àíèçîòðîïèþ ñâîéñòâ (TTI) è ñî÷åòàíèå
íåñêîëüêèõ ïðîñòðàíñòâåííûõ ñèñòåì òðåùèíîâàòîñòè. Â òî æå âðåìÿ Ì2,5D íàêëàäûâàåò
æåñòêîå îãðàíè÷åíèå íà ãåîìåòðèþ ãåîëîãè÷åñêîé ìîäåëè ñðåäû, à èìåííî âñå ñâîéñòâà
äîëæíû áûòü ïîñòîÿííû âäîëü îñè Y . Íåóäîáñòâî óêàçàííîãî îãðàíè÷åíèÿ êîìïåíñèðóåò-
ñÿ âîçìîæíîñòüþ ñèíòåçèðîâàòü ðåàëèñòè÷åñêèå ñåéñìîãðàììû, îòðàæàþùèå íàòóðàëü-
íóþ ñëîæíîñòü ãåîëîãè÷åñêîãî ñòðîåíèÿ, íî òî÷íî ñîîòâåòñòâóþùèå èçâåñòíîé ìîäåëè
ñðåäû. Äàæå ñóïåðêîìïüþòåðû íå ìîãóò âûïîëíèòü ýëàñòè÷åñêîå àíèçîòðîïíîå ìîäåëè-
ðîâàíèå 3D â òîíêîñëîèñòîé ñðåäå çà ïðèåìëåìîå âðåìÿ. Òàêèì îáðàçîì, ñåéñìîãðàììû
Ì2,5D îáëàäàþò óíèêàëüíûìè ñâîéñòâàìè äëÿ çàäà÷è ïëàíèðîâàíèÿ ñåéñìîðàçâåäêè
(ïðèíÿòèÿ ðåøåíèÿ î ðàçìàõå è ïëîòíîñòè ñåòêè íàáëþäåíèé, î âûïîëíåíèè ìíîãîêîìïî-
íåíòíûõ èññëåäîâàíèé), òåñòèðîâàíèÿ ïîñëåäîâàòåëüíîñòåé îáðàáîòêè, îöåíêè ïðåäåëüíîé
òî÷íîñòè ãåîôèçè÷åñêîé èíòåðïðåòàöèè. Àëãîðèòì Ì2,5D ñîñòîèò èç òðåõ øàãîâ:
1) êîíå÷íî-ðàçíîñòíîå ìîäåëèðîâàíèå ðàñïðîñòðàíåíèÿ óïðóãèõ âîëí äëÿ îò-
äåëüíûõ ÷àñòîò ïðîñòðàíñòâåííîãî Ôóðüå-ðàçëîæåíèÿ ñðåäû 2,5D âäîëü îñè ïîñòî-
ÿííûõ ñâîéñòâ Y ;
2) îáðàòíîå ïðåîáðàçîâàíèå Ôóðüå íàáîðà 2D-ñåéñìîãðàìì, ñîîòâåòñòâóþùèõ
îòäåëüíûì ÷àñòîòàì, äëÿ ïîëó÷åíèÿ 3D-ñåéñìîãðàìì â îáû÷íîì ïðîñòðàíñòâå;
3) ðåïëèêàöèÿ (ðàçìíîæåíèå) 3D-ñåéñìîãðàìì îò îäíîé ëèíèè èñòî÷íèêîâ äëÿ
ïîëó÷åíèÿ ïîëíîöåííîé 3D-ñåòè íàáëþäåíèé.
Òðåòüÿ çàäà÷à — ôèëüòðàöèÿ ïîâåðõíîñòíûõ âîëí ðýëååâñêîãî òèïà â òðåõêîì-
ïîíåíòíûõ ñåéñìè÷åñêèõ íàáëþäåíèÿõ (Ô3Ñ) — ïðåäñòàâëÿåò ñîáîé òèïè÷íóþ
ïðîöåäóðó ëîêàëüíîé îáðàáîòêè äàííûõ. Íà âõîä ïîäàþòñÿ ñåéñìîãðàììû ñ çà-
ïèñüþ äâóõ ãîðèçîíòàëüíûõ (ïðîäîëüíîé è ïîïåðå÷íîé) è îäíîé âåðòèêàëüíîé
êîìïîíåíòîâ. Ïîäàâëåíèå âîëíû Ðýëåÿ îáåñïå÷èâàåòñÿ âûïîëíåíèåì â ñêîëüçÿùåì
îêíå íà êàæäîé ìíîãîêîìïîíåíòíîé çàïèñè (íàáîðå èç òðåõ ñîîòâåòñòâóþùèõ
òðàññ ñåéñìîãðàìì êîìïîíåíòîâ) ñëåäóþùåé ïðîöåäóðû [4].
1. Ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèöû ðàçìåðà N � 3 , òðè âåêòîð-ñòîëáöà êîòî-
ðîé ñîäåðæàò ñîîòâåòñòâóþùèå ïî âðåìåíè ôðàãìåíòû òðàññ òðåõ êîìïîíåíòîâ çà-
ïèñè. Ïî òðåì ñîáñòâåííûì çíà÷åíèÿì � � �1 2 3� � âû÷èñëÿåòñÿ ïàðàìåòð
e t( ) ( )( )�
� � � �
1
2
3
2
2
2
3
2 . Çíà÷åíèå e t( ) , ïðåâûøàþùåå ïîðîã, ÿâëÿåòñÿ ïðèçíà-
êîì èñêàæåíèÿ ðýëååâñêèìè âîëíàìè.
2. Îáðàáîòêà èñêàæåííûõ ó÷àñòêîâ íèçêî÷àñòîòíûì ôèëüòðîì.
Êàæäàÿ èç ïåðå÷èñëåííûõ çàäà÷ îáëàäàåò ñâîéñòâàìè, õàðàêòåðíûìè äëÿ øè-
ðîêîãî êëàññà àëãîðèòìîâ, èíòåíñèâíî èñïîëüçóåìûõ â ñåéñìîðàçâåäêå, è åñòåñò-
âåííûì ïàðàëëåëèçìîì.
Îáîñíîâàíèå ðàñïàðàëëåëèâàíèÿ è âûáîð ïëàòôîðìû. Ðåøåíèå î ðàçðà-
áîòêå ïàðàëëåëüíîé ïðîãðàììû èëè î ðàñïàðàëëåëèâàíèè ïîñëåäîâàòåëüíîé ïðî-
ãðàììû ÷àñòî ïðèíèìàåòñÿ èíòóèòèâíî. Ìåæäó òåì ýòîò âîïðîñ äîñòàòî÷íî ñëîæåí
è òðåáóåò ãëóáîêîãî àíàëèçà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 67
Âî-ïåðâûõ, èíæåíåðû ñêëîííû ïåðåîöåíèâàòü êîììåð÷åñêóþ ïðèâëåêàòåëü-
íîñòü áûñòðûõ âû÷èñëåíèé. Âî ìíîãèõ ñëó÷àÿõ ïðèîáðåòåíèå, óñòàíîâêà, ñîäåðæà-
íèå è îáñëóæèâàíèå ñïåöèàëüíîé âû÷èñëèòåëüíîé òåõíèêè äëÿ óñêîðåíèÿ ëèøü íå-
ñêîëüêèõ ïðîãðàìì îêàçûâàþòñÿ íåöåëåñîîáðàçíûìè ñ òî÷êè çðåíèÿ ëèö,
ïðèíèìàþùèõ ðåøåíèÿ.
Âî-âòîðûõ, èíòóèòèâíàÿ îöåíêà ïîòåíöèàëüíîãî âûèãðûøà â ïðîèçâîäèòåëü-
íîñòè ÷àñòî áûâàåò çàâûøåíà. Çàêîí Àìäàëà (1967) âûðàæàåò ýòîò ôåíîìåí ìàòå-
ìàòè÷åñêè. Ïðè èäåàëüíîì ðàñïàðàëëåëèâàíèè äîëè âû÷èñëåíèÿ � íà N ïðîöåññîð-
íûõ ýëåìåíòîâ (ÏÝ) óñêîðåíèå ñîñòàâèò
S
N
N �
1
1
1
1( )� � � �
. (3)
Çíà÷åíèå ýòîãî çàêîíà ïðîÿñíÿåò ïîäñòàíîâêà ÷èñåë: óñêîðåíèå âû÷èñëåíèÿ â
ðåçóëüòàòå èäåàëüíîãî ðàñïàðàëëåëèâàíèÿ 95% ðàñ÷åòîâ íà 20 ÏÝ ñîñòàâëÿåò âñåãî
1/(0,05+0,95/20)=10,26. Íà ïðàêòèêå ýôôåêòèâíîñòü ïàðàëëåëüíûõ âû÷èñëåíèé îêà-
çûâàåòñÿ åùå íèæå. Ïðîñòîé ýêñïåðèìåíò (çàïóñê ÷åòûðåõ íåçàâèñèìûõ ýêçåìïëÿ-
ðîâ ïîñëåäîâàòåëüíîé ïðîãðàììû Ì2,5D íà ñîâðåìåííîì ÏÊ, îñíàùåííîì äâóìÿ
äâóõÿäåðíûìè ïðîöåññîðàìè) ïîêàçàë óñêîðåíèå âñåãî â ïîëòîðà ðàçà ïî ñðàâíå-
íèþ ñ èõ ïîñëåäîâàòåëüíûì âûïîëíåíèåì. Äëÿ äâóõ ýêçåìïëÿðîâ ïðîãðàììû âûèã-
ðûø âðåìåíè ñîñòàâèë 25%. Íàêîíåö, ðàñïàðàëëåëèâàíèå îáû÷íî ñâÿçàíî ñ íàêëàä-
íûìè ðàñõîäàìè íà êîììóíèêàöèþ è ñèíõðîíèçàöèþ, äîïîëíèòåëüíî
çàìåäëÿþùèìè ïàðàëëåëüíîå ðåøåíèå îäíîé çàäà÷è ïî ñðàâíåíèþ ñ ðåøåíèåì
íåñêîëüêèõ íåçàâèñèìûõ çàäà÷ íà òîì æå âû÷èñëèòåëå.
Îäíàêî â çàêîíå Àìäàëà èìååòñÿ «ëàçåéêà», îáíàðóæåííàÿ â 1988 ã. Ãóñòàôñî-
íîì è Áàðñèñîì. ×àñòî âðåìÿ íåïàðàëëåëüíûõ âû÷èñëåíèé ïðîãðàììû ìàëî çàâè-
ñèò îò îáúåìà åå ïàðàëëåëüíîé ÷àñòè.  ÷àñòíîñòè, ýòî ïðîèñõîäèò, åñëè íåïàðàë-
ëåëüíóþ ÷àñòü ïðîãðàììû ñîñòàâëÿþò òîëüêî ïîäãîòîâêà âû÷èñëåíèé è îáðàáîòêà
ðåçóëüòàòîâ.  ýòîì ñëó÷àå â êà÷åñòâå ïàðàìåòðà öåëåñîîáðàçíî âçÿòü äîëþ ýòîé
íåïàðàëëåëüíîé ÷àñòè íå â èñõîäíîì, à â ðàñïàðàëëåëåííîì ðàñ÷åòå:
�
�
� �
N
N
�
1
1/
. (4)
Ïðåîáðàçîâàâ ôîðìóëó (3) ñ ó÷åòîì (4), Ãóñòàôñîí è Áàðñèñ ïîëó÷èëè çàêîí,
íàçâàííûé èõ èìåíàìè:
S N N
N S
N
N N N
N
�
( )1
1
� � . (5)
Ïî ôîðìóëå (5) ìîæíî îöåíèòü ïðåäåëüíóþ äîëþ ïîñëåäîâàòåëüíîé ÷àñòè äëÿ
äîñòèæåíèÿ çàäàííîãî óñêîðåíèÿ. Íàïðèìåð, äëÿ 19-êðàòíîãî óñêîðåíèÿ íà 21 ÏÝ
äîëÿ ïîñëåäîâàòåëüíûõ ðàñ÷åòîâ íà êàæäîì ÏÝ íå äîëæíà ïðåâûøàòü
( ) / ( )21 19 21 1
, ÷òî ñîñòàâëÿåò 10%. Ãëàâíûé âûâîä èç çàêîíà Ãóñòàôñîíà–Áàð-
ñèñà: ðàñïàðàëëåëèâàíèå ýôôåêòèâíî ïðè áîëüøîì âðåìåíè ïàðàëëåëüíûõ âû÷èñ-
ëåíèé, ò.å. äëÿ áîëüøèõ çàäà÷. Ðàñïàðàëëåëèâàíèå íà áîëüøîå ÷èñëî ïðîöåññîðîâ
ýôôåêòèâíî òîëüêî äëÿ î÷åíü áîëüøèõ çàäà÷.
Äëÿ çàäà÷ îáðàáîòêè äàííûõ ñåéñìîðàçâåäêè ðåøàþùèì ôàêòîðîì ÿâëÿþòñÿ
÷ðåçâû÷àéíî áîëüøèå îáúåìû è âûñîêàÿ êîììåð÷åñêàÿ ñòîèìîñòü ðåøåíèÿ. Òèïè÷-
íûé îáúåì îäíîêîìïîíåíòíûõ ñåéñìîãðàìì 3D ñîñòàâëÿåò 50–500 ÃÁ íà ìåñòî-
ðîæäåíèå. Çàòðàòû íà ñåéñìîðàçâåäêó íåñîïîñòàâèìû ñî ñòîèìîñòüþ áóðåíèÿ äàæå
îäíîé ñêâàæèíû: 1–5 ìëí äîëë. — íà ñóøå, 10–50 ìëí äîëë. — íà øåëüôå. Îáúåìû
ñåéñìîãðàìì ïîñòîÿííî ðàñòóò çà ñ÷åò ðàñøèðåíèÿ çîíû ðàçìåùåíèÿ ïðèåìíèêîâ,
óâåëè÷åíèÿ ïëîòíîñòè ñåòêè íàáëþäåíèé è ðåãèñòðàöèè 3Ñ/9Ñ. Ïåðñïåêòèâíûìè
äëÿ íåôòåãàçîäîáû÷è ÿâëÿþòñÿ êóïîëüíûå ñòðóêòóðû, âåðòèêàëüíûå çîíû òðåùè-
íîâàòîñòè, ïðèøòîêîâûå çîíû, êîòîðûå èäåíòèôèöèðóþòñÿ ïî ñêîðîñòíîé ìîäåëè.
Äëÿ ïîâûøåíèÿ òî÷íîñòè ïîñòðîåíèÿ ñêîðîñòíîé ìîäåëè íåîáõîäèìî óâåëè÷èâàòü
÷èñëî ïðîãîíîâ îáðàáàòûâàþùèõ ïðîöåäóð çà îãðàíè÷åííîå âðåìÿ ïîäãîòîâêè ê
òåíäåðó èëè âûïîëíåíèÿ ñåðâèñíûõ ðàáîò. Ýòèì îáúÿñíÿåòñÿ ãîòîâíîñòü ñåðâèñ-
íûõ êîìïàíèé íà çíà÷èòåëüíûå èíâåñòèöèè â âû÷èñëèòåëüíóþ òåõíèêó è ïðîãðàì-
ìíîå îáåñïå÷åíèå. Òàêèì îáðàçîì, äëÿ ðàññìàòðèâàåìûõ çàäà÷ íè êîììåð÷åñêàÿ
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
ïðèâëåêàòåëüíîñòü ðàñïàðàëëåëèâàíèÿ, íè ïîòåíöèàëüíûé âûèãðûø â ïðîèçâîäè-
òåëüíîñòè íå âûçûâàþò ñîìíåíèé. Êëàñòåðíûå âû÷èñëåíèÿ óæå ïîâñåìåñòíî
ïðèìåíÿþòñÿ â ñåéñìîðàçâåäêå.
Ïîìèìî öåëåñîîáðàçíîñòè ðàñïàðàëëåëèâàíèÿ âàæíûì âîïðîñîì ÿâëÿåòñÿ âû-
áîð ïàðàëëåëüíîé ïëàòôîðìû äëÿ ðåàëèçàöèè.  áîëüøèíñòâå ñëó÷àåâ âûáîð
äåëàåòñÿ ìåæäó:
– ìíîãîÿäåðíûìè ÏÊ,
– ÏÊ ñ âû÷èñëèòåëÿìè íà âèäåîêàðòàõ (ãðàôè÷åñêèå ïðîöåññîðíûå óñòðîé-
ñòâà (ÃÏÓ)),
– âû÷èñëåíèÿìè â ëîêàëüíûõ ñåòÿõ ÏÊ,
– âû÷èñëåíèÿìè â Èíòåðíåò (ãðèä- è êëàóä-àðõèòåêòóðû).
Äëÿ ÌÄÂ íåîáõîäèìû äâà âðåìåííûõ êóáà ïðè ìèãðàöèè êàæäîé òðàññû. Íà
îäèí èñòî÷íèê ÷àñòî ïðèõîäèòñÿ 1000–4000 êîîðäèíàò ïðèåìíèêîâ ïðè îáùåì ÷èñ-
ëå ðàçíûõ êîîðäèíàò ïðèåìíèêîâ äî 10000. ×èñëî òî÷åê âîçáóæäåíèÿ òàêæå èçìå-
ðÿåòñÿ òûñÿ÷àìè. Íåîäíîêðàòíûé ðàñ÷åò âðåìåííûõ êóáîâ ñóùåñòâåííî ñíèçèë áû
ïðîèçâîäèòåëüíîñòü. Â ñâÿçè ñ ýòèì äëÿ ýôôåêòèâíîé ðåàëèçàöèè ÌÄÂ íåîáõîäè-
ìî îáåñïå÷èòü äîñòóï âñåõ ïðîöåññîâ ê îáùåìó (âîçìîæíî, ðàñïðåäåëåííîìó) õðà-
íèëèùó âðåìåííûõ ôàéëîâ. Òèïè÷íûé îáúåì ôàéëîâ âðåìåííûõ êóáîâ èçìåðÿåòñÿ
òåðàáàéòàìè. Òàêèì îáðàçîì, åäèíñòâåííûé ïðàêòè÷åñêè ïðèåìëåìûé âûáîð âû-
÷èñëèòåëÿ äëÿ çàäà÷è ÌÄ — êëàñòåð ñ âûñîêîñêîðîñòíûì ïîäêëþ÷åíèåì ê
âûñîêîïðîèçâîäèòåëüíîìó äèñêîâîìó õðàíèëèùó (âîçìîæíî, ðàñïðåäåëåííîìó).
 Ô3Ñ îñíîâíûå çàòðàòû âðåìåíè ïðèõîäÿòñÿ íà âû÷èñëåíèå ñèíãóëÿðíûõ
ðàçëîæåíèé. Áîëåå ïðîñòûå îäíîòðàññíûå ïðîöåäóðû, íàïðèìåð ÷àñòîòíàÿ ôè-
ëüòðàöèÿ, ìîãóò âûïîëíÿòüñÿ è íà ÏÊ, íåñìîòðÿ íà îáúåìû äàííûõ, èçìåðÿåìûå
ñîòíÿìè ÃÁ. Ïðèìåíåíèå Èíòåðíåò-âû÷èñëåíèé äëÿ ðàñïàðàëëåëèâàíèÿ Ô3Ñ íåöå-
ëåñîîáðàçíî ââèäó íåäîñòàòî÷íîé äëÿ òàêèõ îáúåìîâ ïîëîñû ïðîïóñêàíèÿ.
Îñòàëüíûå ïëàòôîðìû ïðèãîäíû äëÿ ðåàëèçàöèè è èñïîëüçîâàíèÿ.
Ì2,5D — íàèáîëåå âû÷èñëèòåëüíî ñëîæíàÿ çàäà÷à èç îòîáðàííûõ. Îíà æå ðàáî-
òàåò ñ íàèìåíüøèìè îáúåìàìè äàííûõ — äî íåñêîëüêèõ ñîòåí ìåãàáàéò íà ñàìîì
äëèííîì ïåðâîì øàãå àëãîðèòìà; îáúåì îäíîãî ïåðåäàâàåìîãî ôàéëà — 1–2 ÌÁ. Âîç-
ìîæíî ïðèìåíåíèå Èíòåðíåò-âû÷èñëåíèé äëÿ ðåàëèçàöèè ýòîãî øàãà. Îäíàêî âòîðîé
è îñîáåííî òðåòèé øàãè Ì2,5D ñâîäÿòñÿ ê èíòåíñèâíîé îáðàáîòêå äàííûõ, ÷òî ïðåïÿ-
òñòâóåò èõ âûïîëíåíèþ â ãðèä-ñèñòåìå. Ïðèìåíåíèå ÃÏÓ òàêæå âîçìîæíî, íî îòñó-
òñòâèå íåîáõîäèìûõ äëÿ ýòîé çàäà÷è êîìïëåêñíûõ ÷èñåë â ÑUDA 1.0 è íåäîñòàòî÷íûé
îáúåì ïàìÿòè íà ñòàðûõ êàðòàõ îãðàíè÷èâàþò ðûíîê òàêîãî ðåøåíèÿ.
 öåëîì êðîññ-ïëàòôîðìíàÿ ðåàëèçàöèÿ â MPI îáåñïå÷èâàåò îïòèìàëüíîå íà ñåãî-
äíÿøíèé äåíü ñîîòíîøåíèå ñòîèìîñòü/ýôôåêòèâíîñòü äëÿ âñåõ ïåðå÷èñëåííûõ çàäà÷.
2. ÒÅÕÍÎËÎÃÈß ÏÐÎÅÊÒÈÐÎÂÀÍÈß ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ
 íàñòîÿùåå âðåìÿ íàèáîëåå ïîëíóþ è äåòàëèçèðîâàííóþ òåõíîëîãèþ ðàçðàáîò-
êè ïàðàëëåëüíûõ ïðîãðàìì ïðåäëàãàåò ßçûê øàáëîíîâ ïàðàëëåëüíîãî ïðîãðàì-
ìèðîâàíèÿ (ßØÏÏ) Ìýòòñîíà, Ñýíäåðñà è Ìýññèíãèëë (1999). Êîíöåïöèþ
«øàáëîíîâ ïðîåêòèðîâàíèÿ» â 1977 ã. ïðåäëîæèë Ê. Àëåêñàíäåð äëÿ ñòðîè-
òåëüñòâà è àðõèòåêòóðû. Øàáëîí ïðîåêòèðîâàíèÿ — ýòî îïèñàíèå õîðîøåãî ðå-
øåíèÿ ïîâòîðÿþùåéñÿ ïðîáëåìû â îïðåäåëåííîì êîíòåêñòå. Øàáëîíû ïîçâîëÿ-
þò èñïîëüçîâàòü îïûò ýêñïåðòîâ áîëåå êîíñòðóêòèâíûì è íåôîðìàëüíûì îáðà-
çîì, ÷åì ýêñïåðòíûå ñèñòåìû, â òî æå âðåìÿ îáåñïå÷èâàÿ åäèíîîáðàçíûé
òåðìèíîëîãè÷åñêèé ñëîâàðü äëÿ ïðåäìåòíîé îáëàñòè ïðîåêòèðîâàíèÿ.  ïðîãðàì-
ìíîé èíæåíåðèè øàáëîíû ïðîåêòèðîâàíèÿ âïåðâûå èñïîëüçîâàëè Áåê è Êóííèí-
ãàì (1987). Â 1994 ã. Ãàììà, Õåëì, Äæîíñîí è Âëèññèäåñ ðàçðàáîòàëè øàáëîíû
äëÿ îáúåêòíî-îðèåíòèðîâàííîãî ïðîãðàììèðîâàíèÿ. Ïðèìåíåíèå øàáëîíîâ ïðî-
åêòèðîâàíèÿ äëÿ ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ íà÷àëè ÌàêÄîíàëä, Øåôýð è
Øàôðîí åùå â 1997 ã. [5], îäíàêî èõ ïîäõîä áûë ñóùåñòâåííî óæå, ÷åì
ßØÏÏ [6]. Èäåÿ ßØÏÏ — ôîðìóëèðîâàíèå óíèâåðñàëüíîé òåõíîëîãèè ðàçðà-
áîòêè ïàðàëëåëüíûõ ïðîãðàìì, ñïîñîáíîé âêëþ÷èòü âñå âîçìîæíûå ïîäõîäû
(èçâåñòíûå, à òàêæå òå, êîòîðûå ìîãóò ïîÿâèòüñÿ â áóäóùåì) è âñå ýòàïû ïðîåê-
òèðîâàíèÿ. Äëÿ ýòîãî ñôîðìèðîâàí ðàñøèðÿåìûé íàáîð âçàèìîñâÿçàííûõ äîêó-
ìåíòîâ (øàáëîíîâ), êàæäûé èç êîòîðûõ îïèñûâàåò îäèí èç ïîäõîäîâ ê ðåøåíèþ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 69
ïðîáëåìû ïðîåêòèðîâàíèÿ ïðîãðàììû. Âñå øàáëîíû óñòðîåíû åäèíîîáðàçíî è
ñîñòîÿò èç ðàçäåëîâ «Ïðîáëåìà» (öåëè ýòîãî øàáëîíà), «Êîíòåêñò» (ñâÿçè ñ äðó-
ãèìè øàáëîíàìè), «Ñèìïòîìû» (ïðèçíàêè öåëåñîîáðàçíîñòè èñïîëüçîâàíèÿ øàá-
ëîíà), «Óñèëèÿ» (öåëè îïòèìèçàöèè, îãðàíè÷åíèÿ è ôàêòîðû, êîòîðûå íóæíî
ó÷èòûâàòü), «Ðåàëèçàöèÿ» (îáùàÿ ñõåìà è ïîøàãîâàÿ ïðîöåäóðà ïðèíÿòèÿ ïðî-
åêòíîãî ðåøåíèÿ ïî øàáëîíó) è «Ïðèìåðû». Íî ßØÏÏ — ýòî íå ïðîñòî íàáîð
øàáëîíîâ, à êîìïëåêñíàÿ ìåòîäîëîãèÿ ðàçðàáîòêè ïàðàëëåëüíîé ïðîãðàììû, íà-
÷èíàÿ ñ ïîèñêà ïàðàëëåëüíîñòè è çàêàí÷èâàÿ êîìïèëÿöèåé. Ñîãëàñíî ýòîé ìåòî-
äîëîãèè øàáëîíû ïðîåêòèðîâàíèÿ ðàçäåëåíû íà ÷åòûðå ãðóïïû (â òåðìèíîëîãèè
ßØÏÏ ÷åòûðå «ïðîñòðàíñòâà ïðîåêòèðîâàíèÿ»), ñîîòâåòñòâóþùèå ÷åòûðåì
ïîñëåäîâàòåëüíûì ýòàïàì ðàçðàáîòêè ïàðàëëåëüíîé ïðîãðàììû. Îïèøåì èõ.
• «Ïîèñê ïàðàëëåëüíîñòè» — âêëþ÷àåò øàáëîíû äåêîìïîçèöèè çàäà÷è è äàííûõ,
àíàëèçà çàâèñèìîñòåé äëÿ ñèíõðîíèçàöèè, ãðóïïèðîâêè è óïîðÿäî÷åíèÿ çàäà÷,
ðàçäåëåíèÿ äàííûõ (îñíîâíûå ôàêòîðû — ñëîæíîñòü è ýôôåêòèâíîñòü ðàñïàðàë-
ëåëèâàíèÿ, áàëàíñèðîâêà çàãðóçêè, ìèíèìèçàöèÿ ïðîñòîÿ, ñèíõðîíèçàöèè è êîì-
ìóíèêàöèé, ìàñøòàáèðîâàíèå ïî ÷èñëó ïðîöåññîðîâ);
• «Ñòðóêòóðû àëãîðèòìà» — âêëþ÷àåò äåðåâî øàáëîíîâ ñïîñîáà ðàñïàðàëëåëèâà-
íèÿ, îáåñïå÷èâàþùåå âûáîð ïðèíöèïà îðãàíèçàöèè ïàðàëëåëüíîé ïðîãðàììû
äëÿ íàéäåííîé ïàðàëëåëüíîñòè (ôàêòîðû — áàëàíñèðîâêà çàãðóçêè, ìèíèìèçà-
öèÿ ïðîñòîÿ è ïðîñòîòà ðåàëèçàöèè, îäíàêî êàæäûé øàáëîí âêëþ÷àåò ñâîè êðè-
òåðèè ñîîòâåòñòâèÿ íàéäåííîé ïàðàëëåëüíîñòè);
• «Âñïîìîãàòåëüíûå ñòðóêòóðû» — âêëþ÷àåò øàáëîíû ñòðóêòóð ïðîãðàììû
è äàííûõ ñîãëàñíî âûáðàííûì ñïîñîáàì ðàñïàðàëëåëèâàíèÿ (ôàêòîðû — ýôôåê-
òèâíîå èñïîëüçîâàíèå ïàìÿòè è ñåòåâûõ ðåñóðñîâ, ìèíèìèçàöèÿ íàêëàäíûõ ðàñ-
õîäîâ íà ñèíõðîíèçàöèþ è êîììóíèêàöèþ);
• «Ìåõàíèçìû ðåàëèçàöèè» — âêëþ÷àåò øàáëîíû îòîáðàæåíèÿ ðàçðàáîòàííîãî
ïàðàëëåëüíîãî àëãîðèòìà íà êîíêðåòíóþ ïðîãðàììíî-àïïàðàòíóþ ñèñòåìó ñ èñ-
ïîëüçîâàíèåì ÿçûêîâ ïðîãðàììèðîâàíèÿ, ñðåä ïàðàëëåëüíîãî èñïîëíåíèÿ ïðî-
ãðàìì è ò.ï. ëèáî ïîäáîð ïîäõîäÿùåãî àïïàðàòíî-ïðîãðàììíîãî ðåøåíèÿ
(îñíîâíûå ôàêòîðû — ïðîñòîòà ðåàëèçàöèè, ìèíèìèçàöèÿ íàêëàäíûõ ðàñõîäîâ,
îïòèìèçàöèÿ èñïîëüçîâàíèÿ ïîòåíöèàëà àïïàðàòóðû).
 íàñòîÿùåå âðåìÿ èç âñåõ ïðîñòðàíñòâ ßØÏÏ íàèáîëåå äåòàëèçèðîâàíû «Ïî-
èñê ïàðàëëåëüíîñòè» è «Ñòðóêòóðû àëãîðèòìà».
Ïðîåêòèðîâàíèå ñ ïîìîùüþ ßØÏÏ. Îïèøåì ïðèìåíåíèå ßØÏÏ íà ïðèìå-
ðå ïðîåêòèðîâàíèÿ ïàðàëëåëüíûõ ïðîãðàìì äëÿ òðåõ âûáðàííûõ çàäà÷: ÌÄÂ,
Ì2,5D è Ô3Ñ.
Ïðîåêòèðîâàíèå ïàðàëëåëüíûõ ïðîãðàìì íà÷èíàåòñÿ ñ ïîèñêà ïàðàëëåëèçìà
(ðèñ. 4) ñ ïîìîùüþ øàáëîíà «Äåêîìïîçèöèÿ». Âñå òðè çàäà÷è èìåþò ïðîñòûå àëãîðèò-
ìû (2–3 øàãà) è ðàáîòàþò ñ áîëüøèìè îáúåìàìè îäíîðîäíûõ äàííûõ. Ïàðàëëåëüíàÿ
îáðàáîòêà äàííûõ ÿâëÿåòñÿ åñòåñòâåííûì ñëåäñòâèåì òàêîé ïðèðîäû çàäà÷, ÷òî ïðèâî-
äèò ê ïðèîðèòåòíîìó ðàññìîòðåíèþ øàáëîíà «Äåêîìïîçèöèÿ äàííûõ».
 çàäà÷å Ô3Ñ äàííûå îáðàáàòûâàþòñÿ íåçàâèñèìî. Ìîæíî âûáèðàòü èç íåñêîëü-
êèõ óðîâíåé äåòàëèçàöèè òàêîé îáðàáîòêè ïî îêíàì â ðàìêàõ îäíîé òðàññû, ïî òðàññàì,
ïî áëîêàì òðàññ. Òåîðåòè÷åñêè äîïóñòèìî ðàçäåëÿòü çàäà÷è ïîèñêà è ôèëüòðàöèè ïî-
âåðõíîñòíûõ âîëí, îäíàêî îòëè÷íîå ìàñøòàáèðîâàíèå çàäà÷è ïðè ðåàëüíî âîçìîæíîì
êîëè÷åñòâå âû÷èñëèòåëüíûõ ýëåìåíòîâ äåëàåò òàêóþ äåêîìïîçèöèþ íåöåëåñîîáðàçíîé.
Øàáëîí «Äåêîìïîçèöèÿ»
Øàáëîí «Äåêîìïîçèöèÿ çàäà÷» Øàáëîí «Äåêîìïîçèöèÿ äàííûõ»
Øàáëîí «Àíàëèç çàâèñèìîñòåé»
Øàáëîí «Ãðóïïèðîâêà çàäà÷»
Øàáëîí «Óïîðÿäî÷åíèå ãðóïï çàäà÷»
Øàáëîí «Ðàçäåëåíèå äàííûõ ìåæäó ãðóïïàìè çàäà÷»
Øàáëîí «Àíàëèç íàéäåííîé ïàðàëëåëüíîñòè»
Ðèñ. 4. Ïðîñòðàíñòâî ïðîåêòèðîâàíèÿ «Ïîèñê ïàðàëëåëüíîñòè»
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
 çàäà÷å Ì2,5D ìîäåëèðîâàíèå ðàñïðîñòðàíåíèÿ âîëíû îò êàæäîãî èñòî÷íèêà
íà êàæäîé ïðîñòðàíñòâåííîé ÷àñòîòå íå çàâèñèò îò äðóãèõ. Òèïè÷íîå ÷èñëî èñòî÷-
íèêîâ â çàäà÷å — 100, ÷èñëî ÷àñòîò — îò 10 äî 100.  áîëüøèíñòâå ñëó÷àåâ äåêîì-
ïîçèöèè ïî ÷àñòîòàì è èñòî÷íèêàì äîñòàòî÷íî. Îäíàêî èíîãäà, íàïðèìåð äëÿ ãîðè-
çîíòàëüíî-ñëîèñòîé ñðåäû, ãäå äîñòàòî÷íî îäíîãî èñòî÷íèêà, ÷èñëî ÏÝ ìîæåò îêà-
çàòüñÿ èçáûòî÷íûì. Òîãäà ìîæíî óâåëè÷èòü ñòåïåíü äåêîìïîçèöèè: êàæäûé øàã
êîíå÷íî-ðàçíîñòíûõ âû÷èñëåíèé âêëþ÷àåò îäíîðîäíûé íåçàâèñèìûé ðàñ÷åò áîëü-
øîãî ìàññèâà ïåðåìåííûõ (ñêîðîñòåé ñìåùåíèÿ ïî íàïðÿæåíèÿì, íàïðÿæåíèé —
ïî ñêîðîñòÿì ñìåùåíèÿ). Ïðè ýòîì êîíå÷íî-ðàçíîñòíûå ðàñ÷åòû íåîáõîäèìî ãðóï-
ïèðîâàòü ïî èñòî÷íèêàì/÷àñòîòàì. Âòîðîé è òðåòèé øàãè àëãîðèòìà íàïîìèíàþò
ïî âîçìîæíîñòÿì äåêîìïîçèöèè Ô3Ñ.
 çàäà÷å ÌÄ ìèãðàöèþ (ñóììèðîâàíèå) òðàññ ìîæíî âûïîëíÿòü íåçàâèñèìî.
Áîëåå òîãî, ïðè ìèãðàöèè îäíîé òðàññû ðàñ÷åò íåçàâèñèìî âûïîëíÿåòñÿ âî âñåõ
òî÷êàõ ñðåäû (â ðàìêàõ àïåðòóð), ÷òî ïîçâîëÿåò ïî÷òè íåîãðàíè÷åííî ìàñøòàáèðî-
âàòü ðåøåíèå. Îäíàêî øàãè ðàñ÷åòà âðåìåí ýéêîíàëîì îãðàíè÷èâàþò äåêîìïîçè-
öèþ äâóìÿ óðîâíÿìè, àíàëîãè÷íûìè Ì2,5D. Îäèí ïîòîê ìîæåò ðàññ÷èòûâàòü âðå-
ìåííîå ïîëå èñòî÷íèêà/ïðèåìíèêà èëè ÷àñòü âðåìåííîãî ïîëÿ íà îäíîé ãëóáèíå ñ
ãðóïïèðîâêîé ïî èñòî÷íèêó/ïðèåìíèêó.
Âñå ðàññìàòðèâàåìûå çàäà÷è ìîæíî ðàçáèòü íà çíà÷èòåëüíîå ÷èñëî ïîäçàäà÷.
Îïòèìàëüíóþ ñòåïåíü äåêîìïîçèöèè âûáèðàþò â çàâèñèìîñòè îò îæèäàåìîãî êî-
ëè÷åñòâà ÏÝ è òèïè÷íîãî ðàçìåðà çàäà÷è. Ïðè÷åì øàáëîí «Àíàëèç çàâèñèìîñòåé»
íå äàåò ïîëåçíîé èíôîðìàöèè äëÿ ýòèõ çàäà÷, ïîñêîëüêó îáðàáàòûâàåìûå ôðàãìåí-
òû äàííûõ íåçàâèñèìû âî âñåõ ðàññìîòðåííûõ âàðèàíòàõ äåêîìïîçèöèè. Øàãè ïà-
ðàëëåëüíîé ïðîãðàììû â öåëîì ñîâïàäàþò ñ øàãàìè ïîñëåäîâàòåëüíûõ àëãîðèò-
ìîâ. Øàáëîí «Àíàëèç íàéäåííîé ïàðàëëåëüíîñòè» ïîêàçûâàåò ïðèãîäíîñòü
ðàññìîòðåííûõ âàðèàíòîâ äåêîìïîçèöèè äëÿ ðåàëèçàöèè.
Ïåðåõîäèì â ïðîñòðàíñòâî ñòðóêòóðû àëãîðèòìà (ðèñ. 5). Âûáðàííûé ïðèíöèï
ðàñïàðàëëåëèâàíèÿ äàííûõ â ñî÷åòàíèè ñ èõ ðåãóëÿðíîé ñòðóêòóðîé ïðèâîäèò ê âûáî-
ðó øàáëîíà «Ãåîìåòðè÷åñêàÿ äåêîìïîçèöèÿ». Äåéñòâèòåëüíî, âî âñåõ òðåõ çàäà÷àõ
äàííûå ëåãêî ðàçäåëÿþòñÿ íà áîëüøîå ÷èñëî ïðèìåðíî ðàâíûõ ïî ðàçìåðó áëîêîâ
ñ åñòåñòâåííûì ïîðÿäêîì ñëåäîâàíèÿ ïî íîìåðó òðàññû èëè èñòî÷íèêà/ïðèåìíèêà.
Ïåðåõîäèì â ïðîñòðàíñòâî âñïîìîãàòåëüíûõ ñòðóêòóð (ðèñ. 6). Ðàññìîòðèì
îñíîâíûå øàáëîíû ñòðóêòóðû ïðîãðàììû. Îíà äîëæíà ñîîòâåòñòâîâàòü ðàíåå âû-
áðàííîé ñòðóêòóðå àëãîðèòìà (ñì. ðèñ. 5). Íà åå ýôôåêòèâíîñòü ñóùåñòâåííî âëèÿ-
åò öåëåâàÿ ïëàòôîðìà ðåàëèçàöèè (àðõèòåêòóðà âû÷èñëèòåëÿ è/èëè ñðåäñòâà
ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ).
 øàáëîíå «Îäíà ïðîãðàììà/ìíîãî äàííûõ» îòñóòñòâóåò íåïîñðåäñòâåííîå
âçàèìîäåéñòâèå ìåæäó ïîòîêàìè âû÷èñëåíèé. Åãî îñîáåííîñòü — ðàâíîïðàâèå ÏÝ.
Îòñóòñòâèå óïðàâëÿþùåãî ïîòîêà óâåëè÷èâàåò ïîëåçíóþ ìîùíîñòü íà îäèí ÏÝ,
÷òî ñóùåñòâåííî ïðè èõ îáùåì íåáîëüøîì êîëè÷åñòâå. Íî äëÿ áàëàíñèðîâêè íà-
ãðóçêè ïðè ýòîì øàáëîíå íåîáõîäèìà ñïåöèàëüíàÿ ñòðóêòóðà «Îáùàÿ î÷åðåäü».
Ïðè îòñóòñòâèè òàêîé áàëàíñèðîâêè ïðîèçâîäèòåëüíîñòü ïîëíîñòüþ îïðåäåëÿåò
«ñëàáîå çâåíî».  öåëîì ýòîò øàáëîí îïòèìàëåí äëÿ îäíîðîäíûõ âû÷èñëèòåëåé ñ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 71
Ðèñ. 5. Ïðîñòðàíñòâî ïðîåêòèðîâàíèÿ «Ñòðóêòóðû àëãîðèòìà»
Øàáëîí «Âûáîð ñòðóêòóðû àëãîðèòìà»
íåáîëüøèì ÷èñëîì ÏÝ (íàïðèìåð, ìíîãîÿäåðíûõ/ìíîãîïðîöåññîðíûõ ÏÊ) èëè
ïëîõî ìàñøòàáèðóåìûõ çàäà÷, â êîòîðûõ ïî îäíîìó ÏÝ ïðèõîäèòñÿ íà êàæäûé ïî-
òîê. Èíîãäà ýòîò øàáëîí — åäèíñòâåííûé äîñòóïíûé âûáîð â ñèëó îñîáåííîñòåé
öåëåâîé ïëàòôîðìû (íàïðèìåð, òðàíñïüþòåðû èëè ÃÏÓ).
Øàáëîí «Õîçÿèí — ðàáîòíèêè» îáåñïå÷èâàåò äèíàìè÷åñêóþ áàëàíñèðîâêó çà-
ãðóçêè, îäíàêî óìåíüøàåò ïîëåçíóþ ìîùíîñòü íà îäèí ÏÝ, âûïîëíÿþùèé óïðàâ-
ëÿþùèé ïðîöåññ. Ýòî åäèíñòâåííûé øàáëîí ñòðóêòóðû ïðîãðàììû, óñòîé÷èâûé
ê îòêàçàì è áåçðàçëè÷íûé ê äèñïðîïîðöèè â ïðîèçâîäèòåëüíîñòè ÏÝ.  öåëîì ýòîò
øàáëîí îïòèìàëåí äëÿ âû÷èñëèòåëåé ñ áîëüøèì ÷èñëîì ÏÝ ïðè óñëîâèè õîðîøåãî
ìàñøòàáèðîâàíèÿ çàäà÷è (ìíîãî ïîäçàäà÷ íà îäèí ÏÝ).  íåêîòîðûõ ñëó÷àÿõ ýòîò
øàáëîí — åäèíñòâåííûé äîñòóïíûé âûáîð â ñèëó îñîáåííîñòåé öåëåâîé
ïëàòôîðìû (íàïðèìåð, ãðèä-ñèñòåìû).
 øàáëîíå «Ðàñïàðàëëåëèâàíèå öèêëîâ», êàê è â øàáëîíå «Îäíà ïðîãðàì-
ìà/ìíîãî äàííûõ», îòñóòñòâóåò íåïîñðåäñòâåííîå âçàèìîäåéñòâèå ìåæäó ïîòîêàìè
âû÷èñëåíèé. Ýòîò øàáëîí èäåàëåí äëÿ ðàñïàðàëëåëèâàíèÿ ãîòîâûõ ïîñëåäîâàòåëü-
íûõ ïðîãðàìì â îäíîðîäíûõ âû÷èñëèòåëÿõ ñ îáùåé ïàìÿòüþ. Çäåñü òàêæå èìååòñÿ
âçàèìîñâÿçü ñ öåëåâîé ïëàòôîðìîé, íàïðèìåð OpenMP.
Øàáëîí «Âåòâëåíèå — îáúåäèíåíèå» ïðèìåíèì, êîãäà ÷èñëî ïîòîêîâ ñëîæ-
íûì îáðàçîì ìåíÿåòñÿ â ïðîöåññå âûïîëíåíèÿ çàäà÷è, ÷òî çàòðóäíÿåò ïðèìåíåíèå
áîëåå ïðîñòûõ øàáëîíîâ. Ýòîò øàáëîí ñîîòâåòñòâóåò ðåêóðñèâíûì ñòðóêòóðàì
àëãîðèòìà, à èç ñðåäñòâ ðåàëèçàöèè — PVM.
Øàáëîíû «Îäíà ïðîãðàììà/ìíîãî äàííûõ» è «Õîçÿèí — ðàáîòíèêè» íàèáîëåå
ïîäõîäÿò äëÿ òðåõ âûáðàííûõ çàäà÷ â ñèëó âîçìîæíîé áàëàíñèðîâêè çàãðóçêè ÏÝ.
Îêîí÷àòåëüíûé âûáîð ñòðóêòóðû ïðîãðàììû íåîòäåëèì îò àíàëèçà öåëåâîé ïëàòôîð-
ìû. Äëÿ âàðèàíòà âû÷èñëåíèé â ñåòè ÏÊ ïîä MPI ðåàëèçàöèÿ ñòðóêòóðû äàííûõ
«Îáùàÿ î÷åðåäü» íåñêîëüêî òðóäíåå, ÷åì ðåàëèçàöèÿ ñòðóêòóðû ïðîãðàììû «Õîçÿ-
èí — ðàáîòíèêè», ïîñêîëüêó òðåáóþòñÿ ñïåöèàëüíûå óñèëèÿ íà ñèíõðîíèçàöèþ îáðà-
ùåíèé ê îáùåìó îáúåêòó (íàïðèìåð, ôàéëó) â ïîòåíöèàëüíî ãåòåðîãåííîé ñðåäå.
Îäíàêî âñå òðè çàäà÷è — âû÷èñëèòåëüíî ñëîæíûå è âåðîÿòíîñòü èõ âûïîëíåíèÿ íà
íåáîëüøîì ÷èñëå ïðîöåññîðîâ — íè÷òîæíà. Ïîýòîìó ïîòåðè íà âûäåëåíèå óïðàâëÿþ-
ùåãî ïðîöåññà ïðåíåáðåæèìî ìàëû. Îêîí÷àòåëüíûé âûáîð ñäåëàí â ïîëüçó øàáëîíà
«Õîçÿèí — ðàáîòíèêè» âîïðåêè ðåêîìåíäàöèÿì øàáëîíà íà ðèñ. 6.
Ñòðóêòóðà äàííûõ âçàèìîñâÿçàíà ñî ñòðóêòóðîé ïðîãðàììû è îñîáåííîñòÿìè
ïëàòôîðìû ðåàëèçàöèè. Â ñèëó âûáîðà ïëàòôîðìû MPI è ïîääåðæêè êëàñòåðîâ íå-
îáõîäèìî îðèåíòèðîâàòüñÿ íà «Ðàñïðåäåëåííûé ìàññèâ». Îäíàêî íèçêîóðîâíåâàÿ
äåêîìïîçèöèÿ â Ì2,5D è ÌÄÂ ïðåäïîëàãàåò øàáëîí «Îáùèå äàííûå». Íà ýòîì
ýòàïå íåäîñòàòî÷íî èíôîðìàöèè, ÷òîáû âûáðàòü äëÿ ýòèõ äâóõ çàäà÷ îäèí ãîòîâûé
øàáëîí: öåëåñîîáðàçíû «Ðàñïðåäåëåííûé ìàññèâ» (ìåæäó óçëàìè) è «Îáùèå
äàííûå» (â ðàìêàõ óçëà).
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Øàáëîí «Ñòðóêòóðû ïðîãðàììû»
Ñîîòâåòñòâèå âûáðàííîé
ñòðóêòóðå àëãîðèòìà
Øàáëîí «Îäíà
ïðîãðàììà /
ìíîãî äàííûõ»
Øàáëîí
«Õîçÿèí —
ðàáîòíèêè»
Øàáëîí
«Ðàñïàðàëëåëè-
âàíèå öèêëîâ»
Øàáëîí
«Âåòâëåíèå —
îáúåäèíåíèå»
Ïàðàëëåëüíûå çàäà÷è **** **** **** **
Ðàçäåëÿé è âëàñòâóé *** ** ** ****
Ãåîìåòðè÷åñêàÿ
äåêîìïîçèöèÿ
**** * *** **
Ðåêóðñèÿ ïî äàííûì ** *
Êîíâåéåð *** * ****
Êîîðäèíàöèÿ ïî ñîáûòèÿì ** * ****
Øàáëîí «Ñòðóêòóðû äàííûõ»
Øàáëîí «Îáùèå äàííûå» Øàáëîí «Îáùàÿ î÷åðåäü»
Øàáëîí «Ðàñïðåäåëåííûé
ìàññèâ»
Ðèñ. 6. Ïðîñòðàíñòâî ïðîåêòèðîâàíèÿ «Âñïîìîãàòåëüíûõ ñòðóêòóð»
Ïðîñòðàíñòâî «Ìåõàíèçìû ðåàëèçàöèè» (ðèñ. 7) ñîäåðæèò íàèìåíåå ôîðìàëè-
çîâàííûå øàáëîíû. Ôóíêöèè óïðàâëåíèÿ ïðîöåññàìè èëè íèòÿìè (èõ ñîçäàíèåì,
ïîäñ÷åòîì è èäåíòèôèêàöèåé) âî ìíîãèõ ñëó÷àÿõ âûïîëíÿåò ïëàòôîðìà ðåàëèçà-
öèè. Îíà òàêæå ïðåäîñòàâëÿåò ñðåäñòâà ïðîãðàììèðîâàíèÿ äëÿ ñèíõðîíèçàöèè è
êîììóíèêàöèè ïîòîêîâ âû÷èñëåíèé. Ñòðóêòóðà ïðîãðàììû «Õîçÿèí — ðàáîòíèêè»
èñïîëüçóåò êîììóíèêàöèþ äëÿ ïîñûëêè çàäàíèé ÏÝ «ðàáîòíèêàì» è ïîëó÷åíèÿ èí-
ôîðìàöèè î ðåçóëüòàòàõ âûïîëíåíèÿ ýòèõ çàäàíèé. Íèçêîóðîâíåâàÿ äåêîìïîçèöèÿ
â Ì2,5D è ÌÄÂ óñëîæíÿåò êîììóíèêàöèþ è ñèíõðîíèçàöèþ. Òîãäà ãëàâíûé ïðî-
öåññ ðàññûëàåò çàäàíèÿ òîëüêî ãëàâíûì ïðîöåññàì êàæäîãî óçëà, à óæå ýòè ïðîöåñ-
ñû ðàñïðåäåëÿþò çàäàíèÿ ìåæäó îñòàëüíûìè ïðîöåññàìè óçëîâ.
Øàáëîí «Âûáîð ìåõàíèçìîâ ðåàëèçàöèè»
Øàáëîí «Óïðàâëåíèå» (óïðàâëåíèå ïðîöåññàìè èëè íèòÿìè)
Øàáëîí «Ñèíõðîíèçàöèÿ» (ïîðÿäîê âûïîëíåíèÿ, ðàçäåëÿåìûå ðåñóðñû)
Øàáëîí «Êîììóíèêàöèÿ» (îáìåí èíôîðìàöèåé ìåæäó ïðîöåññàìè èëè íèòÿìè)
Ðèñ. 7. Ïðîñòðàíñòâî ïðîåêòèðîâàíèÿ «Ìåõàíèçìû ðåàëèçàöèè»
Óòî÷íåíèå è âûáîð ïðîåêòà.  èäåàëå ïðîõîäÿ ïîñëåäîâàòåëüíîñòè øàáëî-
íîâ, ðàçðàáîò÷èê ïîëó÷àåò êîìïëåêñíûé ïðîåêò ïàðàëëåëüíîé ïðîãðàììû. Êðîìå
ïåðåõîäîâ ñâåðõó âíèç, ðÿä øàáëîíîâ âêëþ÷àåò óñëîâèÿ âîçâðàòà íà ïðåäûäóùèå
óðîâíè è ïåðåõîäû ïî ãîðèçîíòàëè. Îäíàêî îáùàÿ êàñêàäíàÿ ñõåìà ïðîåêòèðîâà-
íèÿ íå ãàðàíòèðóåò ïîëó÷åíèÿ íàèëó÷øåãî ïðîåêòà, à òîëüêî ïðèãîäíîãî äëÿ ðåàëè-
çàöèè ëîêàëüíî îïòèìàëüíîãî âàðèàíòà. Íàïðèìåð, àëãîðèòì ðàñïàðàëëåëèâàíèÿ,
èäåàëüíî ïîäõîäÿùèé ê çàäà÷å, ìîæåò îêàçàòüñÿ íåýôôåêòèâíûì ïðè ðåàëèçàöèè
íà êîíêðåòíîì êîìïüþòåðå. Íî òàêèå õàðàêòåðèñòèêè, êàê óäåëüíûé îáúåì îïåðà-
òèâíîé ïàìÿòè íà ïðîöåññîð è ñêîðîñòü ìåæïðîöåññîðíîé êîììóíèêàöèè ó÷èòûâà-
þòñÿ òîëüêî íà ïîñëåäíåì ýòàïå. Îäíàêî ïàðàëëåëüíàÿ ïðîãðàììà, ñïðîåêòèðîâàí-
íàÿ ïîä êîíêðåòíóþ ìàøèíó, ìîæåò óòðàòèòü öåííîñòü â ñâÿçè ñ ïîñòóïëåíèåì íî-
âîé òåõíèêè. Ôàêòè÷åñêè ïîñëå ïðîõîæäåíèÿ âñåõ øàãîâ ïðîöåññà ïðîåêòèðîâàíèÿ
ßØÏÏ ìû óïðîñòèëè ïðèíÿòèå ðåøåíèÿ, çíà÷èòåëüíî ñîêðàòèâ ÷èñëî àëüòåðíàòèâ.
Îäíàêî ñëîæíî âûáðàòü åäèíñòâåííûé âàðèàíò íà êàæäîì øàãå. Ïîñêîëüêó òðóäî-
çàòðàòû è âðåìÿ ïðîåêòèðîâàíèÿ ïàðàëëåëüíîé ïðîãðàììû â ðàìêàõ ßØÏÏ íåçíà-
÷èòåëüíû ïî ñðàâíåíèþ ñ îáùèìè òðóäîçàòðàòàìè è âðåìåíåì ðàçðàáîòêè, öåëåñî-
îáðàçíî ïîäãîòîâèòü íåñêîëüêî ïðîåêòîâ, ñðàâíèòü èõ ïî êîìïëåêñíîìó êðèòåðèþ
è òîëüêî ïîñëå ýòîãî âûáðàòü ïðîåêò äëÿ ðåàëèçàöèè. Äëÿ ïðèíÿòèÿ ðåøåíèé â êà-
÷åñòâå ìåòîäà ýêñïåðòíîãî àíàëèçà èñïîëüçóåì ìåòîä àíàëèçà èåðàðõèé (ÌÀÈ) Ñà-
àòè [7], îñíîâàííûé íà äåêîìïîçèöèè öåëè â äåðåâî ôàêòîðîâ (ðèñ 8).
×èñëîâûå/áàëëüíûå/ñëîâåñíûå îöåíêè èëè ìàòðèöû ïàðíîãî ñðàâíåíèÿ âåð-
øèí-áðàòüåâ ïðåîáðàçóþòñÿ ÌÀÈ â îòíîñèòåëüíûå âåñà òåðìèíàëüíûõ âåðøèí —
ýëåìåíòàðíûõ ôàêòîðîâ. Âçâåøèâàíèå àëüòåðíàòèâ îòíîñèòåëüíî êàæäîãî èç ýëå-
ìåíòàðíûõ ôàêòîðîâ òàêæå ïðîèñõîäèò ïóòåì ÷èñëîâîé/áàëëüíîé/ñëîâåñíîé îöåí-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 73
Ðèñ. 8. Äåðåâî ôàêòîðîâ è àëüòåðíàòèâíûå ïðîåêòû ðåàëèçàöèè Ô3Ñ, Ì2,5D è ÌÄÂ
êè èëè ñ èñïîëüçîâàíèåì ìàòðèöû ïîïàðíîãî ñðàâíåíèÿ. Ñâåðòêà âåêòîðà âåñîâ
àëüòåðíàòèâ îòíîñèòåëüíî êàæäîãî èç ýëåìåíòàðíûõ ôàêòîðîâ ñ îáùèì âåêòîðîì
âåñîâ ýòèõ ôàêòîðîâ äàåò èíòåãðàëüíóþ ýêñïåðòíóþ îöåíêó ýòîé àëüòåðíàòèâû.
 êà÷åñòâå êîìïëåêñíîãî êðèòåðèÿ âûáîðà ïðèíÿòà ìèíèìàëüíàÿ èíòåãðàëüíàÿ ýêñ-
ïåðòíàÿ îöåíêà, ò.å. ìèíèìóì ñîâîêóïíûõ èçäåðæåê ðàçðàáîòêè è âûïîëíåíèÿ ïà-
ðàëëåëüíûõ ïðîãðàìì (òàáë. 1–3).
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ò à á ë è ö à 1 . Ýêñïåðòíàÿ îöåíêà ïðîåêòîâ ðåàëèçàöèè Ô3Ñ
Âçâåøèâàíèå ôàêòîðîâ
Îöåíêà
àëüòåðíàòèâ
Âçâåøèâàíèå àëüòåðíàòèâ
Ôàêòîð Áàëë
Âåñ
â êóñòå
Âåñ Ô1 Ô2 Ô3 Ô1 Ô2 Ô3
À 5 0,5
Á 1 0,1
 4 0,4
A1* 5 0,3125 0,15625 1 3 5 0,017361 0,052083 0,086806
A2* 4 0,25 0,125 5 4 1 0,0625 0,05 0,0125
A3 5 0,3125 0,15625
A4* 2 0,125 0,0625 4 1 5 0,025 0,00625 0,03125
Á1 1 0,5 0,05
Á2* 1 0,5 0,05 0 0 1 0 0 0,05
Â1* 3 0,3 0,12 4 2 5 0,043636 0,021818 0,054545
Â2* 5 0,5 0,2 5 3 5 0,076923 0,046154 0,076923
Â3* 2 0,2 0,08 5 5 4 0,028571 0,028571 0,022857
À3à* 2 0,4 0,0625 5 4 1 0,03125 0,025 0,00625
À3á* 3 0,6 0,09375 5 4 1 0,046875 0,0375 0,009375
Á1à* 2 0,4 0,02 0 0 1 0 0 0,02
Á1á* 3 0,6 0,03 2 2 1 0,012 0,012 0,006
Èòîãî: 0,344117 0,279377 0,376506
Ò à á ë è ö à 2 . Ýêñïåðòíàÿ îöåíêà ïðîåêòîâ ðåàëèçàöèè Ì2,5D
Âçâåøèâàíèå ôàêòîðîâ
Îöåíêà
àëüòåðíàòèâ
Âçâåøèâàíèå àëüòåðíàòèâ
Ôàêòîð Áàëë Âåñ â êóñòå Âåñ Ì1 Ì2 Ì3 Ì1 Ì2 Ì3
À 5 0,41666667
Á 5 0,41666667
 2 0,16666667
A1* 4 0,28571429 0,119048 4 5 3 0,039683 0,049603 0,029762
A2* 4 0,28571429 0,119048 3 4 5 0,029762 0,039683 0,049603
A3 1 0,07142857 0,029762
A4* 5 0,35714286 0,14881 1 3 5 0,016534 0,049603 0,082672
Á1 5 0,625 0,260417
Á2* 3 0,375 0,15625 3 1 5 0,052083 0,017361 0,086806
Â1* 4 0,4 0,066667 1 2 5 0,008333 0,016667 0,041667
Â2* 3 0,3 0,05 3 4 1 0,01875 0,025 0,00625
Â3* 3 0,3 0,05 1 2 4 0,007143 0,014286 0,028571
À3à* 1 0,25 0,00744 3 4 5 0,00186 0,00248 0,0031
À3á* 3 0,75 0,022321 3 4 5 0,00558 0,00744 0,009301
Á1à* 5 0,83333333 0,217014 4 1 5 0,086806 0,021701 0,108507
Á1á* 1 0,16666667 0,043403 1 1 1 0,014468 0,014468 0,014468
Èòîãî: 0,281002 0,258292 0,460706
Íåñìîòðÿ íà ðàçëè÷èÿ â õàðàêòåðå òðåõ çàäà÷ ñåéñìîðàçâåäêè, îáùàÿ äëÿ íèõ
ïðîñòàÿ îäíîðîäíàÿ ñòðóêòóðà äàííûõ ðåøàþùèì îáðàçîì âëèÿåò íà ðàñïàðàëëå-
ëèâàíèå. Ãåîìåòðè÷åñêàÿ äåêîìïîçèöèÿ ñî ñòðóêòóðîé «Îäíà ïðîãðàììà / ìíîãî
äàííûõ» èëè «Õîçÿèí — ðàáîòíèêè» îêàçûâàåòñÿ åñòåñòâåííûì âûáîðîì äëÿ ýòèõ
è äðóãèõ ïîäîáíûõ çàäà÷. ÌÀÈ ïîìîãàåò óòî÷íèòü íåêîòîðûå äåòàëè ðåàëèçàöèè
íà îñíîâå ñîáñòâåííûõ îöåíîê ðàçðàáîò÷èêà. Îïûò ðàçðàáîòêè è èñïîëüçîâàíèÿ ïî-
äîáíûõ çàäà÷ íà öåëåâîé ïëàòôîðìå, ïîíèìàíèå àëãîðèòìà è ðåàëüíàÿ îöåíêà îáúå-
ìîâ äàííûõ, êîòîðûå ïðåäñòîèò îáðàáîòàòü ïðîãðàììå, èãðàþò áîëüøóþ ðîëü âî
âçâåøèâàíèè ôàêòîðîâ, ðàíæèðîâàíèè àëüòåðíàòèâ è óòî÷íåíèè äåòàëåé ïðîåêòà.
 íàøåì ñëó÷àå àíàëèç ïîêàçàë ïðåèìóùåñòâà ïðîåêòîâ Ô2, Ì2 è Ä1.
3. ÎÏÒÈÌÈÇÀÖÈß ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ
Ïîëüçîâàòåëè ïàðàëëåëüíûõ êîìïüþòåðîâ ÷àñòî ñòàëêèâàþòñÿ ñ òåì, ÷òî ïðîèç-
âîäèòåëüíîñòü ïðèêëàäíîé ïðîãðàììû îêàçûâàåòñÿ ãîðàçäî íèæå, ÷åì ìîæíî
îæèäàòü, èñõîäÿ èç îöåíêè ïðîèçâîäèòåëüíîñòè êîìïüþòåðà ïî òåñòó Linpack.
Ýòî åñòåñòâåííî, ó÷èòûâàÿ, ñêîëüêî óñèëèé è âðåìåíè îáû÷íî çàòðà÷èâàþò ðàç-
ðàáîò÷èêè íà ïîäáîð ïàðàìåòðîâ Linpack äëÿ îáåñïå÷åíèÿ íàèáîëüøåé ïðîèçâî-
äèòåëüíîñòè êëàñòåðà. Îïòèìèçàöèÿ ïàðàìåòðîâ è ñðåäû âûïîëíåíèÿ êàæäîé
ïðèêëàäíîé ïðîãðàììû òàêæå òðåáóåò ïðîâåäåíèÿ ðÿäà ýêñïåðèìåíòîâ. Ïîñêîëü-
êó äëèòåëüíûå ýêñïåðèìåíòû íà áîëüøèõ êîìïüþòåðàõ — äîðîãîå óäîâîëüñòâèå,
âàæíîå íàïðàâëåíèå òåîðèè âûñîêîïðîèçâîäèòåëüíûõ âû÷èñëåíèé — ïðîãíîçè-
ðîâàíèå ïðîèçâîäèòåëüíîñòè ïðîãðàììû â ðàçíûõ óñëîâèÿõ åå âûïîëíåíèÿ ïî
ðåçóëüòàòàì íåáîëüøîãî ÷èñëà òåñòîâûõ çàïóñêîâ.
Êëþ÷ ê óñêîðåíèþ ïðîãðàììû — îáíàðóæåíèå «óçêîãî ìåñòà», ñ êîòîðûì ñâÿçàíû
îñíîâíûå ïîòåðè ïðîèçâîäèòåëüíîñòè íà îïðåäåëåííîì âû÷èñëèòåëå. Åñëè äîñòóïåí èñ-
õîäíûé òåêñò ïðîãðàììû, òî âðåìåííûå çàòðàòû íà âûïîëíåíèå îïðåäåëåííûõ îïåðàöèé
ìîæíî èçìåðèòü, âñòàâèâ â íåãî èíñòðóêöèè äëÿ ïå÷àòè âðåìåíè âûïîëíåíèÿ îïðåäåëåí-
íûõ ó÷àñòêîâ êîäà. Îäíàêî äëÿ ïîëüçîâàòåëåé êîììåð÷åñêèõ ïðîãðàìì ýòà âîçìîæíîñòü
îòñóòñòâóåò. Îäíèì èç ïåðâûõ ìåòîäîâ èäåíòèôèêàöèè «óçêîãî ìåñòà» ïî êîñâåííûì
ïðèçíàêàì ñòàëà ìåòðèêà Êàðïà–Ôëàòòà (1990):
e
S N
N
N�
1 1
1 1
/ /
/
. (6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 75
Ò à á ë è ö à 3 . Ýêñïåðòíàÿ îöåíêà ïðîåêòîâ ðåàëèçàöèè ÌÄÂ
Âçâåøèâàíèå ôàêòîðîâ
Îöåíêà
àëüòåðíàòèâ
Âçâåøèâàíèå àëüòåðíàòèâ
Ôàêòîð Áàëë Âåñ â êóñòå Âåñ Ä1 Ä2 Ä3 Ä1 Ä2 Ä3
À 5 0,41666667
Á 5 0,41666667
 2 0,16666667
A1* 5 0,3125 0,130208 4 5 3 0,043403 0,054253 0,032552
A2* 4 0,25 0,104167 1 4 5 0,010417 0,041667 0,052083
A3 5 0,3125 0,130208
A4* 2 0,125 0,052083 2 1 4 0,014881 0,00744 0,029762
Á1 3 0,375 0,15625
Á2* 5 0,625 0,260417 5 5 1 0,118371 0,118371 0,023674
Â1* 5 0,5 00,83333 3 2 5 0,025 0,016667 0,041667
Â2* 4 0,4 0,066667 4 3 5 0,022222 0,016667 0,027778
Â3* 1 0,1 0,016667 1 2 4 0,002381 0,004762 0,009524
À3à* 2 0,4 0,052083 1 3 3 0,00744 0,022321 0,022321
À3á* 3 0,6 0,078125 1 2 2 0,015625 0,03125 0,03125
Á1à* 5 0,625 0,097656 4 5 2 0,035511 0,044389 0,017756
Á1á* 3 0,375 0,058594 2 3 3 0,014648 0,021973 0,021973
Èòîãî: 0,3099 0,37976 0,31034
Ôîðìóëà (6) îïèñûâàåò ñóììàðíûå íàêëàäíûå ðàñõîäû îäíîðîäíîãî âû÷èñëåíèÿ
â ïàìÿòè ãîìîãåííîãî êîìïüþòåðà íà ñèíõðîíèçàöèþ è êîììóíèêàöèþ. Îòíîñè-
òåëüíûå çàòðàòû âðåìåíè íà ñèíõðîíèçàöèþ ïî÷òè íå çàâèñÿò îò ÷èñëà ÏÝ (îíè
âîçíèêàþò â ðåçóëüòàòå ðàçëè÷íîãî âðåìåíè âû÷èñëåíèÿ ïîäçàäà÷ ðàçíûìè ïîòî-
êàìè), à çàòðàòû âðåìåíè íà êîììóíèêàöèþ ïðèáëèçèòåëüíî ëèíåéíî ðàñòóò
ñ óâåëè÷åíèåì ÷èñëà ÏÝ â ñèëó îãðàíè÷åííîé ïîëîñû ïðîïóñêàíèÿ êîììóíèêà-
öèîííîé ñðåäû, ïðè÷åì äëÿ N � 1 çàòðàòû íà êîììóíèêàöèþ — íóëåâûå. Èòàê,
ëèíåéíàÿ àïïðîêñèìàöèÿ äèíàìèêè èçìåíåíèÿ ìåòðèêè Êàðïà–Ôëàòòà ñ ðîñòîì
÷èñëà ÏÝ ïîçâîëÿåò ðàçäåëèòü ñòåïåíü âëèÿíèÿ ñèíõðîíèçàöèè è êîììóíèêàöèè
íà ïîòåðè ïðîèçâîäèòåëüíîñòè (òàáë. 4).
Äëÿ îáðàáîòêè ñåéñìè÷åñêèõ äàííûõ ðåøàþùèì ôàêòîðîì ÿâëÿåòñÿ èõ îáúåì.
 áîëüøèíñòâå ñëó÷àåâ ñåéñìè÷åñêèå äàííûå ñëèøêîì âåëèêè, ÷òîáû äåðæàòü èõ â îïå-
ðàòèâíîé ïàìÿòè íà ïðîòÿæåíèè âñåãî âðåìåíè âûïîëíåíèÿ ïðîãðàììû. Â ðåçóëüòàòå
óâåëè÷åíèå ÷èñëà ïðîöåññîðîâ ïðèâîäèò ê ïðîïîðöèîíàëüíîìó ðîñòó èíòåíñèâíîñòè
ôàéëîâûõ îïåðàöèé. «Óçêèì ìåñòîì» îêàçûâàåòñÿ ôàéëîâàÿ ñèñòåìà èëè êàíàë äîñòóïà
ê ôàéëîâîìó õðàíèëèùó, îáëàäàþùèé îãðàíè÷åííîé ïðîïóñêíîé ñïîñîáíîñòüþ.
Ðàññìîòðèì ìîäåëü ñèíõðîííîé ïàðàëëåëüíîé îáðàáîòêè áîëüøîãî îáúåìà
äàííûõ, ïðåäëîæåííóþ â [8]. Ïóñòü N ïðîöåññîâ âûïîëíÿþòñÿ ïàðàëëåëüíî. Ðàáî-
òó êàæäîãî èç íèõ ìîæíî ïðåäñòàâèòü â âèäå ÷åðåäîâàíèÿ ðàñ÷åòîâ ïðîäîëæèòåëü-
íîñòüþ t i
n è îáðàùåíèé ê äàííûì (÷òåíèÿ èëè çàïèñè ôàéëîâ) ïðîäîëæèòåëüíîñ-
òüþ � i
n ñ îæèäàíèåì ïðîäîëæèòåëüíîñòüþ �i
n . Äðóãèå S ïðîöåññîâ èëè óñòðîéñòâ
îáñëóæèâàþò îáðàùåíèÿ ê äàííûì. Êàæäûé èç íèõ æäåò ïîñòóïëåíèÿ çàïðîñà îò îä-
íîãî èç âû÷èñëèòåëüíûõ ïðîöåññîâ, çàòåì âûïîëíÿåò åãî. Ïîêà îáñëóæèâàþùèé ïðî-
öåññ âûïîëíÿåò çàïðîñ, íà íåãî ìîãóò ïîñòóïèòü äðóãèå çàïðîñû. Âñå îíè ñòàâÿòñÿ
â î÷åðåäü íåîãðàíè÷åííîé åìêîñòè è îáñëóæèâàþòñÿ â ïîðÿäêå ïîñòóïëåíèÿ. Êîììó-
íèêàöèîííûå ðàñõîäû, íå îòíîñÿùèåñÿ ê ÷òåíèþ/çàïèñè äàííûõ, ïðåäïîëàãàåì ïðåíå-
áðåæèìî ìàëûìè. Âðåìÿ çàâåðøåíèÿ âñåõ N ïðîöåññîâ, ñîñòîÿùèõ èç i øàãîâ, îáîçíà-
÷èì T t t tN
n N
n n n n n n n
i
n n�
�
max (
..1 0 1 1 1 2 2 2 2
� � � � � �� t n
2
) .
Ïóñòü îáùèå çàòðàòû íà ÷òåíèå/çàïèñü äàííûõ ïîñëåäîâàòåëüíîé ïðîãðàììû
D i1
� � � , â òîì ÷èñëå íà îïåðàöèè ÷òåíèÿ ïðèõîäèòñÿ R1 . Îáîçíà÷èì ñóììàðíîå
âðåìÿ âûïîëíåíèÿ îáÿçàòåëüíûõ äëÿ êàæäîãî ïðîöåññà (íå ðàñïàðàëëåëèâàåìûõ)
îïåðàöèé ÷òåíèÿ � sec
R , çàïèñè — � sec
W , ìàêñèìàëüíîå âðåìÿ îäíîé îïåðàöèè ÷òå-
íèÿ/çàïèñè — �max , ñðåäíåå âðåìÿ îïåðàöèè äîñòóïà ê äàííûì — � �( ) , ñðåäíèé
êâàäðàò — � ��( ) . Âñå ïåðå÷èñëåííûå ïàðàìåòðû ìîæíî íåïîñðåäñòâåííî èçìå-
ðèòü. Îáîçíà÷èì 0 1�
� äîëþ ðàñïàðàëëåëèâàåìîé ÷àñòè ðàñ÷åòîâ . Çíà÷åíèå �
îïðåäåëÿåòñÿ ïî ðåçóëüòàòàì íåáîëüøîãî ÷èñëà ýêñïåðèìåíòîâ ñ ïàðàëëåëüíîé
ïðîãðàììîé. Äîëÿ ðàñ÷åòíîé ÷àñòè ïîñëåäîâàòåëüíîé ïðîãðàììû ñîñòàâëÿåò
�
( ) /T D T1 1 1, äîëÿ ÷òåíèÿ
� R T1 1/ .
Ïîâåäåíèå òàêîé ìîäåëè çàâèñèò îò ñîîòíîøåíèÿ ìåæäó âðåìåíàìè ðàñ÷åòîâ è äîñ-
òóïà ê äàííûì. Ðàññìîòðèì äâà ïðåäåëüíûõ ñëó÷àÿ: ñî ñëàáîé çàãðóçêîé, êîãäà î÷åðåäü çà-
ïðîñîâ íà äîñòóï ê äàííûì îäíîé îïåðàöèè óñïåâàåò «ðàññîñàòüñÿ» äî íà÷àëà ñëåäóþùåé
îïåðàöèè äîñòóïà ê äàííûì (� � i
n
n
i
nt� ��
1
), è ñ ïîëíîé çàãðóçêîé, êîãäà ýòà î÷åðåäü,
âîçíèêíóâ íà ïåðâîì øàãå, ïðîäîëæàåò ðàñòè ( )� ��
i ti
n
n
i
n�
1
.
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ò à á ë è ö à 4 . Ïðèìåðû îïðåäåëåíèÿ «óçêîãî ìåñòà» ïî ìåòðèêå Êàðïà–Ôëàòòà
Âàðèàíò 1 Âàðèàíò 2
N 2 3 4 5 6 7 8 N 2 3 4 5 6 7 8
S N 1,8 2,5 3,1 3,6 4,0 4,4 4,7 S N 1,9 2,6 3,2 3,7 4,1 4,5 4,7
e 0,1 0,1 0,1 0,1 0,1 0,1 0,1 e 0,07 0,075 0,08 0,085 0,09 0,095 0,1
Âûâîä: ñèíõðîíèçàöèÿ äîìèíèðóåò ñðåäè
íàêëàäíûõ ðàñõîäîâ
Âûâîä: êîììóíèêàöèÿ äîìèíèðóåò ñðåäè
íàêëàäíûõ ðàñõîäîâ
Ïðè äóáëèðîâàíèè íà S óñòðîéñòâàõ ðàñïîëîæåíû êîïèè äàííûõ.  ÷àñòíîì
ñëó÷àå öåíòðàëèçàöèè åäèíñòâåííàÿ êîïèÿ äàííûõ óïðàâëÿåòñÿ îäíèì ïðîöåññîì
íà îäíîì óçëå êëàñòåðà èëè â äèñêîâîé ñòîéêå (S � 1). Äëÿ ñòðàòåãèè äóáëèðîâàíèÿ
ïðè ñëàáîé çàãðóçêå âðåìÿ ðàáîòû ïàðàëëåëüíîé ïðîãðàììû ñîñòàâëÿåò
� �
( )T
N
N N
S
S
TN �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�� 1
1 1
1
1
1
�
�
�
�
�
�
�
�
N
N S
N
S
W
R1 1
�
�
�sec
sec
max .
(7)
Ïðè áîëüøîì ÷èñëå ïðîöåññîâ è èíòåíñèâíîì îáðàùåíèè ê ôàéëàì îáñëóæè-
âàíèå ÷òåíèÿ è çàïèñè äàííûõ ïî÷òè ïîëíîñòüþ îïðåäåëÿåò âðåìÿ ðàáîòû
�
�
�
( ) ( )( ) ( )( )T
S
S
T N
S
tN
W
R
�
1 1
1
11 sec
sec
const , (8)
ãäå t t t i
N
const �
0
1 .
Ðàñ÷ëåíåíèå îçíà÷àåò, ÷òî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà äàííûõ õðàíÿòñÿ
íà ðàçíûõ óñòðîéñòâàõ.  ñëó÷àå ðàñ÷ëåíåíèÿ âðåìÿ âûïîëíåíèÿ çàâèñèò îò ðàñïðå-
äåëåíèÿ äàííûõ ìåæäó ôðàãìåíòàìè, íî äóáëèðîâàíèÿ çàïèñè íå òðåáóåòñÿ. Äëÿ
ñëó÷àéíîãî ðàñïðåäåëåíèÿ ìîæíî îöåíèòü ñðåäíåå çíà÷åíèå âðåìåíè ðàáîòû ïðè
ñëàáîé çàãðóçêå êàê
�
� �
� �
( )
( )
( )
T T C D C DN N NS N NS
�
�
�
�
�
�
�
�
�1
2 2
2
2
1
2
1
4 2
, (9)
ãäå C
N
N
N �
�
�
�
�
�
� �1
1
, D
NS
N
T
NS
W R
�
�
�
�
�
�
�
�
�
1
1 1
1
� �
( ) sec sec . Ïðè ïîëíîé çà-
ãðóçêå
�
� �
( ) ( )T
S
T N
S
tN
W R
�
1
11
sec sec
const . (10)
Ýêñïåðèìåíòàëüíîå îïðîáîâàíèå
íà äåñÿòêå ðàçíûõ êëàñòåðîâ ïîêàçàëî
äîâîëüíî âûñîêóþ òî÷íîñòü ôîðìóë
(7)–(10). Îñíîâíîé ïðàêòè÷åñêèé ðå-
çóëüòàò çàêëþ÷àåòñÿ â òîì, ÷òî òî÷êó
ïåðåñå÷åíèÿ òåîðåòè÷åñêèõ ãðàôèêîâ
ñëàáîé è ïîëíîé çàãðóçêè ìîæíî èñ-
ïîëüçîâàòü â êà÷åñòâå ïåðâîãî ïðèáëè-
æåíèÿ îïòèìàëüíîãî äëÿ çàäà÷è êîëè-
÷åñòâà ïðîöåññîðîâ (ðèñ. 9).
Ïîëó÷åííûå îöåíêè ïîçâîëÿþò
òàêæå âçàèìíî íàñòðàèâàòü ïðîãðàì-
ìû è êëàñòåð, ïîäáèðàÿ îïòèìàëüíûå
êîíôèãóðàöèè (ñïîñîá ðàçìåùåíèÿ
äàííûõ, çíà÷åíèÿ S è N ) äëÿ íîâûõ
çàäà÷, èñõîäÿ èç îæèäàåìîãî âðåìåíè
îïåðàöèé äîñòóïà ê äàííûì è âû÷èñëåíèé. Ýòè âðåìåíà ìîæíî ïðèáëèçèòåëüíî
îöåíèòü ïî àíàëîãèè ñ äðóãèìè çàïóñêàìè òîé æå ïðîãðàììû, ïðåäïîëàãàÿ ïðîïîð-
öèîíàëüíîñòü âðåìåíè îáðàáîòêè îáúåìó èñõîäíûõ äàííûõ.
ÇÀÊËÞ×ÅÍÈÅ
Ïàðàëëåëüíûå ïðîãðàììû îáðàáîòêè äàííûõ ñåéñìîðàçâåäêè ðåàëèçîâàíû è ýêñ-
ïëóàòèðóþòñÿ íà êëàñòåðàõ ÑÊÈÒ ñ 2004 ã. Íàêîïëåí íàáîð íåñëîæíûõ ïðèåìîâ
óñêîðåíèÿ çàäà÷ çà ñ÷åò óìåíüøåíèÿ íàãðóçêè íà ôàéëîâóþ ñèñòåìó:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 77
Ðèñ. 9. Ãðàôèê ïðîãíîçíîãî è ôàêòè÷åñêîãî âðåìåíè ÌÄÂ
Âðåìÿ,
ìèí
Êîëè÷åñòâî ïàðàëëåëüíûõ ïðîöåññîâ
– èñïîëüçîâàíèå ëîêàëüíûõ ïàïîê äëÿ âðåìåííûõ ôàéëîâ îòäåëüíûõ
ïðîöåññîâ,
– äóáëèðîâàíèå èíòåíñèâíî èñïîëüçóåìûõ äàííûõ (ñêîðîñòíîé ìîäåëè) íà
óçëàõ,
– ñîçäàíèå è ïðèìåíåíèå èíäåêñíûõ ôàéëîâ äëÿ óñêîðåíèÿ íàâèãàöèè â áîëü-
øèõ ôàéëàõ äàííûõ,
– ðàñïðåäåëåíèå âðåìåííûõ ðàçäåëÿåìûõ ôàéëîâ ïî íåñêîëüêèì ïàïêàì äëÿ
óìåíüøåíèÿ ñêîðîñòè ðàáîòû ñ äèðåêòîðèÿìè.
Àäìèíèñòðàòîðû ÑÊÈÒ ïðîäåëàëè áîëüøóþ ðàáîòó äëÿ ïîâûøåíèÿ ïðîèçâî-
äèòåëüíîñòè àïïàðàòóðû ôàéëîâîãî õðàíèëèùà è ïðîïóñêíîé ñïîñîáíîñòè ñåòè,
îáñëóæèâàþùåé äîñòóï ê äèñêàì, îïòèìèçàöèè ïàðàëëåëüíîé ôàéëîâîé ñèñòåìû è
êåøèðîâàíèÿ âðåìåííûõ ëîêàëüíûõ ïàïîê.  ðåçóëüòàòå ïîëó÷åí çíà÷èòåëüíûé âû-
èãðûø â ïðîèçâîäèòåëüíîñòè ïðîãðàìì îáðàáîòêè ñåéñìè÷åñêèõ äàííûõ. Åñëè â
2005 ã. ÌÄÂ ïëîùàäè 16 êì2/28 ÃÁ íà 16 ÏÝ âûïîëíÿëàñü 12 ñóòîê, à íà 48 ÏÝ —
äàæå 16 ñóòîê, òî â 2009 ã. ÌÄÂ ïëîùàäè 100 êì2/65 ÃÁ âûïîëíÿëàñü 32 ÷. íà
56 ÏÝ, à ïëîùàäü 500 êì2/108 ÃÁ íà 140 ÏÝ áûëà ìèãðèðîâàíà çà òðîå ñóòîê.
Äèñêîâûå îïåðàöèè íå èñïîëüçóþòñÿ è ñîîòâåòñòâåííî íå ó÷èòûâàåòñÿ
Linpack, îäíàêî îíè êðèòè÷åñêè âàæíû äëÿ ìíîãèõ ðåàëüíûõ ïðèëîæåíèé, ñâÿçàí-
íûõ ñ îáðàáîòêîé áîëüøèõ îáúåìîâ äàííûõ, â òîì ÷èñëå äëÿ ðàññìîòðåííûõ çàäà÷
ñåéñìîðàçâåäêè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. T o p 50 ÑÍÃ (http://supercomputers.ru/?page=rating)
2. M a r m a l e v s k y i N . , R o g a n o v Y . , K o s t y u k e v y c h À . , R o g a n o v V . Duplex wave migration
and interferometry for imaging onshore data without angle limitations / 70th EAGE Conf. & Exhibition —
Rome, Italy, 9–12 June 2008, #P273 (http://www.tesseral-geo.com/publications/Marmalevskyi%20-
%20Duplex%20Wave%20Migration%20and%20Interferometry.zip).
3. K o s t y u k e v y c h A . , M a r m a l e v s k y i N . , R o g a n o v Y . , T u l c h i n s k y V . Anisotropic 2.5D–3C
finite-difference modeling / 70th EAGE Conf. & Exhibition. — Rome, Italy, 9–12 June 2008, #P043
(http://www.tesseral-geo.com/publications/Kostyukevych%20-%20Anisotropic%202.5D%20-%203C
%20Finite-difference%20Modeling.zip).
4. Ò ÿ ï ê è í Þ . Ê . , Ò ÿ ï ê è í à Å . Þ . Ïîëÿðèçàöèîííàÿ ôèëüòðàöèÿ ïîâåðõíîñòíûõ âîëí-ïîìåõ íà
ìíîãîêîìïîíåíòíûõ ñåéñìè÷åñêèõ çàïèñÿõ. Îäíîêàíàëüíûé ìåòîä // Ãåîôèçè÷åñêèé æóðíàë. —
2008. — 30, ¹ 3. — Ñ. 14–26.
5. M a c D o n a l d S . , S c h a e f f e r J . , S z a f r o n D . Pattern-based object-oriented parallel programming //
Proc. of ISCOPE’97. — LNCS, 1997. — 1343. — P. 267–274.
6. M a t t s o n T . G . , S a n d e r s B . A . , M a s s i n g i l l B . L . Patterns for Parallel Programming. — Addi-
son-Wesley, 2004. — 355 p.
7. Ñ à à ò è Ò . Ïðèíÿòèå ðåøåíèé. Ìåòîä àíàëèçà èåðàðõèé. — Ì.: Ðàäèî è ñâÿçü, 1993. — 320 ñ.
8. Ï å ð å â î ç ÷ è ê î â à Î . Ë . , Ò ó ë ü ÷ è í ñ ê è é Â . Ã . , Þ ù å í ê î Ð . À . Ïîñòðîåíèå è îïòèìèçàöèÿ
ïàðàëëåëüíûõ êîìïüþòåðîâ äëÿ îáðàáîòêè áîëüøèõ îáúåìîâ äàííûõ // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2006. — ¹ 4. — Ñ. 117–129.
Ïîñòóïèëà 08.07.2009
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
|