Главная » Просмотр файлов » 1994. Compiler Transformations for High-Perforamce Computing

1994. Compiler Transformations for High-Perforamce Computing (798436)

Файл №798436 1994. Compiler Transformations for High-Perforamce Computing (1994. Compiler Transformations for High-Perforamce Computing)1994. Compiler Transformations for High-Perforamce Computing (798436)2019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

CompilerTransformationsDAVID F. BACON,ComputerSUSANSc~ence Diviszon,In thelastprogramsthreehaveanalysisof scalarmemoryMostsurveywithProgrammerswishinga referencefor techniquesoptimizingcompilercomputertheof eachandProgramming;Subjectthebasedon theoptimizationformaximizeon trackingof theandvariouspurposetheparallelismpropertiesofimportanttypesof eachwritersoptimizationsdevelopedoptimization.Readersand basicprogramDescriptors:D.1.3programof parallelarchitecturestraneformation,explainarehowtoof its application.manually.Compilerhigh-levelsuch as C and Fortran.the performanceto be applied1.2.2 [Artificialrelylanguagesan exampleD.3.4 [Programmingoptimization;In contrast,processorsof theirof the optimizationtechnology.architectureCategoriessequentialunderstandingof the importantfor the detailsoverviewto enhancetheirparallelreducetransformationsanalysis.and giveto improvefor optimizingfor uniprocessorsusingthat94720transformationstechniques.andtransformationsWe describeif it is legal,of compilerprogramfor imperativefor bothin depth.Californiaoptimizationdata-flowvector,is a comprehensiveTransformationsmostanddependencetechniquesdetermineby thesuperscalar,looprestructuringcoverednumberlocalityusingThisa largequantitieshigh-performanceBerkeley,implemented.executedComputingAND OLIVER J.

SHARPof California,decadesbeenof instructionsarraysL. GRAHAM,Unwersbtynumberandfor High-PerformancethatStudentsto date,compilationsurveyor asan overviewofas a referenceforand as a bibliographicto be familiarreferencewithmoderntechniques.[ProgrammingLanguages]:surveycan perform,can obtaincan use thisare expectedIntelligence]:code can use thiscompilersTechniques]:ConcurrentProcessors—compilers;AutomaticProgramming-programtransformationGeneralAdditionalTerms:Languages,Key Wordsmultiprocessors,Performanceand Phrases:optimization,Compilation,parallelism,INTRODUCTIONOptimizingcompilershave become an essential componentof modern high-performance computersystems.In additiontotranslatingthe inputprograminto machine language,they analyzeit and apply varioustransformationsto reduce itsrunningtime or its size.This researchunder contracthas been sponsoredDABT63-92-C-O026,dependencesuperscalaranalysis,processors,locality,vectorizationAs optimizingcompilersbecome moreeffective,programmerscan become lessconcernedabout the details of the underlying machinearchitectureand can employhigher-level,moresuccinct,andmore intuitiveprogrammingconstructsand programorganizations.Simultaneously,hardwaredesignersare able toin part by the Defense AdvancedResearchProjectsAgencyby NSF grant CDA-8722788,and by an IBM ResidentStudy(DARPA)ProgramFellowship to David Bacon,Permissionto copy withoutfee all or part of this materialis grantedprovidedthat the copies are not madeor distributedfor direct commercialadvantage,the ACM copyrightnotice and the title of the publicationand its date appear,and notice is given that copyingis by permissionof the Associationfor ComputingMachinery.To copy otherwise,or to republish,requiresa fee and]orspecific permission.@ 019940360-0300/94/1200-0345$03.50ACMComputingSurveys,Vol.26,No.4, December1994346*DavidF.

Baconet al.CONTENTSINTRODUCTION1.SOURCE2TRANSFORMATIONLANGUAGEISSUES2 1 Correctness223ScopeTARGETARCHITECTURES31Characterizing32Model4COMPILER5DEPENDENCE6.7.PerformanceArchitecturesORGANIZATIONANALYSIS51Typesof Dependences52Representing5,3Loop5.4SubscriptDependencesDependenceAnalysisAnalysisTRANSFORMATIONS61Data-Flow-Based6.2LoopReorderingLoop6.3LoopRestructuring6.4LoopReplacement6.5Memory6.6Partial6.7Redundancy68ProcedureTransformationsTransformationsAccessTransformationsEvaluationEhmmatlonCallTransformationsTRANSFORMATIONSFORPARALLELMACHINES89.71Data72ExposingLayout73Computation74Communication75SIMD76VLIWTransformatlonsCoarse-GrainedParallelismPartltIOnmgOptimizationTransformationsTRANSFORMATION8.1Unified8.2SearchingFRAMEWORKSTransformationtheCOMPILERTransformationSpaceEVALUATION9.1Benchmarks9.2Code9.3Compiler94Instruction-LevelCharacterlstlcsEffectivenessParallehsmCONCLUSIONAPPENDIX:A.1A 2 VectorA3MACHINESuperscalarMODELSDLXDLXMultiprocessorsACKNOWLEDGMENTSREFERENCESemploydesignsthatyieldgreatlyimprovedperformancebecausethey needonly concernthemselveswiththe suitabilityof the designasa compilertarget,not withits suitabilityas a directprogrammerinterface.In this survey we describe transformations that optimizeprogramswritteninACMComputingSurveys,Vol.26,No.4, December1994imperativelanguagessuch as FortranandC for high-performancearchitecincludingsuperscalar,vector,tures,and variousclassesof multiprocessormachines.Mostof the transformationswe describe can be appliedto anyoftheAlgolfamilylanguages;many are applicabletofunctional,logic, distributed,and objectorientedlanguagesas well.

These otherlanguagesraise additionaloptimizationissuesthatspace does not permitusto cover in this survey.The referencesincludesome startingpoints for investigationof optimizationsfor LISPandfunctionallanguages[Appel1992; ClarkandPeyton-Jones1985;Kranzet al.1986], object-orientedlanguages[Chambers and Ungar1989], and the set-basedlanguageSETL[Freudenbergeret al.1983].We have also restrictedthe discussionto higher-leveltransformationsthat requiresome programanalysis.Thus weexclude peepholeoptimizationsand mostmachine-leveloptimizations.We use theterm optimizationas shorthandfor optimizingtransformation.Finally,because of the richnessof thetopic, we have not given a detaileddescriptionof intermediateprogramrepresentationsand analysistechniques.We make use of a numberof differentmachinemodels, all based on a hypothetical superscalarprocessorcalled S-DLX.The Appendixdetailsthe machinemodels, presentinga simplifiedarchitectureand instructionset that we use when weneed to discuss machinecode.

Whileallassemblylanguageexamplesare commented,the reader will need to refer tothe Armendixto understandsome detailsof the’ ~xamples(such as cycle counts).We assumea basic familiaritywith~ro~amcompilationissues. Readers un~am~liarwithprogramflow analysisorother basic compilationtechniquesmayconsult Aho et al. [1986].1. SOURCEAll ofsurveyLANGUAGEthe high-levelexamplesare writtenin a languagein thissimilarCompilerto Fortran90, with minor variationsandextensions;most examplesuse only features found in Fortran77. We have chosen to use Fortranbecause it is the defacto standardof the high-performanceengineeringandscientificcomputingcommunity.Fortranhas also been theinput languagefor a numberof researchprojects studyingparallelization[Allen etal.

1988a;Balasundaramet al. 1989;Polychronopouloset al. 1989]. It was chosen by these projectsnot only because ofits ubiquityamong the user community,but also because its lack of pointersandits staticmemorymodelmake it moreamenableto analysis.It is not yet clearwhateffectthe recentintroductionofpointersintoFortran90 willhave onoptimization.The optimizationswe have presentedare not specific to Fortran—infact, manycommercialcompilersuse the same intermediatelanguageand optimizerforboth C and Fortran.The presence of unrestrictedpointersin C can reduce opportunitiesfor optimizationbecauseit isimpossibleto determinewhich variablesmay be referencedby a pointer.The process of determiningwhich referencesmaypointto the same storagelocationsiscalled alias analysis[Banning1979; Choiet al.

1993; Cooper and Kennedy1989;Landi et al. 1993].The only changesto Fortranin ourexamplesare that arraysubscriptingisdenotedby squarebracketsto distinguish it from functioncalls; and we usedo all loops to indicatetextuallythat allthe iterationsof a loop may be executedconcurrently.To make the structureofthe computationmore explicit,we willgenerallyexpressloopsas iterationsrather than in Fortran90 array notation.We follow the Fortranconventionthatarraysare stored contiguouslyin memory in column-majorform.

If the array istraversedso as to visit consecutivelocations in the linear memory,the first (thatis, leftmost)subscriptvaries the fastest.In traversingthe two-dimensionalarraydeclaredas a[n, m], the followingarraylocationsarecontiguous:a[n – 1, 3],a[n, 31, a[l, 41, a[2, 41.Transformations347“Programmersunfamiliarwith Fortranshouldalso note that all argumentsarepassed by reference.When describingcompilationfor vectormachines,we sometimesuse array notation when the mappingto hardwareregisters is clear. For instance,the loopdoalli=l,64a[i] = a[i] + cend do allcould be implementedwith a scalar-vector add instruction,assuminga machinewith vector registersof length64.

Thiswouldbe writtenin Fortran90 arraynotationasa[l :64] = a[l :64] + cor in vectorasmachineassemblylanguageLFADDILVF2, c(R30);Ioad c into register F2R8, R30, #a ;Ioad addr. of a into R8;Ioad vector a[l :64] toVI, R8ADDSVVI,SvVI.V1F2, VIR8;add scalar to vector;store vector in a[l :64]Arraynotationwill not be used whenloop bounds are unknown,because thereis no longeran obviouscorrespondencebetweenthe source code and the fixedlength vector operationsthat performthecomputation.To use vectoroperations,the compilermust performthe transformationcalled strip-mining,which is discussed in Section 6.2.4.2. TRANSFORMATIONISSUESFor a compilerto apply an optimizationto a program,it must do three things:(1)Decide upon a part of the programtooptimizeand a particulartransformationto apply to it.(2) Verifythat the transformationeitherdoes not change the meaningof theprogramor changes it in a restrictedway that is acceptableto the user.(3)TransformIn thislast step:ACMComputmgthe program.surveywe concentrateon thetransformationof the program.Surveys,Vol.26,No4, December1994348●DavidF.

Характеристики

Тип файла
PDF-файл
Размер
6,02 Mb
Тип материала
Высшее учебное заведение

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов статьи

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