Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » 1994. Compiler Transformations for High-Perforamce Computing

1994. Compiler Transformations for High-Perforamce Computing, страница 4

PDF-файл 1994. Compiler Transformations for High-Perforamce Computing, страница 4 Конструирование компиляторов (53101): Статья - 7 семестр1994. Compiler Transformations for High-Perforamce Computing: Конструирование компиляторов - PDF, страница 4 (53101) - СтудИзба2019-09-18СтудИзба

Описание файла

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.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5075
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее