资源描述：
《Graph Traverse Software Pipelining》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、GraphTraverseSoftwarePipeliningCristinaBarrado,EduardAyguadéandJesúsLabartaComputerArchitectureDepartment,UPC,Barcelona,SpainAcknowledgmentsThisworkhasbeensupportedbytheSpanishMinistryofEducationundercontractCICYT-TIC429/95andbytheCEPBA(EuropeanCenterforParallelismofBarcelona).0Graph
2、TraverseSoftwarePipeliningAbstractSoftwarepipeliningisbecomingwidelyusedasaloopexecutionmodelformicroprocessorssupportingahighinstructionlevelparallelism.Inthispaperwedescribeaheuristicmethodforsoftwarepipelining,namedGraphTraverseSoftwarePipelining(GTSP),thatdividestheschedulingprob
3、lemintwophases:schedulingonagraphandcodegeneration.ThefirstphaseencapsulatestheNP-completepartoftheproblem.Theschedulingisrepresentedonthedatadependencegraph(DDG)throughasetofschedulingrecurrencescomposedofschedulingedges,representingapartialorderingbetweenstatementsintheeachrecurren
4、ce.Aheuristicisgiventoincludesuchedgesinordertogenerateefficientschedules.Itimprovesprevioussoftwarepipeliningtechniquesachievingthemaximumthroughputfor98%ofabenchmarksetcomposedofmorethan500innermostloopsfromtheSpecFP95.Thesecondphaseisafastandautomaticalgorithmthattransformsthesche
5、dulinggeneratedontheDDGintoVLIW-likeinstructions.AmongtheadvantagesofGTSPweremarktheabstractiononthegraphthatbenefitsfromthelargedevelopedgraphtheory,theglobalknowledgeoftheheuristicduringtheschedulingphase,andthepossibilityofreachingmaximumthroughputscheduleswithoutunrollingtheDDG.1
6、.IntroductionCurrenttechnologytrendsareencouragingsystemdesignerstoofferhigh-levelsofpotentialparallelismwithinasinglechip.SuperscalarandVeryLongInstructionWordprocessors(VLIW)[Gwen95,Gwen94,Gwen96,...],basedonthereplicationofprocessorresources,issueseveralinstructionspercyclefromasi
7、nglethreadofexecution;thisparallelismisusallyreferredasinstruction-levelparallelism(ILP).Multiprocessorsonachip[ONHW96,...],basedonthereplicationofprocessors,offeracoarserthread-levelparallelism,whereeachprocessorhasitsownresourcesandbasicallysharesthehigherlevelsofthememoryhierarchy
8、.Inallcases,
