Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://asa.guru.ru/papers/pap1.ps Äàòà èçìåíåíèÿ: Sat Aug 1 11:10:13 1998 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 19:51:09 2012 Êîäèðîâêà: IBM-866

a. s. aNTONOW
tEHNOLOGIÓESKIE ASPEKTY ADAPTACII
POSLEDOWATELXNYH PROGRAMM DLQ
MASSIWNOíPARALLELXNYH KOMPX@TEROW
wWEDENIE
wSèE BOLEE [IROKOE RASPROSTRANENIE MASSIWNOíPARALLELXNYH SUPERí---wm I
PERSPEKTIWY DALXNEJ[EGO RAZWITIQ ``TOGO NAPRAWLENIQ ZASTAWLQ@T PROGRAMí
MISTOW RAZRABATYWATX NOWYE TEHNOLOGII SOZDANIQ PROGRAMM DLQ KOMPX@TEí
ROW S PODOBNOJ ARHITEKTUROJ, A NAKOPLENNYJ ZA MNOGIE GODY BOLX[OJ BAGAV
POSLEDOWATELXNYH PROGRAMM OPREDELQET NEOBHODIMOSTX RAZRABOTKI METODOW
ADAPTACII UVE SU]ESTWU@]IH PROGRAMM NA PRINCIPIALXNO NOWU@ ARHITEKí
TURU. pOSKOLXKU KAK TE, TAK I DRUGIE METODY RAZWITY QWNO NEDOSTATOÓNO
DLQ RAZRABOTKI BOLX[IH I SLOVNYH PROGRAMM, ``FFEKTIWNOE ISPOLXZOWANIE
MASSIWNOíPARALLELXNYH SUPERí---wm QWLQETSQ DO SIH POR OÓENX TRUDOèEMKIM
DELOM. dANNAQ STATXQ NA OSNOWE OPYTA ADAPTACII PROGRAMMY FLO52 IZ PAí
KETA Perfect Club DLQ SUPERí---wm CRAY T3D DEMONSTRIRUET WOZNIK[IE NA
``TOM PUTI TRUDNOSTI I PREDLAGAET NEKOTORYE SPOSOBY IH PREODOLENIQ.
mASSIWNOíPARALLELXNAQ SUPERí---wm (CRAY T3D, Intel Paragon, IBM SP2
I DR.) PREDSTAWLQET IZ SEBQ NABOR ODNOTIPNYH PROCESSORNYH ``LEMENTOW (p---)
S RASPREDELèENNOJ PAMQTX@, SOEDINèENNYH KOMMUNIKACIONNOJ SREDOJ. kONEÓNO,
NA PRIMENQEMYE W TOM ILI INOM SLUÓAE METODY OPREDELèENNOE WLIQNIE MOVET
OKAZATX I OKAZYWAET SAMA KONKRETNAQ ARHITEKTURA, A IMENNO, HARAKTERISTIKI
p--- I KOMMUNIKACIONNOJ SREDY, ODNAKO OB]IJ PODHOD OSTAèETSQ ODIN I TOT VE.
bUDEM PREDPOLAGATX, ÓTO IMEETSQ nproc p---, KOTORYE NUMERU@TSQ OT 1 DO
nproc, I, WOZMOVNO, HOSTíMA[INA, KOTORAQ IMEET NOMER 0. mY BUDEM RASSMAí
TRIWATX TOLXKO SPMDíMODELX (Single Program Multiple Data) PARALLELXNOGO
PROGRAMMIROWANIQ, PO``TOMU RASPREDELENIE RABOT PROIZWODITSQ TOLXKO PO NOí
MERU p---. pERESYLKI DANNYH OSU]ESTWLQ@TSQ S POMO]X@ FUNKCIJ TIPA send
I receive, KOTORYE PREDPOLAGA@T, ÓTO OTSYLA@]IJ p--- WYZYWAET FUNKCI@
send I PRODOLVAET WYPOLNENIE PROGRAMMY NEZAWISIMO OT TOGO, GOTOW LI K
19

a.s. aNTONOW
PRIèEMU DRUGOJ p---, A PRINIMA@]IJ p--- WYZYWAET FUNKCI@ receive I W SLUí
ÓAE OTSUTSTWIQ SOOB]ENIQ BLOKIRUETSQ DO EGO PRIHODA.
cELX@ PREOBRAZOWANIQ PROGRAMMY QWLQETSQ MINIMIZACIQ WREMENI EèE ISí
POLNENIQ. dLQ ``TOGO NEOBHODIMO ISPOLXZOWATX OPTIMALXNOE (ZAMETIM, ÓTO
NE WSEGDA MAKSIMALXNOE) ÓISLO p---, MAKSIMALXNO ZAGRUVATX KAVDYJ IZ ISí
POLXZUEMYH p--- I MINIMIZIROWATX KOLIÓESTWO PERESYLOK MEVDU p---. ~ISLO
PROCESSOROW OGRANIÓIWAETSQ KONSTANTOJ nproc, NO NE SOWSEM QSNO, WSEGDA LI
NEOBHODIMO ISPOLXZOWATX WSE DOSTUPNYE p---; OPTIMIZACIQ ZAGRUZKI I PERESYí
LOK DOSTIGAETSQ PRI POMO]I RAZUMNOGO RASPREDELENIQ RABOT MEVDU p---. rAí
BOTY NADO RASPREDELQTX TAK, ÓTOBY PO WOZMOVNOSTI RAWNOMERNO ZAGRUVATX
WSE p---, A TAKVE ÓTOBY NA KAVDOM p--- DEJSTWIQ WYPOLNQLISX PO WOZMOVNOSTI
NAD ODNIM I TEM VE I, VELATELXNO, NEZAWISIMYM OT DRUGIH p--- NABOROM DANí
NYH. eSLI PRI WYPOLNENII PROGRAMMY NA KAKOMíTO IZ p--- MODIFICIRU@TSQ
NEKOTORYE DANNYE, KOTORYE POZDNEE (PO TEKSTU POSLEDOWATELXNOJ PROGRAMMY)
BUDUT ISPOLXZOWATXSQ NA DRUGIH p---, TO ``TI DANNYE DOLVNY BYTX RAZOSLAí
NY WSEM TAKIM p---, PRIÓèEM ``TI p--- DOLVNY BLOKIROWATXSQ DO PRIHODA ``TIH
DANNYH.
~A]E, PRO]E I LOGIÓNEE WSEGO WYDELQ@TSQ W OTDELXNYE CEPOÓKI WYÓIí
SLENIJ (KOTORYE ZATEM RASPREDELQ@TSQ MEVDU p---) ITERACII CIKLOW PROGRAMí
MY, MEVDU KOTORYMI NET ZAWISIMOSTEJ. rASPREDELENIE ITERACIJ OTDELXNOGO
CIKLA NUVNO PROIZWODITX ISHODQ IZ TEH VE SOOBRAVENIJ RAWNOMERNOJ ZAí
GRUVENNOSTI I MINIMIZACII ÓISLA PERESYLOK. pERWOJ CELI NADO PYTATXSQ
DOSTIÓX PRI POMO]I ANALIZA TELA SAMOGO CIKLA (W PROSTEJ[EM SLUÓAE RASí
PREDELQTX ITERACII MOVNO RAWNYMI PORCIQMI), A DLQ DOSTIVENIQ WTOROJ
CELI NEOBHODIM ANALIZ KONTEKSTA --- NA KAKIH p--- RANEE WYÓISLQLISX DANí
NYE, ISPOLXZUEMYE NA TOJ ILI INOJ ITERACII, A, WOZMOVNO, I NA KAKIH p---
BUDUT ISPOLXZOWATXSQ DALEE. dLQ RE[ENIQ ``TOJ ZADAÓI ÓA]E WSEGO OKAZYWAETí
SQ NEDOSTATOÓNYM IZUÓENIE TEKSTA TOJ PODPROGRAMMY, W KOTOROJ WSTRETILSQ
DANNYJ CIKL, PO``TOMU RASPREDELENIE ITERACIJ L@BOGO CIKLA NUVNO PROWOí
DITX S UÓèETOM ANALIZA WSEJ PROGRAMMY. rASPREDELENIE DANNYH PO PROCESSORí
NYM ``LEMENTAM DOLVNO BYTX SOGLASOWANO S RASPREDELENIEM SOOTWETSTWU@]IH
ITERACIJ TAK, ÓTOBY OBESPEÓIWATX IH PRAWILXNOE WYPOLNENIE.
20

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
1 tEHNOLOGIQ ADAPTACII POSLEDOWATELXNYH
PROGRAMM
1.1 oB]IJ PODHOD
wSE DEJSTWIQ PO ADAPTACII POSLEDOWATELXNOJ PROGRAMMY NA MASSIWNOíPARALí
LELXNU@ ARHITEKTURU MOVNO RAZDELITX NA DWA ``TAPA: ``TAP ANALIZA PROGRAMí
MY I ``TAP EèE PREOBRAZOWANIQ. nA ``TAPE ANALIZA NEOBHODIMO SOSTAWITX MODELX
PARALLELXNOGO WYPOLNENIQ PROGRAMMY SO WSEMI NEOBHODIMYMI KOMMUNIKACIí
QMI MEVDU p---. nA OSNOWE ``TOJ MODELI (REALXNO SU]ESTWU@]EJ W WIDE GRAFA
ILI VE ABSTRAKTNOJ) OSU]ESTWLQETSQ WTOROJ ``TAP. nEOBHODIMOSTX RAZRABOTí
KI ÓèETKOJ POSLEDOWATELXNOSTI DEJSTWIJ NA ``TAPE PREOBRAZOWANIQ PROGRAMMY
SLEDUET IZ TOGO, ÓTO OB×èEM PROGRAMMY I OB×èEM NEOBHODIMYH IZMENENIJ MOí
VET BYTX OÓENX BOLX[IM, A POISK O[IBOK W PARALLELXNOJ PROGRAMME --- OÓENX
TRUDOèEMKOE DELO. ---TO OPREDELQET NEOBHODIMOSTX RAZRABOTKI TAKOJ TEHNOLOí
GII PREOBRAZOWANIJ, KOTORAQ OBESPEÓIWALA BY ``KWIWALENTNOSTX POLUÓAEMYH
W HODE RABOTY WARIANTOW ISHODNOJ PROGRAMME. kROME TOGO, MOVET OKAZATXSQ
WAVNYM UVE NA RANNEM ``TAPE OPREDELITX, NASKOLXKO ``FFEKTIWNO REALIZUí
ETSQ NA DANNOJ ARHITEKTURE RAZRABOTANNYJ NA OSNOWE PARALLELXNOJ MODELI
PROGRAMMY ALGORITM EèE WYPOLNENIQ.
1.2 ---TAP ANALIZA PROGRAMMY
1.2.1 pOSLEDOWATELXNOSTX PROWODIMOGO ANALIZA
aNALIZ PROGRAMMY PODRAZDELQETSQ NA STATIÓESKIJ ANALIZ, TO ESTX ANALIZ
TOLXKO TEKSTA PROGRAMMY BEZ EèE WYPOLNENIQ, I ANALIZ DINAMIKI EèE ISPOLí
NENIQ NA ODNOM PROCESSORE MASSIWNOíPARALLELXNOJ SUPERí---wm. pOSKOLXKU
DOSTUP NA MASSIWNOíPARALLELXNYE KOMPX@TERY QWLQETSQ I DOLGO E]èE BUDET
OSTAWATXSQ OGRANIÓENNYM I DOROGIM, WAVNO KAK MOVNO BOLX[U@ ÓASTX ANAí
LIZA PROWODITX STATIÓESKI.
1.2.2 sTATIÓESKIJ ANALIZ
sNAÓALA W PROGRAMME NEOBHODIMO KAKIMíTO OBRAZOM WYDELITX NAIBOLEE WAVí
NYE CIKLY I GNèEZDA CIKLOW, TO ESTX CIKLY, NA WYPOLNENIE KOTORYH ZATRAí
21

a.s. aNTONOW
ÓIWAETSQ NAIBOLX[EE WREMQ. ---TO MOVNO SDELATX, ANALIZIRUQ GRAF WYZOWOW
PODPROGRAMM, CIKLIÓESKIE PROFILI PODPROGRAMM I ZAGOLOWKI CIKLOW (HOTQ
W ZAGOLOWKAH CIKLOW ÓASTO ISPOLXZU@TSQ SIMWOLXNYE PARAMETRY, ZNAÓENIQ
KOTORYH NEIZWESTNY, --- ``TO ZATRUDNQET ANALIZ). wYDELENIE TAKIH CIKLOW,
PRAWDA, NE GARANTIRUET, ÓTO, RASPREDELIW IH ITERACII DAVE OPTIMALXNYM
OBRAZOM, MY DOSTIGNEM POSTAWLENNOJ CELI, TAK KAK WOZMOVNO, NAPRIMER, NAí
LIÓIE W PROGRAMME BOLX[OGO ÓISLA ``MENEE WAVNYH'' CIKLOW, DLQ WYPOLNENIQ
KAVDOGO IZ KOTORYH PRIDèETSQ DELATX OGROMNOE KOLIÓESTWO PERESYLOK. oDNAí
KO, W PERWU@ OÓEREDX NEOBHODIMO WYPOLNITX ANALIZ NAIBOLEE WAVNYH CIKLOW,
TAK KAK BEZ IH ``FFEKTIWNOJ REALIZACII NEWOZMOVNA USPE[NAQ ADAPTACIQ WSEJ
PROGRAMMY.
dALEE DLQ WSEH WYDELENNYH CIKLOW I GNèEZD CIKLOW NEOBHODIMO OPREDELITX
WOZMOVNOSTX PARALLELXNOGO WYPOLNENIQ IH ITERACIJ. tAKAQ WOZMOVNOSTX
OPREDELQETSQ OTSUTSTWIEM ZAWISIMOSTI PO DANNYM MEVDU ITERACIQMI DANNOí
GO CIKLA. dLQ OSU]ESTWLENIQ TAKOJ PROWERKI HORO[IM SREDSTWOM QWLQETSQ
RAZRABOTANNAQ W LABORATORII nELINEJNYH WYÓISLENIJ niwc mgu SISTEMA
ANALIZA PROGRAMM Víray Analyser & Adviser.
~ASTO OTDELXNYJ CIKL IZ GNEZDA CIKLOW SOOTWETSTWUET PEREWYÓISLENI@
ODNOGO IZMERENIQ NEKOTORYH WYREZOK IZ MASSIWOW. w ``TOM SLUÓAE KAVETSQ
PRAWILXNYM RASPREDELQTX W PERWU@ OÓEREDX TOT CIKL IZ GNEZDA, KOTORYJ:
ffl SOOTWETSTWUET IZMERENIQM MASSIWOW, PEREWYÓISLQEMYM W NAIBOLX[EM
ÓISLE NAIBOLEE WAVNYH CIKLOW;
ffl NE IMEET ZAWISIMOSTEJ MEVDU ITERACIQMI;
ffl TREBUET NAIMENX[EGO KOLIÓESTWA PERESYLOK DANNYH;
ffl SOSTOIT IZ WOZMOVNO BOLX[EGO KOLIÓESTWA ITERACIJ.
zATEM NUVNO WYBRATX METOD RASPREDELENIQ ITERACIJ PO WYBRANNOJ RAZí
MERNOSTI CIKLOW TAK, ÓTOBY MINIMIZIROWATX KOLIÓESTWO PERESYLOK WNUTRI
SOOTWETSTWU@]IH PODPROGRAMM. dLQ ``TOGO NADO WYDELQTX TAKIE GRUPPY ITEí
RACIJ, WNUTRI KOTORYH SOSREDOTOÓENO NAIBOLX[EE ÓISLO ZAWISIMOSTEJ PO
DANNYM, TAK, ÓTOBY PRI RAZBIENII ITERACIJ CIKLA NA ``TI GRUPPY RAZRYWAí
LOSX NAIMENX[EE KOLIÓESTWO SWQZEJ I, SLEDOWATELXNO, TREBOWALOSX NAIMENXí
[EE ÓISLO PERESYLOK. nAPRIMER, ESLI WNUTRI CIKLA SU]ESTWUET ZAWISIMOSTX
22

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
MEVDU ITERACIQMI S [AGOM k, TO NAIBOLEE ESTESTWENNO POME]ATX NA ODIN p---
DANNYE DLQ ITERACIJ, OTSTOQ]IH NA k. pRI ``TOM POTREBU@TSQ PERESYLKI
MEVDU p--- TOLXKO DLQ PERWOJ ILI POSLEDNEJ (SOOTWETSTWENNO S NAPRAWLENIEM
ZAWISIMOSTI) ITERACII IZ TAKOJ GRUPPY.
pERED PREOBRAZOWANIEM POSLEDOWATELXNOJ PROGRAMMY POD MASSIWNOíPAí
RALLELXNU@ ARHITEKTURU NEOBHODIMO DLQ KAVDOJ RASPREDELQEMOJ PODPROí
GRAMMY SOSTAWITX SPISKI IMPORTA --- OPISANIQ NABOROW WHODNYH DANNYH,
NEOBHODIMYH NA KAVDOJ ITERACII, ``KSPORTA --- IZMENQEMYH NA KAVDOJ ITERAí
CII RASPREDELQEMOJ RAZMERNOSTI GLOBALXNYH DANNYH I NEOBHODIMYH WNUTRI
DANNOJ PODPROGRAMMY PERESYLOK.
w KAÓESTWE PERWYH DWUH SPISKOW W PROSTEJ[EM SLUÓAE MOVNO WZQTX WSE
PARAMETRY I WSE DANNYE, ISPOLXZUEMYE W COMMONíBLOKAH DANNOJ PODPROí
GRAMMY. oDNAKO ``TO NEWYGODNO, TAK KAK OB×èEM ``TIH PERESYLOK MOVET STATX
OGROMNYM. oBA SPISKA MOVNO ZNAÓITELXNO SOKRATITX S POMO]X@ STATIÓESKOí
GO ANALIZA TELA PODPROGRAMMY. iZ SPISKA IMPORTA NADO ISKL@ÓITX OB×EKTY,
NE WSTREÓA@]IESQ W PRAWYH ÓASTQH OPERATOROW PRISWAIWANIQ I W UPRAWLQ@í
]IH OPERATORAH, A IZ SPISKA ``KSPORTA --- OB×EKTY, NE WSTREÓA@]IESQ W LEWYH
ÓASTQH OPERATOROW PRISWAIWANIQ. dALEE, W SPISKAH IMPORTA I ``KSPORTA NADO
OSTAWITX LI[X TE WYREZKI IZ MASSIWOW, KOTORYE SOOTWETSTWU@T ITERACIQM,
POPADA@]IM NA DANNYJ p--- PO WYBRANNOJ SHEME RASPREDELENIQ ITERACIJ.
kROME TOGO, METODAMI MEVPROCEDURNOGO ANALIZA MOVNO OPREDELITX OB×EKTY,
IZMENQEMYE DANNOJ PODPROGRAMMOJ, NO ZNAÓENIQ KOTORYH NE ISPOLXZU@TSQ
W DRUGIH PODPROGRAMMAH (TAKOE MOVET BYTX, ESLI, NAPRIMER, MASSIW, WHOí
DQ]IJ W COMMONíBLOK, ISPOLXZUETSQ WO WSEH PODPROGRAMMAH TOLXKO KAK
RABOÓIJ). oSTAW[IESQ POSLE ``TIH DEJSTWIJ SPISKI BUDUT QWLQTXSQ SPISKAMI
IMPORTAí``KSPORTA DANNOJ PODPROGRAMMY. eSLI W SOSTAWLENII SPISKA IMPORí
TA WOZMOVNO UKAZATX BOLX[E DANNYH, ÓEM REALXNO NUVNO PODPROGRAMME, I
``TO NE PRIWEDèET K O[IBKAM, TO LI[NIE DANNYE, POPAW[IE W SPISOK ``KSPORTA,
MOGUT ZATERETX NEKOTORYE POLEZNYE DANNYE, ÓTO PRIWEDèET K TRUDNOOTLAWLIí
WAEMYM O[IBKAM.
pERESYLKI WNUTRI DANNOJ PODPROGRAMMY NEOBHODIMY PRI NALIÓII W GRAí
FE ALGORITMA DANNOJ PODPROGRAMMY DUG, SOEDINQ@]IH GIPERPLOSKOSTI, SOOTí
WETSTWU@]IE DWUM RAZNYM ITERACIQM RASPREDELQEMOJ RAZMERNOSTI, W SLUÓAE
ESLI ``TI ITERACII PRI WYBRANNOJ SHEME RASPREDELENIQ ITERACIJ POPADA@T
NA RAZNYE p---. ---TO OTNOSITSQ KAK K ZAWISIMOSTQM ITERACIJ ODNOGO CIKLA,
23

a.s. aNTONOW
TAK I K ZAWISIMOSTQM MEVDU ITERACIQMI RAZNYH CIKLOW. kAK POKAZYWAET
PRAKTIKA, ÓASTO TREBU@TSQ DOPOLNITELXNYE PERESYLKI GRANIÓNYH ``LEMENí
TOW MASSIWOW, ESLI, KONEÓNO, PRI WYBRANNOM METODE RASPREDELENIQ ITERACIJ
ONI NE POPADUT NA NUVNYJ p---. kROME TOGO, PERESYLKI MOGUT POTREBOWATXSQ
PRI IZMENENII ODNIM ILI NESKOLXKIMI p--- NEKOTORYH OB]IH DANNYH, TAKIH,
NAPRIMER, KAK PEREMENNYE, OPREDELQ@]IE USLOWIQ ILI PARAMETRY CIKLOW.
1.2.3 aNALIZ DINAMIKI ISPOLNENIQ PROGRAMMY
dLQ UTOÓNENIQ POLUÓENNOGO NA ``TAPE STATIÓESKOGO ANALIZA SPISKA NAIBOLEE
WAVNYH PODPROGRAMM I GNèEZD CIKLOW POLEZNO PROWESTI TRASSIROWKU ISHODNOí
GO WARIANTA PROGRAMMY, RABOTA@]EGO NA ODNOM p--- MASSIWNOíPARALLELXNOJ
SUPERí---wm ILI VE NA KAKOMíLIBO DRUGOM PROCESSORE S POHOVEJ ARHITEKTUROJ.
dLQ ``TOGO NADO ZAMERITX WREMQ WYPOLNENIQ KAVDOGO WYZOWA KAVDOJ PODPROí
GRAMMY I PROSUMMIROWATX EGO PO WSEM WYZOWAM, WKL@ÓAQ ILI NE WKL@ÓAQ WREí
MENA WYPOLNENIQ WYZYWAEMYH IZ DANNOJ PODPROGRAMMY PODPROGRAMM. pRI
BOLEE DETALXNOJ TRASSIROWKE MOVNO POLUÓITX PODOBNU@ INFORMACI@ DLQ OTí
DELXNYH CIKLOW, FRAGMENTOW I DAVE OTDELXNYH OPERATOROW. wSèE ``TO POZWOLQí
ET UTOÓNITX I DOPOLNITX KARTINU POTENCIALXNOGO PARALLELIZMA PROGRAMMY
I ZNAÓIMOSTI OTDELXNYH FRAGMENTOW.
aNALIZ DINAMIKI WYPOLNENIQ PROGRAMMY POZWOLQET POLUÓITX DIAPAZOí
NY IZMENENIQ PARAMETROW CIKLOW I ZNAÓENIQ USLOWNYH WYRAVENIJ. ---TI ZNAí
ÓENIQ MOGUT WO MNOGOM POMENQTX PREDSTAWLENIQ O SHEME NEOBHODIMYH PREí
OBRAZOWANIJ. eSLI ÓISLO ITERACIJ WYDELENNOGO CIKLA MNOGO MENX[E ÓISLA
p---, TO WOZMOVNO RAZBIENIE WSEGO NABORA p--- NA GRUPPY, W KAVDOJ IZ KOTORYH
ZNAÓENIE UPRAWLQ@]EGO PARAMETRA DANNOGO CIKLA ODINAKOWO, A ZATEM RASPREí
DELQTX E]èE ODIN CIKL MEVDU p--- KAVDOJ GRUPPY. eSLI VE, NAOBOROT, ÓISLO
ITERACIJ MNOGO BOLX[E ÓISLA p---, TO WOZMOVNO RASPREDELENIE ITERACIJ CIí
KLA MEVDU p---. eSLI VE ÓISLO ITERACIJ BLIZKO K ÓISLU p---, TO WOZMOVNA
NEDOZAGRUZKA NEKOTORYH p---. ---TI RASSUVDENIQ, PRAWDA, OTNOSQTSQ K SLUÓA@,
KOGDA ITERACII PRIMERNO RAWNOCENNY PO WREMENI WYPOLNENIQ, LIBO VE KOGDA
WREMQ WYPOLNENIQ RAZNYH ITERACIJ (A, TOÓNEE, SOOTNO[ENIE WREMèEN) ZARANEE
NEIZWESTNO I EGO NE UDAèETSQ OCENITX. eSLI VE WOZMOVNA OCENKA SOOTNO[ENIJ
WREMèEN WYPOLNENIQ RAZNYH ITERACIJ, TO NEOBHODIMO E]èE PYTATXSQ SGRUPPIí
ROWATX ITERACII TAK, ÓTOBY RAWNOMERNO ZAGRUZITX WSE p---.
24

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
1.3 ---TAP PREOBRAZOWANIQ PROGRAMMY
pOSLE OPREDELENIQ METODA RASPREDELENIQ ITERACIJ WYDELENNYH CIKLOW NEOBí
HODIMO PRISTUPITX K POSLEDOWATELXNOMU RASPREDELENI@ IH ITERACIJ S UÓèEí
TOM POLUÓAEMOGO PRI ``TOM USKORENIQ.
1.3.1 dWE SHEMY ADAPTACII PODPROGRAMM
dLQ POSLEDOWATELXNOJ ADAPTACII PODPROGRAMM S RASPREDELQEMYMI ITERACIí
QMI POD MASSIWNOíPARALLELXNU@ ARHITEKTURU PREDLAGA@TSQ DWE SHEMY DEJí
STWIJ:
ffl W SAMOM NAÓALE POROVDAETSQ nproc PROCESSOW, KAVDYJ IZ KOTORYH NEZAí
WISIMO WYPOLNQET WS@ PROGRAMMU DO WYZOWA SOOTWETSTWU@]EJ PODPROí
GRAMMY, ISPOLNQETSQ PODPROGRAMMA S RASPREDELèENNYMI MEVDU p--- ITEí
RACIQMI, POSLE ÓEGO NEOBHODIMO DANNYE, WYÓISLENNYE NA KAVDOM p---,
PEREDATX WSEM OSTALXNYM p--- DLQ PRODOLVENIQ AWTONOMNOJ RABOTY;
ffl IZNAÓALXNO RABOTAET TOLXKO ODIN PROCESS, NAPRIMER, NA HOSTíMA[INE
ILI NA NEKOTOROM WYDELENNOM p---, PERED KAVDYM WYZOWOM SOOTWETSTWUí
@]EJ PODPROGRAMMY INICIIRU@TSQ nproc PROCESSOW, KOTORYM PERESYí
LA@TSQ NEOBHODIMYE DANNYE, ISPOLNQETSQ PODPROGRAMMA S RASPREDELèENí
NYMI MEVDU p--- ITERACIQMI, POSLE ÓEGO NEOBHODIMO DANNYE, WYÓISLENí
NYE NA KAVDOM p---, PEREDATX HOSTíMA[INE ILI WYDELENNOMU p--- I
PRIOSTANOWITX WSE OSTALXNYE PROCESSY.
pREIMU]ESTWOM PERWOJ SHEMY QWLQETSQ OTNOSITELXNAQ PROSTOTA DEJSTí
WIJ I NEOBHODIMOSTX PERESYLATX TOLXKO REZULXTATY WYPOLNENIQ PODPROGRAMí
MY. nO PRI ``TOM NADO OGRADITX WWODíWYWOD, ÓTOBY NE BYLO POPYTOK SRAZU
NESKOLXKIH PROCESSOW RABOTATX S ODNIM FAJLOM, A TAKVE DLQ RABOTY TESTOí
WYH WARIANTOW TREBU@TSQ PERESYLKI OT ODNOGO p--- WSEM OSTALXNYM, ÓTO NADO
DELATX OÓENX OSTOROVNO, ÓTOBY PREDOTWRATITX PREWY[ENIE PROPUSKNOJ SPOí
SOBNOSTI KOMMUNIKACIONNOJ SETI. pRI ``TOM NE NADO ZABOTITXSQ O NEOBHODIí
MYH DLQ WYPOLNENIQ PODPROGRAMMY DANNYH, TAK KAK ONI PRODUBLIROWANY NA
KAVDOM p---.
wTORAQ SHEMA PREDPOLAGAET PERESYLKU DANNYH KAK PERED WYZOWOM PODPROí
GRAMMY, TAK I POSLE NEGO, NO ZATO NE WOZNIKAET PROBLEM S WWODOMíWYWODOM I
25

a.s. aNTONOW
PERESYLKI TREBU@TSQ TOLXKO MEVDU HOSTíMA[INOJ (ILI WYDELENNYM p---) I
p---, A TAKVE UMENX[AETSQ OB]IJ OB×èEM PERESYLOK ZA SÓèET TOGO, ÓTO NE NADO
PERESYLATX OT KAVDOGO p--- KAVDOMU. kROME TOGO, PRI ISPOLXZOWANII WTOROJ
SHEMY PROGRAMMA MOVET ISPOLNQTXSQ POÓTI CELIKOM NA HOSTíMA[INE, ÓTO
BYSTREE, ÓEM NA p---.
w KAVDOM KONKRETNOM SLUÓAE TA ILI INAQ SHEMA MOVET OKAZATXSQ BOLEE
WYGODNOJ. pRI OTNOSITELXNO NEBOLX[OM KOLIÓESTWE WHODNYH DANNYH, NEOBHOí
DIMYH DLQ RASPREDELQEMOJ MEVDU p--- PODPROGRAMMY, I BOLX[OM KOLIÓESTWE
OPERACIJ WWODAíWYWODA W RASSMATRIWAEMOJ PROGRAMME MOVET OKAZATXSQ BOLEE
WYGODNOJ WTORAQ SHEMA, W PROTIWNOM SLUÓAE --- PERWAQ. mY W SWOIH ``KSPERIí
MENTAH ISPOLXZOWALI OBE, NO POSLE T]ATELXNOGO ISSLEDOWANIQ IH DOSTOINSTW
I NEDOSTATKOW OSTANOWILISX NA PERWOJ.
1.3.2 aDAPTACIQ PODPROGRAMM S WYZOWAMI
pOSLEDOWATELXNOE RASPREDELENIE PODPROGRAMM WNUTRI DANNOJ PROGRAMMY
PREDLAGAETSQ PROWODITX ``SNIZU WWERH''. pOSLE RASPREDELENIQ WSEH WYZYWAEí
MYH PODPROGRAMM NADO RASPREDELITX SAMU WYZYWA@]U@ PODPROGRAMMU. pOí
SLE ``TOGO ISÓEZA@T WSE NAKLADNYE RASHODY NA PERESYLKU DANNYH DO I POSLE
WYPOLNENIQ DLQ WYZYWAEMYH PODPROGRAMM 1 , NO TREBU@TSQ ANALOGIÓNYE PEREí
SYLKI DLQ DANNOJ PODPROGRAMMY, A TAKVE MOGUT POQWITXSQ DOPOLNITELXNYE
PERESYLKI, NEOBHODIMOSTX KOTORYH OPREDELQETSQ NA ``TAPE MEVPROCEDURNOGO
ANALIZA. ---TI PERESYLKI POQWLQ@TSQ IZíZA TOGO, ÓTO WOZMOVNO IZMENENIE NEí
KOTORYH DANNYH DLQ ODNOJ IZ WYZYWAEMYH PODPROGRAMM W DRUGOJ. dWIGAQSX
PODOBNYM OBRAZOM, MOVNO RASPREDELITX WS@ PROGRAMMU. ---FFEKTIWNOSTX POí
LUÓENNOJ PROGRAMMY ZAWISIT OT KAÓESTWA PROWODIMOGO ANALIZA, PRAWILXNOí
STI SDELANNYH PREDPOLOVENIJ I SAMOJ STRUKTURY ALGORITMA, KOTORAQ MOVET
OKAZATXSQ STOLX PLOHOJ, ÓTO NE POZWOLIT ``FFEKTIWNO ISPOLXZOWATX PREIMUí
]ESTWA MASSIWNOíPARALLELXNOJ SUPERí---wm.
1 nADO POZABOTITXSQ LI[X O TOM, ÓTOBY, ESLI NUVNO, SKORREKTIROWATX SPISKI IMPORTA I ``KSPORTA
PODPROGRAMMY W SOOTWETSTWII SO SPISKAMI WYZYWAEMYH PODPROGRAMM.
26

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
1.3.3 oCENKA ``FFEKTA OT RASPREDELENIQ
dLQ OCENKI ``FFEKTA OT RASPREDELENIQ TOJ ILI INOJ PODPROGRAMMY NEOBHODIí
MO SRAWNITX WREMQ WYPOLNENIQ ISHODNOGO WARIANTA PROGRAMMY NA ODNOM PROí
CESSORE MASSIWNOíPARALLELXNOJ MA[INY I RASPREDELèENNOGO WARIANTA. eSLI
WREMENA DLQ ISHODNYH TEKSTOW PODPROGRAMM POLUÓENY RANEE NA ``TAPE TRASí
SIROWKI PROGRAMMY, TO OSTAèETSQ POLUÓITX WREMENA DLQ WSEH WARIANTOW RASí
PREDELèENNYH PODPROGRAMM I SRAWNITX IH. nE PRIHODITSQ RASSÓITYWATX NA
TO, ÓTO ISPOLXZOWANIE nproc p--- DAST USKORENIE W BLIZKOE K nproc ÓISLO RAZ,
PO``TOMU NELXZQ ZARANEE SKAZATX, KAKOJ REZULXTAT NADO SÓITATX HORO[IM. oT
SPECIFIKI ZADAÓI SILXNO ZAWISIT, NASKOLXKO HORO[O ONA BUDET RASPARALLELIí
WATXSQ, NO PO KARTINE PARALLELIZMA PROGRAMMY, POSTROENNOJ NA ``TAPE ANAí
LIZA, WSEGDA MOVNO SKAZATX, WESX LI REZERW PARALLELIZMA MY ISPOLXZOWALI.
2 ---KSPERIMENTY S PROGRAMMOJ FLO52
---KSPERIMENTY PROWODILISX NA KOMPX@TERE CRAY T3D, IME@]EM 256 p---.
kAVDYJ p--- PREDSTAWLQET IZ SEBQ PROCESSOR DEC ALPHA S LOKALXNOJ PAí
MQTX@ W 8 mSLOW. dLQ ORGANIZACII PERESYLOK ISPOLXZOWALASX BIBLIOTEKA,
REALIZOWANNAQ NA OSNOWE FUNKCIJ NIVNEGO UROWNQ, OBESPEÓIWA@]AQ POROVDEí
NIE PARALLELXNYH PROCESSOW, PERESYLKI TIPA sendíreceive, SINHRONIZACI@,
PODSÓèET GLOBALXNYH SUMM, POISK GLOBALXNOGO MINIMUMA I MAKSIMUMA I DRUí
GIE WOZMOVNOSTI.
2.1 aNALIZ PROGRAMMY
dLQ OPREDELENIQ STRUKTURY PROGRAMMY [IROKO ISPOLXZOWALISX KAK STATIÓEí
SKIJ ANALIZ, TAK I ANALIZ DINAMIKI ISPOLNENIQ PROGRAMMY. w DALXNEJ[EM
REZULXTATY PRIMENENIQ ``TIH METODOW NE RAZDELQ@TSQ, ÓTOBY DATX BOLEE POLí
NU@ KARTINU PROGRAMMY.
2.1.1 oB]AQ STRUKTURA PROGRAMMY
pROGRAMMA FLO52 IZ PAKETA Perfect Club Benchmarks BYLA WYBRANA W KAí
ÓESTWE MODELXNOJ DLQ PROWEDENIQ ``KSPERIMENTOW PO OTOBRAVENI@ POSLEDOí
WATELXNYH PROGRAMM NA MASSIWNOíPARALLELXNU@ ARHITEKTURU. dANNAQ PROí
27

a.s. aNTONOW
GRAMMA SU]ESTWUET W DWUH WARIANTAH: W MALOM, POLUÓAEMOM PO UMOLÓANI@,
I W BOLX[OM, POLUÓAEMOM S POMO]X@ PODSTANOWKI BOLX[IH ZNAÓENIJ RAZMERí
NOSTEJ WYÓISLQEMYH MASSIWOW. kROME ``TOGO S POMO]X@ ANALOGIÓNOJ PODSTAí
NOWKI E]èE BOLX[IH RAZMERNOSTEJ MASSIWOW BYL POLUÓEN E]èE ODIN WARIANT. w
DALXNEJ[EM ``TI TRI WARIANTA NAZYWA@TSQ SOOTWETSTWENNO ``MALYJ'', ``SREDí
NIJ'' I ``BOLX[OJ''. pOSKOLXKU SHEMA PARALLELXNOGO WZAIMODEJSTWIQ DLQ WSEH
WARIANTOW ODNA I TA VE, A RESURS PARALLELIZMA U BOLX[IH WARIANTOW BOLX[E,
S ROSTOM RAZMERNOSTI RE[AEMOJ ZADAÓI DOLVNO WYRASTI I POLUÓAEMOE USKOí
RENIE. wSE ``KSPERIMENTY PROIZWODILISX NAD MALYM WARIANTOM, TREBU@]IM
MENX[E WREMENI NA WYPOLNENIE I MENX[IJ OB×èEM OPERATIWNOJ PAMQTI, POSLE
ÓEGO IZ POLUÓIW[EJSQ PROGRAMMY ANALOGIÓNOJ PODSTANOWKOJ BYLI POLUÓENY
RASPREDELèENNYE WERSII DLQ BOLX[IH WARIANTOW. rEZULXTATY PO OTDELXNYM
PODPROGRAMMAM PRIWODQTSQ DLQ SREDNEGO WARIANTA, A OKONÓATELXNYE REZULXí
TATY --- PO WSEM TRèEM WARIANTAM.
pROGRAMMA NE TREBUET SLI[KOM BOLX[OGO OB×èEMA PAMQTI I WREMENI WYí
ÓISLENIQ, PO``TOMU SU]ESTWUET WOZMOVNOSTX WYPOLNENIQ ISHODNOGO WARIANTA
FLO52 NA ODNOM PROCESSORE MA[INY T3D BEZ KAKIHíLIBO MODIFIKACIJ. pRI
``TOM WREMQ ISPOLNENIQ SOSTAWLQET 59.8 SEKUNDY DLQ MALOGO WARIANTA, 235.6
SEKUNDY DLQ SREDNEGO I 999.3 SEKUNDY DLQ BOLX[OGO. tAKAQ WOZMOVNOSTX
POZWOLQET LEGKO OCENITX USKORENIE, POLUÓENNOE PRI WYPOLNENII DANNOJ PROí
GRAMMY NA NESKOLXKIH PROCESSORAH, A TAKVE POZWOLQET NE ZABOTITXSQ O PEREí
OPISANII MASSIWOW DANNOJ PROGRAMMY, RASPREDELQEMYH MEVDU p---.
gLAWNOJ WYÓISLITELXNOJ ÓASTX@ W DANNOJ PROGRAMME QWLQETSQ PODPROí
GRAMMA EULER, IZ KOTOROJ W CIKLE WYZYWA@TSQ NAIBOLEE WAVNYE PODPROí
GRAMMY. kAK POKAZAL ANALIZ DINAMIKI ISPOLNENIQ PROGRAMMY, NA WYPOLí
NENIE PODPROGRAMMY EULER WMESTE SO WSEMI WYZYWAEMYMI IZ NEèE PODPROí
GRAMMAMI NA ODNOM p--- PRIHODITSQ OKOLO 88% WREMENI ISPOLNENIQ FLO52.
---TIM PODPROGRAMMAM I BYLO UDELENO PERWOOÓEREDNOE WNIMANIE. pODPROGRAMí
MA EULER I WYZYWAEMYE IZ NEèE PODPROGRAMMY IME@T W OSNOWNOM DOSTATOÓí
NO HORO[U@ STRUKTURU DLQ RASPREDELENIQ PO p---. pOÓTI WSE CIKLY WNUTRI
``TIH PODPROGRAMM IME@T NEZAWISIMYE ITERACII I ODINAKOWYE GRANICY, A
BOLX[INSTWO GNèEZD CIKLOW --- ODINAKOWU@ STRUKTURU. ---TO ZAMETNO OBLEGÓAET
RASPREDELENIE IH ITERACIJ.
w DOSTATOÓNO BOLX[OM ÓISLE PODPROGRAMM DANNOJ PROGRAMMY WSTREÓAETí
SQ WWODíWYWOD, RASPREDELENIE KOTOROGO QWLQETSQ SKOREE ZADAÓEJ RAZRABOTÓIí
28

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
KOW APPARATURY, A NE PROGRAMMISTOW. pO``TOMU RASPREDELENIE TAKIH PODPROí
GRAMM NE PROIZWODILOSX. nA ``TI PODPROGRAMMY SUMMARNO PRIHODITSQ OKOLO
4% WREMENI ISPOLNENIQ WSEJ PROGRAMMY (W MALOM WARIANTE), ÓTO QWLQETSQ ODí
NIM IZ SDERVIWA@]IH FAKTOROW PRI RASPREDELENII WSEJ PROGRAMMY. bOLEE
TOGO, DWE PODPROGRAMMY, OSU]ESTWLQ@]IE WYWOD ZNAÓENIJ RASPREDELèENNYH
MASSIWOW, PRI[LOSX PEREDELATX TAK, ÓTOBY WYWOD W FAJL OSU]ESTWLQLSQ TOLXí
KO ODNIM p---, DLQ ÓEGO EMU NEOBHODIMO PERESLATX DANNYE SO WSEH OSTALXNYH
p---.
dRUGIMI SDERVIWA@]IMI FAKTORAMI QWLQ@TSQ PODSÓèET GLOBALXNYH
SUMM, GLOBALXNYH MAKSIMUMOW I MINIMUMOW, A TAKVE PODPROGRAMMA PSMOO,
DWE ÓASTI KOTOROJ TREBU@T RAZNOGO RASPREDELENIQ DANNYH: PERWAQ --- POí
SLEDOWATELXNAQ PO IZMERENI@ I S WOZMOVNOSTX@ RASPREDELENIQ PO J, WTORAQ
--- POSLEDOWATELXNAQ PO J S WOZMOVNOSTX@ RASPREDELENIQ PO I. kROME TOGO,
WO MNOGIH PODPROGRAMMAH TREBUETSQ DOSTATOÓNO BOLX[OE KOLIÓESTWO OTNOí
SITELXNO NEBOLX[IH PERESYLOK GRANIÓNYH ZNAÓENIJ MASSIWOW. pOSKOLXKU W
TAKIH PERESYLKAH UÓASTWU@T TOLXKO p---, NA KOTORYE POPADA@T GRANIÓNYE
ITERACII, ``TI p--- ZAMETNO SDERVIWA@T WSE OSTALXNYE.
pODPROGRAMMY COLLC I ADDX OSU]ESTWLQ@T PERERASPREDELENIE DANí
NYH MEVDU p--- PRI PEREHODE OT BOLX[EJ RAZMERNOSTI K MENX[EJ (PODPROí
GRAMMA COLLC) I NAOBOROT (ADDX). pERESYLKI W ``TIH PODPROGRAMMAH OKAí
ZALISX WESXMA SLOVNYMI I NEREGULQRNYMI I TAKVE QWILISX SDERVIWA@]IM
FAKTOROM PRI RASPREDELENII WSEJ PROGRAMMY.
2.1.2 wYBOR RAZMERNOSTI DLQ RASPREDELENIQ
iSHODQ IZ PEREÓISLENNYH WO WTOROJ ÓASTI TREBOWANIJ, NADO WYBRATX RAZí
MERNOSTX DLQ PERWOOÓEREDNOGO RASPREDELENIQ SOOTWETSTWU@]IH EJ ITERACIJ
MEVDU p---. cIKL PO J SRAZU OTBRASYWAETSQ --- DLQ NEGO POTREBOWALOSX BY
SLI[KOM BOLX[OE ÓISLO PERESYLOK, POSKOLXKU WO MNOGIH MESTAH NA JíJ ITERAí
CII TREBU@TSQ DANNYE, WYÓISLENNYE RANEE NA DRUGIH ITERACIQH, DA I WYQSí
NENNOE ``KSPERIMENTALXNO ÓISLO ITERACIJ SLI[KOM MALO --- OT 5 DO 33 (MALYJ
WARIANT). cIKL PO N HORO[ TEM, ÓTO PRI RASPREDELENII EGO ITERACIJ NE POí
TREBUETSQ WOOB]E NIKAKIH PERESYLOK DANNYH, NO ON OÓENX KOROTKIJ --- WSEGO 4
ITERACII, PO``TOMU POSLE NEGO PRI[LOSX BY RASPREDELQTX E]èE ODIN CIKL, ÓTO
SILXNO USLOVNILO BY PROGRAMMU; KROME TOGO, NE WO WSE CIKLIÓESKIE GNèEZDA
29

a.s. aNTONOW
``TOJ PROGRAMMY WHODIT CIKL PO N. pO``TOMU SAMYM PODHODQ]IM DLQ RASPREí
DELENIQ WYGLQDIT CIKL PO I. kOLIÓESTWO ITERACIJ ``TOGO CIKLA MENQETSQ OT
21 DO 161 (W MALOM WARIANTE), A PERESYLKI PO ``TOJ RAZMERNOSTI TREBU@Tí
SQ W OTNOSITELXNO NEMNOGIH MESTAH. kONEÓNO, PRI RASPREDELENII ITERACIJ
TOLXKO CIKLA PO I MY ISPOLXZUEM NE WESX RESURS PARALLELIZMA, ZALOVENNYJ W
PROGRAMME, NO DOPOLNITELXNOE RASPREDELENIE ITERACIJ CIKLOW PO J (I, MOVET
BYTX, PO N) PRIWELO BY K USLOVNENI@ TREBUEMYH PERESYLOK, ÓTO SDELALO BY
ZNAÓITELXNO BOLEE TRUDOèEMKIM PROCESS ADAPTACII DANNOJ PROGRAMMY.
2.1.3 wYBOR METODA RASPREDELENIQ ITERACIJ
mETOD RASPREDELENIQ ITERACIJ W DANNOM SLUÓAE DOSTATOÓNO OÓEWIDEN --- BOLXí
[INSTWO PERESYLOK OSU]ESTWLQETSQ MEVDU SOSEDNIMI ITERACIQMI, PO``TOMU
NAIBOLEE ESTESTWENNYM KAVETSQ POME]ATX NA ODIN p--- KAK MOVNO BOLX[E POí
SLEDOWATELXNYH ITERACIJ. bYLO RE[ENO RASPREDELQTX ITERACII PO WOZMOVí
NOSTI RAWNYMI POSLEDOWATELXNYMI PORCIQMI MEVDU WSEMI p---. kOLIÓESTWO
ITERACIJ CIKLA PO I DELITSQ NA KOLIÓESTWO p---, I KAVDYJ p--- POLUÓAET PORí
CI@ IZ TAKOGO KOLIÓESTWA POSLEDOWATELXNYH ITERACIJ ILI NA ODNU BOLX[E,
ESLI PRI DELENII POLUÓAETSQ NENULEWOJ OSTATOK. pRI ``TOM NESKOLXKIM POí
SLEDNIM p--- MOVET NE DOSTATXSQ NI ODNOJ ITERACII, NO ZATO MINIMIZIRUETSQ
KOLIÓESTWO PERESYLOK, A WREMQ ISPOLNENIQ OPREDELQETSQ TEM VE KOLIÓESTWOM
ITERACIJ, KOTOROE POLUÓILOSX BY PRI POPYTKE ÓASTIÓNO ZAGRUZITX POSLEDí
NIE p--- ZA SÓèET PREDYDU]IH. kROME POSLEDNIH, W NEKOTORYH SLUÓAQH, NAPRIí
MER, KOGDA ITERACII CIKLA NAÓINA@TSQ NE S 1, NESKOLXKO NEDOZAGRUVENNYM
MOVET OKAZATXSQ PERWYJ p---. oDNAKO TAKAQ NEDOZAGRUZKA, ESTESTWENNO, PREDí
POÓTITELXNEE PERERASPREDELENIQ DANNYH DLQ DOSTIVENIQ BOLEE RAWNOMERNOJ
ZAGRUVENNOSTI.
2.2 pOSLEDOWATELXNOE RASPREDELENIE OSNOWNYH PODPROí
GRAMM
rEZULXTATY POSLEDOWATELXNOGO RASPREDELENIQ RASSMATRIWAEMYH NIVE PODí
PROGRAMM PRIWEDENY W SLEDU@]EM PUNKTE, ZDESX VE OBSUVDA@TSQ PROWODIWí
[IESQ PREOBRAZOWANIQ I WSTRETIW[IESQ TRUDNOSTI. sLEDU@]IJ RISUNOK DEí
MONSTRIRUET SHEMY WZAIMODEJSTWIQ PROCESSOROW, WSTRETIW[IESQ W OBSUVDAí
30

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
EMYH NIVE PODPROGRAMMAH.
@
@ @R
@
@ @R
@
@ @R
@
@ @R
...
eflux
? psmoo1
1 2 3 N 1 2 3 N
Q Q Qs
Q
Q Qs
Q Q Qs
...
¦
¦
¦
¦
¦
¦
¦
¦
¦
¦9
\Gamma
\Gamma
\Gamma\Psi
\Phi
\Phi
\Phi
\Phi
\Phi‹
XXXXXXXXX Xz
@
@ @R
H H H H Hj
1 2 3 N
...
...
psmoo2
XXXXXXXXX Xz
¦
¦
¦
¦
¦
¦
¦
¦
¦9
@
@ @R
H H H H Hj
\Gamma
\Gamma
\Gamma\Psi
@
@ @R
P P P P P P Pq
i
i
i
i
i
i
i)
\Phi
\Phi
\Phi
\Phi
\Phi‹
...
1 2 3 N
psmoo3
\Phi
\Phi
\Phi
\Phi
\Phi‹
\Gamma
\Gamma
\Gamma\Psi
H H H H Hj
XXXXXXXXX Xz
¦
¦
¦
¦
¦
¦
¦
¦
¦9
@
@ @R
H H H H Hj
\Gamma
\Gamma
\Gamma\Psi
@
@ @R
P P P P P P Pq
i
i
i
i
i
i
i)
\Phi
\Phi
\Phi
\Phi
\Phi‹
1 2 3 N
\Phi
\Phi
\Phi
\Phi
\Phi‹
\Gamma
\Gamma
\Gamma\Psi
H H H H Hj
XXXXXXXXX Xz
¦
¦
¦
¦
¦
¦
¦
¦
¦9
@
@ @R
H H H H Hj
\Gamma
\Gamma
\Gamma\Psi
@
@ @R
P P P P P P Pq
i
i
i
i
i
i
i)
\Phi
\Phi
\Phi
\Phi
\Phi‹
\Phi
\Phi
\Phi
\Phi
\Phi‹
\Gamma
\Gamma
\Gamma\Psi
H H H H Hj
...
...
...
...
...
...
psmoo4
?
wERTIKALXNYE LINII NA RISUNKE POKAZYWA@T POSLEDOWATELXNYE WYÓISLEí
NIQ NA SOOTWETSTWU@]EM p---, STRELKI IZOBRAVA@T NEOBHODIMYE PERESYLKI,
OSI POKAZYWA@T NAPRAWLENIQ POSLEDOWATELXNOSTI WYÓISLENIJ.
rASPREDELENIE ITERACIJ PODPROGRAMM PO WYBRANNOMU IZMERENI@ BYLO
NAÓATO S PODPROGRAMMY EFLUX. nA WYPOLNENIE NA ODNOM p--- ``TOJ NEBOLXí
[OJ PODPROGRAMMY, SOSTOQ]EJ IZ PQTI CIKLIÓESKIH GNèEZD, TRATITSQ OKOLO
28% WREMENI ISPOLNENIQ WSEJ PROGRAMMY. dLQ RASPREDELENIQ CIKLOW PO I
31

a.s. aNTONOW
W DANNOJ PODPROGRAMME NEOBHODIMY PERESYLKI ÓASTI MASSIWA S POSLEDNEJ
ITERACII, POPAW[EJ NA NEKOTORYJ p---, NA SLEDU@]IJ p--- (SM. RISUNOK). pOí
SLE WYPOLNENIQ PODPROGRAMMY NEOBHODIMO WYÓISLQEMYE W NEJ NA KAVDOM
p--- REZULXTATY PERESLATX WSEM OSTALXNYM p---. ---TO VE OTNOSITSQ I KO WSEM
RASSMATRIWAEMYM DALEE PODPROGRAMMAM. pOSKOLXKU WNUTRI DANNOJ PODPROí
GRAMMY TOLXKO W ODNOM MESTE TREBU@TSQ OTNOSITELXNO NEBOLX[IE PO OB×èEMU
PERESYLKI, NA DANNOJ PODPROGRAMME UDAèETSQ DOSTIÓX DOSTATOÓNO HORO[EGO
USKORENIQ.
w PODPROGRAMME DFLUX DOPOLNITELXNO K UVE OPISANNYM PERESYLKAM
DOBAWLQ@TSQ MNOGOÓISLENNYE PERESYLKI GRANIÓNYH ZNAÓENIJ MASSIWOW I PEí
RESYLKI ÓASTI DANNYH, WYÓISLENNYH NA IíJ ITERACII, NA I\Gamma2í@ ITERACI@.
pOSKOLXKU PODPROGRAMMA DFLUX TREBUET POÓTI TAKOGO VE SUMMARNOGO WREí
MENI ISPOLNENIQ, KAK I EFLUX, HORO[EE EèE RASPREDELENIE NE MENEE WAVNO,
ÓEM RASPREDELENIE EFLUX, NESMOTRQ NA SLOVNOSTI, SWQZANNYE S BOLX[IM
OB×èEMOM PODPROGRAMMY I BOLX[IM KOLIÓESTWOM TREBUEMYH PERESYLOK. uSKOí
RENIE, POLUÓENNOE NA DANNOJ PODPROGRAMME, SRAWNIMO S USKORENIEM, POLUÓENí
NYM NA PODPROGRAMME EFLUX.
nAMNOGO SLOVNEE SITUACIQ OBSTOIT S PODPROGRAMMOJ PSMOO. dELALOSX
NESKOLXKO POPYTOK EèE ``FFEKTIWNOJ REALIZACII, POSKOLXKU UVE POSLE PERWYH
``KSPERIMENTOW STALO QSNO, ÓTO ``TA PODPROGRAMMA WO MNOGOM BUDET QWLQTXí
SQ UZKIM MESTOM PRI RASPREDELENII FLO52 IZíZA NEOBHODIMOSTI RAZLIÓNOGO
RASPREDELENIQ DANNYH DLQ DWUH ÓASTEJ DANNOJ PODPROGRAMMY.
sNAÓALA PREDPRINIMALISX POPYTKI REALIZOWATX PSMOO, NE OSU]ESTWí
LQQ PERERASPREDELENIQ DANNYH MEVDU p---. ---TO PREDPOLAGAET, ÓTO ITERACII
PERWOJ POLOWINY PODPROGRAMMY BUDUT ISPOLNQTXSQ STROGO POSLEDOWATELXNO,
A RASPREDELENY MEVDU p--- BUDUT TOLXKO ITERACII WTOROJ POLOWINY. pRI
``TOM BYLA NADEVDA, ÓTO NEKOTORAQ ``KONOMIQ NA PERESYLKAH KOMPENSIRUET
PROIGRY[, POLUÓENNYJ ZA SÓèET POTERI ÓASTI PARALLELIZMA.
pERWYJ WARIANT (psmoo1) ISPOLNQLSQ STROGO W SOOTWETSTWII S ALGORITí
MOM, TO ESTX KAVDYJ p--- PROSÓITYWAL SWO@ PORCI@ ITERACIJ, PEREDAWAL
DANNYE S POSLEDNEJ ITERACII SLEDU@]EMU p---, POSLE ÓEGO TOT p--- NAÓINAL
RABOTATX (SM. RISUNOK). oDNAKO S ROSTOM ÓISLA p--- RASTèET ÓISLO NEOBHODIí
MYH PERESYLOK, A, SLEDOWATELXNO, I WREMQ ISPOLNENIQ PSMOO RASTèET KATAí
STROFIÓESKI I STANOWITSQ OPREDELQ@]IM FAKTOROM DLQ WREMENI ISPOLNENIQ
WSEJ PROGRAMMY.
32

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
wTOROJ WARIANT (psmoo2) PREDUSMATRIWAL ISPOLNENIE WSEH ITERACIJ PERí
WOJ POLOWINY PSMOO NA p--- S NOMEROM 1. w NAÓALE PSMOO WSE p--- OTSYLALI
PERWOMU SWOI PORCII ISHODNYH DANNYH, A POSLE ISPOLNENIQ PERWOJ POLOWIí
NY PODPROGRAMMY ``TOT p--- RASSYLAL WSEM OSTALXNYM IH PORCII REZULXTATOW
(SM. RISUNOK). pRI ``TOM, KAK WIDNO, TREBUETSQ WSEGO DWE, HOTQ I WESXMA BOLXí
[IH, PERESYLKI. oKAZALOSX, ÓTO POTERQ PARALLELIZMA W PERWOJ POLOWINE
PODPROGRAMMY I NALIÓIE PERESYLOK BOLX[IH OB×èEMOW DANNYH NE POZWOLQ@T
ZNAÓITELXNO ULUÓ[ITX SITUACI@ PO SRAWNENI@ S PREDYDU]IM WARIANTOM.
tRETIJ WARIANT (psmoo3) PREDUSMATRIWAL WYPOLNENIE WSEH ITERACIJ
PERWOJ POLOWINY PSMOO NA KAVDOM p---. dLQ ``TOGO TREBOWALASX EDINSTWENí
NAQ RASSYLKA PERED WYPOLNENIEM PODPROGRAMMY PORCIJ ISHODNYH DANNYH OT
KAVDOGO p--- KAVDOMU (SM. RISUNOK). eSLI NA MALOM ÓISLE p--- ``TOT WARIANT
NEZNAÓITELXNO PREWOSHODIT PREDYDU]IJ, TO NA 128 I 256 p--- OKAZYWAETSQ
DAVE HUVE EGO.
~ETWèERTYJ WARIANT PREDPOLAGAET PERERASPREDELENIE DANNYH I SOOTWETí
STWU@]IH ITERACIJ TAK, ÓTOBY ISPOLXZOWATX W PERWOJ ÓASTI PSMOO PAí
RALLELIZM PO J, A WO WTOROJ --- PO I (psmoo4). dLQ ``TOGO DO I POSLE PERWOJ
ÓASTI TREBUETSQ RASSYLKA OT KAVDOGO p--- KAVDOMU, NO OTNOSITELXNO NEBOLXí
[OJ ÓASTI WHODNYH DANNYH (SM. RISUNOK). dANNYJ WARIANT OKAZALSQ W ITOGE
NAIBOLEE UDAÓNYM.
w PQTOM WARIANTE BYLA REALIZOWANA PARALLELXNAQ SHEMA WYÓISLENIQ REí
KURSII PERWOGO PORQDKA, PODOBNAQ SHEME KASKADNOGO SUMMIROWANIQ (psmoo5).
---TOT WARIANT OTLIÓAETSQ OT WSEH PREDYDU]IH SWOEJ MAS[TABIRUEMOSTX@,
TO ESTX TEM, ÓTO WREMQ WYÓISLENIQ UMENX[AETSQ S ROSTOM ÓISLA p---. oDNAKO
WREMQ WYÓISLENIQ POLUÓENNOGO WARIANTA NA MALOM ÓISLE p--- OKAZALOSX NEí
PRIEMLEMO BOLX[IM, PO``TOMU BYLO PRINQTO RE[ENIE W ZAWISIMOSTI OT ÓISLA
p--- WYZYWATX LIBO ``TOT WARIANT PSMOO, LIBO PREDYDU]IJ.
pODPROGRAMMA FORCF WYZYWAETSQ WSEGO 150 RAZ I ZANIMAET OÓENX MALO
WREMENI PRI POSLEDOWATELXNOM WYPOLNENII. oDNAKO W NEJ WSTRETILSQ PRINí
CIPIALXNO NOWYJ MOMENT --- NEOBHODIMOSTX GLOBALXNOGO SUMMIROWANIQ PO
WSEM p---. sAMA OPERACIQ NE OÓENX SLOVNAQ, NO REALIZOWATX EèE ``FFEKTIWNO
NA KOMPX@TERE S RASPREDELèENNOJ PAMQTX@ NE OÓENX PROSTO. dLQ DANNOJ OPEí
RACII ISPOLXZOWALASX BIBLIOTEÓNAQ FUNKCIQ, OPTIMIZIROWANNAQ SPECIALXNO
POD ARHITEKTURU CRAY T3D.
pODPROGRAMMY BCFAR I BCWALL NE POSTAWILI NIKAKIH PRINCIPIALXí
33

a.s. aNTONOW
NO NOWYH PROBLEM, ZA ISKL@ÓENIEM TOGO, ÓTO PODPROGRAMMA BCFAR SODERVIT
W SEBE WYZOW PODPROGRAMMY FORCF. w ``TOM SLUÓAE, ODNAKO, NIKAKIH DOPOLí
NITELXNYH PERESYLOK NE POTREBOWALOSX, TAK KAK REZULXTATOM PODPROGRAMMY
FORCF QWLQ@TSQ LI[X TRI ÓISLA, WYÓISLENNYH W GLOBALXNOM SUMMIROWAí
NII, KOTORYE PO SMYSLU OPERACII UVE NAHODQTSQ NA WSEH p---. pODPROGRAMMA
BCWALL NE POLUÓILA USKORENIQ PRI UWELIÓENII ÓISLA p--- IZíZA NALIÓIQ
DOSTATOÓNO BOLX[OGO ÓISLA KOROTKIH PERESYLOK GRANIÓNYH ZNAÓENIJ.
sLEDU@]IJ [AG W RASPREDELENII PROGRAMMY ZAKL@ÓAETSQ W RASPREDELEí
NII ITERACIJ PODPROGRAMMY EULER, TAK KAK K ``TOMU MOMENTU RASPREDELENY
WSE WYZYWAEMYE IZ NEèE PODPROGRAMMY. uSPE[NOE RASPREDELENIE PODPROGRAMí
MY EULER IMEET PERWOSTEPENNOE ZNAÓENIE DLQ POLUÓENIQ HORO[EGO USKOREí
NIQ WSEJ PROGRAMMY. aNALIZ POSLEDOWATELXNOSTI WYZOWOW PODPROGRAMM IZ
PODPROGRAMMY EULER POKAZYWAET, ÓTO PRI RASPREDELENII PODPROGRAMMY
EULER NE TREBUETSQ PRAKTIÓESKI NIKAKIH DOPOLNITELXNYH PERESYLOK, SWQí
ZANNYH S PEREDAÓEJ REZULXTATOW WYPOLNENIQ WYZYWAEMYH PODPROGRAMM, TAK
KAK EDINAQ DLQ WSEH PODPROGRAMM SHEMA RASPREDELENIQ ITERACIJ POZWOLQET
OSTAWLQTX NA p--- REZULXTATY IíJ ITERACII, TAK KAK DALEE ONI POTREBU@TSQ
TOLXKO NA ``TOM VE p---. tREBU@TSQ TOLXKO PERESYLKI, NEOBHODIMYE PO TEKSTU
PODPROGRAMMY EULER.
w ``TOT MOMENT ISÓEZA@T WSE NAKLADNYE RASHODY NA PERESYLKI DO I POí
SLE WYZYWAEMYH IZ PODPROGRAMMY EULER PODPROGRAMM. nEOBHODIMY LI[X
PERESYLKI POSLE WYPOLNENIQ EULER DANNYH, WYÓISLENNYH W ``TOJ PODPROí
GRAMME I WO WSEH WYZYWAEMYH IZ NEèE PODPROGRAMMAH. zA SÓèET ``TOGO UVE W
DANNYJ MOMENT MY POLUÓILI USKORENIE DLQ WSEJ PROGRAMMY. kROME UPOí
MQNUTYH PERESYLOK W PODPROGRAMME EULER TREBUETSQ UVE WSTREÓAW[EESQ W
PODPROGRAMME FORCF GLOBALXNOE SUMMIROWANIE, A TAKVE NAHOVDENIE GLOí
BALXNOGO MAKSIMUMA.
pOSLE RASPREDELENIQ PODPROGRAMMY EULER SO WSEMI WYZYWAEMYMI IZ
NEèE PODPROGRAMMAMI OKAZALOSX, ÓTO OÓENX SU]ESTWENNOE WLIQNIE NA OB]EE
WREMQ WYPOLNENIQ FLO52 OKAZYWAET RASSYLKA DANNYH OT KAVDOGO p--- KAVDOí
MU POSLE WYZOWOW DANNOJ PODPROGRAMMY, POQWIW[AQSQ TOLXKO IZíZA ISPOLXZUí
EMOJ POSLEDOWATELXNOSTI DEJSTWIJ PO ADAPTACII PROGRAMMY, PRIÓèEM WREMQ
NA ``TU RASSYLKU BYSTRO RASTèET S ROSTOM ÓISLA p---. dLQ DALXNEJ[EGO USKOí
RENIQ FLO52 NEOBHODIMO IZBAWITXSQ OT ``TOJ RASSYLKI, ÓTO WOZMOVNO TOLXKO
PRI PERENOSE WYBRANNOJ SHEMY RASPREDELENIQ NA UROWENX WSEJ PROGRAMMY.
34

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
dLQ ``TOGO OKAZALOSX DOSTATOÓNYM PRAWILXNO OSU]ESTWITX PERERASPREDELEí
NIE W PODPROGRAMMAH COLLC I ADDX I RAZOBRATXSQ S WYWODOM W WYHODNYE
FAJLY.
w PODPROGRAMMAH COLLC I ADDX TREBU@TSQ BOLEE SLOVNYE PERESYLKI,
ÓEM WSTREÓAW[IESQ RANEE, TAK KAK PRIHODITSQ PERESYLATX DANNYE S ITERACIJ,
RASPREDELENIE KOTORYH PROIZWODILOSX PRI ODNIH ZNAÓENIQH PARAMETROW, NA
ITERACII, RASPREDELENIE KOTORYH PROIZWODITSQ PRI DRUGIH ZNAÓENIQH PARAí
METROW. eSLI W PODPROGRAMME COLLC UDALOSX POLUÓITX NEKOTOROE USKORENIE,
TO PODPROGRAMMA ADDX OKAZALASX E]èE ODNIM UZKIM MESTOM.
oSTALXNYE PODPROGRAMMY FLO52 TREBU@T WESXMA MALOGO WREMENI ISPOLí
NENIQ LIBO ZANIMA@TSQ WWODOMíWYWODOM. pO``TOMU IH RASPREDELENIE (DAVE
KOGDA ONO WOZMOVNO) POTREBUET, WOZMOVNO, ZNAÓITELXNYH USILIJ, NO NE PRIí
NESèET BOLX[OGO ``FFEKTA. pO``TOMU BYLO RE[ENO ``TIM PODPROGRAMMAM WNIMAí
NIQ NE UDELQTX.
pOSLE POLUÓENIQ RASPREDELèENNOGO WARIANTA PROGRAMMY BYLA PROIZWEDEí
NA DOPOLNITELXNAQ OPTIMIZACIQ WYÓISLENIJ NA KAVDOM p---, ZAKL@ÓAW[AQSQ
W BOLEE ``FFEKTIWNOM ISPOLXZOWANII K``[íPAMQTI, ULUÓ[ENII SBALANSIROWANí
NOSTI WYÓISLENIJ I W UMENX[ENII RAZMERNOSTEJ WREMENNYH MASSIWOW. w NAIí
BOLX[EJ STEPENI REZULXTATY ``TOJ OPTIMIZACII SKAZALISX NA MALYH KOLIÓEí
STWAH p---, TAK KAK PRI ``TOM NA KAVDYJ p--- PRIHODITSQ DOSTATOÓNO BOLX[AQ
PORCIQ ITERACIJ.
2.3 rEZULXTATY ``KSPERIMENTOW
w SLEDU@]EJ TABLICE PRIWEDENY WREMENA ISPOLNENIQ RASPREDELQW[IHSQ PODí
PROGRAMM W ZAWISIMOSTI OT ÓISLA PROCESSOROW DLQ SREDNEGO WARIANTA. wREMQ
ISPOLNENIQ NA ODNOM PROCESSORE UKAZANO DLQ ISHODNOGO POSLEDOWATELXNOGO WAí
RIANTA PROGRAMMY.
35

a.s. aNTONOW
wREMENA WYPOLNENIQ PODPROGRAMM, c.
sREDNIJ WARIANT
kOLIÓESTWO p---
p/P 1 2 4 8 16 32 64 128 256
eflux 68.7 38.2 19.3 10.2 5.74 3.49 2.32 1.69 1.41
dflux 53.6 29.0 15.2 8.27 4.83 3.11 2.20 1.76 1.57
psmoo1 27.5 31.0 28.8 29.9 34.5 43.2 58.6 81.4 107.6
psmoo2 27.5 35.7 32.9 34.2 39.5 41.7 44.2 50.3 58.2
psmoo3 27.5 30.3 30.3 33.9 37.1 39.7 44.5 51.3 65.6
psmoo4 27.5 22.6 14.2 9.23 7.15 7.03 8.69 12.0 15.0
psmoo5 27.5 166.7 --- --- 41.96 --- 15.91 10.25 8.22
forcf 0.054 0.031 0.018 0.012 0.009 0.008 0.008 0.008 0.008
bcfar 1.18 0.56 0.33 0.19 0.12 0.09 0.07 0.06 0.05
bcwall 1.85 1.83 1.51 1.29 1.18 1.12 1.10 1.09 1.08
euler 56.1 24.6 13.5 7.88 5.14 3.72 2.95 2.64 2.43
collc 3.93 2.43 1.61 1.43 1.42 1.05 0.73 0.70 0.65
addx 3.79 3.45 2.47 2.16 2.31 2.82 2.80 4.01 4.51
kAK WIDNO IZ TABLICY, USKORENIE PO SRAWNENI@ S ODNOPROCESSORNYM WAí
RIANTOM POLUÓILOSX POÓTI NA WSEH RASSMOTRENNYH PODPROGRAMMAH, ODNAKO
UPOMINAW[IESQ W PREDYDU]EM PUNKTE UZKIE MESTA DEJSTWITELXNO OKAZYWA@T
ZNAÓITELXNOE SDERVIWA@]EE WLIQNIE.
w SLEDU@]EJ TABLICE PRIWODQTSQ OKONÓATELXNYE REZULXTATY, POLUÓENí
NYE NA WSEH TRèEH RASSMATRIWAEMYH WARIANTAH.
wREMENA WYPOLNENIQ WARIANTOW FLO52, c.
kOLIÓESTWO p---
wARIANT 1 2 4 8 16 32 64 128 256
mALYJ 59.7 37.2 23.4 16.4 13.6 13.0 14.0 13.6 13.7
sREDNIJ 235.6 136.3 76.5 46.1 31.9 25.9 24.3 25.4 23.7
bOLX[OJ 999.3 566.7 301.8 167.0 101.5 70.3 56.3 52.2 57.4
sLEDU@]IJ GRAFIK DEMONSTRIRUET USKORENIE, POLUÓENNOE NA WSEH TRèEH
WARIANTAH W ZAWISIMOSTI OT ÓISLA ISPOLXZUEMYH p---.
36

aDAPTACIQ PROGRAMM DLQ MASSIWNOíPARALLELXNYH KOMPX@TEROW
e
e
e
e
e
e
e
e
e
pp pp pp ppppp pppp pp pp pp pppppp pp pp pp pppppppp ppp pp pppp pppp pp ppp pp pppp pp pp ppp pp pp pp pp pp pp pp pp pp pp pp pp pp pp
pp pp pp ppp pp pp ppppp ppppp ppppppppppppp pp pp pp pp ppp pp pp pp pp pp pp pp
e
e
e
e
e
e
e
e
e
pp pp pp ppp pp pp pp pp pp pppppppppp ppp pp pp pp pp ppp pp pp pp ppp pp pp pp pp pp pp pp pp pp pp pp pp pp
pp
pp
pp
pp
pp pp pp pp pp pp pp ppp pp pp pppp ppp pp ppppppppp ppp pppp ppp ppppppppppp pppp ppppppp pppp pppppp pp pp pp pppp ppppp pppppp ppppppppppp pppppp pp pppp pp pp pp pp pp pp pppp
e
e
e
e
e e e e e
1
5
10
15
20
1 2 4 8 16 32 64 128 256
bOLX[OJ
mALYJ
sREDNIJ
kAK WIDNO IZ GRAFIKA I IZ PRIWEDèENNYH REZULXTATOW, POLUÓENNAQ RASPREí
DELèENNAQ PODPROGRAMMA QWLQETSQ MAS[TABIRUEMOJ I PRI DOSTATOÓNO BOLX[OM
OB×èEME WYÓISLENIJ POZWOLQET POLUÓATX SU]ESTWENNOE USKORENIE PRI ISPOLXí
ZOWANII BOLX[OGO ÓISLA p---. oTNOSITELXNO NEBOLX[OE USKORENIE, POLUÓAEMOE
NA MALOM I SREDNEM WARIANTAH, OB×QSNQETSQ NEDOSTATOÓNYM RAZMEROM ZADAÓI,
A TAKVE BOLX[IM ÓISLOM TOÓEK PARALLELXNOGO WZAIMODEJSTWIQ PROCESSOROW
(SUMMARNO BOLEE 35000 ZA WREMQ RABOTY PROGRAMMY). uSKORENIE, POLUÓENNOE
NA MALOM WARIANTE PRI PEREHODE OT 64 K 128 p--- I NA SREDNEM WARIANTE PRI PEí
REHODE OT 128 K 256 p---, OB×QSNQETSQ ISPOLXZOWANIEM W ``TIH SLUÓAQH WARIANTA
PSMOO, W KOTOROM REALIZUETSQ PARALLELXNAQ REKURSIQ (psmoo5). bOLX[OJ
WARIANT OKAZALSQ MAKSIMALXNO WOZMOVNYM, KOTORYJ BEZ SU]ESTWENNYH IZí
MENENIJ MOVET POMESTITXSQ W LOKALXNU@ PAMQTX ODNOGO p---. dALXNEJ[EGO
UWELIÓENIQ RAZMERNOSTI ZADAÓI MOVNO BYLO BY DOSTIÓX PEREOPISANIEM ISí
POLXZUEMYH MASSIWOW TAKIM OBRAZOM, ÓTOBY NA KAVDOM p--- WYDELQLOSX MESTO
LI[X DLQ TOJ PORCII DANNYH, KOTORAQ NA NèEM BUDET ISPOLXZOWATXSQ.
3 zAKL@ÓENIE
pOSKOLXKU DANNAQ STATXQ PISALASX LI[X NA OSNOWE OPYTA PROWEDENIQ ``KSPEí
RIMENTOW S PROGRAMMOJ FLO52, ONA NE PRETENDUET NA POLNOTU OHWATA MATEí
37

a.s. aNTONOW
RIALA, TO ESTX NA RAZRABOTKU METODIKI ADAPTACII L@BOJ POSLEDOWATELXNOJ
PROGRAMMY NA MASSIWNOíPARALLELXNU@ ARHITEKTURU, I RE[ENIE WSEGO RAZí
NOOBRAZIQ WSTA@]IH PRI ``TOM PERED PROGRAMMISTOM PROBLEM. pO``TOMU ZA
RAMKAMI ``TOJ STATXI ZAWEDOMO OKAZYWAETSQ NEKOTOROE KOLIÓESTWO WOPROSOW,
TAKIH KAK, NAPRIMER, QWNOE RAZBIENIE MASSIWOW NA ÓASTI, OTDAWAEMYE OTDELXí
NYM p--- W SLUÓAE, ESLI RAZMERY DANNYH PROGRAMMY TAKOWY, ÓTO ONI NE POí
ME]A@TSQ W OPERATIWNU@ PAMQTX ODNOGO p---. pREDPOLAGAETSQ, ÓTO METODIKA
DEJSTWIJ W PODOBNYH SLUÓAQH BUDET RAZRABATYWATXSQ PO MERE WOZNIKNOWENIQ
PRAKTIÓESKOJ NEOBHODIMOSTI.
lITERATURA
[1] Grassl C. M. Parallel performance of applications on supercomputers//
Parallel Computing. 1991. N17. P.1257í1273.
[2] Blume W. J. Success and limitations in automatic parallelization of the
Perfect Benchmarks programs// CSRD Tech. Rep. 1992. N1249.
[3] Cybenko G., Kipp L., Pointer L., Kuck D. Supercomputer performance
evaluation and the Perfect Benchmarks// CSRD Tech. Rep. 1990. N965.
[4] Pointer L. Perfect: Performance Evaluation for CostíEffective Transformaí
tions Report 2// CSRD Tech. Rep. 1990. N964.
38