Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://asa.guru.ru/papers/pap2.ps Äàòà èçìåíåíèÿ: Sat Aug 1 11:18:55 1998 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 19:57:18 2012 Êîäèðîâêà:

programmirowanie, 1996, N o
3, S.1 ­ ??
tEMATI“ESKIJ RAZDEL VURNALA
udk 21.22
---ffektiwnaq adaptaciq posledowatelxnyh
programm dlq sowremennyh
wektorno­konwejernyh i
massiwno­parallelxnyh super­---wm
c
fl 1996G. a.s. aNTONOW, wL.w. wOEWODIN
pOSTUPILA W REDAKCI@ 22 QNWARQ 1996
dANNAQ RABOTA POSWQ]ENA OBSUVDENI@ OSNOWNYH ``TAPOW I PROBLEM PERENOSA PROGRAMMNOGO OBESPE“E­
NIQ NA PARALLELXNYE KOMPX@TERY. w KA“ESTWE PRIMERA RASSMATRIWAETSQ ADAPTACIQ DWUH PROGRAMM
IZWESTNOGO PAKETA Perfect Club Benchmarks, DLQ KOTORYH UDALOSX POLU“ITX LU“[IE, NA NASTOQ­
]IJ MOMENT, POKAZATELI PROIZWODITELXNOSTI DLQ WEKTORNO­KONWEJERNYH SUPER­---wm CRAY Y--MP
I MASSIWNO­PARALLELXNOGO KOMPX@TERA CRAY T3D.
1. wwedenie
nESMOTRQ NA TO, “TO PROBLEMA OPTIMIZACII
PROGRAMM DLQ KOMPX@TEROW S PARALLELXNOJ AR­
HITEKTUROJ SU]ESTWUET UVE BOLEE DWADCATI LET,
EE RE[ENIE DO SIH POR NELXZQ S“ITATX UDOWLE­
TWORITELXNYM, DAVE DLQ STAW[IH UVE KLASSI­
“ESKIMI, WEKTORNO­KONWEJERNYH SUPER-----wm. w
DEJSTWITELXNOSTI, BYLO PREDLOVENO MNOGO RAZ­
LI“NYH PODHODOW K OPTIMIZACII, NO NE ODIN IZ
NIH NE PREDPOLAGAET KOMPLEKSNOGO RE[ENIQ WSE­
GO MNOVESTWA WOZNIKA@]IH PROBLEM. w DAN­
NOJ RABOTE MY OPISYWAEM PROCESS ADAPTACII
DWUH POSLEDOWATELXNYH PROGRAMM DLQ SEMEJ­
STWA WEKTORNO­KONWEJERNYH KOMPX@TEROW CRAY
I MASSIWNO­PARALLELXNOGO KOMPX@TERA CRAY
T3D.
pODBIRAQ MATERIAL DLQ DANNOJ RABOTY, MY
STAWILI PERED SOBOJ DWE CELI. wO­PERWYH, MY
HOTELI POKAZATX OSNOWNYE ``TAPY SAMOGO PROCES­
SA ADAPTACII PROGRAMM K ARHITEKTURE PARAL­
LELXNYH KOMPX@TEROW. w TOJ ILI INOJ FORME
“EREZ ``TI ``TAPY PRIDETSQ PROJTI WSEM, KTO BU­
DET WOWLE“EN W PODOBNOGO RODA DEQTELXNOSTX, PO­
``TOMU POLU“ENNYJ NAMI OPYT POMOVET DRUGIM
ISSLEDOWATELQM LU“[E PREDSTAWITX HARAKTER I
OB—EM PREDSTOQ]EJ RABOTY.
nA MNOGIH ``TAPAH PRIHODILOSX RE[ATX DO­
WOLXNO SLOVNYE, DAVE W PLANE POSTANOWKI, ZADA­
“I. s “ASTX@ IZ NIH NAM UVE PRIHODILOSX IMETX
DELO, ODNAKO MNOGIE WOZNIKLI LI[X W PROCESSE
REALXNOJ RABOTY. ---TA STORONA PRODELANNOJ RA­
BOTY PREDOPREDELILA WTORU@ CELX --- OPISATX I
TEM SAMYM PRIWLE“X WNIMANIE DRUGIH SPECIA­
LISTOW K ZADA“AM, WOZNIKA@]IM NA KAVDOM IZ
``TAPOW PROCESSA ADAPTACII. mNOGIE ZADA“I HO­
RO[O IZWESTNY, I DLQ IH RE[ENIQ SU]ESTWU@T
``FFEKTIWNYE METODY, NO DRUGU@ “ASTX DO SIH
POR PRIHODITSQ ''RE[ATX WRU“NU@'', “TO DELAET
PROCESS ADAPTACII O“ENX TRUDOEMKIM.
oPISYWAEMYE W DANNOJ RABOTE ANALIZ I PRE­
OBRAZOWANIE PROGRAMM MY WYPOLNQLI S POMO­
]X@ V­Ray TEHNOLOGII I POSTROENNOJ NA EE
OSNOWE SISTEME V­Ray. tEHNOLOGIQ IMEET SE­
RXEZNOE MATEMATI“ESKOE OSNOWANIE, OPIRA@]EE­
SQ NA REZULXTATY TEORII GRAFOW ALGORITMOW, TE­
ORII GRAFOW I TEORII STATI“ESKOGO ANALIZA PRO­
GRAMM. sAMA TEHNOLOGIQ OPISANA W NESKOLXKIH
RABOTAH, NAPRIMER, W [1,2], A ZDESX MY HOTELI BY
BOLX[E SOSREDOTO“ITXSQ NA REZULXTATAH I OPYTE
REALXNOJ RABOTY NA SUPER­---wm.
dLQ ``KSPERIMENTOW MY WZQLI PAKET Perfect
Club Benchmarks, KOTORYJ UVE W TE“ENIE MNO­
GIH LET ISPOLXZUETSQ DLQ OPREDELENIQ REALX­
NOJ PROIZWODITELXNOSTI PARALLELXNYH KOMPX@­
TEROW NA PROMY[LENNYH PRILOVENIQH. k NA­
STOQ]EMU WREMENI EGO SOSTAW, STRUKTURA OTDELX­
NYH PROGRAMM, KL@“EWYE FRAGMENTY OTDELXNYH
PROCEDUR, PROIZWODITELXNOSTI DLQ BOLX[OGO “I­
SLA RAZLI“NYH KOMPX@TEROW I MNOGIE DRUGIE PA­
RAMETRY PODROBNO ISSLEDOWANY I NEODNOKRATNO
1

2 antonow, woewodin
OPISANY WO MNOGIH RABOTAH [3,4]. oDNAKO IMEN­
NO [IROKAQ IZWESTNOSTX PAKETA I POKAZALASX NAM
PRIWLEKATELXNOJ: WO­PERWYH, NAMNOGO INTERES­
NEE POLU“ITX NETRIWIALXNYJ REZULXTAT TAM, GDE
PREVDE UVE RABOTALI DRUGIE ISSLEDOWATELI, A,
WO­WTORYH, TOLXKO TAKIM OBRAZOM I MOVNO OB—­
EKTIWNO OCENITX ``FFEKTIWNOSTX NOWOJ TEHNOLO­
GII PO SRAWNENI@ S SU]ESTWU@]IMI METODAMI
ANALIZA I PREOBRAZOWANIQ PROGRAMM.
iZ SAMOGO PAKETA MY WYBRALI PROGRAMMY
TRFD I FLO52, TAK KAK PERWAQ IMEET KRAJNE
NIZKU@ PROIZWODITELXNOSTX NA WSEH PARALLELX­
NYH KOMPX@TERAH FIRMY CRAY, A WTORAQ O“ENX
SLOVNA DLQ ADAPTACII K MASSIWNO­PARALLELXNOJ
ARHITEKTURE I, NASKOLXKO NAM IZWESTNO, USPE[­
NYH POPYTOK EE OPTIMIZACII NE BYLO.
sUTX PROBLEMY LEGKO OB—QSNITX NA PRIMERE
PROGRAMMY TRFD. nA ISHODNOM WARIANTE TRFD
ODIN PROCESSOR KOMPX@TERA CRAY Y--MP s90
S PIKOWOJ PROIZWODITELXNOSTX@ PO“TI 1 Gflop/s
DOSTIGAET TOLXKO 89.5 Mflop/s. lU“[IJ WARIANT
RU“NOJ OPTIMIZACII ``TOGO KODA UWELI“IL PROIZ­
WODITELXNOSTX LI[X DO 139.7 Mflop/s (ZNA“ENIQ
PROIZWODITELXNOSTI POSLE RU“NOJ OPTIMIZACII
PREDOSTAWLENY d.bRUKSOM IZ CRAY Research,
Inc., Eagan MN, USA). qSNO, “TO PROGRAMMA W
PERWONA“ALXNOM WIDE NE TOLXKO DOSTATO“NO PLO­
HO WEKTORIZUETSQ, NO I ''RU“NYE'' IZMENENIQ NE
MOGLI SU]ESTWENNO ISPRAWITX POLOVENIQ DEL.
eSTESTWENNO SRAZU WOZNIKA@T DWA WOPROSA:
ffl w “EM PRI“INA STOLX NIZKOJ PROIZWODITELX­
NOSTI?
ffl mOVNO LI UWELI“ITX PROIZWODITELXNOSTX
TOLXKO S POMO]X@ ``KWIWALENTNOGO PREOBRA­
ZOWANIQ ISHODNOGO TEKSTA DANNOJ PROGRAM­
MY?
zABEGAQ NEMNOGO WPERED, MY DADIM OTWET SRA­
ZU --- DA, ``TO SDELATX MOVNO! w REZULXTATE PRO­
WEDENNYH ISSLEDOWANIJ NAM UDALOSX, WO­PERWYH,
PODNQTX PROIZWODITELXNOSTX ODNOGO PROCESSORA
CRAY Y--MP C90 NA DANNOJ PROGRAMME DO 579.7
Mflop/s, WO­WTORYH, DOBITXSQ USTOJ“IWOGO RO­
STA PROIZWODITELXNOSTI DLQ MNOGOPROCESSORNYH
KONFIGURACIJ, I, NAKONEC, POLU“ITX DEJSTWI­
TELXNO MAS[TABIRUEMU@ PROGRAMMU S PROIZWO­
DITELXNOSTX@ 1.7 Gflop/s NA 256­TI PROCESSOR­
NOM KOMPX@TERE CRAY T3D. kAK DOBITXSQ TAKO­
GO ``FFEKTA --- OB ``TOM I BUDET RASSKAZANO NIVE.
rABOTA SOSTOIT IZ “ETYREH “ASTEJ. w PER­
WOJ “ASTI KRATKO OPISANY OSNOWNYE OSOBEN­
NOSTI WEKTORNO­KONWEJERNYH I MASSIWNO­PARAL­
LELXNYH KOMPX@TEROW. wTORAQ I TRETXQ “A­
STI POSWQ]ENY OPISANI@ PROCESSA OPTIMIZACII
PROGRAMM TRFD I FLO52, I WMESTE S ``TIM, ``TI
“ASTI SODERVAT OPISANIE GLAWNYH ``TAPOW, HA­
RAKTERNYH DLQ OPTIMIZACII PRAKTI“ESKI WSEH
REALXNYH PROGRAMM. w ZAKL@“ENII PRIWEDEN
KRATKIJ SPISOK OSNOWNYH ZADA“, S KOTORYMI
PRIHODITSQ STALKIWATXSQ W PROCESSE ANALIZA I
PREOBRAZOWANIQ PROGRAMM, PRI“EM DLQ ODNIH ZA­
DA“ RE[ENIE POLU“ITX NE SLOVNO, A DLQ DRUGIH
NASTOLXKO NETRIWIALXNO, “TO WOPROS O NAHOVDE­
NII PRIEMLEMOGO RE[ENIQ OSTAETSQ OTKRYTYM
DO SIH POR.
2. nemnogo o kompx`terah CRAY
Y--MP i CRAY T3D
aRHITEKTURA KOMPX@TEROW CRAY Y­MP
C90 SOHRANILA WSE LU“[IE “ERTY WEKTORNO­
KONWEJERNYH MODELEJ FIRMY CRAY Research,
Inc.: CRAY--1, CRAY X--MP I CRAY Y--MP M90.
kAK I PREVDE, OSNOWNAQ STAWKA DELAETSQ NA ``F­
FEKTIWNOE WYPOLNENIE KONWEJERNYMI FUNKCIO­
NALXNYMI USTROJSTWAMI OPERACIJ NAD WEKTORA­
MI. wREMQ TAKTA UMENX[ENO DO 4.1 NSEK I, WME­
STE S TEM, UWELI“EN OB—EM OPERATIWNOJ PAMQTI
DO 8 gBAJT, PRI“EM WSQ PAMQTX ODINAKOWO DO­
STUPNA DLQ WSEH PROCESSOROW. aRHITEKTURA ``TO­
GO KOMPX@TERA DOSTATO“NO HORO[O IZWESTNA, I EE
OPISANIE MOVNO NAJTI, NAPRIMER, W [5].
pOQWIW[IJSQ OTNOSITELXNO NEDAWNO CRAY
T3D PREDSTAWLQET SOBOJ MASSIWNO­PARALLELX­
NYJ KOMPX@TER S RASPREDELENNOJ PAMQTX@, OB—­
EDINQ@]IJ OT 32 DO 2048 PROCESSOROW DEC
ALPHA. kAVDYJ PROCESSOR RABOTAET NA “ASTO­
TE 150 MgC, IMEET SWO@ LOKALXNU@ PAMQTX OT 2
DO 8 MSLOW (KAVDOE SLOWO --- 64 RAZRQDA), K``[­
PAMQTX KOMAND I K``[­PAMQTX DANNYH PO 1KSLO­
WU. wSE PROCESSORY RAZBITY NA PARY, KAVDAQ
PARA SOSTAWLQET WY“ISLITELXNYJ UZEL, A WSE UZ­
LY OB—EDINENY W TREHMERNYJ TOR. sWQZX MEV­
DU SOSEDNIMI UZLAMI MOVET IDTI ODNOWREMENNO
W OBOIH NAPRAWLENIQH PO DWUM ODNONAPRAWLEN­
NYM KANALAM. mAR[RUTIZACIQ SOOB]ENIJ MEV­
DU DWUMQ UZLAMI WSEGDA PROISHODIT TAK, “TO SNA­
“ALA WYRAWNIWA@TSQ IH KOORDINATY PO IZMERE­
NI@ X , ZATEM PO Y , I W KONCE PO Z. mAKSIMALX­
NAQ SKOROSTX PEREDA“I PO KANALU SOSTAWLQET 140
MBAJT/S.
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 3
rIS. 1.
nESMOTRQ NA TO, “TO PAMQTX FIZI“ESKI RAS­
PREDELENA PO PROCESSORAM, PREDUSMOTRENA AP­
PARATNAQ PODDERVKA UDALENNOGO DOSTUPA W PA­
MQTX DRUGOGO PROCESSORA, PRI“EM WREMQ UDALEN­
NOGO DOSTUPA WSEGO LI[X W 6 RAZ BOLX[E WREMENI
OBRA]ENIQ K LOKALXNOJ PAMQTI. sPECIALXNYE
APPARATNYE SHEMY SINHRONIZACII QWLQ@TSQ HO­
RO[EJ PODDERVKOJ DLQ REALIZACII TRADICIONNO
''NEUDOBNYH'' PRIMITIWOW PARALLELXNOJ RABOTY
PROCESSOW TIPA BARXERNOJ SINHRONIZACII.
3. issledowanie i optimizaciq
programmy TRFD
3.1. oB]AQ HARAKTERISTIKA I STRUKTURA
TRFD
iTAK, PREVDE, “EM NA“INATX OPTIMIZACI@
PROGRAMMY, NEOBHODIMO PONQTX EE OB]U@ STRUK­
TURU: KAKIE PODPROGRAMMY SOSTAWLQ@T OSNOW­
NOE WY“ISLITELXNOE QDRO, GDE SOSREDOTO“EN
WWOD/WYWOD, KAKOWA POSLEDOWATELXNOSTX WYZOWA
OTDELXNYH PODPROGRAMM I T. P. dLQ PROGRAM­
MY TRFD ``TO SDELATX LEGKO, TAK KAK ONA OTNO­
SITELXNO NEWELIKA --- WESX WWOD/WYWOD RASPOLO­
VEN W GLAWNOJ “ASTI, A B'OLX[AQ “ASTX WREMENI
PRIHODITSQ NA PODPROGRAMMU OLDA. sTRUKTURU
DANNOJ PODPROGRAMMY MOVNO PREDSTAWITX S PO­
MO]X@ EE CIKLI“ESKOGO PROFILQ, W KOTOROM KA­
VDAQ GORIZONTALXNAQ SKOBKA SOOTWETSTWUET OD­
NOMU CIKLU DO (RIS. 1).
zNA“ITELXNOE “ISLO CIKLOW, BOLX[AQ GLUBINA
IH WLOVENNOSTI (5) W SOWOKUPNOSTI I OPREDELQ­
@T WY“ISLITELXNU@ SLOVNOSTX DANNOJ PODPRO­
GRAMMY. oDNAKO DLQ ANALIZA INFORMACIONNOJ
STRUKTURY ``TI FAKTORY SAMI PO SEBE NE QWLQ@T­
SQ SERXEZNYMI PREPQTSTWIEM. wAVNOJ OSOBENNO­
STX@ PODPROGRAMMY OLDA QWLQETSQ TO, “TO, WO­
PERWYH, “ISLO ITERACIJ W KAVDOM CIKLE OTNOSI­
TELXNO NEWELIKO, I, WO­WTORYH, OSNOWNOJ MNOGO­
MERNYJ MASSIW W CELQH ``KONOMII PAMQTI HRA­
NITSQ KOMPAKTNO W WIDE ODNOMERNOGO, PO``TOMU
INDEKSNYE WYRAVENIQ WY“ISLQ@TSQ PO SLOVNYM
NELINEJNYM (OTNOSITELXNO PARAMETROW OB—EM­
L@]IH CIKLOW) FORMULAM.
pOSLE PERWOGO ANALIZA PODPROGRAMMY OLDA
BYLI OBNARUVENY TRI INTERESNYH FAKTA:
ffl WEKTORIZUEMOSTX WSEH SAMYH WNUTRENNIH CI­
KLOW OLDA MOVNO OPREDELITX DAVE SAMYMI
PROSTYMI SREDSTWAMI ANALIZA;
ffl WOZMOVNOSTX RASPARALLELIWANIQ CIKLOW,
NAHODQ]IHSQ NA WNE[NEM UROWNE, OPREDE­
LITX FORMALXNYMI METODAMI SLOVNO, NO
LEGKO GLQDQ NA TEKST, INYMI SLOWAMI, WI­
ZUALXNO. iMENNO PO ``TOJ PRI“INE NE UWELI­
“IWALISX ZNA“ENIQ BAZOWOJ PROIZWODITELX­
NOSTI DLQ ISHODNOGO WARIANTA S ROSTOM “I­
SLA PROCESSOROW, I IMENNO ``TOT FAKT POZWO­
LIL UWELI“ITX ZNA“ENIQ PROIZWODITELXNO­
STI DLQ MNOGOPROCESSORNYH KONFIGURACIJ W
SLU“AE RU“NOJ OPTIMIZACII;
ffl KOMBINACIQ SLOVNOJ CIKLI“ESKOJ STRUKTU­
RY, BOLX[OJ WLOVENNOSTI CIKLOW I KOM­
PAKTNOJ FORMY HRANENIQ OSNOWNOGO MASSIWA
QWLQETSQ O“ENX SERXEZNYM PREPQTSTWIEM DLQ
WYPOLNENIQ SKOLXKO­NIBUDX SLOVNOGO PRE­
OBRAZOWANIQ PROGRAMMY.
bEZUSLOWNO, TRETIJ FAKT SILXNO PORTIT OB­
]EE WPE“ATLENIE O PROGRAMME, NO ESLI PODPRO­
GRAMMA OLDA UVE OBLADAET ''HORO[EJ'' STRUK­
TUROJ, TO, BYTX MOVET, NAM NI“EGO S NEJ DELATX
I NE PRIDETSQ? oSOBENNOSTI ARHITEKTURY KOM­
PX@TEROW CRAY Y--MP --- NESKOLXKO WEKTORNO­
KONWEJERNYH PROCESSOROW NAD OB]EJ PAMQTX@,
DIKTU@T OB]EPRINQTU@ ''OPTIMALXNU@'' FORMU
PROGRAMM DLQ MA[IN DANNOGO KLASSA: WEKTORI­
ZUEMOSTX SAMYH WNUTRENNIH CIKLOW I WOZMOV­
NOSTX RASPARALLELIWANIQ NA WNE[NEM UROWNE.
dLQ NA“ALA POSMOTRIM, “TO DAET REALIZACIQ
ISHODNOGO WARIANTA TRFD, KOTORAQ U“ITYWA­
ET LI[X STRUKTURU WNE[NIH I WNUTRENNIH CI­
KLOW. s ODNOJ STORONY, W ISHODNOJ PROGRAMME
UDALOSX NAJTI STRUKTURY, HORO[O SOGLASU@]I­
ESQ S ARHITEKTUROJ KOMPX@TEROW TIPA CRAY Y--
MP: PRAKTI“ESKI WSE OPERACII PROGRAMMY IS­
POLNQ@TSQ W WEKTORNOM REVIME I PRAKTI“ESKI
WSE WREMQ WSE PROCESSORY MOGUT BYTX ZAGRUVE­
NY POLEZNOJ RABOTOJ. s DRUGOJ STORONY, DAVE
W SLU“AE RU“NOJ OPTIMIZACII, PROIZWODITELX­
NOSTX KAVDOGO PROCESSORA NE PREWY[AET 25% OT
programmirowanie N o
3 1996

4 antonow, woewodin
a a a a a a a a a a a
a a
a a a
a
a a a
a a
a a
rIS. 2.
PIKOWOJ!
qSNO, “TO NADO POPYTATXSQ “TO­TO IZMENITX,
NO WYPOLNITX KAKOE­LIBO SERXEZNOE PREOBRAZO­
WANIE PROGRAMMY, TAK VE KAK I PONQTX, NA “TO
IMENNO ONO DOLVNO BYTX NAPRAWLENO, NELXZQ ---
STRUKTURA PROGRAMMY WO MNOGOM OSTALASX NE­
RASKRYTOJ. w SAMOM DELE MY OPREDELILI TOLXKO
STRUKTURU SAMYH WNE[NIH I SAMYH WNUTRENNIH
CIKLOW ISHODNOJ PROGRAMMY. iMEQ STOLX BED­
NU@ INFORMACI@, MY NE SMOVEM NAJTI RE[ENIE
NI ODNOJ SERXEZNOJ PROBLEMY:
ffl NELXZQ OCENITX POTENCIALXNYH SWOJSTW PRO­
GRAMMY, W “ASTNOSTI, POTENCIAL PARALLE­
LIZMA;
ffl MNOGIE SWOJSTWA PROGRAMMY SKRYTY, A ZNA­
“IT I NE PONQTNO, NA USTRANENIE KAKIH FAK­
TOROW DOLVNO BYTX NAPRAWLENO PREOBRAZO­
WANIE;
ffl ESLI, ISHODQ IZ KAKIH­TO PREDPOLOVENIJ,
MY I WYBEREM SKOLXKO­NIBUDX NETRIWIALX­
NOE PREOBRAZOWANIE, TO W RAMKAH SU]ESTWU­
@]EJ FORMY ZAPISI PROGRAMMY WYPOLNITX
EGO BUDET TEHNI“ESKI KRAJNE SLOVNO;
ffl W PRINCIPE, WOZMOVEN I TAKOJ WARIANT, PRI
KOTOROM UVE POLU“ENNYE DLQ DANNOJ PRO­
GRAMMY 139.7 Mflop/s MY PREWYSITX I NE
SMOVEM, NO W ``TOM NADO BYTX TO“NO UWEREN­
NYM PREVDE, “EM OTKAZYWATXSQ OT KAKIH­
LIBO DALXNEJ[IH POPYTOK ULU“[ITX PROIZ­
WODITELXNOSTX.
wESX UKAZANNYJ KOMPLEKS PROBLEM BYL USPE[­
NO RE[EN, I PRINCIPIALXNO WAVNYE ``TAPY IS­
SLEDOWANIQ STRUKTURY PROGRAMMY OPISANY W
SLEDU@]EM RAZDELE.
3.2. TRFD I WEKTORNO­KONWEJERNAQ
ARHITEKTURA CRAY Y--MP
wOSSTANOWLENIE POLNORAZMERNYH MASSI­
WOW PO IH KOMPAKTNOJ FORME. mY UVE GO­
WORILI O TOM, “TO SERXEZNYM PREPQTSTWIEM DLQ
ANALIZA TRFD QWLQETSQ KOMPAKTNAQ FORMA HRA­
NENIQ MASSIWOW. ~TOBY RE[ITX ``TU PROBLEMU,
MY ISPOLXZOWALI TEHNIKU WOSSTANOWLENIQ POL­
NORAZMERNYH STRUKTUR DANNYH PO IH KOMPAKT­
NOJ FORME. nESMOTRQ NA TO, “TO DANNAQ ZADA“A
MOVET IMETX MNOGO RE[ENIJ, MY MOVEM WZQTX
L@BOE, PRI KOTOROM NOWYE INDEKSNYE WYRAVE­
NIQ BUDUT IMETX WID LINEJNOJ FUNKCII. w DAN­
NOM SLU“AE DLQ NAS WAVNO OPREDELITX STRUKTURU
PROGRAMMY, A S POMO]X@ KAKIH IMENNO STRUK­
TUR DANNYH --- TEH, S KOTORYMI RABOTAL AWTOR
PROGRAMMY, ILI KAKIH­LIBO DRUGIH --- ``TO NE
TAK SU]ESTWENNO. oDNOWREMENNO ZAMETIM, “TO
MY SOWSEM NE OTKAZYWAEMSQ OT ZADA“I ``KONOMII
PAMQTI, A LI[X OTKLADYWAEM EE RE[ENIE NA BO­
LEE POZDNIJ ``TAP.
oSNOWNOJ REZULXTAT DANNOJ PROCEDURY ZA­
KL@“AETSQ W TOM, “TO POSLE EE WYPOLNENIQ IN­
FORMACIONNAQ STRUKTURA PODPROGRAMMY OLDA
MOVET BYTX POLNOSTX@ OPREDELENA. ---TO DEJ­
STWITELXNO PRINCIPIALXNO WAVNYJ [AG, KOTO­
RYJ POMOG WYPOLNITX ``FFEKTIWNU@ OPTIMIZA­
CI@ DANNOJ PROGRAMMY KAK DLQ CRAY Y--MP,
TAK I DLQ CRAY T3D.
oPREDELENIE TO“NOJ INFORMACIONNOJ
STRUKTURY PROGRAMMY. pRIWEDENIE PODPRO­
GRAMMY K ANALIZIRUEMOJ FORME POZWOLILO TO“NO
OPREDELITX WSE INTERESU@]IE NAS SWOJSTWA: SU­
]ESTWOWANIE ILI OTSUTSTWIE ZAWISIMOSTI MEV­
DU OTDELXNYMI OPERATORAMI I FRAGMENTAMI, LO­
KALXNOSTX ISPOLXZOWANIQ DANNYH, WOZMOVNOSTX
PRIWATIZACII MASSIWOW I MNOGIE DRUGIE, NAIBO­
LEE WAVNYE IZ KOTORYH BUDUT OPISANY NIVE.
nAHOVDENIE I OPISANIE WSEGO POTENCI­
ALXNOGO PARALLELIZMA. dANNYJ PUNKT QWLQ­
ETSQ PRQMYM SLEDSTWIEM PREDYDU]EGO, TAK KAK
ESLI MY ZNAEM TO“NU@ INFORMACIONNU@ STRUK­
TURU PROGRAMMY, TO, ESTESTWENNO, MOVEM WY­
DELITX I WESX EE POTENCIALXNYJ PARALLELIZM.
wESX KOORDINATNYJ PARALLELIZM CIKLOW PODPRO­
GRAMMY OLDA HORO[O WIDEN NA EE CIKLI“ESKOM
PROFILE (RIS. 2), GDE TO“KAMI POME“ENY CIKLY S
NEZAWISIMYMI ITERACIQMI (WOSSTANOWLENIE POL­
NORAZMERNYH MASSIWOW PRIWELO K POQWLENI@ NO­
WYH CIKLOW, KOTORYH NE BYLO NA PROFILE ISHOD­
NOJ PODPROGRAMMY).
zAMETIM, “TO IZ DANNOJ KARTINKI SLEDUET
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 5
tABLICA 1.
CRAY M90 pIKOWAQ PROIZW. bAZOWAQ PROIZW. rU“NAQ OPT. V­Ray OPT.
CPUs Mflop/s Mflop/s Mflop/s Mflop/s
1 333 56:19 \Lambda 81:72 ! 247 y
4 1332 54.86 261.64 822
8 2664 54.34 481.03 954 +z
CRAY C90 pIKOWAQ PROIZW. bAZOWAQ PROIZW. rU“NAQ OPT. V­Ray OPT.
CPUs Mflop/s Mflop/s Mflop/s Mflop/s
1 960 89:5 \Lambda 139:71 ! 579:7 y
8 7680 89.6 962.68 2440:5 z
CRAY EL pIKOWAQ PROIZW. bAZOWAQ PROIZW. rU“NAQ OPT. V­Ray OPT.
CPUs Mflop/s Mflop/s Mflop/s Mflop/s
1 132 11.37 --- 54.60
2 264 11.40 --- 106.03
4 528 11.38 --- 193.32
rEZULXTATY OPTIMIZACII PROGRAMMY TRFD DLQ SEMEJSTWA
WEKTORNO­KONWEJERNYH SUPERKOMPX@TEROW CRAY.
O“ENX WAVNYJ WYWOD: ESLI W PROGRAMME ISPOLX­
ZOWATX TOLXKO PARALLELIZM SAMYH WNE[NIH I SA­
MYH WNUTRENNIH CIKLOW, TO BOLX[AQ “ASTX PO­
TENCIALA PROGRAMMY NE BUDET NIKAK ISPOLXZO­
WANA. oDNOWREMENNO S ``TIM, MY WIDIM I TOT RE­
ZERW, ZA S“ET KOTOROGO MOVNO W DALXNEJ[EM PO­
LU“ITX USKORENIE, I KOTORYJ OPREDELQET OB]U@
STRATEGI@ PREOBRAZOWANIQ PROGRAMMY:
ffl OB—EDINITX PO DWA SAMYH WNE[NIH CIKLA
W PERWOM I TRETXEM GNEZDE W ODIN, UWELI­
“IW IH DLINU W SREDNEM S num=2 DO num \Lambda
(num + 1)=2, PEREMESTITX ``TI DLINNYE CI­
KLY WNUTRX I IMENNO IH ISPOLXZOWATX DLQ
WEKTORIZACII (WTOROE GNEZDO SLUVIT TOLXKO
DLQ PERESYLKI DANNYH I NE SODERVIT ARIF­
METI“ESKIH OPERACIJ);
ffl SAMYE WNUTRENNIE CIKLY ISHODNOGO WARIAN­
TA PODPROGRAMMY PEREMESTITX NARUVU I IS­
POLXZOWATX DLQ PARALLELXNOGO ISPOLNENIQ
WSEMI PROCESSORAMI KOMPX@TERA CRAY Y--
MP;
ffl POSLEDOWATELXNYE CIKLY, OPREDELQ@]IE PE­
REWY“ISLENIE ODNIH I TEH VE ``LEMENTOW MAS­
SIWOW, ISPOLXZOWATX DLQ POWY[ENIQ LOKALX­
NOSTI OBRA]ENIQ K DANNYM.
oPTIMIZACIQ RABOTY S PAMQTX@. oPTI­
MIZACIQ RABOTY S PAMQTX@ IMEET BOLX[OE ZNA­
“ENIE DLQ ``FFEKTIWNOJ RABOTY PROGRAMM NA
KOMPX@TERAH TIPA CRAY Y--MP, HOTQ ``TOT
ASPEKT O“ENX “ASTO UPUSKAETSQ IZ RASSMOTRENIQ.
~A]E WSEGO DANNYJ WID OPTIMIZACII SWODITSQ
K UMENX[ENI@ “ISLA PERESYLOK DANNYH MEVDU
PAMQTX@ I WEKTORNYMI REGISTRAMI. w TERMI­
NAH V­Ray TEHNOLOGII TAKAQ OPTIMIZACIQ OZNA­
“AET ISSLEDOWANIE LOKALXNOSTI ISPOLXZOWANIQ
DANNYH I CELESOOBRAZNOSTI ISPOLXZOWANIQ WRE­
MENNYH MASSIWOW. w “ASTNOSTI, DLQ PROGRAMMY
TRFD IMENNO UWELI“ENIE LOKALXNOSTI ISPOLX­
ZOWANIQ WEKTOROW PRIWELO K ZAMETNOMU UWELI“E­
NI@ PROIZWODITELXNOSTI.
pRIWATIZACIQ (privatization) MASSIWOW.
dANNAQ ZADA“A K NASTOQ]EMU MOMENTU IZWEST­
NA DOSTATO“NO HORO[O I ZAKL@“AETSQ W NAHOVDE­
NII PEREMENNYH, KOTORYE MOGUT BYTX OB—QWLENY
LOKALXNYMI DLQ KAVDOJ PARALLELXNO RABOTA@­
]EJ WETWI PROGRAMMY. iSPOLXZOWANNAQ TEHNIKA
PRIWATIZACII MASSIWOW, TAK VE KAK I TEHNIKA
ISSLEDOWANIQ SWOJSTW LOKALXNOSTI PROGRAMMY,
OPIRALASX NA ANALIZ FORMULXNOGO PREDSTAWLE­
NIQ STRUKTURY GRAFA ALGORITMA ISSLEDUEMOGO
FRAGMENTA.
bYLA PROWEDENA SERIQ ``KSPERIMENTOW NA KOM­
PX@TERAH CRAY Y--MP M90/C90 I CRAY EL,
REZULXTATY KOTORYH PRIWEDENY W TABLICE 1. ~E­
TYRE STOLBCA S RAZLI“NYMI ZNA“ENIQMI PROIZ­
WODITELXNOSTI OZNA“A@T SLEDU@]EE:
ffl ''pIKOWAQ PROIZW.'': PIKOWAQ PROIZWODITELX­
NOSTX KOMPX@TERA W UKAZANNOJ KONFIGURA­
programmirowanie N o
3 1996

6 antonow, woewodin
CII;
ffl ''bAZOWAQ PROIZW.'': PROIZWODITELXNOSTX, PO­
LU“ENNAQ NA PROGRAMME, K KOTOROJ NE PRIME­
NQLOSX NIKAKOJ RU“NOJ OPTIMIZACII, ZA IS­
KL@“ENIEM ISPOLXZOWANIQ PODHODQ]IH FLA­
GOW KOMPILQTORA;
ffl ''rU“NAQ OPT.'': NAILU“[IE ZNA“ENIQ PROIZ­
WODITELXNOSTI, POLU“ENNYE NA MOMENT WY­
POLNENIQ NA[IH ISSLEDOWANIJ S POMO]X@
RU“NOJ OPTIMIZACII KODA;
ffl ''V­Ray OPT.'': ZNA“ENIQ PROIZWODITELXNO­
STI, POLU“ENNYE POSLE PREOBRAZOWANIQ PRO­
GRAMMY TRFD SOGLASNO V­Ray TEHNOLOGII.
sDELAEM NESKOLXKO ZAME“ANIJ K TABL. 1:
(+) DANNOE ZNA“ENIE POLU“ENO NE W MONOPOLXNOM
REVIME I ZAWEDOMO MOVET BYTX ULU“[ENO;
(*) CIFRY ZANIMA@T SEDXMOE MESTO SREDI ZNA“E­
NIJ PROIZWODITELXNOSTI WSEH TRINADCATI PRO­
GRAMM PAKETA Perfect Club;
(!) CIFRY ZANIMA@T DEWQTOE MESTO SREDI ZNA­
“ENIJ PROIZWODITELXNOSTI ''rU“NAQ OPT.'' WSEH
OPTIMIZIROWANNYH PROGRAMM DANNOGO PAKETA;
(y) CIFRY ZANQLI PERWOE MESTO SREDI ZNA“E­
NIJ PROIZWODITELXNOSTI WSEH OPTIMIZIROWAN­
NYH (''rU“NAQ OPT.'') PROGRAMM PAKETA;
(z) CIFRY ZANQLI WTOROE MESTO SREDI ZNA“E­
NIJ PROIZWODITELXNOSTI WSEH OPTIMIZIROWAN­
NYH (''rU“NAQ OPT.'') PROGRAMM PAKETA Perfect
Club, USTUPAQ LI[X HORO[O OPTIMIZIRUEMOJ
PROGRAMME MG3D.
wAVNO OTMETITX I TO, “TO WSQ OPTIMIZACIQ
DANNOJ PROGRAMMY BYLA WYPOLNENA NA UROWNE
fORTRANA BEZ ISPOLXZOWANIQ ASSEMBLERNYH WSTA­
WOK I OBRA]ENIJ K WYSOKO``FFEKTIWNYM BIBLIO­
TE“NYM PODPROGRAMMAM.
3.3. TRFD I MASSIWNO­PARALLELXNAQ
ARHITEKTURA CRAY T3D
mETODY OPTIMIZACII PROGRAMMY TRFD, KO­
TORYE MY ISPOLXZOWALI DLQ KOMPX@TERA CRAY
T3D, KORENNYM OBRAZOM OTLI“A@TSQ OT METODOW
OPTIMIZACII DLQ WEKTORNO­KONWEJERNYH MODELEJ
CRAY Y­MP M90/C90 I CRAY EL. ---TO RAZLI­
“IE OPREDELQETSQ TEM, “TO CRAY T3D --- ``TO
MASSIWNO­PARALLELXNYJ KOMPX@TER S RASPREDE­
LENNOJ PAMQTX@.
dLQ POLU“ENIQ DEJSTWITELXNO MAS[TABIRUE­
MOJ PROGRAMMY S HORO[EJ PROIZWODITELXNOSTX@
NEOBHODIMO MAKSIMALXNO INTENSIWNO ISPOLXZO­
WATX WSE OSOBENNOSTI DANNOJ ARHITEKTURY, A
ZNA“IT, W PROCESSE ISSLEDOWANIQ I PREOBRAZOWA­
NIQ ISHODNOJ PROGRAMMY NADO POPYTATXSQ:
ffl WYDELITX PARALLELXNYE WETWI WY“ISLENIJ,
“ISLO KOTORYH DOLVNO BYTX SRAWNIMO S “I­
SLOM PROCESSOROW;
ffl NAJTI RASPREDELENIE MASSIWOW PO PROCESSO­
RAM, SOGLASOWANNOE S PARALLELIZMOM WY“I­
SLENIJ DLQ MINIMIZACII MEVPROCESSORNOGO
OBMENA;
ffl PROWESTI OPTIMIZACI@ NA KAVDOM PROCES­
SORE DLQ ``FFEKTIWNOGO ISPOLXZOWANIQ K``[­
PAMQTI I SBALANSIROWANNOJ ZAGRUZKI FUNK­
CIONALXNYH USTROJSTW PROCESSORA DEC
ALPHA.
rESURS PARALLELIZMA PROGRAMMY TRFD NAM
UVE IZWESTEN --- EGO OSNOWNAQ “ASTX BYLA POKA­
ZANA NA RAZME“ENNOM CIKLI“ESKOM PROFILE POD­
PROGRAMMY OLDA. dLQ ISSLEDOWANIQ MNOVESTWA
WOZMOVNYH RASPREDELENIJ DANNYH PO PROCESSO­
RAM MY ISPOLXZOWALI SREDSTWA V­Ray TEHNOLO­
GII, W REZULXTATE “EGO BYLO DOKAZANO, “TO:
ffl DLQ KAVDOGO IZ TREH GNEZD PODPROGRAMMY
OLDA SU]ESTWU@T RASPREDELENIQ DANNYH,
SOGLASOWANNYE S ISPOLXZOWANIEM DWUMERNO­
GO PARALLELIZMA (DWUMERNYJ PARALLELIZM
PREDPOLAGAET NEZAWISIMOSTX ITERACIJ DWUH
CIKLOW GNEZDA, A SOGLASOWANNOSTX RASPRE­
DELENIQ, W DANNOM SLU“AE, OZNA“AET OTSUT­
STWIE PERESYLOK DANNYH MEVDU ITERACIQMI
``TIH CIKLOW);
ffl NE SU]ESTWUET EDINOGO DLQ WSEH TREH GNEZD
RASPREDELENIQ DANNYH, SOGLASOWANNOGO S IS­
POLXZOWANIEM HOTQ BY ODNOMERNOGO PARALLE­
LIZMA W KAVDOM GNEZDE;
rASPOLAGAQ TAKOJ INFORMACIEJ, NAM OSTAET­
SQ EDINSTWENNOE RE[ENIE: PARALLELXNOE WYPOL­
NENIE KAVDOGO GNEZDA I PERERASPREDELENIE DAN­
NYH MEVDU NIMI. rEZULXTIRU@]AQ PARALLELX­
NAQ PROGRAMMA BYLA NAPISANA W TERMINAH SPECI­
ALXNOJ BIBLIOTEKI KOMMUNIKACIONNYH PRIMI­
TIWOW, POSKOLXKU [TATNYE SREDSTWA (TIPA PVM
DLQ CRAY T3D) OKAZALISX O“ENX NE``FFEKTIWNY­
MI.
rEZULXTATY “ISLENNYH ``KSPERIMENTOW POKAZA­
NY W TABL. 2, STOLBCY 2­5 KOTOROJ OZNA“A@T SLE­
DU@]EE:
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 7
tABLICA 2.
CRAY T3D PVM OPT. No cache OPT. V­Ray OPT. V­Ray OPT.
PEs seconds seconds seconds Mflop/s
4 11.35 11.03 6.013 71.66
8 6.05 6.04 3.215 134.01
16 3.23 3.23 1.702 253.43
32 1.68 1.72 0.896 480.85
64 1.02 0.93 0.494 871.44
128 0.79 0.56 0.301 1435.96
256 0.86 0.41 0.253 1700.93
rEZULXTATY OPTIMIZACII PROGRAMMY TRFD DLQ MASSIWNO­PARALLELXNOGO
SUPERKOMPX@TERA CRAY T3D.
''PVM OPT.'' --- REZULXTATY RABOTY PARALLELX­
NOJ PROGRAMMY, NAPISANNOJ W TERMINAH PVM,
BEZ WYPOLNENIQ SKALQRNOJ OPTIMIZACII;
''No cache OPT.'' --- REZULXTATY RABOTY PARAL­
LELXNOJ PROGRAMMY, NAPISANNOJ W TERMINAH NA­
[EJ BIBLIOTEKI KOMMUNIKACIONNYH PRIMITI­
WOW, BEZ WYPOLNENIQ SKALQRNOJ OPTIMIZACII;
''V­Ray OPT.'' --- PREDYDU]IJ WARIANT I SKALQR­
NAQ OPTIMIZACIQ.
dANNAQ TABLICA O“ENX HORO[O DEMONSTRIRU­
ET ``FFEKT, POLU“AEMYJ NA RAZNYH ``TAPAH OPTI­
MIZACII PROGRAMMY. nESMOTRQ NA PRISUTSTWIE
W ISHODNOJ WERSII PROGRAMMY OPERACII, ANALO­
GI“NOJ TRANSPONIROWANI@ (WTOROE GNEZDO W POD­
PROGRAMME OLDA), KOTORAQ, PO OB]EMU PRIZNA­
NI@, QWLQETSQ KRAJNE ''NEUDOBNOJ'' DLQ MASSIWNO­
PARALLELXNYH KOMPX@TEROW S RASPREDELENNOJ
PAMQTX@, O“EWIDNO WYSOKOE KA“ESTWO POLU“EN­
NOJ PARALLELXNOJ PROGRAMMY.
4. issledowanie i optimizaciq
programmy FLO52
4.1. oB]AQ HARAKTERISTIKA I STRUKTURA
FLO52
pROGRAMMA FLO52 PREDSTAWLQET SOBOJ UPRO­
]ENNYJ WARIANT REALIZACII ODNOJ IZ ZADA“ WY­
“ISLITELXNOJ GIDRODINAMIKI. w OTLI“IE OT
TRFD, ONA DOSTATO“NO WELIKA I SOSTOIT IZ
31 PODPROGRAMMY OB]IM OB—EMOM BOLEE 2000
STROK NA QZYKE fORTRAN. iSHODNYJ WARIANT
FLO52 UVE BYL NAPISAN W RAS“ETE NA WEKTORNO­
KONWEJERNU@ ARHITEKTURU, PO``TOMU DLQ NAS
OSNOWNOJ INTERES PREDSTAWLQLA WOZMOVNOSTX ``F­
FEKTIWNOJ ADAPTACII ``TOJ PROGRAMMY K PRIN­
CIPIALXNO INOJ ARHITEKTURE KOMPX@TERA CRAY
T3D.
kAK I DLQ L@BOJ PROGRAMMY, PERWOE, “TO NEOB­
HODIMO PONQTX PERED OPTIMIZACIEJ, --- ``TO EE OB­
]AQ STRUKTURA: GDE SOSREDOTO“ENA NAIBOLX[AQ
“ASTX WY“ISLENIJ, GDE NAHODITSQ WWOD/WYWOD,
INICIALIZACIQ I T. D. ---TU INFORMACI@ MOVNO
POLU“ITX RAZNYMI SPOSOBAMI, NAPRIMER, ANALI­
ZIRUQ GRAF WYZOWOW PROGRAMMY I GRAFY UPRA­
WLENIQ OTDELXNYH PODPROGRAMM. nA RIS. 3 POKA­
ZAN GRAF WYZOWOW PROCEDUR PROGRAMMY FLO52.
tEMNYE WER[INY SOOTWETSTWU@T PODPROGRAM­
MAM OSNOWNOGO WY“ISLITELXNOGO QDRA, NA KOTO­
ROE PRIHODITSQ PO“TI 90% WREMENI WYPOLNENIQ
WSEJ PROGRAMMY, PO``TOMU IH ANALIZ NADO PROIZ­
WODITX W PERWU@ O“EREDX.
nAKLONNOJ “ERTOJ W GRAFE POME“ENY PODPRO­
GRAMMY, SODERVA]IE OPERACII WWODA­WYWODA.
pOSKOLXKU PARALLELXNYJ WWOD­WYWOD W CRAY
T3D POKA NE REALIZOWAN, MY BYLI WYNUVDENY
WYPOLNQTX ``TI PODPROGRAMMY W POSLEDOWATELX­
NOM REVIME. pRI POSLEDOWATELXNOM WYPOLNE­
NII WSEJ PROGRAMMY NA PODPROGRAMMY S WWODOM­
WYWODOM SUMMARNO PRIHODITSQ OKOLO 2% WREME­
NI, PO``TOMU PO ZAKONU aMDALA POLU“ITX USKORE­
NIE BOLX[E 50­TI BUDET W PRINCIPE NEWOZMOVNO.
4.2. pOTENCIAL PARALLELIZMA PROGRAMMY
pOSLE OPREDELENIQ STRUKTURY PROGRAMMY I
WYDELENIQ NAIBOLEE WAVNYH EE U“ASTKOW WOZNI­
KAET ZADA“A NAHOVDENIQ WSEGO PRISU]EGO PRO­
GRAMME PARALLELIZMA. dLQ OCENKI POTENCIA­
LA PARALLELIZMA ISSLEDUETSQ INFORMACIONNAQ
programmirowanie N o
3 1996

8 antonow, woewodin
rIS. 3.
a a a a a a a a a a
a
rIS. 4.
STRUKTURA OTDELXNYH PODPROGRAMM, “TO POZWO­
LQET NAJTI REZERW OSNOWNYH WIDOW PARALLELIZ­
MA: NEZAWISIMYH WETWEJ WY“ISLENIJ, KOORDI­
NATNOGO I SKO[ENNOGO PARALLELIZMA CIKLOW, A
TAKVE WYDELITX POSLEDOWATELXNYE CIKLY, RE­
ALIZU@]IE GLOBALXNYE OPERACII, DLQ KOTORYH
MOVNO BUDET ISPOLXZOWATX SPECIALXNYE METODY
OBRABOTKI.
pRIMENITELXNO K FLO52 BYLO OBNARUVENO,
“TO W PROGRAMME ESTX BOLX[OJ REZERW PROSTO­
GO DLQ ISPOLXZOWANIQ KOORDINATNOGO PARAL­
LELIZMA. pRAKTI“ESKI WSE CIKLY EE WY“ISLI­
TELXNOGO QDRA OBLADA@T SWOJSTWOM ParDo, KO­
TOROE OZNA“AET, “TO NA POSLEDOWATELXNOSTX WY­
POLNENIQ ITERACIJ ``TIH CIKLOW NE NAKLADYWA­
ETSQ NIKAKIH OGRANI“ENIJ, I, W “ASTNOSTI, IH
MOVNO WYPOLNQTX PARALLELXNO. wOZXMEM, NA­
PRIMER, CIKLI“ESKIJ PROFILX PODPROGRAMMY
EFLUX (RIS. 4), IZ KOTOROGO WIDNO, “TO ``TIM
SWOJSTWOM OBLADA@T WSE CIKLY DANNOJ PODPRO­
GRAMMY, I TAKAQ SITUACIQ QWLQETSQ TIPI“NOJ
DLQ WSEGO QDRA.
pOSLEDOWATELXNYE CIKLY --- KANDIDATY
W GLOBALXNYE OPERACII. dAVE ESLI CIKL
QWLQETSQ POSLEDOWATELXNYM, INOGDA EGO MOVNO
WYPOLNITX BOLEE ``FFEKTIWNO, ISPOLXZUQ DRUGOJ
ALGORITM DLQ ZALOVENNOJ W NEM OPERACII. w
PODPROGRAMMAH EULER, FORCF I STEP BYLI
OBNARUVENY FRAGMENTY, W KOTORYH WYPOLNQ@T­
SQ GLOBALXNYE OPERACII NAD CELYMI MASSIWA­
MI (NAHOVDENIE GLOBALXNOJ SUMMY, GLOBALXNYH
MINIMUMA I MAKSIMUMA). pRI REALIZACII TA­
KIH OPERACIJ NA KOMPX@TERE S RASPREDELENNOJ
PAMQTX@ POTREBU@TSQ SU]ESTWENNYE NAKLADNYE
RASHODY, PO``TOMU OBNARUVENNYE FRAGMENTY BY­
LI ZAMENENY NA WYZOWY PODPROGRAMM, OPTIMI­
ZIROWANNYH SPECIALXNO DLQ ARHITEKTURY CRAY
T3D. pOSKOLXKU PODOBNAQ SITUACIQ QWLQETSQ TI­
PI“NOJ DLQ MASSIWNO­PARALLELXNYH KOMPX@TE­
ROW, TO PRAKTI“ESKI WEZDE ZARANEE PREDUSMOTRE­
NY PROCEDURY DLQ GLOBALXNYH OPERACIJ.
eSTX LI DOPOLNITELXNYE REZERWY PARAL­
LELIZMA? ---TOT WOPROS PRINCIPIALXNO WAVEN
PRI ADAPTACII L@BOJ PROGRAMMY. iSPOLXZUQ
ANALITI“ESKIE I WIZUALXNYE SREDSTWA ANALIZA
SISTEMY V­Ray, MOVNO POKAZATX, “TO DRUGOJ WOZ­
MOVNOSTI, KROME ISPOLXZOWANIQ KOORDINATNOGO
PARALLELIZMA PODPROGRAMM, NET. s DRUGOJ STO­
RONY, ISPOLXZOWANIE WSEGO NAJDENNOGO PARALLE­
LIZMA NECELESOOBRAZNO IZ­ZA SLOVNOSTI NEOBHO­
DIMYH PERESYLOK DANNYH, PO``TOMU W DALXNEJ­
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 9
d ­ d ­ d ­ d ­ d ­ d ­ d
d d d d d d d
d
6
d
6
d
6
d
? d
? d
6
­
6
­
1
JL JL
1
1 IL IL
1
oe
oe
oe
oe
oe
J J
I I
2 2
2 2
X
X
Xy
d ­ d ­ d ­ d ­ d ­ d ­ d
d d d d d d
oe
oe
oe
oe
oe X
X
Xy
d ­ d ­ d ­ d ­ d ­ d ­ d
d d d d d d
oe
oe
oe
oe
oe X
X
Xy
d ­ d ­ d ­ d ­ d ­ d ­ d
d d d d d d
oe
oe
oe
oe
oe X
X
Xy
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
d
d
6
d
6
d
6
d
? d
? d
C
C CW
rIS. 5.
j j j j
j j j j
j
1 2 3 4
5 6 7 8
9
PE1 PE2 PE3 PE4
j j j j
j j j j
j
1 4 6 8
2 5 7 9
3
PE1 PE2 PE3 PE4
j j j
j j j
j
j j
1 4 7
2 5 8
9
3 6
PE1 PE2 PE3 PE4
j j j j
j j j j
j
1 3 5 7
2 4 6 8
9
PE1 PE2 PE3 PE4
cIKLI“ESKIE RASPREDELENIQ bLO“NYE RASPREDELENIQ
PO ODNOJ PO NESKOLXKO S RAWNOMERNOJ S MAKSIMALXNOJ
ITERACII ITERACIJ ZAGRUZKOJ ZAGRUZKOJ
rIS. 6.
[EM NADO OPREDELITX TU “ASTX PARALLELIZMA, NA
KOTOROJ I BUDET BAZIROWATXSQ PARALLELXNAQ WER­
SIQ PROGRAMMY.
4.3. kAKOE RASPREDELENIE DANNYH
ISPOLXZOWATX?
pOSLE NAHOVDENIQ RESURSA PARALLELIZMA PRO­
GRAMMY NADO OPREDELITX, KAKIM OBRAZOM EGO
LU“[E ISPOLXZOWATX, T. E. KAK RASPREDELITX DAN­
NYE PROGRAMMY I WYPOLNQEMYE OPERACII MEVDU
p--- (PROCESSORNYMI ``LEMENTAMI). cELX OPTI­
MIZACII PROGRAMMY --- MINIMIZACIQ WREMENI
EE ISPOLNENIQ. ---TOGO MOVNO DOSTI“X S POMO­
]X@ RAWNOMERNOGO RASPREDELENIQ RABOTY MEVDU
PROCESSORAMI I MINIMIZACII MEVPROCESSORNOGO
WZAIMODEJSTWIQ.
tRIWIALXNOE RASPREDELENIE MASSIWOW.
~ASTX FRAGMENTOW FLO52 USTROENA TAK, “TO DLQ
NIH ODINAKOWO HORO[O PODHODIT L@BOE RAWNO­
MERNOE RASPREDELENIE DANNYH. pRI ``TOM LEGKO
OBESPE“ITX RAWNOMERNU@ ZAGRUZKU PROCESSOROW I
ORGANIZOWATX PARALLELXNOE WYPOLNENIE BEZ PE­
RESYLOK WOOB]E. sTRUKTURA ``TIH FRAGMENTOW
PRIMERNO TAKOWA (PRIMER WZQT IZ PODPROGRAMMY
EULER):
DO 42 J=2,JL
DO 42 I=2,IL
WR(I,J,1) = WR(I,J,1) ­DW(I,J,1)
WR(I,J,2) = WR(I,J,2) ­DW(I,J,2)
WR(I,J,3) = WR(I,J,3) ­DW(I,J,3)
WR(I,J,4) = WR(I,J,4) ­DW(I,J,4)
42 CONTINUE
w TAKIH FRAGMENTAH NA KAVDOJ ITERACII TRE­
BU@TSQ TOLXKO ZNA“ENIQ S ``ODNOIMENNYH'' ITERA­
CIJ PREDYDU]IH CIKLOW, I PRI EDINOM DLQ WSEH
CIKLOW RASPREDELENII ITERACIJ PO PROCESSORAM
PERESYLOK NE TREBUETSQ SOWSEM.
kOORDINATNOE RASPREDELENIE. dLQ BOLX­
[EJ “ASTI PODPROGRAMM WY“ISLITELXNOGO QDRA
LU“[IM RASPREDELENIEM MASSIWOW QWLQETSQ KO­
ORDINATNOE, T. E. RASPREDELENIE ODNOJ ILI
NESKOLXKIH RAZMERNOSTEJ KL@“EWYH MASSIWOW.
pRI TAKOM RASPREDELENII REALIZACIQ PODOBNYH
CIKLOW TREBUET MINIMALXNOGO KOLI“ESTWA PERE­
SYLOK, QWLQ@]IHSQ REGULQRNYMI. nAPRIMER:
DO 20 J=2,JL
DO 20 I=2,IL
FS(I,J,N) = DIS2(I,J)*FS(I,J,N)­
* DIS4(I,J)*DW(I,J,N)
20 CONTINUE
DO 30 J=2,JL
DO 30 I=2,IL
programmirowanie N o
3 1996

10 antonow, woewodin
FW(I,J,N) = SFIL*FW(I,J,N)­
* FS(I,J,N)+FS(I­1,J­1,N)
30 CONTINUE
pOSKOLXKU OBA DWUMERNYH CIKLA QWLQ@TSQ
PARALLELXNYMI, PERESYLKI PRI SOGLASOWANNOM
RASPREDELENII OSNOWNYH MASSIWOW MOGUT POTRE­
BOWATXSQ TOLXKO PERED WYPOLNENIEM WTOROGO CI­
KLA, TAK KAK W NEM NA (I ; J)­OJ ITERACII TREBU­
@TSQ ``LEMENTY MASSIWA FS, WY“ISLENNYE W PRE­
DYDU]EM CIKLE NA (I \Gamma 1; J \Gamma 1)­OJ ITERACII.
tAKIE PERESYLKI POTREBU@TSQ PRI L@BOM RAS­
PREDELENII DANNYH, NO PRI KOORDINATNOM RAS­
PREDELENII ONI STANOWQTSQ PRO]E.
PSMOO --- UZKOE MESTO DLQ FLO52. nA
PODPROGRAMMU PSMOO NA POSLEDOWATELXNOJ MA­
[INE PRIHODITSQ OKOLO 20% WREMENI RABOTY
WSEJ PROGRAMMY, ODNAKO ONA STANOWITSQ E]E BO­
LEE ZNA“IMOJ PRI REALIZACII NA PARALLELXNOM
KOMPX@TERE. kAK POKAZYWAET DETALXNYJ ANALIZ,
NE SU]ESTWUET TAKOGO RASPREDELENIQ DANNYH I
ITERACIJ, PRI KOTOROM WOZMOVNO WYPOLNENIE W
PARALLELXNOM REVIME WSEJ PODPROGRAMMY BEZ
PERESYLOK WOOB]E: DWE EE “ASTI OBLADA@T PA­
RALLELIZMOM PO RAZNYM RAZMERNOSTQM, OSTAWA­
QSX SU]ESTWENNO POSLEDOWATELXNYMI PO DRUGIM.
dWE “ASTI RIS. 5 SHEMATI“NO IZOBRAVA@T IN­
FORMACIONNYE ZAWISIMOSTI W PROSTRANSTWE ITE­
RACIJ DWUH “ASTEJ PSMOO. pERWAQ “ASTX SODER­
VIT POSLEDOWATELXNYE WY“ISLENIQ WDOLX OSI I ,
A WTORAQ --- WDOLX OSI J . wER[INY, RASPOLO­
VENNYE NA RISUNKE RQDOM, A TAKVE W SOOTWET­
STWU@]IH POZICIQH DWUH “ASTEJ RISUNKA, OTWE­
“A@T WY“ISLENI@ ODNIH I TEH VE ``LEMENTOW MAS­
SIWA. wSE ``LEMENTY MASSIWA (KROME POSLEDNIH)
W KAVDOJ IZ DWUH “ASTEJ PSMOO WY“ISLQ@TSQ
DWAVDY: PRI WY“ISLENII WDOLX SOOTWETSTWU@­
]EJ OSI I OBRATNO. iSPOLXZOWANIE EDINOGO RAS­
PREDELENIQ DLQ OBEIH “ASTEJ PSMOO PRIWEDET
K PARALLELXNOMU WYPOLNENI@ TOLXKO ODNOJ PO­
LOWINY PODPROGRAMMY, SLEDOWATELXNO, NA L@­
BOM “ISLE PROCESSOROW NEWOZMOVNO BUDET POLU­
“ITX USKORENIE BOLX[E, “EM W DWA RAZA. pO ``TOJ
PRI“INE DLQ PARALLELXNOGO WYPOLNENIQ PSMOO
NEOBHODIMO PROWODITX PERERASPREDELENIE DAN­
NYH, PRI“EM PERERASPREDELENIE POTREBUETSQ PE­
RED WYPOLNENIEM TOJ “ASTI PSMOO, KOTORAQ IS­
POLXZUET INOE PO OTNO[ENI@ K OSNOWNOJ SHEME
RASPREDELENIE, I POSLE NEE DLQ WOSSTANOWLENIQ
ISHODNOGO RASPREDELENIQ.
wYBOR RASPREDELENIQ. wOZMOVNOSTX IS­
POLXZOWANIQ PARALLELIZMA TOLXKO PO ODNOJ RAZ­
MERNOSTI W ODNOJ IZ NAIBOLEE WAVNYH PODPRO­
GRAMM (PSMOO) I MALOE “ISLO ITERACIJ PO DRU­
GIM RAZMERNOSTQM OPREDELILI TO, “TO W PRO­
GRAMME FLO52 PRI[LOSX ISPOLXZOWATX KOORDI­
NATNYJ PARALLELIZM TOLXKO PO SAMOJ BOLX[OJ
RAZMERNOSTI. wMESTE S TEM, “ISLO ITERACIJ PO
``TOJ RAZMERNOSTI, MENQ@]EESQ OT 21 DO 161 W MA­
LOM WARIANTE FLO52, OKAZALOSX SU]ESTWENNYM
SDERVIWA@]IM FAKTOROM PRI WYPOLNENII PRO­
GRAMMY DAVE NA OTNOSITELXNO NEBOLX[OM “ISLE
PROCESSOROW, TAK KAK UVE PRI 32 p--- NE WSEGDA
HWATAET ITERACIJ DLQ ZAGRUZKI WSEH PROCESSOROW
POLEZNOJ RABOTOJ.
4.4. kAK RASPREDELQTX ITERACII CIKLOW?
dLQ ISPOLXZOWANIQ WYBRANNOJ “ASTI PARALLE­
LIZMA NUVNO WYBRATX METOD RASPREDELENIQ ITE­
RACIJ CIKLOW MEVDU PROCESSORAMI WY“ISLI­
TELXNOJ SISTEMY. wOZMOVNYE RASPREDELENIQ
--- CIKLI“ESKI PO ODNOJ ITERACII, CIKLI“ESKI
PO NESKOLXKO ITERACIJ, RAWNYMI MAKSIMALXNY­
MI POSLEDOWATELXNYMI PORCIQMI I T. D., MOGUT
MINIMIZIROWATX KOLI“ESTWO NEOBHODIMYH PERE­
SYLOK. dLQ ``TOGO NEOBHODIMO WYDELITX TAKIE
GRUPPY ITERACIJ, WNUTRI KOTORYH BYLO BY SO­
SREDOTO“ENO NAIBOLX[EE “ISLO ZAWISIMOSTEJ PO
DANNYM. nA RIS. 6 PREDSTAWLENY WOZMOVNYE
SHEMY RASPREDELENIQ ITERACIJ. kONE“NO, WY­
BOR SHEMY RASPREDELENIQ ITERACIJ POLNOSTX@
OPREDELQETSQ OSOBENNOSTQMI KAVDOJ KONKRETNOJ
PROGRAMMY. wO FLO52 BOLX[INSTWO PERESYLOK
SWQZYWA@T SOSEDNIE ITERACII RASPREDELQEMYH
CIKLOW, PO``TOMU WYGODNEE ISPOLXZOWATX BLO“­
NYE RASPREDELENIQ, PRI KOTORYH MAKSIMALXNOE
“ISLO POSLEDOWATELXNYH ITERACIJ POPADAET NA
ODIN p---. iZ BLO“NYH RASPREDELENIJ SLEDUET WY­
BRATX RASPREDELENIE S MAKSIMALXNOJ ZAGRUZKOJ.
nERAWNOMERNOSTX ZAGRUZKI PROCESSOROW NE SKA­
VETSQ NA OB]EM WREMENI WYPOLNENIQ CIKLA, TAK
KAK OPREDELQTX WREMQ BUDUT PROCESSORY S NAI­
BOLX[IM “ISLOM ITERACIJ. w TO VE WREMQ, PRI
RASPREDELENII S MAKSIMALXNOJ ZAGRUZKOJ POTRE­
BUETSQ MENX[E PERESYLOK, “EM PRI RASPREDELE­
NII S RAWNOMERNOJ ZAGRUZKOJ, “TO SNIVAET NA­
GRUZKU NA KOMMUNIKACIONNU@ SETX I, KAK SLED­
STWIE, POZWOLQET UMENX[ITX OB]EE WREMQ WYPOL­
NENIQ PROGRAMMY. kAK POKAZALA PRAKTIKA, IS­
POLXZOWANIE RASPREDELENIQ S MAKSIMALXNOJ ZA­
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 11
@ @R @ @R @ @R @ @R
...
eflux psmoo1
1 2 3 N 1 2 3 N
Q Qs
Q Qs
Q Qs
...
¸
¸
¸
¸
¸
¸9 \Gamma
\Gamma\Psi
\Phi
\Phi
\Phiú
XXXXX Xz
@ @R
H H Hj
1 2 3 N
...
...
psmoo2
XXXXX Xz
¸
¸
¸
¸
¸
¸9 @ @R
H H Hj
\Gamma
\Gamma\Psi @ @R
P P P P Pq
i
i
i
i
i)
\Phi
\Phi
\Phiú
...
1 2 3 N
psmoo3
\Phi
\Phi
\Phiú \Gamma
\Gamma\Psi
H H Hj XXXXX Xz
¸
¸
¸
¸
¸
¸9 @ @R
H H Hj
\Gamma
\Gamma\Psi @ @R
P P P P Pq
i
i
i
i
i)
\Phi
\Phi
\Phiú
1 2 3 N
\Phi
\Phi
\Phiú \Gamma
\Gamma\Psi
H H Hj
XXXXX Xz
¸
¸
¸
¸
¸
¸9 @ @R
H H Hj
\Gamma
\Gamma\Psi @ @R
P P P P Pq
i
i
i
i
i)
\Phi
\Phi
\Phiú
\Phi
\Phi
\Phiú \Gamma
\Gamma\Psi
H H Hj
...
...
...
...
...
...
psmoo4
rIS. 7.
tABLICA 3.
kOLI“ESTWO p---
p/P 1 2 4 8 16 32 64 128 256
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
wREMENA WYPOLNENIQ WARIANTOW PSMOO, c. (SREDNIJ WARIANT).
GRUZKOJ DAET NA REALXNYH PODPROGRAMMAH WY­
IGRY[ PRIMERNO 10% PO SRAWNENI@ S RASPREDE­
LENIEM S RAWNOMERNOJ ZAGRUZKOJ.
4.5. sOGLASOWANIE RASPREDELENIJ DANNYH I
ITERACIJ
pOSLE PRINQTIQ RE[ENIQ O METODE RASPREDE­
LENIQ DANNYH I ITERACIJ CIKLOW NEOBHODIMO
SOGLASOWATX UKAZANNYE RASPREDELENIQ I OPREDE­
LITX, GDE W TEKSTE PROGRAMMY TREBU@TSQ PERE­
SYLKI DANNYH. dLQ ILL@STRACII STRUKTURY PE­
RESYLOK MOVNO ISPOLXZOWATX SHEMY PARALLELX­
NOGO WZAIMODEJSTWIQ PROCESSOROW. dLQ BOLX­
[INSTWA TO“EK PARALLELXNOGO WZAIMODEJSTWIQ
PROGRAMMY FLO52 HARAKTERNY ODINAKOWYE SHE­
MY, OPREDELQ@]IE PEREDA“U DANNYH LIBO S KA­
VDOJ ITERACII CIKLA NA SLEDU@]U@ ILI PRE­
DYDU]U@, LIBO PERESYLKU GRANI“NYH ZNA“ENIJ.
nA RIS. 7 PRIWEDENY OBSUVDAEMYE NIVE SHE­
MY. wERTIKALXNYE LINII POKAZYWA@T POSLEDO­
WATELXNYE WY“ISLENIQ NA SOOTWETSTWU@]EM p---,
A STRELKI IZOBRAVA@T NEOBHODIMYE PERESYLKI.
pERWAQ SHEMA (eflux) QWLQETSQ TIPI“NOJ DLQ
FLO52 I OPISYWAET SITUACI@, PRI KOTOROJ KA­
VDYJ PROCESSOR OSU]ESTWLQET PERESYLKI TOLX­
KO LOGI“ESKI SLEDU@]EMU p---. ---TO PROSTAQ I
LEGKO REALIZUEMAQ OPERACIQ. iNTERESNEE POSMO­
TRETX, KAKIE WARIANTY PARALLELXNOJ REALIZA­
CII MOVNO PREDUSMOTRETX DLQ PODPROGRAMM SO
STRUKTUROJ WY“ISLENIJ, PODOBNOJ PODPROGRAM­
ME PSMOO. nE TOLXKO DLQ FLO52, NO I DLQ L@­
BOJ DRUGOJ PROGRAMMY PODOBNYE FRAGMENTY BU­
DUT SERXEZNYM PREPQTSTWIEM DLQ POLU“ENIQ ``F­
FEKTIWNOGO PARALLELXNOGO WARIANTA.
w PERWOM WARIANTE (psmoo1 NA RIS. 7) KAVDYJ
PROCESSOR PROS“ITYWAET SWO@ PORCI@ ITERACIJ,
PEREDAET DANNYE S POSLEDNEJ ITERACII SLEDU­
@]EMU, POSLE “EGO TOT NA“INAET RABOTATX. w
KAVDYJ MOMENT WREMENI RABOTAET TOLXKO ODIN
PROCESSOR, ODNAKO S ROSTOM “ISLA PROCESSOROW
RASTET “ISLO NEOBHODIMYH PERESYLOK, I, SLEDO­
WATELXNO, KATASTROFI“ESKI RASTET WREMQ ISPOL­
NENIQ. wREMENA WYPOLNENIQ ``TOGO I WSEH POSLE­
DU@]IH WARIANTOW PSMOO PRIWODQTSQ W TABL.
3. wREMQ ISPOLNENIQ NA ODNOM PROCESSORE UKA­
ZANO DLQ ISHODNOGO POSLEDOWATELXNOGO WARIANTA
PROGRAMMY.
wTOROJ WARIANT (psmoo2) PREDUSMATRIWAET
ISPOLNENIE WSEH ITERACIJ PERWOJ POLOWINY
PSMOO TOLXKO NA PERWOM PROCESSORE. wNA“ALE
WSE p--- OTSYLA@T PERWOMU SWOI PORCII ISHOD­
NYH DANNYH, A POSLE WYPOLNENIQ PERWOJ POLO­
programmirowanie N o
3 1996

12 antonow, woewodin
WINY PODPROGRAMMY ``TOT PROCESSOR RASSYLAET
WSEM OSTALXNYM IH PORCII REZULXTATOW. zDESX
TREBUETSQ WSEGO DWE, HOTQ I WESXMA OB—EMNYH,
PERESYLKI, “TO NE POZWOLQET ZNA“ITELXNO ULU“­
[ITX SITUACI@ PO SRAWNENI@ S PREDYDU]IM WA­
RIANTOM.
w TRETXEM WARIANTE (psmoo3) WSE ITERACII
PERWOJ POLOWINY PSMOO WYPOLNQ@TSQ NA KA­
VDOM p--- (POLNOE DUBLIROWANIE RABOTY). dLQ
``TOGO PERED WYPOLNENIEM PODPROGRAMMY TREBU­
ETSQ EDINSTWENNAQ RASSYLKA PORCIJ ISHODNYH
DANNYH OT KAVDOGO p--- KAVDOMU. eSLI NA MALOM
“ISLE p--- ``TOT WARIANT NEZNA“ITELXNO PREWOS­
HODIT PREDYDU]IJ, TO IZ­ZA PEREGRUZKI KOMMU­
NIKACIONNOJ SETI NA 128 I 256 p--- OKAZYWAETSQ
HUVE EGO.
~ETWERTYJ WARIANT PREDPOLAGAET PERERASPRE­
DELENIE DANNYH TAK, “TOBY ISPOLXZOWATX W PER­
WOJ “ASTI PSMOO PARALLELIZM PO ODNOJ RAZ­
MERNOSTI, A WO WTOROJ --- PO DRUGOJ (psmoo4).
dLQ ``TOGO DO I POSLE PERWOJ “ASTI TREBUETSQ RAS­
SYLKA OT KAVDOGO PROCESSORA KAVDOMU NEBOLX­
[OJ “ASTI WHODNYH DANNYH. kROME TOGO, W OT­
LI“IE OT PREDYDU]IH WARIANTOW, PERWAQ “ASTX
PSMOO ISPOLNQETSQ DEJSTWITELXNO PARALLELX­
NO, I ``TOT WARIANT OKAZALSQ W ITOGE NAIBOLEE
UDA“NYM.
w PQTOM WARIANTE REALIZOWANA PARALLELXNAQ
SHEMA WY“ISLENIQ REKURSII PERWOGO PORQDKA, PO­
DOBNO SHEME KASKADNOGO SUMMIROWANIQ (psmoo5
--- EE SHEMY NET, NO ESTX REZULXTAT W TABL. 3).
pRI WY“ISLENII REKURSII GLUBINY n KOLI“E­
STWO WY“ISLENIJ WOZROSLO W 1 + log 2 n RAZ, PO­
``TOMU PRI REALIZACII NA MALOM “ISLE p--- WRE­
MQ WY“ISLENIQ ZAMETNO UWELI“ILOSX. wMESTE S
TEM, ``TOT WARIANT OTLI“AETSQ OT WSEH PREDYDU­
]IH SWOEJ MAS[TABIRUEMOSTX@, TAK KAK WREMQ
EGO RABOTY POSTOQNNO UMENX[AETSQ S ROSTOM “I­
SLA p---. w ZAWISIMOSTI OT “ISLA PROCESSOROW
MOVNO WYZYWATX LIBO ``TOT WARIANT PSMOO, LI­
BO PREDYDU]IJ.
kONE“NO, NE WO WSEH PODPROGRAMMAH TREBU@TSQ
PERESYLKI LI[X PO REGULQRNOJ SHEME. w “AST­
NOSTI, PODPROGRAMMY ADDX I COLLC OSU]E­
STWLQ@T PERERASPREDELENIE DANNYH PRI IZMENE­
NII RAZMEROW OBLASTI WY“ISLENIQ, A POTOMU TRE­
BU@T NEREGULQRNYH PERESYLOK I QWLQ@TSQ E]E
ODNIM UZKIM MESTOM PRI REALIZACII PARALLELX­
NOGO WARIANTA FLO52. eSLI NA PODPROGRAMME
COLLC POLU“AETSQ NEBOLX[OE USKORENIE, TO SO­
OTNO[ENIE MEVDU OB—EMOM PERESYLOK I “ISLOM
ARIFMETI“ESKIH OPERACIJ NE POZWOLQ@T DOSTI“X
I ``TOGO W PODPROGRAMME ADDX.
4.6. oPTIMIZACIQ RABOTY PROGRAMMY NA
KAVDOM PROCESSORE
pOSLE POLU“ENIQ RASPREDELENNOGO WARIANTA
PROGRAMMY I OPTIMIZACII SHEM PARALLELXNOGO
WZAIMODEJSTWIQ PROCESSOROW NEOBHODIMO PROIZ­
WESTI TONKU@ NASTROJKU PROGRAMMY. oNA ZA­
KL@“AETSQ W OPTIMIZACII WY“ISLENIJ NA KA­
VDOM PROCESSORE I, W “ASTNOSTI, DLQ DEC
ALPHA PREDPOLAGAET ISPOLXZOWANIE TAKIH OSO­
BENNOSTEJ ARHITEKTURY, KAK K``[­PAMQTX KO­
MAND, K``[­PAMQTX DANNYH I RAZDELXNYE FUNK­
CIONALXNYE USTROJSTWA. nA PRAKTIKE ``TO TRE­
BUET UWELI“ENIQ LOKALXNOSTI DANNYH, SBALANSI­
ROWANNOSTI WY“ISLENIJ, OPTIMIZACII STRUKTU­
RY UPRAWLENIQ PROGRAMMY, OCENKI CELESOOBRAZ­
NOSTI ISPOLXZOWANIQ WREMENNYH MASSIWOW I MNO­
GIH DRUGIH DEJSTWIJ.
4.7. rEZULXTATY OPTIMIZACII FLO52
---KSPERIMENTY PROIZWODILISX S PROGRAMMOJ
FLO52 W TREH KONFIGURACIQH: W MALOJ, SREDNEJ
I BOLX[OJ, KOTORYE ZADA@T WY“ISLENIQ W OBLA­
STQH RAZMEROM X \Theta Y , 2X \Theta 2Y I 4X \Theta 4Y SOOT­
WETSTWENNO. dLQ ORGANIZACII PERESYLOK ISPOLX­
ZOWALASX TA VE BIBLIOTEKA KOMMUNIKACIONNYH
PRIMITIWOW, “TO I PRI OPTIMIZACII PROGRAMMY
TRFD.
w TABL. 4 PRIWEDENY WREMENA ISPOLNENIQ NE­
KOTORYH RASPREDELQW[IHSQ PODPROGRAMM W ZA­
WISIMOSTI OT “ISLA PROCESSOROW DLQ SREDNEGO
WARIANTA PROGRAMMY FLO52. wREMQ ISPOLNE­
NIQ NA ODNOM PROCESSORE UKAZANO DLQ ISHODNO­
GO POSLEDOWATELXNOGO WARIANTA PROGRAMMY. iZ
TABLICY WIDNO, “TO USKORENIE POLU“ENO PO“TI
NA WSEH RASSMOTRENNYH PODPROGRAMMAH, ODNA­
KO UPOMINAW[IESQ W PREDYDU]IH PUNKTAH UZKIE
MESTA OKAZYWA@T ZNA“ITELXNOE WLIQNIE NA WRE­
MENA RABOTY OTDELXNYH FRAGMENTOW. tABL. 5
SODERVIT OKON“ATELXNYE REZULXTATY, POLU“EN­
NYE NA WSEH TREH WARIANTAH.
gRAFIK NA RIS. 8 DEMONSTRIRUET USKORENIE,
POLU“ENNOE NA TREH WARIANTAH W ZAWISIMOSTI OT
“ISLA ISPOLXZUEMYH p---. o“EWIDNO, “TO POLU­
“ENNAQ PROGRAMMA OBLADAET HORO[IMI ''PARAL­
programmirowanie N o
3 1996

---ffektiwnaq adaptaciq posledowatelxnyh programm 13
tABLICA 4.
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
euler 56.1 24.6 13.5 7.88 5.14 3.72 2.95 2.64 2.43
psmoo4 27.5 22.6 14.2 9.23 7.15 7.03 8.69 12.0 15.0
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
wREMENA WYPOLNENIQ PODPROGRAMM, c. (SREDNIJ WARIANT).
tABLICA 5.
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
wREMENA WYPOLNENIQ WARIANTOW FLO52, S.
c c
c
c
c
c
c
c
c
pp ppp pp ppp ppp ppp ppp pp ppp ppp pp ppp ppp ppp pp pp pp pp pp pp pp pp pp pp pp pp pp pp pp
pp pp ppp pppp pppppppppppp pppp pp pp pp pp pp pp
c c
c
c
c
c c c c
pp ppp pp ppp ppp ppp ppp ppp ppp pp ppp ppp pp pp pp pp pp pp
pp pp pp pp pp ppp ppp ppp ppp pppppp pp ppppppppppp pp pppp pppp ppp ppp ppp ppp ppp pppp ppppppp pppp ppppp pppppp ppp ppp ppp pp ppp pp pp pp pp pp pp pp
c c c
c c c c c c
1
5
10
15
20
1 2 4 8 16 32 64 128 256
bOLX[OJ
mALYJ
sREDNIJ
~ISLO p---
uSKORENIE
rIS. 8.
LELXNYMI'' SWOJSTWAMI, TAK KAK PRI DOSTATO“­
NOM OB—EME WY“ISLENIJ POZWOLQET POLU“ATX SU­
]ESTWENNOE USKORENIE NA BOLX[OM “ISLE p---.
oTNOSITELXNO NEBOLX[OE USKORENIE NA MALOM I
SREDNEM WARIANTAH OB—QSNQETSQ MALYM RAZME­
ROM ZADA“I, BOLX[IM “ISLOM TO“EK PARALLELX­
NOGO WZAIMODEJSTWIQ (BOLEE 60 PO WSEJ PROGRAM­
ME, PRI“EM SUMMARNOE “ISLO IH PROHOVDENIJ
ZA WREMQ RABOTY PROGRAMMY PREWY[AET 35000)
I NALI“IEM SUGUBO POSLEDOWATELXNYH PODPRO­
GRAMM. dOPOLNITELXNOE USKORENIE, POLU“ENNOE
NA 128 I 256 p--- NA MALOM I SREDNEM WARIANTAH,
OB—QSNQETSQ ISPOLXZOWANIEM DRUGOGO ALGORITMA
PRI REALIZACII PODPROGRAMMY PSMOO.
5. zakl`~enie
w ZAKL@“ENII MY HOTELI BY OTOJTI OT TRADI­
CIONNOJ FORMY IZLOVENIQ I DATX KRATKU@ FOR­
MULIROWKU OSNOWNYH ZADA“, WOZNIK[IH W PRO­
CESSE ADAPTACII PROGRAMM K ARHITEKTURE PA­
RALLELXNYH KOMPX@TEROW. ~ASTX IZ ``TIH ZADA“
programmirowanie N o
3 1996

14 antonow, woewodin
NEOBHODIMO RE[ATX WSEGDA, DRUGIE POTREBU@T­
SQ TOLXKO DLQ OPREDELENNOGO KLASSA ARHITEKTUR.
dLQ “ASTI IZ PERE“ISLENNYH PROBLEM UVE PRO­
WODILISX OB[IRNYE ISSLEDOWANIQ (NAPRIMER, [6­
11]), ODNAKO NEKOTORYE TREBU@T SERXEZNOGO MA­
TEMATI“ESKOGO ISSLEDOWANIQ.
1. iSSLEDOWANIE OB]EJ STRUKTURY PROGRAM­
MY: WYDELENIE OSNOWNOGO WY“ISLITELXNOGO
QDRA, LOKALIZACIQ WWODA­WYWODA, INICIALI­
ZACII (NEOBHODIMO POMNITX, “TO REALXNYE
PRILOVENIQ MOGUT OB—EDINQTX SOTNI PROCE­
DUR I DESQTKI TYSQ“ STROK TEKSTA).
2. oPREDELENIE POTENCIALXNOGO PARALLELIZMA
FRAGMENTA, A W DALXNEJ[EM I WYBOR TOJ EGO
“ASTI, KOTORU@ RAZUMNO ISPOLXZOWATX DLQ
ISSLEDUEMOJ PROGRAMMY.
3. wYDELENIE “ISTO POSLEDOWATELXNYH FRAG­
MENTOW WY“ISLENIJ, RASPOZNAWANIE IDIOM I
ISPOLXZOWANIE ALXTERNATIWNYH ALGORITMOW
DLQ TAKIH FRAGMENTOW.
4. iSSLEDOWANIE MNOVESTWA WOZMOVNYH RAS­
PREDELENIJ DANNYH, POISK RASPREDELENIQ,
MINIMIZIRU@]EGO “ISLO ILI OB—EM PERESY­
LOK, OPREDELENIE I MINIMIZACIQ “ISLA TO­
“EK PERERASPREDELENIQ.
5. dOKAZATELXSTWO WOZMOVNOSTI WYPOLNENIQ
TRADICIONNYH PREOBRAZOWANIJ CIKLOW W
PROCESSE PREOBRAZOWANIQ PROGRAMMY: PE­
RESTANOWKA CIKLOW, SLIQNIE, RAS]EPLENIE,
OB—EDINENIE I T. D.
6. mINIMIZACIQ “ISLA I OB—EMA WREMENNYH
MASSIWOW DLQ OPTIMIZACII RABOTY S K``[­PA­
MQTX@ I WEKTORNYMI REGISTRAMI.
7. pEREHOD OT ISHODNOJ PROGRAMMY, RABOTA@­
]EJ S POLNYMI MASSIWAMI, K PROGRAMME, OB­
RABATYWA@]EJ TOLXKO LOKALXNU@ PORCI@,
RASPREDELENNU@ NA PROCESSOR: IZMENENIE
RAZMEROW MASSIWOW I SOOTWETSTWU@]EE PRE­
OBRAZOWANIE TEKSTA PROGRAMMY.
8. pRIWATIZACIQ MASSIWOW --- WYDELENIE MAS­
SIWOW, LOKALXNYH DLQ KAVDOGO PROCESSORA.
9. dLQ DANNOGO RASPREDELENIQ MASSIWOW I ITE­
RACIJ SGENERIROWATX OTWE“A@]IJ ZADANNO­
MU CIKLU FRAGMENT PARALLELXNOJ PROGRAM­
MY, PEREBIRA@]IJ LOKALXNU@ PORCI@ ITE­
RACIJ I SODERVA]IJ PRIMITIWY KOMMUNI­
KACIJ TIPA Send­Receive.
10. uWELI“ENIE LOKALXNO­
STI ISPOLXZOWANIQ DANNYH PROGRAMMY DLQ
OPTIMIZACII RABOTY K``[­PAMQTI.
spisok literatury
1. Voevodin V.V. Mathematical foundations of
parallel computing// Computer Science Series,
Vol.33, World Sci. Publ. Co., Singapore, 1992.
2. wOEWODIN wL.w. tEORIQ I PRAKTIKA ISSLE­
DOWANIQ PARALLELIZMA POSLEDOWATELXNYH PROG­
RAMM// pROGRAMMIROWANIE. 1992. N o 3. S.38­53.
3. Cybenko G., Kipp L., Pointer L., and Kuck D.
Supercomputer performance evaluation and the
Perfect Benchmarks, Tech. Rep. 965, CSRD, Univ.
of Illinois at Urbana, Technical Report, 1990.
4. Grassl C.M. Parallel Performance of Applica­
tions on Supercomputers// Parallel Computing
v.17 (1991), pp.1257­1273.
5. wOEWODIN wL.w. lEGKO LI POLU“ITX OBE]AN­
NYJ GIGAFLOP? //pROGRAMMIROWANIE. 1995. N o
4. s.13­23.
6. Wolfe M.J. Optimizing Supercompilers
for Supercomputers, The MIT Press, Cambridge,
Massachusetts, 1989.
7. Polychronopoulos C.D. et al. Parafrase--
2: An Environment for Parallelizing, Partitioning,
Synchronizing, and Scheduling Programs on
Multiprocessors// Proc. of the 1989 Int. Conf.
on Parallel Processing, St. Charles, Illinois, 1989.
8. Feautrier P. Some efficient solutions to the
affine scheduling problem, part I/II. //Tech. Rep.
92.28/78, IBP/MASI, France, 1992.
9. Kelly W., Pugh W. A Framework for Unifying
Reordering Transformations. Tech. Rep. CS­TR­
2995.1. Dept. of Comp. Science, University of
Maryland, College Park, 1993.
10. Maydan D., Amarasinghe S., Lam M. Array
Data­flow
Analysis and Its Use in Array Privatization. //
Proc. of the 1993 ACM Conference on Principles
of Programming Languages, 1993.
11. Torrellas J., Lam M., Hennessy J. False
Sharing and Spatial Locality in Multiprocessors
Caches// IEEE Trans. on Computers, Vol.43,
No.6, June, 1994, p.651­663.
programmirowanie N o
3 1996