Adaptive Information Processing- An Effective Way to Improve .ppt

1、Adaptive Information Processing: An Effective Way to Improve Perceptron Predictors,Hongliang Gao Huiyang Zhou,University of Central Florida,2,Information system model,Source (program),Information:Br addressBr historyBr typeOther run time info.,Informationvector,Information processor,PredictorFSMsPer

2、ceptrons 2,Information system model by Chen et. al. ASPLOS-VII. Key observations Shortcomings: Fixed information vector while different workloads/branches need different information data. Perceptron weights Correlation Assemble information vector to maximize correlation,Our contribution Re-assemble

3、the information vector based on correlation (weights) Performed at a coarse grain, so it is not latency critical,University of Central Florida,3,Adaptive Information Processing,Profile-directed adaptation Correlation-directed adaptation,Perceptron Predictor,Fixed,GHR,LHR,PC,Information,University of

4、 Central Florida,4,Profile-directed adaptation, ,w0 table,wt table 1,wt table 2,wt table N,Prediction = sign(y),y,GHR,LHR table,weights,weights,weights,PC,Information,Information vector,4,Update Logic,University of Central Florida,5,Profile-directed adaptation,Workload Detector,type, ,INT,FP,MM,SERV

5、,Table 1,Table 2,Table N,G0:3 XOR G4:7,University of Central Florida,6,Workload Detector,Detection criteria SERV: a large number of static branchesFP: a small number of static branches,a high number of floating point operation, and a high number of instructions using XMM registersMM: a medium number

6、 of static branches, a medium number of floating point operation, and a medium number of instructions using XMM registersINT: default,Workload Detector,type,Source (program),Run time info:# of fp instsXMM accesses# of static br,University of Central Florida,7,Correlation-directed adaptation, , ,w0 t

7、able,wt table 1,wt table 2,wt table N,Prediction = sign(y),y,GHR,LHR table,weights,weights,weights,PC,Information,Information vector,type,4,type,4,Workload Detector,type,Update Logic,University of Central Florida,8,Correlation-directed adaptation, , ,GHR,LHR table,weights,weights,weights,PC,Informat

8、ion,Information vector,4,4,type,4,type,4,Information feeding logic,MUX2,4,4,MUX1,4,4,type (INT),Workload Detector,type,PC,LHR,Sum1,Sum2,SumN,Large Sum1 = strong correlation with PC bits Small SumN = weak correlation with certain GHR bits cN PC = more PC bits,Table 1,Table 2,Table N,PC,University of

9、Central Florida,9,Overall scheme,Loop branch predictor,PC,tag,loop count,taken count,confidence,LRU,PC,Bias branch predictor,GHR,LHR table,PC,MAC perceptron predictor,workload detector,runtime info.,initial (predict NT),always NT (predict NT),always Taken(predict T),Not biased (use other predictors)

10、,loop hit,loop prediction,loop hit,NT,Taken,loop prediction,prediction,prediction,University of Central Florida,10,Summary,Observations Different workloads/branches need different information. Perceptron weights Correlation Contributions Profile-directed adaptation Correlation-directed adaptation Re

11、ducing aliasing from bias and loop branches Result Significant improvement,Thank you and Questions?,University of Central Florida,12,References,1 I. K. Chen, J. T. Coffey, and T. N. Mudge, “Analysis of branch prediction via data compression”, Proc. of the 7th Int. Conf. on Arch. Support for Programm

12、ing Languages and Operating Systems (ASPLOS-VII), 1996. 2 D. Jimenez and C. Lin, “Dynamic branch prediction with perceptrons”, Proc. of the 7th Int. Symp. on High Perf. Comp. Arch (HPCA-7), 2001. 3 D. Jimenez and C. Lin, “Neural methods for dynamic branch prediction”, ACM Trans. on Computer Systems,

13、 2002. 4 S. MacFarling, “Combining branch predictors”, Technical Report, DEC, 1993. 5 A. Seznec, “Revisiting the perceptron predictor”, Technical Report, IRISA, 2004. 6 T.-Y. Yeh and Y. Patt, “Alternative implementations of two-level adaptive branch prediction”, Proc. of the 22nd Int. Symp. on Comp. Arch (ISCA-22), 1995.,University of Central Florida,13,Predictor configuration,