DISTRIBUTION STATEMENT First issue 35 copies. SUPP

TECHNICALREPORT94-8RandomizedOn-lineAlgorithmsforthePageReplicationProblemHisashiKoga(Univ.ofTokyo)April6,1994TDepartmentofInformationScienceFacultyofScience,UniversityofTokyo7{3{1Hongo,Bunkyo-KuTokyo,113JapanTECHNICALREPORT94-8TITLERandomizedOn-lineAlgorithmsforthePageReplicationProblemAUTHORSHisashiKoga(Univ.ofTokyo)KEYWORDSANDPHRASESCompetitiveanalysis,Distributedsharedmemory,Pagereplication,On-linealgo-rithmPotentialfunctionABSTRACTInadistributedsharedmemoryconsistingofmultipleprocessors,eachofwhichhasitsownlocalmemories,eachread-onlypageneedstobelocatedatappropriateprocessorsbyreplicationsoastomakethetotalcostlower.Thepurposeofthepagereplicationproblemistoimplementthislow-costlocating.Thispaperconsiderson-linealgorithmsforthisproblemintermsofcompetitiveness,theratioofthecostofon-linealgorithmstothatoftheo-lineoptimalalgorithms.Especiallyweapplyrandomizedtechniquesdevelopedforthepagemigrational-gorithmstothepagereplicationproblem.Asaresult,wendrandomizedalgo-rithmsfortreeswhichbreakthedeterministiclowerbound.Moreover,memorylesscoin-ippingalgorithmsareinvestigated.Weprovethatacoin-ippingalgorithmis2-competitivefortrees.Forcircles,wedevelopanewgeneralizedcoin-ippingalgorithmthatis4-competitive.Thisnewalgorithmforcircleshasthelowestcom-petitiveratioamongalreadyknownalgorithms.ANYOTHERIDENTIFYINGINFORMATIONOFTHISREPORTThepreliminaryversionofthispaperwaspresentedatISAAC’93inHongKong.DISTRIBUTIONSTATEMENTFirstissue35copies.SUPPLEMENTARYNOTESREPORTDATEApril6,1994TOTALNO.OFPAGES25WRITTENLANGUAGEEnglishNO.OFREFERENCES13DEPARTMENTOFINFORMATIONSCIENCEFacultyofScience,UniversityofTokyo7-3-1Hongo,Bunkyo-ku,Tokyo113,JapanRandomizedOn-lineAlgorithmsforthePageReplicationProblemHisashiKoga(Univ.ofTokyo)April6,19941IntroductionAcommondesignforasharedmemorymultiprocessorsystemisanetworkofprocessors,eachofwhichhasitsownlocalmemory.Insuchadesign,aprogrammingabstractionofasimpleglobalmemoryissupportedbyavirtualmemorysystemthatdistributesthephysicalpagesamongthelocalmemories.Inadistributedsharedmemorysystem,whenprocessorqwishestoaccessmemoryaddressaofpageb,rstqexamineswhetherthepageiscontainedinitslocalmemory.Ifso,thepageaccessisdonelocallywithnocost.Otherwise,qmustsearchtheprocessorpholdingthepagebandsendamemoryaccessrequesttop.Thentheprocessorprespondstotherequestandthevalueofthelocationaistransmittedbacktoq.Thisactionincursthecostproportionaltothedistancebetweenpandq.Noteeverytimeqaccessesthepage,thispositivecostisrequiredprovidedqdoesnothavethepage.Therefore,ifqrequiresthepageaccesstobsooften,themigration/replicationofafullpageofbmayresultinlowercost,becauseqcanaccessthepageat0cost,afterqhasthepage.Ontheotherhand,movingafullpageincursalargeamountofcommunicationcostproportionaltothepagesize.Inthispaper,wedealwithdistributedsharedmemorysystemswherebroadcast,invalidate,orsnoopingmechanismsarenotallowed.Insuchsystems,awritablepageisrestrictedtohaveonlyonecopytoavoidthedicultyofmaintainingconsistencyamongmultiplecopies.Therefore,forawritablepageitisimportanttoconsiderthepagemigrationproblem.Thepurposeofthisproblemistodeviseresidencystrategiesthatdecidewhichlocalmemoryshouldhavetheonlycopyofthewritablepageinordertoreducetheamountofcommunicationinprocessingasequenceofpage-accessrequests.Onthecontrary,foraread-onlypage,manycopiesmayexistatthesametime,becausetheconsistencycannotbebroken.Therefore,tondresidencystrategiesthatdecidewhichsubsetofthelocalmemoriesshouldcontainthecopyofthepageisessential.Thisproblemiscalledthepagereplicationproblem.Inthispaper,wefocusonon-linealgorithmsforthepagereplicationproblem.Analgorithmissaidtobeon-lineifitprocessesarequestbasedonlyonthatrequestandthepastrequests.Toevaluateon-linealgorithms,weusecompetitiveanalysisintroducedin[13].Roughlyspeaking,anon-linealgorithmAisc-competitiveifforanyrequestsequence,thecostofAtoprocessisnomorethanctimesthecostoftheo-lineoptimalalgorithm.1Thecompetitiveanalysisisinasenseapessimisticapproachbasedonevaluatingtheworst-case,andcanbeaectedbyafewbadexamples.However,byconsideringtheexpectedcostofrandomizedalgorithms,theinuenceofsuchbadexamplesinthecom-petitiveanalysisareweakened.Inthissense,randomizationgivesstrongpowertoon-linealgorithms.Infact,therearemanyon-lineproblemssuchthatrandomizedon-linealgo-rithmsbreakthedeterministiclowerboundofthecompetitiveratio.Thisphenomenonreectstheabovefact.Forthemigrationproblem,BlackandSleator[4]developed3-competitivedetermin-isticon-linealgorithmsforuniformnetworks(completegraphswitheachedgehavingalengthof1)andtreenetworkswitharbitraryedgelength.Theyalsoshowthatnodeterministicon-linealgorithmcannotbebetterthan3-competitiveevenwhenthegraphconsistsofasingleedge.However,Westbrookshowsthatrandomizationcanbeatthede-terministiclowerbound[14].Hegavea5+p174’2:28-competitiverandomizedalgorithmforuniformnetworkswhenthepagesizefactorislarge.Forgeneralgraphs,hedeviseda2.62-competitiverandomizedalgorithm.Inaddition,heprovedthatasimplecoin-ippingalgorithmis3-competitiveagainstanytopologiesofnetworks.SubsequenttoWestbrook’sresult,C