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

sOWREMENNYE METODY MEVPROCEDURNOGO ANALIZA
PROGRAMM \Lambda
a. s. aNTONOW y
6 MAQ 1998
wWEDENIE
nEOBHODIMOSTX WYPOLNENIQ MEVPROCEDURNOGO ANALIZA PROGRAMM O“ENX “ASTO WOZ­
NIKAET NA PRAKTIKE, W “ASTNOSTI PRI ANALIZE PARALLELXNYH SWOJSTW PROGRAMM. w
OB]EM SLU“AE POD TAKIM ANALIZOM PONIMAETSQ NE TOLXKO OPREDELENIE WLIQNIQ WYZO­
WA PROCEDUR NA KONTEKST WYZOWA [5], NO I OPREDELENIE WLIQNIQ KONTEKSTA WYZOWA NA
ISPOLNENIE WYZYWAEMOJ PODPROGRAMMY. pERWOE POMOGAET OPREDELITX PARALLELXNYE
SWOJSTWA WYZYWA@]EJ PODPROGRAMMY, A WTOROE --- WYZYWAEMOJ. mOVNO PRIWESTI
MNOVESTWO PRIMEROW ZADA“, RE[AEMYH S ISPOLXZOWANIEM TEHNIKI MEVPROCEDURNOGO
ANALIZA: OPREDELENIE NEZAWISIMOSTI WHOVDENIJ W TELO PODPROGRAMMY PARAMETROW
I GLOBALXNYH PEREMENNYH, RASPARALLELIWANIE CIKLOW, SODERVA]IH WYZOWY PODPRO­
GRAMM, OPREDELENIE NEOBHODIMYH PERESYLOK DANNYH DLQ WYZOWA RASPREDELQEMOJ POD­
PROGRAMMY PRI ISPOLXZOWANII KOMPX@TEROW S RASPREDELENNOJ PAMQTX@, PODDERVKA
KORREKTNOSTI DANNYH W K``[­PAMQTI MNOGOPROCESSORNYH SISTEM I MNOGIE DRUGIE.
eSLI NE PROIZWODITX MEVPROCEDURNYJ ANALIZ, TO PRIDETSQ PREDPOLOVITX, “TO WSE
FAKTI“ESKIE PARAMETRY I WNE[NIE PEREMENNYE KAK ISPOLXZU@TSQ, TAK I PEREOPREDE­
LQ@TSQ W WYZYWAEMOJ PODPROGRAMME, A TAKVE “TO ONI POTENCIALXNO MOGUT SSYLATXSQ
NA ODNU I TU VE OBLASTX PAMQTI. ---TO PRIWEDET K TOMU, “TO MNOGIE POLEZNYE SWOJSTWA
PROGRAMMY NE BUDUT ISPOLXZOWANY.
oDNIM IZ PERWYH METODOW RAZRE[ENIQ PROBLEMY MEVPROCEDURNOGO ANALIZA BY­
LA PREDLOVENA PODSTANOWKA TELA PODPROGRAMMY NA MESTO WYZOWA (inline expansion
[25]), NO ONA SILXNO ZATRUDNENA, ESLI W GRAFE WYZOWOW ESTX KONTURY, “TO PRIWODIT
K SILXNOMU UWELI“ENI@ RAZMERA KODA I WREMENI ANALIZA.
w IZWESTNYH OBZORAH [5, 26] BOLX[OE WNIMANIE UDELQLOSX METODAM MEVPROCEDUR­
NOGO ANALIZA BEZ U“ETA INDEKSNYH PEREMENNYH. rE[AEMYE ``TIMI METODAMI ZADA“I,
TAKIE KAK SOWME]ENIE PARAMETROW PROCEDURY (aliasing), ANALIZIRUEMOE S TO“NOSTX@
DO IMEN, MEVPROCEDURNOE RASPROSTRANENIE KONSTANT (constant propagation) I OPRE­
DELENIE WHODNYH I WYHODNYH PARAMETROW PROCEDUR S TO“NOSTX@ DO IMEN, RE[A@TSQ
\Lambda rABOTA PODDERVANA rOSSIJSKIM fONDOM fUNDAMENTALXNYH iSSLEDOWANIJ, GRANT 97--01--00977
y E­mail: asa@vvv.srcc.msu.su
1

DOWOLXNO PROSTYMI METODAMI I PODROBNO OPISANY. kROME TOGO, TAKOJ ANALIZ QWLQ­
ETSQ WESXMA GRUBYM I NEDOSTATO“NYM DLQ REALXNYH PROGRAMM, POSKOLXKU W BOLX­
[INSTWE SLU“AEW NEOBHODIM ANALIZ SU]ESTWOWANIQ ZAWISIMOSTI MEVDU SSYLKAMI NA
OTDELXNYE ``LEMENTY MASSIWOW. w RABOTE [24] NA OSNOWE IZU“ENIQ NEKOTOROJ WYBORKI
PROGRAMM NA QZYKE pASKALX DELAETSQ DAVE WYWOD O BESPOLEZNOSTI TAKOGO ANALIZA
DLQ PREOBRAZOWANIQ REALXNYH PROGRAMM. pO``TOMU POD MEVPROCEDURNYM ANALIZOM
W DALXNEJ[EM BUDEM PONIMATX MEVPROCEDURNYJ ANALIZ, PROIZWODIMYJ S TO“NOSTX@
DO OTDELXNYH ``LEMENTOW MASSIWOW.
mETODY MEVPROCEDURNOGO ANALIZA S U“ETOM INDEKSNYH PEREMENNYH W POSLEDNEE
WREMQ POLU“ILI DALXNEJ[EE RAZWITIE WO MNOGIH RABOTAH. aNALIZU I SRAWNENI@
TAKIH METODOW POSWQ]ENA DANNAQ STATXQ. kROME TOGO, RASSMATRIWAETSQ NOWYJ POD­
HOD, OSNOWANNYJ NA ANALIZE SWOJSTW GRAFA ALGORITMA [1, 2, 3], WPERWYE OPISANNYJ
W RABOTE [4].
mEVPROCEDURNYJ ANALIZ MOVNO RAZDELITX NA DWE “ASTI: NAHOVDENIE WHODNYH I
WYHODNYH DANNYH PODPROGRAMMY I OPISANIE ``TIH DANNYH W TERMINAH FAKTI“ESKIH
PARAMETROW (OBRATNAQ PODSTANOWKA). rAZDELY 2--6 DANNOJ RABOTY POSWQ]ENY SU]E­
STWU@]IM PODHODAM K RE[ENI@ PERWOJ ZADA“I, A RAZDEL 7 --- PODHODAM K RE[ENI@
WTOROJ.
1 oSNOWNYE POLOVENIQ
w BOLX[INSTWE RABOT, POSWQ]ENNYH MEVPROCEDURNOMU ANALIZU, RASSMATRIWA@TSQ
TOLXKO TE OBLASTI, KOTORYE SOOTWETSTWU@T WYREZKAM IZ MASSIWOW, ISPOLXZUEMYM
ILI IZMENQEMYM W ANALIZIRUEMOJ PODPROGRAMME. sLEDUQ [14], BUDEM NAZYWATX TAKIE
OBLASTI READ I WRITE OBLASTQMI. oDNAKO ZNANIQ IH MOVET OKAZATXSQ NEDOSTA­
TO“NO DLQ POLNOCENNOGO ANALIZA, TAK KAK READ OBLASTI MOGUT SODERVATX DANNYE,
WY“ISLENNYE RANEE W ISSLEDUEMOJ PODPROGRAMME, A, SLEDOWATELXNO, ONI NE BUDUT
PREDSTAWLQTX WHODNYH DANNYH ANALIZIRUEMOJ PROCEDURY. WRITE OBLASTI MOGUT
SODERVATX DANNYE, KOTORYE NE POTREBU@TSQ NIGDE W DALXNEJ[EM TEKSTE PROGRAMMY,
“TO TAKVE NE SOOTWETSTWUET WYHODNYM DANNYM PODPROGRAMMY. dLQ BOLEE TO“NO­
GO ANALIZA WWODQTSQ IN I OUT OBLASTI, KOTORYE PREDSTAWLQ@T IMENNO WHODNYE I
WYHODNYE DANNYE PODPROGRAMMY, TO ESTX DANNYE, NEOBHODIMYE DLQ WYPOLNENIQ POD­
PROGRAMMY, I DANNYE, WY“ISLQEMYE W ISSLEDUEMOJ PODPROGRAMME I ISPOLXZUEMYE
GDE­LIBO DALEE.
wSE METODY OPISANIQ READ I WRITE OBLASTEJ MOVNO RAZDELITX NA DWA KLASSA:
NETO“NYE I TO“NYE METODY. nETO“NYE METODY PRO]E, NO, W OTLI“IE OT TO“NYH, OPI­
SYWA@T TOLXKO NEKOTORU@ APPROKSIMACI@ NEOBHODIMOJ OBLASTI. tO“NYE VE METODY
MOGUT POTREBOWATX MNOGO PAMQTI I MOGUT POTREBOWATX MNOGO WREMENI DLQ ANALIZA
PROGRAMM. w NEKOTORYH SLU“AQH MOGUT ISPOLXZOWATXSQ KOMBINIROWANNYE METODY,
NAPRIMER, PRIBLIVENNOE OPISANIE OB—EDINENIQ TO“NO OPISANNYH OBLASTEJ.
dLQ OPISANNYH L@BYM METODOM OBLASTEJ NAIBOLEE WAVNYMI OPERACIQMI QWLQ­
2

@TSQ OB—EDINENIE I PERESE“ENIE. oB—EDINENIE OBLASTEJ POZWOLQET SUMMIROWATX
READ I WRITE OBLASTI DLQ WSEH WHOVDENIJ KAKOJ­NIBUDX PEREMENNOJ, A PERESE­
“ENIE NEOBHODIMO DLQ OPREDELENIQ SU]ESTWOWANIQ ZAWISIMOSTEJ MEVDU RAZLI“NYMI
WHOVDENIQMI. w SLU“AE PERESE“ENIQ OBLASTEJ NAS INTERESUET PREVDE WSEGO NALI“IE
ILI OTSUTSTWIE ZAWISIMOSTI, TO ESTX SAM FAKT CELO“ISLENNOJ PUSTOTY ILI NEPUSTO­
TY POLU“AEMOJ OBLASTI. dWE OSNOWNYE OPERACII OB—EDINENIQ I PERESE“ENIQ BUDUT
RASSMOTRENY DLQ WSEH METODOW.
wSE OPISYWAEMYE DALEE METODY PROILL@STRIRUEM NA ODNOM PRIMERE --- OPI[EM
S POMO]X@ KAVDOGO METODA WRITE OBLASTX DLQ FRAGMENTA PROGRAMMY, PROIZWODQ­
]EGO WY“ISLENIQ DLQ NIVNETREUGOLXNOJ “ASTI MASSIWA I ODNOJ IZ EGO STROK. ---TOT
FRAGMENT I SUMMARNAQ WRITE OBLASTX PRIWEDENY NA RIS. 1. nA ``TOM RISUNKE, KAK I
NA WSEH POSLEDU@]IH, IZOBRAVA@]IH APPROKSIMACII ``TOJ OBLASTI, PREDPOLAGAETSQ,
“TO ``LEMENT A(1, 1) NAHODITSQ W LEWOM WERHNEM UGLU, A ``LEMENTY PERWOJ RAZMERNOSTI
MASSIWA RASPOLAGA@TSQ SWERHU WNIZ.
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@
PARAMETER (N = 13, K = 7)
DIMENSION A(N+1, N+1)
C OBRA]ENIE K NIVNETREUGOLXNOJ
C “ASTI MASSIWA
DO I = 1, N
DO J = 1, I
A(I, J) = : : :
END DO
END DO
C OBRA]ENIE K STROKE S NOMEROM K
DO J = 1, N
A(K, J) = : : :
END DO
rIS. 1. fRAGMENT PROGRAMMY I WY“ISLQEMAQ OBLASTX MASSIWA
sLEDUQ [13], OPI[EM OTDELXNOE OBRA]ENIE K ``LEMENTAM MASSIWA PRI POMO]I TREH
WEKTOROW: WEKTORA INDEKSNYH WYRAVENIJ d­MERNOGO MASSIWA \Phi(A) = (OE 1 ; : : : ; OE d ),
WEKTORA PAR OGRANI“ENIJ NA UPRAWLQ@]IE PARAMETRY l OB—EML@]IH CIKLOW B(A) =
(fi 1 ; : : : ; fi l ), GDE fi j --- UPORQDO“ENNAQ PARA (lb j ; ub j ) OGRANI“ENIJ SNIZU I SWERHU NA
PARAMETR j­OGO CIKLA, I WEKTORA [AGOW CIKLOW \Sigma(A) = (oe 1 ; : : : ; oe l ). tOGDA OPISATELX
DOSTUPA K MASSIWU \Delta(A) PREDSTAWLQETSQ W WIDE TROJKI ! \Phi; B; \Sigma ?.
2 nETO“NYE METODY POLU“ENIQ READ I WRITE
OBLASTEJ
rEGULQRNYE SEKCII (regular sections) BYLI PREDLOVENY W RABOTE [10] KAK PROSTOJ
SPOSOB APPROKSIMACII READ I WRITE OBLASTEJ. oNI BYWA@T DWUH OSNOWNYH TI­
3

POW --- OGRANI“ENNYE REGULQRNYE SEKCII (restricted regular sections [9]) I OPISANIQ S
POMO]X@ TRIPLETOW (bounded regular sections [16]).
oGRANI“ENNYE REGULQRNYE SEKCII PREDSTAWLQ@TSQ S POMO]X@ WEKTORA INDEKSNYH
WYRAVENIJ MASSIWA \Phi(A), W KOTOROM KAVDAQ KOMPONENTA OE k QWLQETSQ LIBO KONSTANT­
NYM WYRAVENIEM (INWARIANTOM PODPROGRAMMY), LIBO WYRAVENIEM WIDA ff \Sigma i j , GDE i j
--- PEREMENNAQ, SOPOSTAWLQEMAQ j­OMU IZMERENI@ MASSIWA (k 6= j), A ff --- KONSTANTNOE
WYRAVENIE (INWARIANT PODPROGRAMMY), LIBO OSOBYM ZNA“KOM ?, KOTORYJ OZNA“AET
WS@ RAZMERNOSTX MASSIWA. s POMO]X@ TAKOJ KONSTRUKCII MOVNO OPISATX OTDELXNYJ
``LEMENT MASSIWA, POLNYE STROKU, STOLBEC ILI DIAGONALX, A TAKVE IH MNOGOMERNYE
ANALOGI.
oB—EDINENIE DWUH OGRANI“ENNYH REGULQRNYH SEKCIJ POLU“AETSQ SLEDU@]IM OB­
RAZOM. eSLI NA k­TOM MESTE W ODNOJ IZ SEKCIJ STOIT ?, TO NA SOOTWETSTWU@]EM
MESTE OE k W OB—EDINENII TAKVE BUDET ?. eSLI NA k­TOM MESTE W OBEIH SEKCIQH STOIT
ODNA I TA VE KONSTANTA, TO W OB—EDINENII TAKVE BUDET ``TA KONSTANTA. eSLI NA
SOOTWETSTWU@]IH MESTAH STOQT RAZNYE KONSTANTY, TO W OB—EDINENII BUDET ?. eSLI
NA k­TOM MESTE HOTQ BY W ODNOJ IZ SEKCIJ STOIT WYRAVENIE ff \Sigma i j , TO PROWODITSQ
PROCESS, NAZYWAEMYJ NORMALIZACIEJ[26], KOTORYJ PRIWODIT K TOMU, “TO W KAVDOJ
IZ SEKCIJ OE k PREDSTAWLQETSQ LIBO ZNA“KOM ?, LIBO WYRAVENIEM ff \Sigma i j , GDE j ! k
I OE j =?. pOSLE ``TOGO W OB—EDINENII BUDET ff \Sigma i j , ESLI ``TI WYRAVENIQ DLQ OBEIH
SEKCIJ W TO“NOSTI IDENTI“NY, ILI ? W PROTIWNOM SLU“AE.
pOSTROENIE PERESE“ENIQ DWUH SEKCIJ OSU]ESTWLQETSQ TAKVE SRAWNENIEM WEKTO­
ROW INDEKSNYH WYRAVENIJ. dLQ SU]ESTWOWANIQ NEPUSTOGO PERESE“ENIQ DLQ KAVDOGO
``LEMENTA WEKTOROW DOLVNO WYPOLNQTXSQ HOTQ BY ODNO IZ “ETYREH USLOWIJ:
1. w ODNOM IZ WEKTOROW STOIT ZNA“OK ?.
2. w ODNOM IZ WEKTOROW STOIT ff \Sigma i j , A W DRUGOM WYRAVENIE, NE ZAWISQ]EE OT i j .
3. w OBOIH WEKTORAH STOIT ff + i j ILI ff \Gamma i j S ODINAKOWOJ KONSTANTOJ ff.
4. w OBOIH WEKTORAH STOIT KONSTANTA ff.
eSLI HOTQ BY DLQ ODNOJ PARY ``LEMENTOW WEKTOROW NI ODNO IZ ``TIH USLOWIJ NE
WYPOLNQETSQ, TO PERESE“ENIE PUSTO, INA“E NEPUSTO.
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
4

rIS. 2. oBLASTX, POLU“ENNAQ METODOM OGRANI“ENNYH REGULQRNYH SEKCIJ
dLQ PRIMERA, PRIWEDENNOGO NA RIS. 1, WRITE OBLASTX, POLU“ENNAQ METODOM OGRA­
NI“ENNYH REGULQRNYH SEKCIJ, OPISYWAETSQ SLEDU@]IM OBRAZOM:
RRS 1 (A) = (?; ? );
RRS 2 (A) = (K; ?);
RRS 1[2 (A) = (?; ? ):
sLEDOWATELXNO, POLU“AETSQ OPISANIE WSEGO MASSIWA A (RIS. 2).
w OTLI“IE OT OGRANI“ENNYH REGULQRNYH SEKCIJ, OPISANIE S POMO]X@ TRIPLETOW
(bounded regular sections) NE POZWOLQET ZADAWATX DIAGONALI, NO WKL@“AET INFORMACI@
O GRANICAH I [AGAH CIKLOW. tRIPLET OPISYWAETSQ DLQ KAVDOGO IZMERENIQ MASSIWA
S ISPOLXZOWANIEM ``LEMENTOW WEKTOROW B(A) I \Sigma(A) W WIDE [lb i : ub i : oe i ], GDE lb i ; ub i I
oe i --- KONSTANTY ILI INWARIANTNYE WYRAVENIQ PODPROGRAMMY.
oB—EDINENIE DWUH OPISANNYH S POMO]X@ TRIPLETOW SEKCIJ STROITSQ SLEDU@]IM
OBRAZOM. w KA“ESTWE NIVNEJ (WERHNEJ) GRANICY PO KAVDOMU IZMERENI@ BERETSQ MI­
NIMALXNAQ (MAKSIMALXNAQ) IZ NIVNIH (WERHNIH) GRANIC PO DANNOMU IZMERENI@ IZ
OPISANIJ OB—EDINQEMYH OBLASTEJ, A W KA“ESTWE [AGA --- NAIBOLX[IJ OB]IJ DELITELX
[AGOW IZ OPISANIJ ``TIH OBLASTEJ.
dLQ OPREDELENIQ PERESE“ENIQ DWUH SEKCIJ NUVNO WZQTX PARU TRIPLETOW DLQ KA­
VDOGO IZMERENIQ [lb 1
i : ub 1
i : oe 1
i ] I [lb 2
i : ub 2
i : oe 2
i ] I SOSTAWITX SISTEMU RAWENSTW I
NERAWENSTW:
8 ? !
? :
lb 1
i + oe 1
i k 1
i = lb 2
i + oe 2
i k 2
i
0 Ÿ k 1
i Ÿ (ub 1
i \Gamma lb 1
i )=oe 1
i
0 Ÿ k 2
i Ÿ (ub 2
i \Gamma lb 2
i )=oe 2
i ;
GDE k 1
i ; k 2
i 2 Z.
eSLI OPISYWAEMAQ TAKOJ SISTEMOJ OBLASTX CELO“ISLENNO NEPUSTA DLQ KAVDOGO
IZMERENIQ, TO PERESE“ENIE DWUH SEKCIJ NEPUSTO. cELO“ISLENNU@ NEPUSTOTU OBLASTI
MOVNO OPREDELQTX, NAPRIMER, S POMO]X@ oMEGA­TESTA[23]. w NEKOTORYH SLU“AQH ``TU
ZADA“U MOVNO RE[ITX S POMO]X@ PROSTYH ``WRISTIK.
dLQ RASSMATRIWAEMOGO PRIMERA (RIS. 1) WRITE OBLASTX, POLU“ENNAQ METODOM
OPISANIQ S POMO]X@ TRIPLETOW, OPISYWAETSQ SLEDU@]IM OBRAZOM:
BRS 1 = ([1 : N : 1]; [1 : N : 1]);
BRS 2 = (K; [1 : N : 1]);
BRS 1[2 = ([1 : N : 1]; [1 : N : 1]):
---TA OBLASTX POKAZANA NA RIS. 3.
5

\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
rIS. 3. oBLASTX, POLU“ENNAQ METODOM OPISANIQ S POMO]X@ TRIPLETOW
pROSTYE SEKCII (simple sections), PREDLOVENNYE W RABOTE [6], PREDSTAWLQ@T SO­
BOJ OBLASTI MASSIWOW, KOTORYE MOGUT BYTX OPISANY PRI POMO]I NABORA OGRANI“ENIJ
SPECIALXNOGO WIDA. dLQ OPISANIQ OBLASTEJ PREDLAGAETSQ ISPOLXZOWATX GIPERPLOS­
KOSTI, KOTORYE LIBO PARALLELXNY KOORDINATNYM GIPERPLOSKOSTQM, LIBO NAKLONENY
POD UGLOM 45 ffi K L@BYM DWUM TAKIM GIPERPLOSKOSTQM. pRI ``TOM POLU“AETSQ AP­
PROKSIMACIQ NUVNOGO MNOVESTWA OBRA]ENIJ K MASSIWU WYPUKLOJ OBLASTX@ PROSTO­
GO WIDA. w OB—EDINENIE DWUH OBLASTEJ WOJDUT MINIMALXNOE IZ OGRANI“ENIJ SNIZU
I MAKSIMALXNOE IZ OGRANI“ENIJ SWERHU IZ OPISANIJ RASSMATRIWAEMYH OBLASTEJ DLQ
KAVDOJ KOORDINATNOJ GIPERPLOSKOSTI I DLQ KAVDOJ DIAGONALI. w PERESE“ENIE DWUH
OBLASTEJ WOJDUT MAKSIMALXNOE IZ OGRANI“ENIJ SNIZU I MINIMALXNOE IZ OGRANI“E­
NIJ SWERHU IZ OPISANIJ OB—EDINQEMYH OBLASTEJ DLQ KAVDOJ KOORDINATNOJ GIPER­
PLOSKOSTI I DLQ KAVDOJ DIAGONALI. pERESE“ENIE DWUH PROSTYH SEKCIJ NEPUSTO, ESLI
MAKSIMALXNOE IZ OGRANI“ENIJ SNIZU NE PREWOSHODIT MINIMALXNOE IZ OGRANI“ENIJ
SWERHU DLQ KAVDOJ KOORDINATNOJ GIPERPLOSKOSTI I DLQ KAVDOJ DIAGONALI.
WRITE OBLASTX, POLU“ENNAQ METODOM PROSTYH SEKCIJ DLQ RASSMATRIWAEMOGO PRI­
MERA (RIS. 1), OPISYWAETSQ SLEDU@]IM OBRAZOM:
SS 1 = f 1 Ÿ I Ÿ N; 1 Ÿ J [Ÿ N ]; [2 Ÿ]I + J [Ÿ 2N ];
0 Ÿ I \Gamma J [Ÿ N \Gamma 1] g;
SS 2 = f K Ÿ I Ÿ K; 1 Ÿ J Ÿ N; [K + 1 Ÿ]I + J [Ÿ K +N ];
[K \Gamma N Ÿ]I \Gamma J [Ÿ K \Gamma 1] g;
SS 1[2 = f 1 Ÿ I Ÿ N; 1 Ÿ J Ÿ N; [2 Ÿ]I + J [Ÿ 2N ];
K \Gamma N Ÿ I \Gamma J [Ÿ N \Gamma 1] g:
w KWADRATNYE SKOBKI ZAKL@“ENY POLU“IW[IESQ IZBYTO“NYE NERAWENSTWA. rEZULX­
TIRU@]AQ OBLASTX POKAZANA NA RIS. 4.
6

\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@ \Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
rIS. 4. oBLASTX, POLU“ENNAQ METODOM PROSTYH SEKCIJ
w RABOTAH [14, 28] RASSMATRIWAETSQ OPISANIE MNOVESTWA OBRA]ENIJ K MASSIWU
W WIDE MINIMALXNOJ WYPUKLOJ OBOLO“KI (convex hull) ``TOGO MNOVESTWA. wYPUKL­
AQ OBOLO“KA OPISYWAETSQ S POMO]X@ UPORQDO“ENNOGO NABORA INDEKSNYH WYRAVENIJ
(region) I KONTEKSTA ISPOLNENIQ (execution context). pOD KONTEKSTOM ISPOLNENIQ
PONIMAETSQ NABOR OGRANI“ENIJ NA UPRAWLQ@]IE PARAMETRY CIKLOW. rEZULXTIRU­
@]IM OPISANIEM READ I WRITE OBLASTEJ QWLQETSQ NABOR LINEJNYH RAWENSTW I
NERAWENSTW, OPISYWA@]IH WYPUKLU@ OBLASTX.
dLQ RASSMATRIWAEMOGO PRIMERA (RIS. 1) WRITE OBLASTX APPROKSIMIRUETSQ PRI
POMO]I MINIMALXNOJ WYPUKLOJ OBOLO“KI SLEDU@]IM OBRAZOM:
CH 1 = f I – 1; I Ÿ N; J – 1; J Ÿ I g;
CH 2 = f I = K; J – 1; J Ÿ N g;
CH 1[2 = f I – 1; I Ÿ N; J – 1; J Ÿ N; I – (K \Gamma1)J +N \GammaK
N \Gamma1 g:
rEZULXTIRU@]AQ OBLASTX IZOBRAVENA NA RIS. 5.
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
\Gamma \Gamma @
@
rIS. 5. oBLASTX, ZADANNAQ MINIMALXNOJ WYPUKLOJ OBOLO“KOJ
7

3 tO“NYE METODY POLU“ENIQ READ I WRITE OB­
LASTEJ
pODHOD bURKE­sAJTRONA [8] ZAKL@“AETSQ W TOM, “TO WSQ PAMQTX RASSMATRIWAETSQ KAK
ODNOMERNYJ MASSIW MEM . sSYLKI NA ``LEMENTY KONKRETNOGO MASSIWA PREOBRAZU@T­
SQ W SSYLKI NA ``LEMENTY MASSIWA MEM , PRI“EM WAVNO TOLXKO WZAIMNOE RASPOLO­
VENIE ISSLEDUEMYH MASSIWOW. pRI ISPOLXZOWANII ``TOGO PODHODA SRAZU RAZRE[A@T­
SQ PROBLEMY, SWQZANNYE S SOWME]ENIEM PARAMETROW PODPROGRAMMY (aliasing). dLQ
SLIQNIQ NESKOLXKIH LINEJNYH U“ASTKOW MOVET PRIMENQTXSQ OGRUBLENIE REZULXTATA
(PREDPOLOVENIE, “TO ``LEMENTY MEVDU WERHNEJ GRANICEJ ODNOGO LINEJNOGO U“ASTKA
MASSIWA MEM I NIVNEJ GRANICEJ DRUGOGO U“ASTKA PRINADLEVAT REZULXTIRU@]EJ
OBLASTI); W ``TOM SLU“AE DANNYJ METOD STANOWITSQ NETO“NYM. oB—EDINENIE NESKOLX­
KIH LINEJNYH U“ASTKOW, OTNOSQ]IHSQ K DANNOMU MASSIWU, MOVET NE BYTX LINEJNYM
U“ASTKOM, PO``TOMU EGO DALEKO NE WSEGDA MOVNO TO“NO PREDSTAWITX S POMO]X@ DANNOGO
PODHODA. dLQ POSTROENIQ PERESE“ENIQ DWUH OBLASTEJ S CELX@ OPREDELENIQ SU]ESTWO­
WANIQ ZAWISIMOSTI NUVNO PEREBRATX WSE SO“ETANIQ LINEJNYH U“ASTKOW IZ OPISANIJ
RAZNYH OBLASTEJ.
dLQ NA[EGO PRIMERA (RIS. 1) POLU“ATSQ SLEDU@]IE OPISANIQ:
M 1 = MEM [(J \Gamma 1) \Lambda (N + 1) + I + SA ]; 1 Ÿ I Ÿ N; 1 Ÿ J Ÿ I;
M 2 = MEM [(J \Gamma 1) \Lambda (N + 1) +K + SA ]; 1 Ÿ J Ÿ N;
GDE SA --- SDWIG NA“ALA MASSIWA A OTNOSITELXNO NA“ALA MASSIWA MEM . tO“NOE
SLIQNIE M 1 I M 2 W DANNOM SLU“AE NEWOZMOVNO, PO``TOMU NUVNO LIBO HRANITX OBA
OPISANIQ, LIBO OGRUBLQTX REZULXTAT, “TO PRIWEDET K OPISANI@ TAKOJ VE OBLASTI,
KAK I W METODE OPISANIQ S POMO]X@ TRIPLETOW (RIS. 3).
w RABOTE [27] OPISYWAETSQ METOD, W KOTOROM DLQ OPISANIQ OTDELXNOGO OBRA]ENIQ
K MASSIWU ISPOLXZUETSQ SISTEMA LINEJNYH RAWENSTW I NERAWENSTW, A DLQ OB—EDI­
NENIQ OBLASTEJ, SOOTWETSTWU@]IH NESKOLXKIM OBRA]ENIQM, STROITSQ SOWOKUPNYJ
OBRAZ (merged image). sOWOKUPNYJ OBRAZ POLU“AETSQ WWEDENIEM NOWYH CELO“ISLEN­
NYH PEREMENNYH. pUSTX p OBRA]ENIJ K MASSIWU OPISYWA@TSQ S POMO]X@ p SISTEM
LINEJNYH RAWENSTW I NERAWENSTW ~
OE j = F j ~ i j +~c j ; B j ~ i j Ÿ ~ b j ; 1 Ÿ j Ÿ p, GDE ~ i j --- WEKTOR
UPRAWLQ@]IH PARAMETROW CIKLOW, B j I ~ b j --- MATRICA I WEKTOR SWOBODNYH “LENOW,
ZADA@]IE OGRANI“ENIQ NA GRANICY IZMENENIQ PARAMETROW CIKLOW, A F j I ~c j --- MA­
TRICA I WEKTOR, ZADA@]IE INDEKSNYE WYRAVENIQ OBRA]ENIQ K MASSIWU. tOGDA DLQ
FORMALXNOGO OB—EDINENIQ WSEH p OBLASTEJ W ODNU WWODITSQ WEKTOR IZ p CELO“ISLEN­
NYH PEREMENNYH ~x = (x 1 ; : : : ; x p ), TAKIH “TO x 1 + : : :+x p = p \Gamma 1; 0 Ÿ x i Ÿ 1; 1 Ÿ i Ÿ p,
I REZULXTIRU@]AQ OBLASTX ZAPISYWAETSQ S POMO]X@ NERAWENSTW:
B j ~ i j Ÿ ~ b j ; ( ~ OE min \Gamma ~
OE max )x j Ÿ OE \Gamma F j ~ i j \Gamma ~c j Ÿ ( ~
OE max \Gamma ~
OE min )x j ;
GDE ~
OE min I ~
OE max --- L@BYE WEKTORA, TAKIE “TO ~
OE min Ÿ F j ~ i j + ~c j Ÿ ~ OE max DLQ L@BOGO j,
PRI KOTOROM B j ~ i j Ÿ ~ b j .
8

dLQ RASSMATRIWAEMOGO PRIMERA (RIS. 1) DWE WRITE OBLASTI OPISYWA@TSQ SLEDU­
@]IMI SISTEMAMI RAWENSTW I NERAWENSTW:
T 1 = f OE 1 = I; OE 2 = J; 1 Ÿ I Ÿ N; 1 Ÿ J Ÿ I g;
T 2 = f OE 1 = K; OE 2 = J; 1 Ÿ J Ÿ N g:
w KA“ESTWE ~ OE min I ~ OE max WOZXMEM WEKTORA IZ KONSTANT, WZQTYH IZ OPISANIQ MASSIWA A:
~ OE min =
/
1
1
!
; ~ OE max =
/
N + 1
N + 1
!
:
tOGDA SOWOKUPNYJ OBRAZ DWUH OBLASTEJ T 1 I T 2 BUDET SLEDU@]IM:
T 1[2 = f x 1 + x 2 = 1; 0 Ÿ x 1 Ÿ 1; 0 Ÿ x 2 Ÿ 1;
1 Ÿ I 1 Ÿ N; 1 Ÿ J 1 Ÿ I 1 ; 1 Ÿ J 2 Ÿ N;
\Gamma Nx 1 Ÿ OE 1 \Gamma I Ÿ Nx 1 ;
\Gamma Nx 1 Ÿ OE 2 \Gamma J Ÿ Nx 1 ;
\Gamma Nx 2 Ÿ OE 1 \Gamma K Ÿ Nx 2 ;
\Gamma Nx 2 Ÿ OE 2 \Gamma J Ÿ Nx 2 g:
4 sRAWNENIE METODOW POLU“ENIQ READ I WRITE
OBLASTEJ
rEZULXTATY SRAWNENIQ OPISANNYH METODOW OSNOWANY NA ANALIZE, PROWEDENNOM W RA­
BOTE [13].
pO TREBUEMOMU OB—EMU PAMQTI DLQ OPISANIQ OBLASTI. dLQ OPISANIQ OGRA­
NI“ENNOJ REGULQRNOJ SEKCII TREBUETSQ UKAZATX d KOMPONENT WEKTORA INDEKSNYH WY­
RAVENIJ MASSIWA \Phi(A), DLQ “EGO NEOBHODIM OB—EM PAMQTI, PROPORCIONALXNYJ d. dLQ
ZADANIQ REGULQRNOJ SEKCII S ISPOLXZOWANIEM TRIPLETNOJ NOTACII TAKVE TREBUET­
SQ OB—EM PAMQTI, PROPORCIONALXNYJ d, NO S B'OLX[IM KO``FFICIENTOM, TAK KAK DLQ
KAVDOGO IZMERENIQ MASSIWA TREBUETSQ HRANITX TRI POLQ. dLQ OPISANIQ PROSTOJ SEK­
CII TREBUETSQ 2d OGRANI“ENIJ, PARALLELXNYH KOORDINATNYM PLOSKOSTQM, I 2d 2 \Gamma 2d
OGRANI“ENIJ, ZADA@]IH WSE WOZMOVNYE DIAGONALI. w ITOGE POLU“AETSQ, “TO OB—EM
TREBUEMOJ PAMQTI PROPORCIONALEN d 2 . oPISANIE W WIDE WYPUKLOJ OBOLO“KI TRUDNO
OCENITX PO ZATRATAM PAMQTI, POSKOLXKU MNOGOE ZAWISIT OT KONKRETNOJ SITUACII.
oPISANIE OTDELXNOGO OBRA]ENIQ K MASSIWU PRI POMO]I SISTEMY LINEJNYH NERA­
WENSTW TREBUET ZADANIQ NERAWENSTW NA INDUKTIWNYE PEREMENNYE CIKLOW I RAWENSTW
DLQ WSEH IZMERENIJ MASSIWA. tREBUEMYJ DLQ ``TOGO OB—EM PAMQTI PROPORCIONALEN
l(l + 1)=2 +d l (l --- KOLI“ESTWO OB—EML@]IH CIKLOW). tREBOWANIQ K OB—EMU PAMQTI W
PODHODE bURKE­sAJTRONA ZAWISQT OT SPOSOBA HRANENIQ KO``FFICIENTOW, NO PO PORQDKU
``TO WELI“INA, PROPORCIONALXNAQ l(d + l).
pO SLOVNOSTI OPERACII OB—EDINENIQ SSYLOK NA ODIN I TOT VE MASSIW.
oB—EDINENIE OGRANI“ENNYH REGULQRNYH SEKCIJ TREBUET PROWEDENIQ NORMALIZACII,
9

“TO TREBUET O(d 2 ) [AGOW PO WREMENI. oB—EDINENIE REGULQRNYH SEKCIJ, ZADANNYH S
POMO]X@ TRIPLETOW, TREBUET TOLXKO LINEJNOGO PROSMOTRA SSYLOK NA MASSIW, TO ESTX
O(d) [AGOW PO WREMENI. oB—EDINENIE DWUH PROSTYH SEKCIJ TREBUET PROSMOTRA WSEH
OGRANI“ENIJ, TO ESTX ZATRATY PO WREMENI SOSTAWQT WELI“INU PORQDKA O(d 2 ). wREMQ
NA POLU“ENIE MINIMALXNOJ WYPUKLOJ OBOLO“KI DWUH OBLASTEJ NE MOVET BYTX WYRA­
VENO “EREZ d I l. sOGLASNO [28] DLQ ``TOGO OBY“NO TREBUETSQ O(I 2 V ) [AGOW PO WREMENI,
GDE I --- “ISLO NERAWENSTW W OPISANIQH OBLASTEJ, A V --- “ISLO PEREMENNYH W ``TIH
NERAWENSTWAH. pOSTROENIE OB—EDINENIQ DWUH OBLASTEJ W PODHODE bURKE­sAJTRONA MO­
VET PONIMATXSQ LIBO KAK PROSTO NABOR LINEJNYH U“ASTKOW, LIBO APPROKSIMIROWATX­
SQ, LIBO W OPREDELENNYH SLU“AQH WOZMOVNO SLIQNIE, “TO, ODNAKO, MOVET POTREBOWATX
ZNA“ITELXNYH ZATRAT WREMENI. pOSTROENIE SOWOKUPNOGO OBRAZA TREBUET LINEJNOGO
PROSMOTRA SSYLOK NA MASSIW DLQ NAHOVDENIQ WEKTOROW ~
OE min I ~ OE max , TO ESTX ZATRATY
PO WREMENI SOSTAWQT WELI“INU PORQDKA O(d).
pO SLOVNOSTI OPERACII PERESE“ENIQ (ANALIZ NA SU]ESTWOWANIE ZAWI­
SIMOSTI). dLQ NETO“NYH METODOW NE IMEET SMYSLA PRIMENQTX TO“NYE TESTY NA
NALI“IE ZAWISIMOSTEJ, TO ESTX POLNOSTX@ REALIZOWYWATX OPERACI@ PERESE“ENIQ. pO­
``TOMU WREMQ NA POSTROENIE PERESE“ENIQ ZAWISIT OT PRIMENQEMOGO TESTA NA NALI“IE
ZAWISIMOSTI. pOSTROENIE PERESE“ENIQ DLQ PROSTYH SEKCIJ TREBUET O(d 2 ) [AGOW PO
WREMENI. dLQ OPREDELENIQ PERESE“ENIQ DWUH OBLASTEJ, ZADAWAEMYH PRI POMO]I ME­
TODA bURKE­sAJTRONA, NUVNO PROANALIZIROWATX WOZMOVNOSTI PERESE“ENIQ WSEH WOZ­
MOVNYH PAR LINEJNYH U“ASTKOW. eSLI ODNA IZ OBLASTEJ SOSTOIT IZ m 1 LINEJNYH
U“ASTKOW, A DRUGAQ --- IZ m 2 , TO DLQ POSTROENIQ PERESE“ENIQ NEOBHODIMO O(m 1 m 2 )
RAZ PROIZWESTI OPERACI@ ``LEMENTARNOGO PERESE“ENIQ. pRI POSTROENII SOWOKUPNOGO
OBRAZA ``TOGO UDAETSQ IZBEVATX, TAK KAK WSE SSYLKI NA MASSIW OB—EDINENY W ODNOM
OPISATELE.
5 pOLU“ENIE IN I OUT OBLASTEJ IZ READ I
WRITE OBLASTEJ
mETODY POLU“ENIQ IN I OUT OBLASTEJ IZ READ I WRITE OBLASTEJ PODROBNO OPISA­
NY W [14, 15]. pOD IN OBLASTX@ MASSIWA, ISPOLXZUEMOGO W ANALIZIRUEMOJ PODPROGRAM­
ME, PONIMAETSQ MNOVESTWO ``LEMENTOW DANNOGO MASSIWA, NEOBHODIMYH DLQ WYPOLNENIQ
PODPROGRAMMY I NE WY“ISLQEMYH RANEE W EE TELE, TO ESTX POLU“ENNYH IZWNE DANNOJ
PODPROGRAMMY. pOD OUT OBLASTX@ MASSIWA PONIMAETSQ MNOVESTWO ``LEMENTOW, WY­
“ISLQEMYH W TELE PODPROGRAMMY I ISPOLXZUEMYH GDE­LIBO POSLE WYHODA IZ NEE. IN
I OUT OBLASTI TO“NO OPISYWA@T WLIQNIE PODPROGRAMMY NA KONTEKST EE WYZOWA, TO
ESTX RE[A@T ODNU IZ ZADA“ MEVPROCEDURNOGO ANALIZA.
pROCESS WY“ISLENIQ IN OBLASTEJ IDET ``SNIZU WWERH'' --- OT WYZYWAEMYH PODPRO­
GRAMM K WYZYWA@]IM. wNUTRI ODNOJ PODPROGRAMMY WY“ISLENIE IN OBLASTI IDET
W PORQDKE, OBRATNOM NAPRAWLENI@ DUG GRAFA UPRAWLENIQ. sNA“ALA W KA“ESTWE IN
OBLASTI PRINIMAETSQ READ OBLASTX, SOOTWETSTWU@]AQ POSLEDNEMU OPERATORU, WY­
10

“ISLQ@]EMU ``LEMENTY ANALIZIRUEMOGO MASSIWA. zATEM PRI DWIVENII PO OPERATO­
RAM K NA“ALU PODPROGRAMMY IZ TEKU]EJ OBLASTI WY“ITA@TSQ WRITE OBLASTI, SO­
OTWETSTWU@]IE DANNOMU MASSIWU, I DOBAWLQ@TSQ SOOTWETSTWU@]IE READ OBLASTI.
pODOBNYJ VE ALGORITM SU]ESTWUET I DLQ POLU“ENIQ IN OBLASTI DO­CIKLA, SUMMI­
RU@]EJ IN OBLASTI SO WSEH EGO ITERACIJ.
dLQ POLU“ENIQ OUT OBLASTI PODPROGRAMMY NEDOSTATO“NO ANALIZA EE TELA, NE­
OBHODIMO ZNANIE ISPOLXZOWANIQ ``LEMENTOW DANNOJ OBLASTI W POSLEDU@]EM TEKSTE.
pO``TOMU PROCESS WY“ISLENIQ OUT OBLASTEJ IDET ``SWERHU WNIZ'' --- OT WYZYWA@]IH
PODPROGRAMM K WYZYWAEMYM. sNA“ALA DLQ ANALIZIRUEMOGO MASSIWA POLU“A@TSQ IN
OBLASTI DLQ OPERATOROW WYZYWA@]EJ PODPROGRAMMY I DRUGIH WYZOWOW POSLE WYZOWA
DANNOJ PODPROGRAMMY. oB—EDINENIE POLU“ENNYH OBLASTEJ PERES“ITYWAETSQ W TER­
MINAH FORMALXNYH PARAMETROW ANALIZIRUEMOJ PODPROGRAMMY, POSLE “EGO I NA“INA­
ETSQ SOBSTWENNO PROCESS POSTROENIQ OUT OBLASTI DLQ DANNOJ PODPROGRAMMY. dLQ
WSEH OPERATOROW PODPROGRAMMY, PEREBIRAEMYH W PORQDKE, ZADAWAEMOM DUGAMI GRAFA
UPRAWLENIQ, BERETSQ PERESE“ENIE WRITE OBLASTEJ, SOOTWETSTWU@]IH ANALIZIRUEMO­
MU MASSIWU S PEREDANNOJ W PODPROGRAMMU OBLASTX@, POSLE “EGO BERETSQ OB—EDINENIE
TAKIH PERESE“ENIJ.
6 pOLU“ENIE IN I OUT OBLASTEJ S POMO]X@ GRAFA
ALGORITMA
iSPOLXZOWANIE GRAFA ALGORITMA, WWEDENNOGO W [1, 2, 3], POZWOLQET POLU“ITX TO“NOE
OPISANIE WHODNYH I WYHODNYH DANNYH FRAGMENTA PROGRAMMY.
oSNOWNAQ IDEQ ``TOGO METODA ZAKL@“AETSQ W TOM, “TOBY POLU“ITX OPISANIE NUVNO­
GO MNOVESTWA W PROSTRANSTWE ``LEMENTOW MASSIWA SREDSTWAMI ANALIZA PROSTRANSTWA
ITERACIJ. eSLI IZ WSEJ OBLASTI SRABATYWANIQ
OPERATORA\Omega J [3] WY“ESTX WSE OBLASTI
\Delta k IZ OPISANIQ GRAFA ALGORITMA FRAGMENTA PO WHODU A i (TO“KI OBLASTEJ \Delta k QWLQ­
@TSQ KONE“NYMI TO“KAMI DUG GRAFA ALGORITMA DANNOGO FRAGMENTA), TO POLU“ENNAQ
OBLASTX\Omega inp BUDET OPISYWATX MNOVESTWO TO“EK PROSTRANSTWA ITERACIJ, W KOTORYH
A i POTREBLQET WHODNYE DLQ ISSLEDUEMOGO FRAGMENTA DANNYE.
tEPERX NUVNO POLU“ITX OPISANIE OBLASTI PROSTRANSTWA
ITERACIJ\Omega inp W PRO­
STRANSTWE ``LEMENTOW MASSIWA A. rASSMOTRIM ZADA“U DLQ WHODA A i (P (J)) MASSIWA A,
GDE P (J) --- ``TO WEKTORNAQ FUNKCIQ, OPREDELQ@]AQ INDEKSNYE WYRAVENIQ DANNOGO
WHODA. bUDEM PREDPOLAGATX, “TO DLQ WHODA A i NAJDENA PODOBLASTX PROSTRANSTWA ITE­
RACIJ\Omega i
inp , W KAVDOJ TO“KE KOTOROJ ARGUMENTOM DLQ WHODA A i QWLQ@TSQ NA“ALXNYE
DANNYE. pO OPREDELENI@ DANNOJ OBLASTI, DLQ L@BOJ TO“KI J
2\Omega i
inp ``LEMENT MASSIWA
A i (P (J)) NIGDE W DANNOM FRAGMENTE NE WY“ISLQETSQ, A BERETSQ IZ WHODNYH DANNYH,
T.E. QWLQETSQ ``LEMENTOM ISKOMOGO MNOVESTWA.
CKONSTRUIRUEM WSPOMOGATELXNYJ FRAGMENT, SODERVA]IJ WHOD A 0 PO PEREMENNOJ
11

A:
DO I 1 = l 1 ; u 1
: : :
DO I d = l d ; u d
: : : = : : : A 0 (I 1 ; I 2 ; : : : ; I d ) : : :
END DO
: : :
END DO ,
GDE d --- ``TO RAZMERNOSTX PEREMENNOJ A, A l k ; u k --- NIVNQQ I WERHNQQ GRANICY k­GO
IZMERENIQ MASSIWA A SOOTWETSTWENNO, k = 1; d. bUDEM S“ITATX, “TO DANNYJ FRAGMENT
DOSTIVIM IZ KAVDOJ TO“KI PROGRAMMY I WSEGDA SRABATYWAET POSLEDNIM --- ``TOGO
WSEGDA MOVNO DOBITXSQ ``KWIWALENTNYM PREOBRAZOWANIEM FRAGMENTA.
wOZXMEM L@BU@ TO“KU J
OBLASTI\Omega i
inp . qSNO, “TO ``LEMENT MASSIWA A i (P (J)) =
A i (p 1 (J); : : : ; p d (J)) PRINADLEVIT ISKOMOMU MNOVESTWU I NADO NAJTI OPISANIE WSEH
PODOBNYH TO“EK P (J) W PROSTRANSTWE ``LEMENTOW MASSIWA A.
pREDPOLOVIM, “TO W KAVDOJ TO“KE J
OBLASTI\Omega i
inp PROISHODIT NE ISPOLXZOWANIE,
A OPREDELENIE ``LEMENTA A i (P (J)), T.E. WHOD A i BUDET IGRATX ROLX WYHODA. bUDEM S“I­
TATX OBLASTX@ SRABATYWANIQ OPERATORA, SODERVA]EGO A i , NE
OBLASTX\Omega J , A OBLASTX
\Omega i
inp . oBLASTX SRABATYWANIQ WHODA A 0 OPREDELQETSQ TOLXKO GRANICAMI CIKLOW WSPO­
MOGATELXNOGO FRAGMENTA, TAK KAK ON BEZUSLOWNO DOSTIVIM IZ KAVDOJ TO“KI PROGRAM­
MY.
w TAKIH PREDPOLOVENIQH RE[IM STANDARTNU@ ZADA“U POSTROENIQ ``LEMENTARNOGO
GRAFA ALGORITMA A i ! A 0 I NAJDEM OBLASTX \Delta A 0
, NA KOTOROJ OPREDELENY DUGI GRAFA
ALGORITMA. oSOBENNOSTX MNOVESTWA \Delta A 0
ZAKL@“AETSQ W TOM, “TO, QWLQQSX MNOGOGRAN­
NIKOM W PROSTRANSTWE ITERACIJ, ON ODNOWREMENNO QWLQETSQ I OPISANIEM MNOVESTWA
WHODNYH DANNYH W PROSTRANSTWE ``LEMENTOW MASSIWA A DLQ WHODA A i .
aNALOGI“NYM OBRAZOM DANNAQ ZADA“A RE[AETSQ DLQ WSEH WHODOW, A ISKOMOE PODMNO­
VESTWO WHODNYH ``LEMENTOW MASSIWA A QWLQETSQ OB—EDINENIEM OBLASTEJ, POLU“ENNYH
PRI RE[ENII DANNOJ ZADA“I DLQ KAVDOGO OTDELXNOGO WHODA.
iSPOLXZOWANIE TAKOGO METODA POZWOLQET POLU“ITX TO“NOE OPISANIE IN I OUT
OBLASTEJ PODPROGRAMMY. sU]ESTWOWANIE ``FFEKTIWNYH ALGORITMOW POSTROENIQ GRA­
FA ALGORITMA OBESPE“IWAET WOZMOVNOSTX ISPOLXZOWANIQ ``TOGO METODA PRI ANALIZE
REALXNYH PROGRAMM.
7 oPISANIE WHODNYH I WYHODNYH DANNYH PODPRO­
GRAMMY W TERMINAH FAKTI“ESKIH PARAMETROW
pEREJDEM TEPERX K RE[ENI@ WTOROJ ZADA“I MEVPROCEDURNOGO ANALIZA --- OPISANI@
WHODNYH I WYHODNYH DANNYH PODPROGRAMMY W TERMINAH FAKTI“ESKIH PARAMETROW.
12

oPISYWAEMYJ ZDESX METOD OPIRAETSQ NA [14] I TREBUET, “TOBY WHODNYE I WYHODNYE
DANNYE PODPROGRAMMY UVE BYLI OPISANY W WIDE SISTEMY LINEJNYH NERAWENSTW.
pUSTX W PROGRAMME ESTX DWE PODPROGRAMMY P I Q, TAKIE, “TO:
SUBROUTINE P(: : : )
DIMENSION A p (lp 1 : up 1 ; : : : ; lp p : up p )
: : :
CALL Q(: : : ; A p (op 1 ; : : : ; op p ); : : :)
: : :
END
SUBROUTINE Q(: : : ,A q ,: : : )
DIMENSION A q (lq 1 : uq 1 ; : : : ; lq q : uq q )
: : :
END
pUSTX ``LEMENTY MASSIWA A q , PREDSTAWLQ@]IE “ASTX WHODNYH I WYHODNYH DANNYE
PODPROGRAMMY Q, PREDSTAWLENY W WIDE
OBLASTI\Omega q , OPISANNOJ S POMO]X@ NABORA
LINEJNYH RAWENSTW I NERAWENSTW. tREBUETSQ PERES“ITATX ``TU OBLASTX W TERMINAH
WYREZKI IZ SOOTWETSTWU@]EGO FAKTI“ESKOGO PARAMETRA­MASSIWA A p .
zAPI[EM USLOWIE \Gamma pq TOGO, “TO DWA ``LEMENTA MASSIWOW A p (/ 1 ; : : : ; / p ) I A q (OE 1 ; : : : ; OE q )
SSYLA@TSQ NA ODNU I TU VE OBLASTX PAMQTI:
\Gamma pq : (/ 1 \Gamma lp 1 ) +
p
X
i=2
2
4 (/ i \Gamma lp i )
i\Gamma1 Y
j=1
(up j \Gamma lp j + 1)
3
5 \Gamma offset =
= (OE 1 \Gamma lq 1 ) +
q
X
i=2
2
4 (OE i \Gamma lq i )
i\Gamma1 Y
j=1
(uq j \Gamma lq j + 1)
3
5 ;
GDE
offset = (op 1 \Gamma lp 1 ) +
p
X
i=2
2
4 (op i \Gamma lp i )
i\Gamma1 Y
j=1
(up j \Gamma lp j + 1)
3
5 :
tOGDA PERESE“ENIE TREH
OBLASTEJ\Omega =\Omega q `` \Gamma pq `` flp i Ÿ / i Ÿ up i j i = 1; pg NEQWNO
ZADAET
OBLASTX\Omega p MASSIWA A p , SOOTWETSTWU@]U@
OBLASTI\Omega q MASSIWA A q . dLQ PO­
LU“ENIQ QWNOGO
OPISANIQ\Omega p NEOBHODIMO POLU“ITX PROEKCI@ (p + q)­MERNOJ OBLASTI
\Omega NA p­MERNOE PODPROSTRANSTWO, SOOTWETSTWU@]EE MASSIWU A p . ---TO MOVNO SDELATX
S POMO]X@ ISKL@“ENIJ fURXE­mOCKINA [21, 23], ESLI RAWENSTWO \Gamma pq LINEJNO. oPRE­
DELENIE USLOWIJ EGO LINEJNOSTI RASSMATRIWAETSQ W DALXNEJ[EM IZLOVENII.
eSLI RAWENSTWO \Gamma pq NELINEJNO, TO PRI NEKOTORYH USLOWIQH MOVNO POLU“ITX BOLEE
PROSTOE USLOWIE. eSLI MASSIWY A p I A q IME@T ODINAKOWOE “ISLO ``LEMENTOW W PERWYH
(d\Gamma 1) RAZMERNOSTQH (TO ESTX up i \Gamma lp i = uq i \Gamma lq i ; 1 Ÿ i Ÿ d\Gamma 1), I op i = lp i ; 1 Ÿ i Ÿ d\Gamma 1,
13

TO DOBAWIM W OPISANIE
OBLASTI\Omega RAWENSTWA / i \Gamma lp i = OE i \Gamma lq i ; 1 Ÿ i Ÿ d \Gamma 1 I SOSTAWIM
“ASTI“NOE URAWNENIE RANGA d:
\Gamma d
pq : (/ d \Gamma lp d ) +
p
X
i=d+1
2
4 (/ i \Gamma lp i )
i\Gamma1 Y
j=d
(up j \Gamma lp j + 1)
3
5 \Gamma offset =
= (OE d \Gamma lq d ) +
q
X
i=d+1
2
4 (OE i \Gamma lq i )
i\Gamma1 Y
j=d
(uq j \Gamma lq j + 1)
3
5 ;
GDE
offset = (op d \Gamma lp d ) +
p
X
i=d+1
2
4 (op i \Gamma lp i )
i\Gamma1 Y
j=d
(up j \Gamma lp j + 1)
3
5 :
---TO URAWNENIE PRO]E, “EM \Gamma pq , I W REALXNYH SLU“AQH MOVET OKAZATXSQ LINEJNYM,
W TO WREMQ KAK POLNOE URAWNENIE TAKOWYM NE QWLQETSQ. eSLI KOLI“ESTWO RAZMERNO­
STEJ S ODINAKOWYM “ISLOM ``LEMENTOW RAWNO q, NO MENX[E p, TO W OPISANIE
OBLASTI\Omega WMESTO USLOWIQ \Gamma d
pq NUVNO DOBAWITX RAWENSTWA f/ i = op i ; j i = q + 1; pg.
pRAKTI“ESKI TAKOJ VE METOD OPISAN I W [27]. tAM RASSMOTRENIE OGRANI“IWAET­
SQ SLU“AEM, KOGDA “ISLO IZMERENIJ FORMALXNOGO PARAMETRA­MASSIWA NE PREWOSHODIT
“ISLA IZMERENIJ SOOTWETSTWU@]EGO FAKTI“ESKOGO PARAMETRA, RAZMERY ``TIH MASSI­
WOW SOWPADA@T W PERWYH (d \Gamma 1) RAZMERNOSTQH I MOGUT OTLI“ATXSQ TOLXKO W d­OJ
RAZMERNOSTI. ---TIH USLOWIJ DOSTATO“NO, “TOBY RAWENSTWO \Gamma d
pq BYLO LINEJNYM, TO
ESTX DLQ PROWEDENIQ POLNOGO ANALIZA I PREDYDU]IM METODOM. sAM VE OPISANNYJ
ZDESX METOD OTLI“AETSQ OT PREDYDU]EGO PRAKTI“ESKI TOLXKO TEM, “TO FORMULY NE
WYPISYWA@TSQ QWNO, A POLU“A@TSQ “EREZ POSLEDOWATELXNOSTX PROMEVUTO“NYH [AGOW.
dLQ TOGO, “TOBY POLU“ITX PROEKCI@ (p + q)­MERNOJ
OBLASTI\Omega NA p­MERNOE PRO­
STRANSTWO, NEOBHODIMO ISKL@“ITX PEREMENNYE, WWEDENNYE DLQ
OPISANIQ\Omega q , IZ WSEH
RAWENSTW I NERAWENSTW. ---TO MOVNO SDELATX METODOM fURXE­mOCKINA ([21] [23]), ESLI
WSE OGRANI“ENIQ, SODERVA]IE ``TI PEREMENNYE, LINEJNY. tAK KAK W
OPISANIE\Omega q
WHODQT TOLXKO LINEJNYE OGRANI“ENIQ, NELINEJNOSTX PO DANNYM PEREMENNYM MOVET
WOZNIKNUTX TOLXKO W RAWENSTWE \Gamma pq (\Gamma d
pq ). kROME TOGO, DLQ PROWEDENIQ DALXNEJ[EGO
ANALIZA PROGRAMMY WAVNO, “TOBY WSE POLU“A@]IESQ OGRANI“ENIQ TAKVE BYLI LI­
NEJNYMI. pO``TOMU NUVNO WYDELITX USLOWIQ NA WNE[NIE PEREMENNYE, PRI KOTORYH
\Gamma pq (\Gamma d
pq ) BUDET LINEJNYM PO WSEM PEREMENNYM.
dLQ ``TOGO BEREM RAWENSTWO \Gamma pq (\Gamma d
pq ), PRIWODIM W NEM PODOBNYE, POSLE “EGO PRI­
RAWNIWAEM K NUL@ WSE NELINEJNYE “ASTI. eSLI IZ POLU“IW[IHSQ RAWENSTW MOVNO
WYRAZITX PEREMENNYE, WWEDENNYE DLQ
OPISANIQ\Omega q , “EREZ WNE[NIE PEREMENNYE, I
PODSTANOWKA ``TIH WYRAVENIJ W OGRANI“ENIQ WMESTO PEREMENNYH NE WHODIT W PROTIWO­
RE“IE S ZADANNYMI OGRANI“ENIQMI NA WNE[NIE PEREMENNYE, TO DOBAWIM K RAWENSTWU
\Gamma pq (\Gamma d
pq ) S ZANULENNYMI NELINEJNYMI “ASTQMI OGRANI“ENIQ lp i Ÿ / i Ÿ up i ; 1 Ÿ i Ÿ p
I lq i Ÿ OE i Ÿ uq i ; 1 Ÿ i Ÿ q. pOSLE ``TOGO ISKL@“AEM IZ POLU“IW[IHSQ LINEJNYH
OGRANI“ENIJ WSE PEREMENNYE, KROME WNE[NIH, I POLU“AEM ISKOMYE OGRANI“ENIQ NA
WNE[NIE PEREMENNYE.
14

rASSMOTRIM PRIMER:
SUBROUTINE P(: : : )
DIMENSION A p (N; N;N)
: : :
CALL Q(: : : ; A p (1; s; m); : : :)
: : :
END
SUBROUTINE Q(: : : ,A q ,: : : )
DIMENSION A q (N; t)
: : :
END
pERWAQ RAZMERNOSTX MASSIWOW OPISANA ODINAKOWO, PO``TOMU ZAPISYWAEM RAWENSTWO
/ 1 \Gamma 1 = OE 1 \Gamma 1, TO ESTX / 1 = OE 1 . dLQ OSTAW[EJSQ “ASTI ZAPISYWAEM “ASTI“NOE
URAWNENIE RANGA 2:
\Gamma 2
pq : (/ 2 \Gamma 1) + (/ 3 \Gamma 1)N \Gamma (s \Gamma 1) \Gamma (m \Gamma 1)N = OE 2 \Gamma 1:
pRIWEDQ PODOBNYE, POLU“AEM OE 2 = / 2 \Gamma s + 1 + (/ 3 \Gamma m)N . ---TO RAWENSTWO BUDET
LINEJNYM PRI / 3 = m. tAK KAK 1 Ÿ / 3 Ÿ N , TO ``TO WOZMOVNO PRI 1 Ÿ m Ÿ N . k
POLU“IW[EMUSQ LINEJNOMU RAWENSTWU OE 2 = / 2 \Gamma s + 1 DOBAWLQEM OGRANI“ENIQ 1 Ÿ
OE 2 Ÿ t I 1 Ÿ / 2 Ÿ N . pOSLE ISKL@“ENIQ PEREMENNYH OE 2 I / 2 POLU“AEM NERAWENSTWA
s – 1 I t Ÿ N \Gamma s + 1. iTAK, RAWENSTWO \Gamma 2
pq BUDET LINEJNYM PRI WYPOLNENII USLOWIJ:
8 ? !
? :
1 Ÿ m Ÿ N
1 Ÿ t Ÿ N \Gamma s + 1
1 Ÿ s
tAKIM OBRAZOM NAKLADYWA@TSQ DOPOLNITELXNYE USLOWIQ NA WNE[NIE PEREMENNYE
PODPROGRAMMY, WYPOLNENIE KOTORYH GARANTIRUET LINEJNOSTX USLOWIQ \Gamma pq (\Gamma d
pq ), A
ZNA“IT, I WOZMOVNOSTX PROWEDENIQ MEVPROCEDURNOGO ANALIZA.
nAMI BYLA SOBRANA STATISTIKA PO MNOGIM REALXNYM PROGRAMMAM S CELX@ OPREDE­
LITX PRIMENIMOSTX METODOW MEVPROCEDURNOGO ANALIZA I, W “ASTNOSTI, WOZMOVNOSTX
OPISANIQ WHODNYH I WYHODNYH DANNYH PODPROGRAMMY W TERMINAH FAKTI“ESKIH PA­
RAMETROW. sTATISTIKA SOBIRALASX PO MNOGIM PARAMETRAM. nEKOTORYE POLU“ENNYE
DANNYE DLQ NESKOLXKIH PROEKTOW PRIWEDENY W TABLICE NA RIS. 6. pREDSTAWLENY PRO­
EKTY IZ SAMYH RAZLI“NYH OBLASTEJ, NAPRIMER, FLO52 I MHD WZQTY IZ IZWESTNOGO
PAKETA Perfect Club, GCMA --- PROGRAMMA MODELIROWANIQ DOLGOWREMENNYH IZMENENIJ
KLIMATA, LIU FTC --- PROGRAMMA MODELIROWANIQ USTOJ“IWOSTI PLAZMY W USTANOWKAH
UPRAWLQEMOGO TERMOQDERNOGO SINTEZA. dANNYE ANALIZIROWALISX DLQ WSEH WYZOWOW
PODPROGRAMM I FUNKCIJ PO WSEM ARGUMENTAM I WSEM DANNYM IZ COMMON­BLOKOW.
15

GCMA ELVEC K SPA MHD LIU FTC FLO52
~ISLO STROK 15288 1187 42732 2577 26765 1990
~ISLO PODPROGRAMM 161 11 344 71 404 28
~ISLO WYZOWOW 366 50 3079 147 4890 86
sKALQRY 1410 309 12351 6075 617349 803
mASSIWY 1198 95 5474 3668 126734 170
sOWPADENIE 918 57 4976 3668 126561 79
aNALIZIRUEMO 120 38 249 0 152 35
dRUGIE SLU“AI 160 0 249 0 21 56
pROCENT 77% 100% 94% 100% 99% 76%
rIS. 6. rEZULXTATY SBORA STATISTIKI
nEKOTORYE POQSNENIQ K TABLICE. w EE STOLBCAH PRIWEDENY DANNYE DLQ 6 DOSTA­
TO“NO BOLX[IH I RAZNORODNYH PROEKTOW. sTROKI TABLICY OBOZNA“A@T SLEDU@]EE:
''~ISLO STROK'' --- “ISLO STROK ISHODNOGO TEKSTA PROGRAMMY; ''~ISLO PODPROGRAMM''
--- KOLI“ESTWO PROGRAMMNYH EDINIC W PROEKTE; ''~ISLO WYZOWOW'' --- OB]EE “ISLO PRO­
ANALIZIROWANNYH WYZOWOW W TEKSTE; ''sKALQRY'' --- KOLI“ESTWO SKALQRNYH ARGUMENTOW
W WYZOWAH; ''mASSIWY'' --- KOLI“ESTWO ARGUMENTOW­MASSIWOW W WYZOWAH; ''sOWPADENIE''
--- KOLI“ESTWO SLU“AEW, KOGDA OPISANIE FORMALXNOGO PARAMETRA­MASSIWA W TO“NO­
STI SOWPADAET S OPISANIEM FAKTI“ESKOGO PARAMETRA; ''aNALIZIRUEMO'' --- KOLI“ESTWO
WHOVDENIJ ARGUMENTOW­MASSIWOW, NE POPAW[IH W PREDYDU]IJ PUNKT, NO NE SOSTA­
WLQ@]IH PROBLEMY PRI MEVPROCEDURNOM ANALIZE; ''dRUGIE SLU“AI'' --- WHOVDENIQ
ARGUMENTOW­MASSIWOW, NE POPAW[IE W PREDYDU]IE DWA PUNKTA (``TO NE OBQZATELXNO
ZNA“IT, “TO ``TO SLU“AI SOSTAWLQ@T TRUDNOSTX DLQ MEVPROCEDURNOGO ANALIZA, PO­
TOMU “TO STATISTIKA SOBIRALASX S ISPOLXZOWANIEM OTNOSITELXNO GRUBYH ``WRISTIK);
''pROCENT'' --- PROCENT WYZOWOW, WSE ARGUMENTY KOTORYH NE POPALI W PREDYDU]IJ
SLU“AJ (TO ESTX WYZOWOW, ZAWEDOMO NE PREPQTSTWU@]IH MEVPROCEDURNOMU ANALIZU).
iZ TABLICY WIDNO, “TO OPISYWAEMAQ TEHNIKA PRIMENIMA K PODAWLQ@]EMU BOLX­
[INSTWU WYZOWOW W REALXNYH PROGRAMMAH. pRI“EM DOPOLNITELXNOE ISSLEDOWANIE
NAIBOLEE SLOVNOJ DLQ MEVPROCEDURNOGO ANALIZA PROGRAMMY FLO52 POKAZALO, “TO W
OSNOWNOJ WY“ISLITELXNOJ “ASTI, NA KOTORU@ PRIHODITSQ BOLEE 90 % WREMENI ISPOL­
NENIQ PROGRAMMY, NET NI ODNOGO NEANALIZIRUEMOGO ARGUMENTA.
8 zAKL@“ENIE
w DANNOJ RABOTE PRIWEDEN OBZOR SU]ESTWU@]IH METODOW MEVPROCEDURNOGO ANALIZA
PROGRAMM, A TAKVE PREDLOVENY NEKOTORYE PUTI IH DALXNEJ[EGO USOWER[ENSTWOWA­
NIQ. pRIWEDENNAQ STATISTIKA PO REALXNYM PROGRAMMAM PODTWERVDAET RAZRE[I­
MOSTX ZADA“ MEVPROCEDURNOGO ANALIZA DLQ BOLX[INSTWA PRILOVENIJ. oPISANNAQ
TEHNIKA MEVPROCEDURNOGO ANALIZA ISPOLXZUETSQ WO MNOGIH REALXNYH SISTEMAH, TA­
KIH KAK: PIPS [17], FIAT [11], ParaScope [12], Polaris [7], Parafrase­2 [22].
16

hO“ETSQ WYRAZITX BOLX[U@ BLAGODARNOSTX p.a. cERETELI ZA POMO]X W SBORE STA­
TISTIKI, A TAKVE wL.w. wOEWODINU ZA WNIMATELXNOE PRO“TENIE STATXI, MNOGO“ISLEN­
NYE ZAME“ANIQ I PREDLOVENIQ.
lITERATURA
[1] w.w. wOEWODIN mATEMATI“ESKIE OSNOWY PARALLELXNYH WY“ISLENIJ// m., 1991.
[2] wL.w. wOEWODIN sTATI“ESKIJ ANALIZ I WOPROSY ``FFEKTIWNOJ REALIZACII PRO­
GRAMM// wY“ISLITELXNYE PROCESSY I SISTEMY (pOD. RED. g.i. mAR“UKA). m.,
1992. N ffi 9. s. 249­301.
[3] wL.w. wOEWODIN tEORIQ I PRAKTIKA ISSLEDOWANIQ PARALLELIZMA POSLEDOWATELX­
NYH PROGRAMM// pROGRAMMIROWANIE. 1992. N ffi 3. s. 38--53.
[4] wL.w. wOEWODIN oPISANIE WHODNYH I WYHODNYH DANNYH FRAGMENTOW PROGRAMM//
wESTNIK mOSKOWSKOGO UNIWERSITETA. sERIQ 15. 1997. N ffi 1. s. 41--44.
[5] w.a. eWSTIGNEEW, w.a. sEREBRQKOW mETODY MEVPROCEDURNOGO ANALIZA (OBZOR)//
pROGRAMMIROWANIE. 1992. N ffi 3. s. 4--15.
[6] V. Balasundaram, K. Kennedy A Technique for Summarizing Data Access and Its
Use in Parallelism Enhancing Transformation// In Proceedings of the 1989 ACM
SIGPLAN Conference on Programming Language Design and Implementation. Vol.
24. N ffi 7. pp. 41--53. Portland, Orgen. June 1989.
[7] W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, T. Lawrence, J. Lee,
D. Padua, Y. Paek, B. Pottenger, L. Rauchwerger, P. Tu Parallel programming with
Polaris// Computer. Vol. 29. N ffi 12. pp. 78--82. December 1996.
[8] M. Burke, R. Cytron Interprocedural Dependence Analysis and Parallelisation//
ACM SIGPLAN'86 Symposium on Compiler Construction. Vol. 21. N ffi 7. pp. 162--
175. June 1986.
[9] D. Callahan, K. Kennedy Analysis of Interprocedural Side Effects in a Parallel Pro­
gramming Environment// Journal of Parallel and Distributed Computing. Vol. 5.
pp. 517--550. Oktober 1988.
[10] D. Callahan A Global Approach to Detection of Parallelism// PhD thesis. Rice Uni­
versity. Comp. Sci. Tech. Rep. TR87­50. March 1987.
[11] A. Carle, M. W. Hall, J. Mellor­Crummey, R. Rodriguez FIAT: A Framework for
Interprocedural Analysis and Transformation// Rice University. CRPC Tech. Rep.
TR95522­S. March 1995.
17

[12] D. Callahan, K. D. Cooper, R. T. Hood, K. Kennedy, L. Torczon ParaScope: A Par­
allel Programming Environment// The International Journal Supercomputer. Vol.
2. N ffi 4. pp. 84--99. 1988.
[13] S.­E. Choi An Overview of Compiler Techniques for Interprocedural Array Section
Analysis// University of Washington. Tech. Rep. 95­11­06. November 1995.
[14] B. Creusillet, F. Irigoin Interprocedural Array Region Analyses// Eighth Internation­
al Workshop on Languages and Compilers for Parallel Computing. pp.4­1 to 4­15.
Colombus (Ohio), USA. August 1995.
[15] B. Creusillet IN and OUT Array Region Analyses// Fifth Workshop on Compilers
for Parallel Computers. Malaga, Spain. June 1995.
[16] P. Havlak, K. Kennedy An Implementation of Interprocedural Bounded Regular Sec­
tion Analysis// IEEE Transactions on Parallel and Distributed Systems. Vol. 2. N ffi 3.
pp. 350--360. July 1991.
[17] F. Irigoin, P. Jouvelot, R. Triolet Semantical Interprocedural Parallelisation: An
Overview of the PIPS Project// ACM International Conference on Supercomputing,
ICS'91. Cologne, Allemagne. June 1991.
[18] Z. Li, P.­C. Yew Efficient Interprocedural Analysis for Program Parallelisation and
Restructuring// In Proceedings of ACM SIGPLAN Symposium on Parallel Pro­
gramming: Experience with Applications, Languages and Systems. Vol. 23. N ffi 9.
pp. 85--99. July 1988.
[19] Z. Li, P.­C. Yew Interprocedural Analysis and Program Restructuring for Parallel
Programs// CSRD Tech. Rep. 720. January 1988.
[20] Z. Li, P.­C. Yew Interprocedural Analysis for Parallel Computing// Proceedings of
the 1988 International Conference on Parallel Processing. Vol. 2. pp. 221--228. August
1988.
[21] D. E. Maydan, J. L. Hennessy, M. S. Lam. Efficient and Exact Data Dependence
Analysis// Proceedings of the ACM SIGPLAN'91 Conference on Programming Lan­
guage Design and Implementation.
[22] C. D. Polychronopoulos, M. B. Gircar, M. R. Haghighat, C. L. Lee, B. P. Leung,
D. A. Shouten The Structure of Parafrase­2: Advanced Parallelizing Compiler for
C and Fortran// Languages and Compilers for Parallel Computing. Pitman Publ.
London. 1990.
[23] W. Pugh. A Practical Algorithm for Exact Array Dependence Analysis// Communi­
cations of the ACM. Vol. 35, N ffi 8. pp. 102­114. August 1992.
18

[24] S. Richardson, M. Ganapathi Interprocedural Analysis Useless for Code Optimiza­
tion// Stanford University. Tech. Rep. CSL­TR­87­342. November 1987.
[25] R. W. Scheifler An Analysis of Inline Substitution for a Structured Programming
Language// Communications of the ACM. Vol. 20. N ffi 9. September 1977.
[26] D. A. Schouten An Overview of Interprocedural Analyses Techniques for High Per­
formance Parallelizing Compilers// Univ. of Illinois at Urbana­Champaign. CSRD
Tech. Rep. 1005. May 1990.
[27] P. Tang Exect Side Effects for Interprocedural Dependence Analysis// Australian
National University. Tech. Rep. TR­CS­92­15. November 1992.
[28] R. Triolet, F. Irigoin, P. Feautrier Direct Parallelism of Call Statements// In Pro­
ceedings of the ACM SIGPLAN'86 Symposium on Compiler Construction. SIG­
PLAN Notices. Vol. 21. N ffi 7. pp. 176--185. June 1986.
19