资源描述：
《towards an optimal bit-reversal permutation program》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、TowardsanOptimalBit-ReversalPermutationProgramLarryCarterandKangSuGatlincarter,kgatlin@cs.ucsd.eduDepartmentofComputerScienceandEngineering,UCSD9500GilmanDrive,LaJolla,CA,92093-0114AbstractThus,forinstance,r(01101)=10110,andr(ab)=r(b)r(a).Thespeedofmanycomputationsisli
2、mitednotbytheArrayswillbeindexedbybinarystrings.Thepseudo-numberofarithmeticoperationsbutbythetimeittakestocodestatementªfori=0toN-1ºmeansthatiit-moveandrearrangedataintheincreasinglycomplicatederatesthroughallbinarystringsoflengthlg(N),wherelgmemoryhierarchiesofmodern
3、computers.Arraytrans-representslogbasetwo.poseandthebit-reversalpermutation±trivialoperationsConsiderthefollowingthreeprograms,whereNisaonaRAM±presentnon-trivialproblemswhendesigningpowerof2,N=N1N2,andAandBarearraysoflengthhighly-tunedscienti®clibraryfunctions,particul
4、arfortheN:FastFourierTransform.WeproveapreciseboundforRo-Col,asimplepebble-typegamethatisrelevanttoimple-Copy(A,B):mentingthesepermutations.WeuseRoColtogivelowerfori=0toN-1boundsontheamountofmemorytraf®cinacomputerwithB[i]=A[i]four-levelsofmemory(registers,cache,TLB,an
5、dmemory),takingintoaccountsuchªmessyºfeaturesasblockmovesTranspose(A,B):andset-associativecaches.Theinsightsfromthisanalysisfori=0toN1-1leadtoabit-reversalalgorithmwhoseperformanceiscloseforj=0toN2-1tothetheoreticalminimum.ExperimentsshowitperformsB[j,i]=A[i,j]signi®ca
6、ntlybetterthaneveryprograminacomprehensivestudyof30publishedalgorithms.BitReverse(A,B):fori=0toN-1B[r(i)]=A[i]1.BackgroundandrelatedworkIntheRandomAccessMachine(RAM)modelofcom-putation[AHU74],allthreeprogramshavethesamecom-Givenbinarystringsaandb,letabdenotetheirplexit
7、y,(N).IfweonlycountthecostofLoadsandStoresconcatenationandr(a)denotethereversalofa.ofarrayelements(i.e.,weassumethatalladdressingandCopyright1998IEEE.PublishedintheProceedingsofloopingcomputationsarefree)theneachofthesepermuta-FOCS'98,8-11November1998inPaloAlto,CA.Per-
8、tionshascomplexityexactly2N.sonaluseofthismaterialispermitted.However,per-Yetinpractice,inthemindsofpeoplewhowritehig
