先進的計算基盤システムシンポジウム SACSIS 2011 Symposium on Advanced Computing Systems and Infrastructures SACSIS /5/25 Combining Bimode Bimode-Plus Agree Hybr

Size: px

Start display at page:

Download "先進的計算基盤システムシンポジウム SACSIS 2011 Symposium on Advanced Computing Systems and Infrastructures SACSIS /5/25 Combining Bimode Bimode-Plus Agree Hybr"

ぜんすけくぬぎ
4 years ago
Views:

1 Combining Bimode Bimode-Plus Agree Hybrid 5 SPECint2000 9% A Branch Predictor Using Miss-prediction Bias Lin Meng and Shigeru Oyanagi Modern processors exploit instruction level parallelism by deeper pipeline and wider instruction issue width, which result in an increase of branch miss penalty. Hence, more accurate branch prediction is indispensable for higher performance. This article proposes a novel branch prediction mechanism by using branch miss prediction bias. This mechanism is attached to a conventional branch predictor, and utilizes local history of biased branch instructions. Experiments are done by attaching proposed mechanism to Combine, Bimode, Bimode-Plus, Agree and Hybrid predictors. The result shows that our proposal can reduce 9% of miss prediction rate to the conventional predictors at SPECint Graduate School of Science and Engineering, Ritsumeikan University College of Information Science and Engineering, Ritsumeikan University Bimodal 1) 2 PHT(Pattern History Table) Gshare 2) PHT PHT Gshare PHT 92 c 2011 Information Processing Society of Japan

2 PHT Bimodal Gshare Combining 2) Combining Bimodal Gshare 2 Selector Gshare Bimodal 9) Bimodal Gshare Bimode 3) Taken NotTaken PHT Bimode Taken Gshare NotTaken Gshare Gshare ChoicePHT Bimode-Plus 6) Taken NotTaken Bimode-Plus Bimode-Plus Bimode Taken flag NotTaken flag Bias Table Bimode Bimode Agree 5) Agree BTB BTB XOR Hybrid 4) Hybrid 2bc Gshare pshare GAS AVG BTB PPM-Like L-TAGE 7),8) 10) PPM-like L-TAGE PPM(prediction by partial matching) (GBHR) PHT PHT PHT GBHR 3. SimpleScalar Tool Set 14) Combining Bimode SPECint2000 bzip gcc gzip mcf parser twolf vpr vortex 8 1 SimpleScalar PISA c 2011 Information Processing Society of Japan

3 20M M 8KB 16KB 32KB 3 Combining 2) Gshare Bimodal Combining Bimodal Selector 8K 16K 32K Gshare 16K 32K 64K Bimode Gshare 8K 16K 32K ChoicePHT 16K 32K 64K Combining Bimode 8 70% 16 80% Championship Branch Predicton 11) L-TAGE 11) 10M 8 50% 90% L-TAGE Pipeline Fetch Decode Dispatch 1 Table 1 Processor configuration 5 stages: 1 Fetch 1 Decode 1 Execute 1 Memory Access, 1 Commit 4 instructions Issue Int: 4 fp: 2 mem: 2 Window BTB Memory Dispatch queue:256, Issue queue:256 2K-entry 4-way associative BTB 32-entry RAS 64KB, 4-way associative, 1-cycle instruction and date caches 2MB, 8-way associative, 10-cycle L2 1 Combining Fig. 1 Miss prediction bias rate in Combining predictor 2 Bimode Fig. 2 Miss prediction bias rate in Bimode predictor MBP(Miss Bias Predictor) LHBP(Local History Branch Predictor) MBP LHBP MBP BTB EBTB: Extended BTB MBB(Miss 94 c 2011 Information Processing Society of Japan

4 Fig. 3 3 Block diagram of proposed branch predictor Bias Buffer) LHBP Selector LHBP 4.1 MBP EBTB BTB MCT(Miss Counter) Base Predictor EBTB BTB (Tag) (T addr:target address) MBB Addr LH U FR Addr LH U 1 0 FR(Failure Rate) LHBP 8 16 MBB 8 16 MBP MBB : EBTB EBTB EBTB MCT EBTB BTB Tag MCT MCT 0 EBTB MCT MBB EBTB MCT MBB MBB MBB MBB U 0 U MBB U 1 LRU(Least Recently Used) LRU LHBP MBB MBB : MBB MBB LH FR LHBP LHBP FR LHBP FR LHBP LHBP MBB 4.2 LHBP LHBP 95 c 2011 Information Processing Society of Japan

5 LPHT LPHT MBB MBB LPHT1 LHPT LPHT n 2 n LPHT NTCT CF Miss Resetting Counter 12),13) 3 Miss Resetting Counter PVN Predictive Value of a Negative Test 12) LPHT MBB MBB MBB LPHT NTCT CF CF MBB MBB MBB LH LPHT NTCT CF LHBP Selector LHBP NTCT Taken NotTaken CF LHBP MCT MBB (LPHT ) LPHT (LH ) SimpleScalar Tool Set 14) 4 MCT Fig. 4 Miss bias rate to MCT size. 5 Fig. 5 MCT Miss reduction rate to MCT size. 1 SPECint2000 bzip gcc gzip mcf parser twolf vpr vortex 8 CommBench[12] drr reed dec reed enc rtr zip enc 5 SimpleScalar PISA MCT EBTB MCT MCT EBTB MCT MBB 16KB Bimode MCT 4bit 8bit MBB 8 LPHT MCT (SPECint2000 CommBench ) 5 MCT (SPECint2000 CommBench ) 4 MCT SPECint % CommBench 75% 5 MCT SPECint % 96 c 2011 Information Processing Society of Japan

6 6 MBB LPHT (Combining) Fig. 6 Miss prediction reduction rate to MBB and LPHT size (Combining) 8 MBB LPHT (Bimode- Plus) Fig. 8 Miss prediction reduction rate to MBB and LPHT size (Bimode-Plus) 7 MBB LPHT (Bimode) Fig. 7 Miss prediction reduction rate to MBB and LPHT size (Bimode) CommBench 8% 70% MCT MCT MBB LPHT MBB LPHT MBB LPHT LPHT (MBB LH) MBB LPHT MBB LPHT (8,512) (8,1024) (16,512) (16,1024) 6 8 Combining Bimode Bimode-Plus MBB LPHT (8KB 16KB 32KB 64KB) SPECint2000 CommBench 6 8 MBB 16 LPHT 1024 MBB 8 LPHT 512 SPECint MBB LPHT Combining SPECint2000 (MBB=16 LPHT=1024) (MBB=8 LPHT=512) 2% CommBench 1% Bimode Bimode-Plus MBB LPHT MBB 8 LPHT Combining Bimode Bimode-Plus Agree Hybrid 5 97 c 2011 Information Processing Society of Japan

7 9 Combining Fig. 9 Miss prediction reduction rate to Combining 10 Bimode Fig. 10 Miss prediction reduction rate to Bimode 11 Bimode-Plus Fig. 11 Miss prediction reduction rate to Bimode-Plus Combining, Bimode, Bimode-Plus, Agree (8KB 16KB 32KB 64KB) Hybrid 10.5KB 17.75KB 30KB 60.5KB 9 11 Combining Bimode Bimode- Plus 9 11 Combining Bimode Bimode- Plus SPECint % 10% CommBench 30% 6% Agree SPECint % 10% CommBench 30% 6% Hybrid SPECint % 7% CommBench 20% 3% L-TAGE 11) L-TAGE 10M 3% 5.3 EBTB MCT EBTB 1KB MBB 8 Addr 32 bit LH 9 bit U 1 bit FR 7 bit 49 bit 392 CAM LPHT NTCT 2 bit CF 2 bit 4 bit 2KB 2 MPKI(missprediction per kilo instruction) MPKI 2 8KB Combining 3KB 64KB Combining Bimode, Bimode-Plus 98 c 2011 Information Processing Society of Japan

8 2 MPKI ( ) Table 2 Result of MPKI (Average) Predictor Specint2000 CommBench 8KB 16KB 32KB 64KB 8KB 16KB 32KB 64KB Combining Combining Bimode Bimode Bimode-Plus Bimode-Plus Combining Bimode Bimode-Plus Agree Hybrid SimpleScalar Tool Set SPECint2000 9% CommBench IPC 1) J.E.Smith A Study of Branch Prediction Strategies ISCA 1981 pp ) S.McFarling Combining Branch Predictors Technical report TN-36 Digital Western Research Laboratory ) Chih-Chieh Lee I-Cheng K. Chen Trevor N. Mudge The bi-mode branch predictor MI- CRO97 pp.4-13 Dec ) M.Evers, P-Y.Chang, Y.N.Patt, Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the Presence of Context Switches, ISCA 1996, pp.3-11, May ) Eric Sprangle, Robert S. Chappell, Mitch Alsup, Yale N. Patt. The Agree Predictor: A Mechanism for Reducing Negative Branch History, ISCA 1997, pp , June ) Bimode-Plus ACS 10 PP ) A. Seznec The L-TAGE branch predictor JILP vol. 9 May ) M. pierre A PPM-Like, tag-based predictor JILP April ) L.Porter D.M.Tullsen Greating Artificial Global History to Improve Branch Prediction Accuracy ICS 09 PP ) I.-C.K. Chen J.T.Coffey T.N.Mudge Analysis of branch prediction via data compression ASPLOS-VII pp Oct ) JILP:The 2nd JILP Championship Branch Predicton Competition 12) H. Akkary S. T. Srinivasan R. Koltur Y. Patil W. Refaai Perceptron-Based Branch Confidence Estimation HPCA-10 pp.265 Feb ) SACSIS2009 pp May ) D.Burger T.M.Austin The SimpleScalar Tool Set Version2.0 Technical Report University of Wisconsin-Madison Computer Sciences Dept July ) T.Wolf M.A.Franklin CommBench - a Telecommunications Benchmark for Network Processors ISPASS-2000 Austin TX pp April (??? ) (??? ) 99 c 2011 Information Processing Society of Japan

FabHetero FabHetero FabHetero FabCache FabCache SPEC2000INT IPC FabCache 0.076%

2013 (409812) FabHetero FabHetero FabHetero FabCache FabCache SPEC2000INT 6 1000 IPC FabCache 0.076% Abstract Single-ISA heterogeneous multi-core processors are increasing importance in the processor architecture.