1994. Compiler Transformations for High-Perforamce Computing, страница 4
Описание файла
PDF-файл из архива "1994. Compiler Transformations for High-Perforamce Computing", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Anothercommonnotationfor _dependencesuses S~ 8S4 forfjl~ + S4, S58SG for S5 ++ SG, and S7 ~“safor S7 + Sa,In the case of data dependence,whenwe writeX * Y we are being somewhatimprecise:the individualvariablereferences withina statementgeneratethedependence,not thestatementas awhole. In the output dependenceexampleabove, b, C, d, and e can all be read frommemoryin any order, and the resultsofb * c and d + e can be executed as soon astheiroperandshavebeenreadfrommemory.S7 * S~ actuallymeansthatthe store of the valueb * c into a mustprecede the store of the value d + e intoa.
When there is a potentialambiguity,we willdistinguishbetweendifferentvariablereferenceswithinstatements.5.2 RepresentingDependenceTo capturethe dependenceinformationfor a piece of code, the compilercreates adependence graph;typicallyeach node inthe graph representsone statement.Anarc betweentwo nodesindicatesthatthere is a dependencebetweenthe computationsthey represent.Because it can be cumbersometo account for both controland data dependenceduringanalysis,sometimescompilersconvertcontroldependenceinto data dependenceusing a techniquecalledif-conversion[Allenet al.
1983].If-conversionintroducesadditionalboolean variablesthat encode the conditional predicates;every statementwhoseexecutiondependson the conditionalisthen modifiedto test the booleanvariable. In the transformedcode, data dependencesubsumescontroldependence.●Transformationsdoi=2,n1a[i]= a[il2b[i]= a[i-1]355+ c* b [i]end doFigure 3.Loop-carried5.3 Loop Dependencedependence.AnalysisSo far we have examineddependenceinthe context of straight-linecode with conditionals—analyzingloopsis a morecomplicatedproblem.Instraight-linecode, each statementis executedat mostonce, so the dependencearcs describedsofar captureall the possibledependencerelationships.In loops, each statementmay be executedmanytimes,and formanytransformationsit is necessaryto describedependencethatexist betweeniterations,calledloop-carrieddependence.A simpleexampleof loop-carrieddependenceis shown in Figure3.
There isno dependencebetweenS’l and S2 within any singleiterationof the loop, butthere is one betweentwo successive iterations. When i = k, S2 reads the value ofa[k – 1] writtenby S1 in iterationk – 1.To compute dependenceinformationforloops, the key problemis to understandthe use of arrays;scalar variablesarerelativelyeasy to manage.
To track arraybehavior,the compilermust analyzethesubscriptexpressionsineacharrayreference.To discoverwhetherthere is a dependence in the loop nest, it is sufficienttodeterminewhetherany of the iterationscan write a value that is read or writtenby any of the other iterations.Dependingon the language,loop incrementsmaybe arbitraryexpressions.However,the dependenceanalysisalgorithmsmay requirethat the loops haveonly unit increments.When they do not,the compilermay be able to normalizethem to fit the requirementsof the analysis, as describedin Section6.3.6. Forthe remainderof this section we will assume that all loops are incrementedby 1for each iteration.ACMComputingSurveys,Vol.
26, No 4, December1994356eDavidF. Bacondo ilet al.= 11, u1do id = [d,1a[fl(il,2. ..=Ud. . ..id). fm($l, ($l, . . . ..d)] = . . .a[gl(il)...,id), . . ..9m(&!..., id)]end doenddoend doFigure 4.GeneraI loop nest.Figure4 shows a generalizedperfectnest of d loops. The body of the loop nestreadsand writeselementsof themdimensionalarray a. The functionf, andg, map the currentvaluesof the 100Piterationvariablesto integersthat indexthe ith dimensionof a. The generalizedloop can give rise to any type of datadependence:for instance,two differentiterationsmay write the same elementofa, creatingan outputdependence.An iterationcan be uniquelynamed bya vectorof d elements1 = (ii, . .
. , id),where each index falls withinthe iteration rangeof its correspondingloop inthe nesting(thatis, 1P < iP < u ). Theoutermostloop correspondsto t L e leftmost index.We wish to discoverwhat loop-carrieddependenceexist between the two references to a, and to describe somehow thosedependencethat exist. Clearly,a reference in iterationJ can dependonly onanotherreferencein iteration1 that wasexecutedbefore it, not after it.
We formalize the notion of “before”with the <relation:I<Jiff3p:(iP<jPAvq<p:iq=jq).ACMComputmg~p:Surveys,fP(I)=gP(J).Vol. 26, No, 4, Decemberfp(~) = fp(w.For example,suppose that we are attemptingto describethe behaviorof theloop in Figure5(a).
Each iterationof theinner loop writes the elementa[i, j]. Thereis a dependenceif any otheriterationreads or writesthatsame element.Inthis case, there are many pairs of iterationsthatdependon each other.Consider iterations1 = (1,3) and J = (2, 2).Iteration1 occurs first,and writesthevalue a[l, 3]. This value is read in iterationJ, so thereis a flow dependencefrom iteration1 to iterationJ.
Extending the notationfor dependence,wewrite I + J.WhenX - Y, we definethe depenasY–X=(yl–dencedistancexl, ..., y~ – x~). In Figure5(a), the dependence distanceJ – I = (1,– 1).WhenallNotethatthisdefinitionmustbe extendedslightlywhen the loop incrementmay be negative.A referencein some iterationJ depends on a referencein iteration1 if andonly if at least one referenceis a writeandI + JAIn otherwords,thereis a dependencewhen the values of the subscriptsare thesame in differentiterations.If no such 1and J exist, the two referencesare independentacross all iterationsof the loop.In the case of an outputdependencecaused by the same writein differentiterations,the conditionis simplyVp:1994thedependencedistancesfora spe-cific pair of referencesare the same, thepotentiallyunboundedsetof dependencecan be representedby the dependence distance.When a dependencedistance is used to describe the dependencefor all iterations,it is called a distancevector(introducedby Kuck[1978]andMuraoka[1971]).A legal distancevector V must be leximeaningthatO <cographicallypositive,Compilerdoi=2,ndo j= 1,n-1j]= a[i,a[i,j]+ a[i-l,j+l]end doend dondo j= 2,The+ a[j-11+ a[j+il)/3end do(b) {(0,1),(1,0),(1,-1)}Figure 5.Distancevectors.V (the first nonzeroelementof the distance vector must be positive).A negative element in the distance vector meansthat the dependencein the correspondingloop is on a higher-numberediteration.Ifthe first nonzeroelementwas negative,this wouldindicatea dependenceon afutureiteration,which is impossible.The readershouldnote that distancevectors describe dependenceamong iterations,not amongarrayelements.Theoperationson array elementscreate thedependence,but the distance vectors describe dependenceamong iterations.Forinstance,the loop nest that updatestheone-dimensionalarraya in Figure5(b)has dependencedescribedby the set oftwo-elementdistance vectors {(O, 1), (1, O),(1, - l)}.In some cases it is not possibleto determinethe exact dependencedistanceatcompile-time,or the dependencedistancemay vary between iterations;but there isenoughinformationto partiallycharacterize the dependence.A directionvector(introducedby Wolfe[1989b])is commonlyusedto describesuchdependence.For a dependenceI * J, we define thedirectionvector W = (w ~, ..., w~) where<Iif iP < jp‘P=357We will use the generaltermdependence vector to encompassboth distanceand directionvectors.In Figure5 thedirectionvectorfor loop (a) is ( <, >),and the directionvectors for loop (b) aren-1a[jl=(a[jlend do“{(=,<),(<,=),(<,>)}.
Notethatadirection vector entry of < correspondstoa distancevectorentrythatis greaterthan zero.(a) {(1, -l)}doi=l,Transformations.—if ip = jp>ifip>jP.dependencebehaviorofa loopisdescribedby the set of dependencevectors for each pair of possiblyconflictingreferences.These can be summarizedintoa single loop directionvector, at the expense of some loss of information(andpotentialfor optimization).The dependenceof the loop in Figure5(b) can besummarizedas ( < , *). The symbol#denotes both a < and > direction.and* denotes< , > and = .AparticulardependencebetweenstatementsS’l and S2 is denoted by writing the dependencevector above the ar(<)row, for exampleSI -+ S2.Burkeand Cytron[1986]presentaframeworkfor dependenceanalysisthatdefinesa hierarchyof dependencevectorsandallowsflowandantide~endences to be treatedsymmetrically:Anantidependenceis simplya flow dependencewithan impossibledependencevector (V + O).5.4SubscriptAnalysisIn discussingthe analysisof loop-carrieddependence,we omittedan importantdetail:how the compilerdecides whethertwo array referencesmightrefer to thesame elementin differentiterations.Inexamininga loop nest, first the compilertries to prove that differentiterationsareindependentby applyingvarioustests tothe subscriptexpressions.Thesetestsrely on the fact that the expressionsarealmost always linear.
When dependenceare found, the compilertries to describethem with a directionor distancevector.If the subscriptexpressionsare too complex to analyze,the compilerassumesthe statementsare fullydependentonone anothersuch that no change in execution order is permitted.ACMComputingSurveys,Vol26, No 4, December1994358●DavidF. Baconet al.There are a large varietyof tests, all ofwhichcan prove independencein somecases. It is infeasibleto solve the problemdirectly,even for linear subscriptexpressions,becausefindingdependenceisequivalentto the NP-completeproblemof findingintegersolutionsto systems oflinearDiophantineequations[Banerjeeet al.
1979]. Two generaland approximate tests are the GCD [Towle 1976] andBanerjee’sinequalities[Banerjee1988a].Additionally,there are a large numberof exact tests that exploitsome subscriptcharacteristicsto determinewhetheraparticulartype of dependenceexists. Oneof the less expensiveexact tests is theSingle-IndexTest [Banerjee1979; Wolfe1989b]. The Delta Test [Goff et al. 1991]is a more generalstrategythat examinessome combinationsof dimensions.Othertests that are more expensiveto evaluateconsiderthe multiplesubscriptdimensions simultaneously,such as the A-test[Li et al.