欢迎来到天天文库
浏览记录
ID:34555282
大小:621.28 KB
页数:77页
时间:2019-03-07
《external memory algorithms with dynamically changing memory allocations long version》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、CS{1998{09ExternalMemoryAlgorithmswithDynamicallyChangingMemoryAllocations.RakeshBarveJereyS.VitterDepartmentofComputerScienceDukeUniversityDurham,NorthCarolina27708{0129June1998ExternalMemoryAlgorithmswithDynamicallyChangingMemoryAllocations.12RakeshBarveJereySco
2、ttVitterDept.ofComputerScienceDept.ofComputerScienceDukeUniversityDukeUniversityDurham,N.C.27708{0129Durham,N.C.27708{0129.May19981SupportwasprovidedinpartbyanIBMGraduateFellowship.2SupportwasprovidedinpartbytheNationalScienceFoundationundergrantCCR{9522047andbytheU
3、.S.ArmyResearchOceunderMURIgrantDAAH04{96{1{0013.AbstractWeconsidertheproblemofdevisingexternalmemoryalgorithmswhosememoryallocationscanchangedynamicallyandunpredictablyatrun-time.Theinvestigationofmemory-adaptive"algorithms,whicharedesignedtoadapttodynamicallycha
4、ngingmemoryallocations,canbeconsideredanaturalextensionoftheinvestigationoftraditional,non-adaptiveexternalmemoryalgorithms.Ourstudyismotivatedbyhighperformancedatabasesystemsandoperatingsystemsinwhichapplicationsareprioritizedandinternalmemoryisdynamicallyallocated
5、inaccordancewiththepriorities.Insuchsituations,externalmemoryapplicationsareexpectedtoperformaswellaspossibleforthecurrentmemoryallocation.Thecomputationmustbereorganizedtoadapttothesequenceofmemoryallocationsinanonlinemanner.Inthispaperwepresentasimpleandnaturaldyn
6、amicmemoryalloca-tionmodel.Wedenememory-adaptiveexternalmemoryalgorithmsandspecifywhatisneededforthemtobedynamicallyoptimal.Usingnoveltechniques,wedesignandanalyzedynamicallyoptimalmemory-adaptivealgorithmsfortheproblemsofsorting,permuting,FFT,permutationnet-works,
7、(standard)matrixmultiplicationandLUdecomposition.Wealsopresentadynamicallyoptimal(inanamortizedsense)memory-adaptiveversionofthebuertree,agenericexternalmemorydatastructureforalargenumberofbatcheddynamicapplications.Weshowthatapreviouslydevisedapproachtomemory-adap
8、tiveexternalmergesortisprovablynonop-timalbecauseoffundamentaldrawbacks.Thelowerboundprooftechniquesforsortingandmatrixmultiplicationarefu
此文档下载收益归作者所有