高精度低コストパーセプトロン分岐予測器と予測信頼性の高精度判定に関する研究 A High-accuracy Low-cost perceptron Branch Predictor and Accurate Confidence Estimation for Branch Prediction

博士論文

2010

This thesis describes a high-accuracy low-cost perceptron branch predictor anda method of improving accuracy of confidence estimation for branch prediction.The type of predictor concerned in this thesis is part of a processor and iswidely used as a means of predicting the branch direction of a conditional branchinstruction. Since instructions are executed speculatively following the branchdirections predicted by a branch predictor, such a predictor can improve theperformance and energy efficiency of a processor. Because prediction accuracyaffects the success rate of the speculative execution of the processor, there is aneed for more accurate branch predictors. Further, since the area a branch predictormay occupy in a processor is limited, there is a need for smaller and atthe same time more cost-efficient branch predictors. Hence, reducing the amountof energy consumed has become one of the major concerns in designing processorstoday. Because unused speculative execution cased by erroneous branchpredictions results in wasted energy, some means of preventing this problem isrequired.In this thesis, the accuracy of a perception branch predictor is improved byusing the execution path history of branch instructions effectively. The numberof weight tables needed for a branch prediction is also reduced to reduce thearea cost. Simulation results confirmed that the proposed predictor reduces theamount of erroneous predictions that conventional predictors make by 9.5% andreduces the amount of circuitry needed for prediction and learning by 25%.Furthermore, a new method of improving accuracy of confidence estimation forbranch prediction is proposed. This method, taking into account the differenceiiin prediction accuracy of taken and not-taken branches, includes two kinds ofconfidence thresholds depending on these branch directions. These thresholdsare updated dynamically so that during program execution the mis-predictionrates are sustained within a tolerance level. Simulation results revealed that theproposed method improves the predictive values of a negative test by up to 47%.Application of confidence estimation to the branch prediction reversal revealedthat the prediction accuracy is more significantly improved with the proposedmethod than without the method.These results provide evidence that proposed methods achieve high branchprediction accuracy, low cost and high confidence estimation accuracy.本研究では, パーセプトロン分岐予測器の分岐予測精度の向上と実装コスト削減，パーセプトロン分岐予測器を用いた予測の信頼性判定精度向上を行う方法を述べる．分岐予測器は，プロセッサにフェッチされた条件分岐命令の分岐方向を予測する回路であり，現在広く利用されている．分岐予測器の予測を元に条件分岐命令の後続パスを投機実行することで，プロセッサは処理性能や電力効率を向上させることができる．分岐予測器の予測精度はプロセッサの投機実行の成功率と密接な関係があり，より高い予測精度を示す分岐予測器が必要とされている．また，分岐予測器はプロセッサ内に実装されるため，実装面積の制約が大きい．分岐予測器には予測精度の向上とともに実装コストの削減も同時に求められている．さらに，近年の半導体技術の微細化によって，プロセッサの設計において消費電力の削減は重要な要素となっている．分岐予測失敗による不要な投機実行は電力を浪費するため，分岐予測精度の向上以外にも対策が求められている．本研究では，プロセッサが過去に実行した分岐命令の履歴を効率的に利用することにより，パーセプトロン分岐予測器の予測精度を向上させる手法を提案した．また，1 つの分岐命令の予測に使用する重みの数を減らすことにより，実装コストを削減した．提案手法は，プロセッサシミュレータを用いた分岐予測失敗率の評価から，従来法の分岐予測失敗の9.5% を平均で削減できることが分かった．また，ハードウェア量に関する考察から，予測と学習に要する演算回路を1/4 に削減できることが分かった．さらに，分岐方向による予測失敗率の差を利用した分岐予測の信頼性判定手法を提案した．提案手法は，分岐命令の予測失敗率が分岐方向により異なることを利用するために，分岐予測結果に応じて分岐成立の場合の閾値と分岐不成立の場合の閾値を使い分ける．これにより，同じ予測の確かさを持つ分岐予測に対し，分岐方向に応じて異なる判定をすることが可能となった．さらに，提案手法は判定閾値をアプリケーivションの実行中に動的に更新する．判定閾値は，プログラム実行中に計測する予測失敗率が予め設定した予測失敗率の許容範囲に収まるように更新される．プロセッサシミュレータを用いた評価から，提案手法を信頼性判定手法に適用することで，判定精度の一指標であるPredictive Value of a Negative Test が最大で47% 向上することを示した．さらに，本手法による信頼性判定結果を分岐予測反転に適用し，分岐予測精度が従来法より向上することを示した．以上のように，本研究により分岐予測精度の向上，実装コストの削減，予測信頼性の判定精度向上が達成され，その有用性が確かめられた．