20-HPS, A New Microarchitecture- Introduction and Rationale.pdf

HPS,ANEWMICROARCHITECTURE:RATIONALEANDINTRODUCTIONYaleN.Patt,Wen-meiHwu,andMichaelShebanowComputerScienceDivisionUniversityofCalifornia,BerkeleyBerkeley,CA94720ABSTRACTHPS(HighPerformanceSubstrate)isanewmicroarchitecturetargetedforimplementingveryhighperformancecomputingengines.Ourmodelofexecutionisarestrictiononfinegranularitydataflow.Thispaperintroducesthemodel,providestherationaleforitsselection,anddescribesthedatapathandflowofinstructionsthroughthemicroengine.1.IntroductionAcomputersystemisamultilevelstructure,algorithmsatthetop,gatesandwiresatthebottom.Toachievehighperformance,onemustoptimizeatalllevelsofthisstructure.Atmostlevels,theconventionalwisdomsuggestsexploitingconcurrency.Severalproposalshavebeenputforwardastohowtodothis.Wealsoargueforexploitingconcurrency,focusinginparticularonthemicroarchitecturelevel.1.1.RestrictedDataFlow.WearecallingourengineHPS,whichstandsforHighPerformanceSubstrate,toreflectthenotionthatwhatweareproposingshouldbeusefulforimplementingverydissimilarISParchitectures.Ourmodelofthemicroengine(i.e.,arestrictiononclassicalfinegranularitydataflow)isnotunlikethatofDennis3,ArvindZl,andothers,butwithsomeveryimportantdifferences.Thesedifferenceswillbediscussedndetailinsection3.Forthemoment,itisimportanttounderstandthatunlikeclassicaldatafiowmachines,onlyasmallsubsetoftheentireprogramisintheHPSmicroengineatanyonetime.Wedefinethe“activewindow”asthesetofISPinstructionswhosecorrespondingdataflownodesarecurrentlypartofthedataflowgraphwhichisresidentinthemicroengine.AstheactivewindowmovesthroughPermissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarcnotmadeordistributedfordirectcommercialadvantage,theACMcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheAssociationforComputingMachinery.Tocopyotherwise,ortorepublish,requiresafeeand/orspecificpermission.thedynamicinstructionstream,HPSexecutestheentireprogram.1.2.PotentialLimitationsofOtherApproaches.Webelievethatanessentialingredientofhighperformancecomputingistheeffectiveutilizationofalotofconcurrency.Thusweseeapotentiallimitationinmicroenginesthatarelimitedtooneoperationpercycle.Similarly,weseeapotentiallimitationinamicroenginethatunderutilizesitsbandwidthtoeitherinstructionmemoryordatamemory.Finally,althoughweappreciatetheadvantagesofstaticscheduling,weseeapotentiallimitationinamicroenginethatpurportstoexecuteasubstantialnumberofoperationseachcycle,butmustrelyonanon-run-timeschedulerfordeterminingwhattodonext.1.3.Outlineofthispaper.Thispaperisorganizedinfoursections.Section2delineatesthefundamentalreasonswhichledustothisnewmicroarchitecture.Section3describesthebasicoperationofHPS.Section4offerssomeconcludingremarks,anddescribeswhereourresearchinHPSisheading.2.Rationale.2.1.TheThreeTierModel.Webelievethatirregularparallelisminaprogramexistsbothlocallyandglobally.Ourmechanismexploitsthelocalparallelism,butdisregardsglobalparallelism.Ourbeliefisthattheexecutionofanalgorithmshouldbehandledinthreetiers.Atthetop,whereglobalparallelismcanbebestidentified,theexecutionmodel-.shouldutilizelargegranularitydataflow.muchliketheproposaloftheCEDARproject41.Inthemiddle,wherefortyyearsofcollectedexperienceincomputerprocessingcanbeexploitedprobablywithoutharm,classicalsequentialcontrolflowshouldbethemodel.Atthebottom,wherewewanttoexploitlocalparallelism,finegranularitydataflowisrecommended.Ourthreetiermodelreflectsourconceptionthatthetoplevelshouldbealgorithmoriented,themiddlelevelsequentialcontrolflowISParchitectureoriented,andthebottomlevelmicroengineoriented.Q1985ACMO-89791-1725/85/0012/0103$00.752.2.LocalParallelism.Wefeelobligedtore-emphasizetheimportanceoflocalparallelismtoourchoicea4executionmodel.indeed,wechosethisrestrictedformofdataflowspecificallybecauseourstudieshaveshownthattheparallelismavailablefrom.themiddlecontrolflowtier(i.e.,thesequentialcontrolflowarchitecture)ishighlylocalized.Wearguethat,byrestrictingtheactiveinstructionwindow,wecanexploi,talmostalloftheinherentparallelismintheprogramwhileincurringverylittleofthesynchronizationcostswhichwouldbeneededtokeeptheentireprogramaroundasatotaldataflowgraph.2.3,Stalls,Bandwidth,andConcurrency.Webelievethatahighperformancecomputingengineshouldexhibitanumberofcharacteristics.First,allitacomponentsmustbekeptbusy.Theremustbefewstalls,bothintheflowofinformation(i.e.,thepathtomemory,loadingofregisters,etc.)andintheprocessingofinformation(i.e.,thefunctionalunits).Second,theremustbeahighdegreeofconcurrermyavailable,suchasmultiplepathstomemory,multipleprocessingelements,andsomeformofpipelining,forexample.Inourview,therestricteddataflowmodel,withitsout-of-orderexecutioncapability,bestenablestheabovetworequirements,asfollows:Thecenterofourmodelisthesetofnodetables,whereoperationsawaittheiroperands.Instructionmemoryfeedsthemicroengineataconstantratewithfewstalls.DatamemoryandI/Osupplyandextractdataatconstantrateswithfewstalls.Functionalunitsarekeptbusybynodesthatcanfire.Somewhereinthissystem,therehastobe“slack.”Theslackisinthenodeswaitinginthenodetables.Sincenodescanexecuteout-of-order,thereisnoblockingduetounavailabledata.Decodedinstructionsaddnodestothenodetablesandexecutednodesremovethem.Thenodetablestendtogrowinthepresenceofdatadependencies,andshrinkasthesedependenciesbecomefewer.Meanwhile,ourpreliminarymeasurementssupport,themultiplecomponentsofthemicroenginearekeptbusy.3.TheHPSModelofExecution.3.1.Overview.AnabstractviewofHPSisshowninfigure1.Instructionsarefetchedanddecodedfromadynamicinstructionstream,shownatthetopofthefigure.ThefigureimpliesthattheinstructionstreamistakenfromasequentialcontrolflowISParchitecture.WeneedtoemphasizethatthisisnotanecessarypartoftheHPSspecification.Indeed,weareinvestigatinghavingHPSdirectlyprocessmultinodewords(i.e.,thenodesofadirectedgraph)whichwouldbeproducedasthetargetcodeofa(forexample)Ccompiler.Whatisnecessaryisthat,foreachinstruction,theoutputofthedecoderwhichispresentedtotheMergerforhandlingbyHPSisadataflowgraph.AveryimportantpartofthespecificationofHPSisthenotionoftheactiveinstructionwindow.Unlikeclassicaldataflowmachines,itisnotthecasethatthedataflowgraphfortheentireprogramisinthemachineatonetime.WedefinetheactivewindowasthesetofISPinstructionswhosecorrespondingdataflownodesarecurrentlybeingworkedoninthedataflowmicroengine.Astheinstructionwindowmovesthroughthedynamicinstructionstream,HPSexecutestheentireinstructionstream.Parallelismwhichexistswithinthewindowisfullyexploitedbythemicroengine.Thisparallelismislimitedinscope；ergo,theterm“restricteddataflow.”TheMergertakesthedataflowgraphcorrespondingtoeachISPinstructionand,usingageneralizedTomasuloalgorithmtoresolveanyexistingdatadependencies,mergesitintotheentiredataflowgraphfortheactivewindow.Eachnodeofthedataflowgraphisshippedtooneofthenodetableswhereitremainsuntilitisreadytofire.Whenalloperandsforadataflownodeareready,thedataflownodefiresbvtransmittinethenodetotheappropriatefunctionalunit.Thefunctionalunit(anALU,memory,orI/Odevice)executesthenodeanddistributestheresult,ifany,tothoselocationswhereitisneededforsubsequentprocessing:thenodetables,theMerger(forresolvingsubsequentdependencies)andtheFetchControlUnit(forbringingnewinstructionsintotheactivewindow).Whenallthedataflownodesforaparticularinstructionhavebeenexecuted,theinstructionissaidtohaveexecuted.Aninstructionisretiredfromtheactivewindowwhenithasexecuted104andalltheinstructionsbeforeithaveretired.Allsideeffectstomemoryaretakencareofwhenaninstructionretiresfromtheactivewindow.Thisisessentialforthecorrecthandlingofpreciseinterruptsll.Theinstructionfetchinganddecodingunitsmaintainthedegreeofparallelisminthenodetablesbybringingnewinstructionsintotheactivewindow,whichresultsinnewdataflownodesbeingmergedintothedataflownodetables.3.2.InstructionFlowFigure2showstheglobaldatapathofHPS.InstructionsenterthedatapathasinputtotheMerger.Thisinputisintheformofadateflowgraph,oneperinstruction.Thedataflowgraphcanbetheresultofdecodinganinstructioninaclassicalsequentialinstructionstream,oritcanbetheoutputofanon-conventionalcompiler.Ineithercase,theMergerseesasetofdataflownodes(anddatadependencies),oneforeachoperationthatmustbeperformedintheexecutionofthatinstruction,operationsare,forexample,reads,writes,addresscomputationsandALUfunctions,Intheexampleoffigure3,thedataflowgraphcorrespondingtotheVAXinstructionADDW#lOOO,A,Bconsistsofthreenodes:amemoryread,memorywrite,andanALUoperation.Figure3alsoshowsthestructureofthethreenodesandthefivevaluebufferentriesrequiredfortheinstruction.TheMerger,usingtheRegisterAliasTabletoresolvedatadependenciesnotexplicitintheindividualinstruction,formsthesetofdataflownodeswhicharenecessarytoexecutetheinstruction,Nodesarethentransmittedtotheappropriatenodetables.Nodetables,asweshallsee,arecontentaddressiblememories,andthusshouldbekeptsmall.ThesizeofeachnodetableisafunctionofthesizeoftheactivewindowandthedecodingrateoftheVonNeumanninstructionstream.InourexperimentswiththeVAXarchitecture,forexample,anactivewindowof16instructions,coupledwithadecodingrateofeightnodespercycle,requiredatmosta35entrynodetable.Foreachnode,aslotisreservedintheglobalmulti-portvaluebufferforstoringtheresultoftheoperationofthatnode.Theindexofeachslotisdesignatedasatagforthecorrespondingnode,andiscarriedalongwiththenodeuntilitcompletesitsexecution.Valuebufferslotsareassignedinacircularqueue,thesizeofthebufferbeinglargeenoughtoguarranteeretirementofaninstructionbeforeitsvaluebufferslotisagainneeded.(InthecaseofoursimulatedimplementationoftheVAXarchitecture,anactivewindowof16instructions,havingapproximatelyfournodesperinstruction,meansthatavaluebufferof136entriesismorethanadequate.)Anoderemainsinitsnodetableuntilallofitsoperandsareavailable,atwhichpointitisreadytofire(i.e.,itisexecutable).Anodeisfiredbytransmittingitsoperator,tag,andsetofoperandstooneofthefunctionalunitaassociatedwiththatnodetable.Whenexecutioncompletes,theresultanditstagaredistributedtoeachpotiofthevaluebuffer.Inthecaseofaresultdestinedforageneralpurposeregister,thecorrespondingtagisalsotransmittedtotheRegisterAliasTabletoupdateinformationstoredthere.Thecorrespondingtagisalsotransmittedtothenodetablesforthepurposeofsettingthereadybitsinthosenodesawaitingthisresult.nodes.Thenumberofresultsthatcanbedistributedinasinglecycleisafunctionofthebusstructureandtheorganizationofthenodetables.Theintentisthatineachcycle,multiplenodeswillbeineachstageoftheprocess.#DO&3IIOOO,A,83.3.DataDependenciesandtheirResolution.ftclm3.Memoryreadandwritenodespresentadditionalcomplications.Althoughthesewillbediscussedingreaterdetailin71,afewobservationshereareinorder.FirstisthefactthatatthetimememoryaccessnodesareissuedbytheMerger(dependingofcourseontheaddressingstructureofthetargetarchitecture),theaddressofthememoryaccessmaybeunknown,andtheaddressesofothermemoryaccesseswhichcouldblockthenodebeingissuedmayalsobeunknown.AMemoryAliasTableandaReadStagingUnitareprovidedtohandletheseproblems,Secondisthefactthatwritescanoccuroutofordercoupledwithourrequirementthatexceptionhandlingmustallowthemachinestatetoberecovered“precisely.”AWriteBufferandanalgorithmforretiringinstructionsareprovidedforhandlingthisproblem.Onefinalobservationabouttheprocessingofnodesmustbemade.Thestagesthatanodegoesthrough(i.e.,merging,waitingforoperands,firing,executing,anddistributingitsresults)isindependentoftheothernodesinthenodetables.Thatis,forexample,thenumberofnodesfirableinagivencycleislimitedbytheabilitytodetectthatmultiplenodesarefirableandthenumberoffunctionaluniteavailableforconcurrentprocessingofFundamentaltothecorrect,fast,out-of-orderexecutionofoperationsinHPSisthehandlingofdatadependenciesand,aswewillsee,theabsenceofblockinginthosecaseswhereblockingisunnecessary.Sinceourlocallyconcurrentimplementationmodelhastoconformtothetargetarchitecture,thelocalconcurrencyexploitedmustnotcauseincorrectexecutionresults.3.3.1.Data,Anti,andOutputDependencies.Amicro-operationBdependsonanothermicro-operationAifBhastobeexecutedafterAinordertoproducethecorrectresult.Therearethreewaysinwhichamicro-operationcandependonanothermicro-operationthroughregisterusage:data,anti,andoutputdependencies.Adata(read-after-write)dependencyoccurswhenAisgoingtowritetotheregisterfromwhichBisgoingtoread.Inthiscase,AsuppliesinformationessentialtotheexecutionofB.Ananti(write-after-read)dependencyoccurswhenAisgoingtoreadfromtheregistertowhichBisgoingtowrite.Anoutput(write-after-write)dependencyoccurswhenAandBaregoingtowritetothesameregister.Inthelasttwocases,theexecutionofAdoesnotsupplyanyinformationnecessaryfortheexecutionofB.TheonlyreasonBdependsonAisthataregisterhasbeenallocatedtotwodifferenttemporaryvariablesduetoashortageofregisters.Infact,ifwehadanunlimitednumberofregisters,differenttemporaryvariableswouldneverhavetobeallocatedtothesameregisterandthesecondandthethirddependencieswouldneveroccur.So,aproperrenamingmechanismandextrabufferregisterswouldremoveantianddatadependencies.Then,theonlytypeofdependencythatcoulddelaymicreoperationexecutionwouldbeadatadependency.Inotherwords,amicro-operationcouldbeexecutedassoonasitsinputoperandsareproperlygenerated.Thisisexactlythedescriptionofadatatlowexecutionmodel.3.3.2.OurModifiedTomasuloAlgorithm.OuralgorithmforenforcingdatadependenciesandremovingantiandoutputdependenciesissimilartotheTomasuloalgorithmwhichwasusedintheFloatingPointUnitoftheIBM360191161.Duringexecution,thealgorithmmanagestwomajordatastructures:aregisteraliastableandasetofnodetables.Eachentryintheregisteraliastablekeepstrackofthedynamicinformationforaregisternecessaryeithertosupplyaninputoperandvalueortoestablishdependencyarcs.Therearetwofieldsineachregisteraliastableentry.Thefirstisareadybit.Thisbit,ifcleared,indicatesthatthereisanactivemicro-operationwhichisgoingtosupplytheregistervalue.Thesecondfieldisthetagfieldwhichprovidesanindexintoaresultbuffer.Thisindicateswheretheregistervaluecanbefoundifthereadybitisset.106Eachentryinanodetablecorrespondstoamicro-operationandhasanoperationfield,aresulttugfield,andtwooperandrecords.Theoperationfieldspecifiestheactionthatwillbeperformedontheinputoperands,Theresulttugfieldprovidesthelocationintheresultbufferthattheresultvaluewillbeshippedtoaftertheexecutionofthemicro-operation,Eachoperandrecordconsistsoftwofields.Thefirstisareadybit.Thisbitissetwhentheinputoperandhasbeenproperlyproduced.Thesecondfieldisthetagfieldwhichcontainsanindexintotheoperandbuffer.Thisindicateswheretheoperandcanbefoundifthereadybitisset.AdatapathdesignedforourmodifiedTomasuloalgorithmispresentedinfigure2.Therearetwophasesineachmachinecycle:merging/schedulinganddistribution,Initiallyallregisteraliastableentriesarereadyandtheinitialregistervaluesareinresultbufferentrieswhoseindexisinthetagfieldsofthecorrespondingregisteraliastableentries.Merging/SchedulingAnewmicro-operationisassignedanentryinanodetableandisgivenauniqueresulttag,First,thecontentsofbothfieldsintheregisteraliastableforeachinputoperandarecopiedtothecorrespondingfieldsintheoperandrecordsofthenewnodetableentry.Second,thereadybitoftheregistertobewrittenbythemicro-operationisresetandtheresulttagforthemicro-operationiswrittenintothetagfieldofthealiastableentry.Ifbothoperandsofanodearemarkedready,thisnodecanfire.Thetagsintheoperandrecordsareusedtoindexintotheresultbufferandobtaintheoperandvalues.Theoperationandtheoperandvaluesaresenttothefunctionunitforexecution.Theresulttag,whichwillbeusedtodistributetheresult,isalsosenttothefunctionunit.DistributionWhenafunctionunitfinishesexecutingamicro-operation,theresulttagofthatmicro-operationisusedtoselectaresultbufferentryandtheresultvalueisstoredintotheentry.Theresulttagisalsodistributedtotheregisteraliastableandthenodetable.Boththeregisteraliastableandthenodetablearecontentaddressablememories.Entriesinthesetablesareaddressedbythevalueoftheresulttag.Alloftheregisteraliastableentriesandalloftheoperandrecordsinthenodetableentriessettheirreadybitifthedistributedresulttugmatchestheirtagfieldcontents.Afterexecution,alltheregisteraliastableentriesarereadyandthecorrespondingregistervaluesareintheresultbufferentrieswhoseindicesareinthetagfields.Thealgorithmdescribedaboveisawinonatleasttwocounts.First,itremovesantiandoutputdependencieswithoutproducingincorrectresults.Infact,itcanheshownthatreservationschemeswithoutrenamingcannotremoveantiandoutputdependencieswithoutproducingincorrectresults.Second,unlikeScoreboarding(forexample),theissuingprocessneverhastostallduetodependencies.Itcanalsobeshownthatanyreservationschemewithoutrenamingwillhavetostallforsomedependencies.4.ConcludingRemarks.ThepurposeofthispaperhasbeentointroducetheHPSmicroarchitecture.CurrentresearchatBerkeleyistakingHPSalongfourtracks.First,weareattemptingtodesign,athighperformance,threeverydissimilararchitectures:themicroVAX,aCmachine,andaPrologprocessor.Equallyimportant,weareinvestigatingthelimitsofthismicroarchitecture,bothfromthestandpointofaminimalimplementationandfromthestandpointofacadilIacversion.Asistobeexpected,thereareissuestoberesolvedbeforeaneffectiveHPSimplementationcanbe,achieved.Forexample,ifHPSistoimplementasequentialcontrolbasedISParchitecture,thentherearedecodingissues,includingthequestionofanodecache,whichneedtobedecided.Second,HPSrequiresadatapaththat(1)hashighbandwidthand(2)allowstheprocessingofveryirregularparalleldata.Third,HPSneedsaschedulerwhichcandetermine,inreal-time,whichnodesarefirableandwhicharenot.Fourth,the-out-of-orderexecutionofnodesrequiresadditionalattentiontothedesignofthememorysystem,theinstructionretirementandrepairmechanisms,andtheI/Osystem.Theseissuesarethesubjectofacompanionpaper171intheseProceedings.Acknowledgement.TheauthorswishtoacknowledgefirsttheDigitalEquipmentCorporationforsupportingverygenerouslyourresearchinanumberofpositiveways:LindaWright,formerlyHeadofDigit