Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Branch Prediction using Branch Prediction using Advanced Neural Advanced Neural MethodsMethodsSunghoon KimSunghoon KimCS252 ProjectCS252 ProjectIntroductionIntroductionDynanmic Branch PredictionDynanmic Branch PredictionNo doubt about its importance in No doubt about its importance in Speculation performanceSpeculation performanceGiven history of branch behaviors, predict Given history of branch behaviors, predict branch behaviors at the next stepbranch behaviors at the next stepCommon solutions: gshare, bimode,hybrid…Common solutions: gshare, bimode,hybrid… Replace saturating counters with neural Replace saturating counters with neural methods?methods?Neural methodsNeural methodsCapable of classification (predicting Capable of classification (predicting into which set of classes a particular into which set of classes a particular instance will fall)instance will fall)Learns correlations between inputs Learns correlations between inputs and output, and generalized learning and output, and generalized learning to other inputsto other inputsPotential to solve problems of most Potential to solve problems of most two-levels predictors two-levels predictorsSimulation Models - GshareSimulation Models - Gshare20-bit Global history shift register20-bit Global history shift registerPer-address history table with 2-bit Per-address history table with 2-bit saturation countersaturation counterPHTBrachPC>>2GHT Predict Updatecounters2-bit saturation counterSimulation Models - Simulation Models - PerceptronPerceptron14-bit Global history shift register14-bit Global history shift registerPer-address history table with 8-bit weights Per-address history table with 8-bit weights and biasand biasIndexed by Gshare or BranchPC aloneIndexed by Gshare or BranchPC alonePHTBrachPC>>2GHT PredictTrainingweights & biasBrachPC>>2ORSimulation Models - Simulation Models - BackpropagationBackpropagation10-bit GHR10-bit GHRSigmoid transfer functionSigmoid transfer functionFloating point computationFloating point computationFloating point weights and biasesFloating point weights and biases20 neurons one hidden layer20 neurons one hidden layerPHTBrachPC>>2GHT PredictTrainingweights & biasBrachPC>>2ORSimulation Models Simulation Models – Radial Basis Networks– Radial Basis NetworksTransfer function for radial basis Transfer function for radial basis neuron exp(-nneuron exp(-n22))Distance function between an input Distance function between an input vector and a weight vectorvector and a weight vectorPHTBrachPC>>2GHT PredictTrainingweights & biasBrachPC>>2ORSimulation Models Simulation Models – Elman Networks– Elman NetworksFeedback from the hidden layer Feedback from the hidden layer outputs to the first layeroutputs to the first layerPHTBrachPC>>2GHT PredictTrainingweights & biasBrachPC>>2ORSimulation Models – Learning Simulation Models – Learning Vector Quantization NetworksVector Quantization NetworksDistance function as Radial but without biasesDistance function as Radial but without biasesCompetitive function gives one only to an winning Competitive function gives one only to an winning input (biggest value) and zeroe to the otherinput (biggest value) and zeroe to the otherPHTBrachPC>>2GHT PredictTrainingweights & biasBrachPC>>2ORSimulation EnvironmentSimulation EnvironmentSimpleScalar ToolSimpleScalar ToolSome of SPEC2000 benchmarksSome of SPEC2000 benchmarksExecute 100,000,000 instructions and Execute 100,000,000 instructions and dump conditional branch historiesdump conditional branch histories5000 branch instructions are used for 5000 branch instructions are used for training training Make all budgets for PHTs the sameMake all budgets for PHTs the sameFloating point is 4 byteFloating point is 4 byteResultsResultsHardware constraintsHardware constraintsPredictors must predict within a (few) Predictors must predict within a (few) cyclecycleGshare : easy to achieve Gshare : easy to achieve Perceptron : Integer adders, possible Perceptron : Integer adders, possible alternative, more accurate if more layersalternative, more accurate if more layersOther advanced neural net : Hard to Other advanced neural net : Hard to implement, Floating point functional implement, Floating point functional units,units,Future WorksFuture WorksReplace floating point weights and biases Replace floating point weights and biases with scaled integer ones?with scaled integer ones?Replace floating point function with Replace floating point function with approximately equivalent integer function, approximately equivalent integer function, using Taylor’s series?using Taylor’s series?Without budget consideration, what will be Without budget consideration, what will be the best performance of advanced neural the best performance of advanced neural network methods?network methods?Look at codes carefully if there are mistakesLook at codes carefully if there are mistakesConclusionsConclusionsThere is not much of benefit using There is not much of benefit using advanced neural networks on the same advanced neural networks on the same budget as Gshare, sometimes worsebudget as Gshare, sometimes worseElman Networks method is the bestElman Networks method is the bestHard to implement in hardware unless Hard to implement in hardware unless floating point computation are easy to floating point computation are easy to dodoNN can be alternative predictors if well NN can be alternative predictors if well
View Full Document