Shared memory consistency models A tutorial

SEPTEMBER1995WRLResearchReport95/7SharedMemoryConsistencyModels:ATutorialSaritaV.AdveKouroshGharachorloodigitalWesternResearchLaboratory250UniversityAvenuePaloAlto,California94301USATheWesternResearchLaboratory(WRL)isacomputersystemsresearchgroupthatwasfoundedbyDigitalEquipmentCorporationin1982.Ourfocusiscomputerscienceresearchrelevanttothedesignandapplicationofhighperformancescientificcomputers.Wetestourideasbydesigning,building,andusingrealsystems.Thesystemswebuildareresearchprototypes;theyarenotintendedtobecomeproducts.TherearetwootherresearchlaboratorieslocatedinPaloAlto,theNetworkSystemsLab(NSL)andtheSystemsResearchCenter(SRC).AnotherDigitalresearchgroupislocatedinCambridge,Massachusetts(CRL).Ourresearchisdirectedtowardsmainstreamhigh-performancecomputersystems.OurprototypesareintendedtoforeshadowthefuturecomputingenvironmentsusedbymanyDigitalcustomers.Thelong-termgoalofWRListoaidandacceleratethedevelopmentofhigh-performanceuni-andmulti-processors.TheresearchprojectswithinWRLwilladdressvariousaspectsofhigh-performancecomputing.Webelievethatsignificantadvancesincomputersystemsdonotcomefromanysingletechnologicaladvance.Technologies,bothhardwareandsoftware,donotalladvanceatthesamepace.Systemdesignistheartofcomposingsystemswhichuseeachleveloftechnologyinanappropriatebalance.Amajoradvanceinoverallsystemperformancewillrequirereexaminationofallaspectsofthesystem.Wedoworkinthedesign,fabricationandpackagingofhardware;languageprocessingandscalingissuesinsystemsoftwaredesign;andtheexplorationofnewapplicationsareasthatareopeningupwiththeadventofhigherperformancesystems.ResearchersatWRLcooperatecloselyandmovefreelyamongthevariouslevelsofsystemdesign.Thisallowsustoexploreawiderangeoftradeoffstomeetsystemgoals.Wepublishtheresultsofourworkinavarietyofjournals,conferences,researchreports,andtechnicalnotes.Thisdocumentisaresearchreport.Researchreportsarenormallyaccountsofcompletedresearchandmayincludematerialfromearliertechnicalnotes.Weusetechnicalnotesforrapiddistributionoftechnicalmaterial;usuallythisrepresentsresearchinprogress.Researchreportsandtechnicalnotesmaybeorderedfromus.Youmaymailyourorderto:TechnicalReportDistributionDECWesternResearchLaboratory,WRL-2250UniversityAvenuePaloAlto,California94301USAReportsandtechnicalnotesmayalsobeorderedbyelectronicmail.Useoneofthefol-lowingaddresses:DigitalE-net:JOVE::WRL-TECHREPORTSInternet:[e-mail]:decpa!wrl-techreportsToobtainmoredetailsonorderingbyelectronicmail,sendamessagetooneoftheseaddresseswiththeword‘‘help’’intheSubjectline;youwillreceivedetailedinstruc-tions.ReportsandtechnicalnotesmayalsobeaccessedviatheWorldWideWeb::ATutorial*SaritaV.Adve*KouroshGharachorlooSeptember1995AlsopublisedasRiceUniversityECETechnicalReport9512.*SaritaV.AdveiswiththeDepartmentofElectricalandComputerEngineering,RiceUniversity,Houston,Texas77251-1892.MostofthisworkwasperformedwhileSaritaAdvewasattheUniversityofWisconsin-MadisonandKouroshGharachorloowasatStanfordUniversity.AtWisconsin,SaritaAdvewaspartlysupportedbyanIBMgraduatefellowship.SheiscurrentlysupportedbytheNationalScienceFoundationunderGrantNo.CCR-9502500andCCR-9410457,bytheTexasAdvancedTechnologyProgramunderGrantNo.003604016,andbyfundsfromRiceUniversity.AtStanford,KouroshGharachorloowassupportedbyDARPAcontractN00039-91-C-0138andpartlysupportedbyafellowshipfromTexasInstruments.ThisworkhasbeensubmittedtotheIEEEforpossiblepublication.Copyrightmaybetransferredwithoutnotice,afterwhichthisversionwillbesuperseded.digitalWesternResearchLaboratory250UniversityAvenuePaloAlto,California94301USAAbstractParallelsystemsthatsupportthesharedmemoryabstractionarebecomingwidelyacceptedinmanyareasofcomputing.Writingcorrectandefficientprogramsforsuchsystemsrequiresaformalspecificationofmemorysemantics,calledamemoryconsistencymodel.Themostintuitivemodel---sequentialconsistency---greatlyrestrictstheuseofmanyperformanceoptimizationscom-monlyusedbyuniprocessorhardwareandcompilerdesigners,therebyreducingthebenefitofusingamultiprocessor.Toalleviatethisproblem,manycurrentmultiprocessorssupportmorerelaxedconsistencymodels.Unfortunately,themodelssupportedbyvarioussystemsdifferfromeachotherinsubtleyetimpor-tantways.Furthermore,preciselydefiningthesemanticsofeachmodeloftenleadstocomplexspecificationsthataredifficulttounderstandfortypicalusersandbuildersofcomputersystems.Thepurposeofthistutorialpaperistodescribeissuesrelatedtomemorycon-sistencymodelsinawaythatwouldbeunderstandabletomostcomputerprofes-sionals.Wefocusonconsistencymodelsproposedforhardware-basedshared-memorysystems.Manyofthesemodelsareoriginallyspecifiedwithanemphasisonthesystemoptimizationstheyallow.Weretainthesystem-centricemphasis,butuseuniformandsimpleterminologytodescribethedifferentmodels.Wealsobrieflydiscussanalternateprogrammer-centricviewthatdescribesthemodelsintermsofprogrambehaviorratherthanspecificsystemoptimizations.i1IntroductionThesharedmemoryorsingleaddressspaceabstractionprovidess