symbolic array dataflow analysis

《symbolic array dataflow analysis》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ToappearinProceedingsofSupercomputing'95SymbolicArrayData owAnalysis1forArrayPrivatizationandProgramParallelizationyJunjieGuZhiyuanLiGyunghoLeeDepartmentofComputerScienceyDepartmentofElectricalEngineeringUniversityofMinnesota200UnionStreetS.E.Minneapolis,MN55455fg

2、u,lig@cs.umn.edu,ghlee@ee.umn.eduAbstractArraydata owinformationplaysanimportantroleforsuccessfulautomaticparallelizationofFortranprograms.Thispaperproposesapowerfulsymbolicarraydata owanalysistosupportarrayprivatizationandloopparallelizationforprogramswitharbitra

3、rycontrol owgraphsandacycliccallgraphs.OurschemesummarizesarrayaccessinformationusingguardedarrayregionsandpropagatessuchregionsoveraHierarchicalSupergraph(HSG).TheuseofguardsallowsustousetheinformationinIFconditionstosharpenthearraydata owanalysisandtherebytohand

4、ledicultcaseswhicheludeotherexistingtechniques.Theguardedarrayregionsretainthesimplicityofsetoperationsforregulararrayregionsincommoncases,andtheyenhanceregulararrayregionsincomplicatedcasesbyusingguardstohandlecomplexsymbolicexpressionsandarrayshapes.Scalarvalue

5、sthatappearinarraysubscriptsandlooplimitsaresubstitutedonthe yduringthearrayinformationpropagation,whichdisambiguatesthesymbolicvaluespreciselyforsetoperations.Wepresentecientalgorithmsthatimplementourscheme.InitialexperimentsofapplyingouranalysistoPerfectBenchma

6、rksshowpromisingresultsofimprovedarrayprivatization.1IntroductionRecentexperimentsshowthatthereexistssignicantperformancedierencebetweenautomaticallyandmanuallyparallelizedcodes[7,8].Oneimportantfactorcausingsuchadiscrepancyisrelatedtoarrayvariables.Quiteoften,a

7、rrayelementswritteninoneiterationofaDOloopareusedinthesameiterationbeforebeingoverwritteninthenextiteration.Thiskindofarraysusuallyservesasatemporaryworkingspacewithinaniterationandthearrayvaluesindierentiterationsareunrelated.Usingthesamearrayforalliterationscau

8、sesunnecessaryloop-carriedoutputandanti-dependences[20,2]whichpreventDOloopsfrombeingparallelized.Arrayprivatizationisatechniquethatcreatesadistinctcopy