臺灣博碩士論文加值系統

本論文針對現代擁有管線式(Pipeline)的微處理器所進行的研究，特別是在改善管線式處理器所遇到的控制危障進行分析。並模擬在目前市面上最熱門的SoC (System on a Chip)產業所量身訂作的微處理器ARM (Advanced Reduced Instruction Set Computer Machine)，其也應用在內嵌式系統(Embedded System)。藉由分支預測器來改善管線式微處理器所遭遇的分支危障以企圖提升微處理器之效能。
現代化的管線式微處理器皆會受到分支(Branch)指令的影響，導致微處理器的效能下降。而本計畫便是研究與模擬並分析當前的分支預測法來提出一些較有效可改善微處理器效能的預測法，防止當微處理器遇到分支指令時所造成的危障，進而使微處理器效能有所提升，也希望能有效應用在內嵌式系統的微處理器上，特別是ARM。並利用模擬軟體Simplescalar與Mibench的基準程式來找出一個分支預測器相較於現在複雜的分支預測器可達到面積較小，而在預測準確率上可比一般傳統的預測器高些，以更符合ARM需求。

The thesis focuses on design and analysis of a branch predictor for a microprocessor which has a deep pipeline architecture. When pipeline is getting deeper, accurate branch prediction is critical to achieve high performance since fetched instruction after a branch have to be flushed inside pipeline when prediction is wrong. The thesis simulates the performance of several types of branch predictors on Advanced Reduced Instruction Set Computer Machine, which is known as ARM. ARM which is applied hot SoC (System on a Chip) and embedded system products, is a good performance microprocessor.
Modern processors with a pipeline architecture are affected by the branch instructions and result in decreasing their performance. The thesis will study some branch prediction, which will avoid microprocessor’s control hazard when catch the branch instruction. We hope the branch prediction applied embedded system, such as ARM. By using Simplescalar with Mibench benchmark programs, the branch predictor will achieve lower area than complex branch predictor and higher branch prediction rate than general branch predictor.

中文摘要.....................................................................................................i
英文摘要....................................................................................................ii
誌謝...........................................................................................................iii
目錄...........................................................................................................iv
圖目錄......................................................................................................vii
表目錄.......................................................................................................xi
第一章 緒論..............................................................................................1
1.1 前言....................................................................................................1
1.2 研究背景............................................................................................2
1.2.1 管線式處理器效能評估..................................................................2
1.2.2 分支指令造成的控制危障..............................................................3
1.2.3 流程控制指令的分類......................................................................5
1.2.4 分支危障的避免方式......................................................................5
1.2.4.1 管線暫停(Pipeline stall) ..............................................................6
1.2.4.2 延遲分支(delayed branch) ..........................................................6
1.2.4.3 分支預測法(branch prediction) ...................................................7
1.2.4.4 分支目的地緩衝區(branch-target buffer) ...................................9
1.2.4.5 分支摺疊(branch folding) .........................................................11
1.2.4.6 返回位址預測(return address prediction) .................................12
1.3 論文組織..........................................................................................13
第二章 ARM微處理器簡介...................................................................14
第三章 分支預測技術簡介....................................................................24
3.1 靜態分支預測器...............................................................................24
3.2 動態分支預測器...............................................................................25
3.3 分支預測器的干擾(interference)問題.............................................44
第四章 gb-share分支預測器之設計......................................................48
4.1 設計規範...........................................................................................48
4.2 架構...................................................................................................49
4.3 加強型...............................................................................................52
第五章 軟體模擬與硬體實作................................................................54
5.1 軟體模擬...........................................................................................54
5.1.1 模擬之軟體....................................................................................54
5.1.2 模擬之benchmarks........................................................................55
5.2 硬體實作...........................................................................................56
5.2.1 硬體架構........................................................................................56
5.2.2 Branch Predictor架構設計.............................................................57
第六章 結果與討論................................................................................62
6.1 模擬結果.......................................................................................62
6.1.1 實驗(1) ..........................................................................................63
6.1.2 實驗(2) ..........................................................................................64
6.1.3 實驗(3) ..........................................................................................69
6.2 硬體比較...........................................................................................74
6.3 問題與討論.......................................................................................76
第七章 結論與後續研究........................................................................80
7.1 結論…...............................................................................................80
7.2 後續研究...........................................................................................81
參考文獻..................................................................................................83

[1]溫宏仁、李隆財， ”SoC系統晶片：ARM軟硬體原理” ，全華科技圖書
[2]Steve Furber， “ARM System-on-Chip Architecture” ，Addison Wesley
[3]ARM, http://www.arm.com
[4]David A. Patterson & John L. Hennessy， “Computer Organization & Design The Hardware / Software Interface” ， Morgan Kaufmann
[5]M. Evers and T.-Y. Yeh “Understanding Branches and Designing Branch Predictors for High-Performance Microprocessors”, Proceedings of the IEEE Vol. 89, No. 11, November 2001
[6]S. McFarling. “Combining branch predictors.” Technical Report TN-36, Digital Western Research Laboratory, June 1993.
[7]T.-Y. Yeh and Y.N. Patt. “Two-Level adaptive branch prediction.” In Proceedings of the 24th Annual ACM/IEEE international Symposium on Microarchitecture, pages 51-61, 1991.
[8]T.-Y. Yeh and Y.N. Patt. “Alternative implementations of two-level adaptive branch prediction.” In Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 124-134, 1992.
[9] J.L. Hennessy and D.A. Patterson, “Computer Architecture, A Quantitative Approach”, Morgan Kaufmann Publish, New York, N.Y., 1993
[10]J. E. Smith, “A study of branch prediction strategies”, in 8th Int. Symp. Computer Architecture, 1981.
[11] Ditzel, D. & McLellan, H. (1987) Branch folding in the CRISP microprocessor: reducing branch delay to zero. In: The 14th Annual Int. Symp. on Computer Architecture; Conf. Proc., 2-5 June 1987, Pittsburgh, pp. 2-9
[12] Ditzel, D., McLellan, H., & Berenbaum, A. (1987a) The hardware architecture of the CRISP microprocessor. In: The 14th Annual Int. Symp. on Computer Architecture; Conf. Proc., 2-5 June 1987, Pittsburgh, pp. 309-319
[13] D. Kaeli and P. Emma, "Branch history table prediction of moving target branches due to subroutine returns," in Proc. 18th ISCA, and Comput. Architecture News, vol. 19, no. 3, pp. 34-41 May 1991
[14]E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt, “The agree predictor: A mechanism for reducing negative branch history interference”, in Proc. 24th Annu. Int. Symp. Computer Architecture, 1997.
[15]Y.-J. Kang and J.-W. Cho, “Improving accuracy of self history-based branch predictors using BHT cache“, Electronics Letters, Vol. 36, No. 15, 20th July 2000.
[16]P-Y. Chang, M. Evers, and Y.N. Patt, “Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference”, International Conference on Parallel Architectures and Compilation Techniques, (October 1996).
[17]P. Michaud, A. Seznec, and R. Uhlig, “Trading conflict and capacity aliasing in conditional branch predictors”, in 24th Annu. Int. Symp. Computer Architecture, 1997.
[18]S. Pasricha, A. Veidenbaum “Improving Branch Preidction Accuracy in Embedded Processors in the Presence of Context Switches”, Proceedings of the 21st International Conference on Computer Design.
[19]C.-C. Lee, I.-C. K. Chen, and T. N. Mudge, “The bi-mode branch predictor,” in 30th ACM/IEEE Int. Symp. Microarchitecture, 1997.
[20]M.-C. Chang and Y.-W. Chou “Branch Prediction using both global and local branch history information”, IEE Proc.-Comput. Digit. Tech., Vol. 149. No. 2, March 2002
[21] Tieling Xie, R. Evans, Y. Chu, “A study for branch predictors to alleviate the aliasing problem”, SoutheastCon, 2005. Proceedings. IEEE,8-10 April 2005 Page(s):603 – 608 Digital Object Identifier 10.1109/SECON.2005.
[22] SimpleScalar LLC, http://www.simplescalar.com
[23] SimpleScalar Version 4.0 Test Releases, http://www.simplescalar.com/v4test.html
[24]D. Burger and T. M. Austin “The SimpleScalar Tool Set, Version 2.0”, Technical Report #1342, Computer Sciences Department, University of Wisconsim-Madison, June 1997.
[25]M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, R. B. Brown “MiBench: A free, commercially representative embedded benchmark suit“, IEEE 4th Annual Workshop on Workload Characterization, pages 83-94, 2001.
[26]MiBench Version 1.0 , http://www.eecs.umich.edu/mibench
[27]EDN Embedded Microprocessor Benchmark Consortium, http://www.eebbc.org
[28]OPENCORES, http://opencores.org
[29] J. C. H. Park and M. Schlansker “On Predicated Execution” Technical Report HPL-91-58, HP Labs, May 1991.