臺灣博碩士論文加值系統

在目前的嵌入式處理器中，也開始採用動態的分支預測器來解決管線式處理器架構執行分支指令時，可能造成的效能衰減。目前的動態分支預測器，大多依據分支指令在通用處理器上的執行行為而設計，這會使得動態分支預測器著重的分支行為，以適應各類型應用程式為考量。而嵌入式系統，擁有與通用處理器不同的特性，嵌入式的處理器，往往面對的是執行固定、少變化的特殊應用程式，例如：通訊或多媒體應用程式…等等，則其所產生的分支指令執行行為也可能與通用處理器上不同。因此，本篇論文藉由詳盡地模擬各式常用的動態分支預測器及實作數個低功耗分支預測器技術，以期了解多媒體應用程式在嵌入式處理器上執行時，分支預測器呈現之特性與適用性。

Modern embedded processors employ dynamic branch prediction to reduce performance penalty caused by branch instructions. Existing branch predictor designs are all based on the behavior of applications on a GPP (general purpose processor). However, for an embedded system, such as smart phone, multimedia applications are the main workload. Therefore, in this thesis, we performed detailed performance/power characterization of multimedia applications and implemented several famous power-aware prediction techniques. We believe that identifying important characteristics of different branch predictor design of multimedia applications is important for choosing an adequate branch predictor for embedded processors.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
3 Branch Predictor Studied . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 Branch Prediction Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.1.1 Bimodal Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.1.2 Global History Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
3.1.3 Local History Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9
3.1.4 Hybrid Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Branch Prediction Schemes with Low-Power Consideration . . . . . . . . . . . 11
3.2.1 Banking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Prediction Probe Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.3 Branch Predictor Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.4 Selective Predictor Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Simulation Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1 Design Space Exploration for Branch Prediction Schemes . . . . . . . . . . . . . 23
5.1.1 Bimodal Branch Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.2 Global History Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
5.1.3 Local History Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.1.4 Hybrid Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
5.1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
5.2 Evaluation of Low-Power Branch Prediction Schemes . . . . . . . . . . . . . . . . . .38
5.2.1 Banking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38
5.2.2 Prediction Probe Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
5.2.3 Branch Predictor Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2.4 Selective Predictor Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
Bibliography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

[1] Intel XScale Microarchitecture, 2000.
[2] J. Smith, “A Study of Branch Prediction Stragtegies,” 8th International Symposium
on Computer Architecture, 1981.
[3] B. Bishop, T. P. Kelliher, and M. J. Irwin, “A Detailed Analysis of MediaBench,”
IEEE Workshop on Signal Processing Systems, November 1999.
[4] Z. Hu, P. Juang, P. Diodato, S. Kaxiras, K. Skadron, M. Martonosi, and D. Clark,
“Managing Leakage for Transient Data: Decay and Quasi-Static Memory Cells,”
Proc. 2002 Int’l Symp. Low Power Electronics and Design, pp. 52–55, August 2002.
[5] Z. Hu, P. Juang, K. Skadron, D. Clark, and M. Martonosi, “Applying Decay Strate-
gies to Branch Predictors for Leakage Energy Savings,” Proc. 2002 Int’l Conf. Com-
puter Design, pp. 442–445, September 2002.
[6] T.-Y. Yeh and Y. Patt, “Two-Level Adaptive Training Branch Prediction,” Proc.
24th Ann. Int’l Symp. Microarchitecture, pp. 51–61, November 1991.
[7] S.-T. Pan, K.so, and J. Rahmeh, “Improving the Accuracy of Dynamic Branch
Prediction Using Branch Correlation,” Proc. Fifth Int’l Conf. Architectural Support
for Programming Languages and Operating Systems, pp. 79–84, October 1992.
[8] S. McFarling, “Combining Branch Predictors,” DEC WRL, Tech. Rep., June 1993.
[9] P. Chang, E. Hao, and Y. Patt, “Alternative Implementations of Hybrid Branch
Predictors,” Proc. 28th Ann. Int’l Symp. Microarchitecture, pp. 252–257, December
1995.
[10] D. Parikh, K. Skadron, Y. Zhang, M. Barcella, and M. Stan, “Power Issues Re-
lated to Branch Prediction,” Proc. Eighth Int’l Symp. High Performance Computer
Architecture, pp. 233–244, February 2002.
[11] A. Baniasadi and A. Moshovos, “Branch Predictor Prediction: A Power-Aware
Branch Predictor for High-Performance Processors,” Int’l. Conference on Computer
Design, September 2002.
[12] ——, “SEPAS: A Highly Accurate Energy-Effcient Branch Predictor,” Proceedings
of the 2004 International Symposium on Low Power Eelctronics and Design, pp.
38–43, August 2004.
[13] C. Su and A. M. Despain, “Cache Designs for Energy Efficiency,” Proc. of the 28th
Hawaii International Conference on System Science, January 1995.
[14] D. Parikh, K. Skadron, Y. Zhang, and M. Stan, “Power-Aware Branch Prediction:
Characterization and Design,” IEEE Trans. Computer, vol. 53, no. 2, pp. 168–186,
February 2004.
[15] M. M., P. G., S. M., S. C., Z. V., and Z. R., “Power-Aware Branch Prediction
Techniques: A Compiler-Hints Based Approach for VLIW Processors,” ACM Great
Lakes Symposium on VLSI 2004, pp. 440–443, April 2004.
[16] D. Chaver, L. Pinuel, M. Prieto, F. Tirado, and M. C. Huang, “Branch Prediction
On Demand: an Energy Effcient Solution,” Proceedings of the 2003 International
Symposium on Low Power Eelctronics and Design, August 2003.
[17] M. C. Huang, D. Chaver, L. Pinuel, M. Prieto, and F. Tirado, “Customizing the
Branch Predictor to Reduce Complexity and Energy Consumption,” IEEE Micro,
pp. 12–25, September 2003.
[18] P. P. and O. A., “Low-power Branch Target Buffer for Application-Specific Em-
bedded Processors,” Proceedings of the Euromicro Symposium on Digital Systems
Design, pp. 158–165, 2003.
[19] J. Smith, “A Study of Branch Prediction Strategies ,” Proceedings of Eighth Ann.
Int’l Symposium Computer Architecture, pp. 135–148, May 1981.
[20] Sim-Panalyzer, http://www.eecs.umich.edu/ panalyzer/.
[21] C. Lee, M. Potkonjak, and W. H. Mangione-Smith, “MediaBench: A Tool for Eval-
uating and Synthesizing Multimedia and Communications Systems,” Proc. 30th An-
nual International Symposium on Microarchitecture, pp. 330–335, December 1997.
[22] R. Gonzalez and M. Kamble, “Energy Dissipation in General Purpose Microproces-
sors,” IEEE J. Solid-State Circuits, vol. 31, no. 9, September 1996.
[23] B.-H. Zhuang, “Branch Behavior Characterization for Multimedia Applications,”
Master’s thesis, National Taiwan University, 2005.
[24] S.-Y. W. Chia-Lin Yang and Y.-J. Chen, “Branch Behavior Characterization for
Multimedia Applications,” LNCS, no. 4186, pp. 523–530, September 2006.