BTB索引散列算法的研究与设计.pdf

《BTB索引散列算法的研究与设计.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机研究与发展DOI：10．7544／issnl000—1239．2014．20130132JournalofComputerResearchandDevelopment51(9)：2003—2011，2O14BTB索引散列算法的研究与设计王国澎胡向东尹飞朱英(国家高性能集成电路设计中心上海201204)(wgp06@mail．uste．edu．cn)ResearchandDesignofHashIndexingMechanismforBTBWangGuopeng，HuXiangdong，YinFei，andZhuYing(NationalHigh

2、PerforraanceICDesignCenter，Shanghai201204)AbstractItiSwellknownthatbranchmisDredictionshavebecomeaseriousbottlenecktoachievebetterprocessorperformance．Branch—targetbuffer(BTB)，whichcachesthemostrecentresolvedtarget，istheimportantdedicatedstructuretoprovidebranchtargetaddressinm

3、odernprocessors．However，becauseofinheritingfromcache，theperformanceofBTBisrestrictedbyitshitratio．Duetothenonuniformdistributionofbranchinstructions．theconventionalindexingmethodalwayscausesmanyunnecessaryconflicts，havingnegativeeffectsonBTBperformance．Suchmispredictionscausedb

4、yconflictscarlbeeasilyavoidedbymeansofaproperlychosenHashfunction．AlthoughHashfunctionshavebeenwellstudiedtoimprovetheutilizationofmemorysystem，theHash—indexingmethod，whichisspecificallyindicatedforBTB，isnotexploredinliterature．Inthispaper，basedonanalysisofregularpatternofbranc

5、hdistributionandcontrolflowinprogram，theHashindexingmechanismforBTBisresearchedandtwoHash—indexingmethodsforBTBaredesignedinthispaper．OneisXOR—basedHashfunction，theotheriSoptimizedbit—selectmethod．TheevaluationframeworkiSestimatedforsetindexfunctionSOthatthebest-performingtrans

6、formationmatrixcanbefastdetected．Themaximalnumberofbranches。whicharemappedtothesameBTBsetunderHash—indexingmechanism，isevaluatedbyprobabilitytheory．TheexperimentalresultsshowthatourHash—indexingmethodsareefficienttominimizeBTBmis—predicitonscausedbyconflictmiss：theXOR—basedHash

7、functionperformsevenbetter．Keywordsbranchtargetbuffer(BTB)；Hashindex；XOR—Hashfunction；branchtargetprediction；branchprediction摘要分支误预测是影响高性能处理器性能进一步提升的一个主要因素．现代处理器采用分支目标缓存(branchtargetbuffer，BTB)预测分支指令的目标地址，BTB的预测精度受限于其命中率．由于程序中分支指令的分布并不均匀，传统的BTB索引方式无法充分利用BTB资源，从而造成不必要的冲突缺失，影响分支目

8、标地址的预测精度，采用散列索引方式优化访问映射关系是有效解决方法之一．当前大量文献研究了cache的访问方式