臺灣博碩士論文加值系統

為提昇處理器(Processor)的執行效能( Performance)，各種理論與架構不斷的被研究與討論。而自管線式(Pipelining)架構處理器的觀念被提出以來，管線式的架構已成為高速處理器的主流。理論上，管線式架構利用指令重疊的方式可以使單一處理器得到很好的效能。但是實際上在程式執行的時候，因為分支指令( Branch Instructions)需暫停(Stall)及清除(Flush)管線以得到正確的執行結果，會使得處理器的整體效能降低。
分支預測(Branch Prediction)是目前普遍用來減少分支指令所造成分支損失(Branch Penalty)的方法，這個方法是在編譯時期或是執行時期收集分支指令的資料，以便在程式執行時期用來做預測，以提高管線式架構的效能。而分支目的緩衝器(Branch Target Buffer)則是被廣泛的使用於各式的處理器，可見於目前各種商用的處理器之中。這是利用一個小的緩衝器來儲存之前程式執行的狀況，並用來預測下一步可能的執行方向。
未來的CPU發展趨勢是將管線加長以提高效能。但是當分支預測錯誤時，在管線中需被捨棄的指令數目也隨之增加，也就是會損失更多的週期時間(Cycle Time)，這樣的結果可能導致增長管線的好處反而被抵銷了。因此，分支預測的準確性將扮演更重要的角色。
本篇論文主要在提出一個機制來減少分支損失和預測錯誤時的效能損失，利用雙階層組織─DBB和一些提高命中率的技巧，來增進處理器的效能。

Pipelining is the major organizational technique by which computers can execute several instructions simultaneously to reach higher single-processor performance. Branches are recognized as a major impediment to achieve the maximum performance of pipelining and superscalar processors due to stalls caused by unresolved branches. Branch prediction is an effective strategy to reduce the branch penalty via predicting, prefetching and executing the speculative instructions before the branch is resolved. A branch target buffer (BTB)[13] can reduce the performance caused by branches via predicting the direction of the branch and caching information about the branch. While prediction is incorrect, the processor requires flushing the speculative instructions, undoing the effects of the improperly initiated speculative execution and resuming on the correct path. These flushing and refilling degrade significantly processor performance.
In this thesis we propose a mechanism, Double Level Branch Buffer, which can reduce the branch penalty and performance loss caused from incorrect prediction. We try to cache the information of branch about both taken and not taken direction. The pipeline will degrade the dependence upon branch prediction accuracy by utilizing this mechanism.

目錄
第一章 導論
第二章 先前之研究
第三章 雙層分支緩衝器
第四章 效能評估
第五章 結論

[1]J.L. Hennessy and D.A. Paterson, Computer Architecture A Quantitative Approach, Morgan Kaufman Publishers, Inc., 1990.[2]D.J. Lilia, “Reducing The Branch Penalty in Pipelined Processors,” IEEE Computer Magazine, pp: 47-55, July 1988.[3]S. McFarling, J.L. Hennessy, “Reducing The Cost of Branches,” Proceeding of 13th Annual International Symposium on Computer Architecture, pp: 396-403, June 1986.[4]N.P. Jouppi, D.W. Wall, “Available Instruction-Level Parallelism for Superscalar and Superpipelined Machine,” The 3rd Int. Symposium on ASPLO, pp: 272-282, April 1989.[5]M. Johnson, Superscalar Microprocessor Design, PTR Prentice Hill, Inc. 1991.[6]A.M. Gonzalez, “A Survey of Branch Techniques in Pipelined Processors,” Microprocessing and Microprogramming, pp: 243-257 Vol. 36, 1993.[7]C.C. Lee, “Optimizing High Performance Dynamic Branch Predictors”, PhD. Dissertation, The University of Michigan, Ann Arbor, 1998.[8]J.E. Smith, “A Study of Branch Prediction Strategies”, Proceeding of 8th Symposium on Computer Architecture, pp: 135-148, May 1984.[9]T.R. Gross and J.L. Hennessy, “Optimizing Delayed Branches”, Proceeding of 15th Annual Workshop on Microprogramming, ACM SIGMICRO, pp: 114-120, October 1982.[10]Control Data 7600 Hardware Reference Manual 60367200, Control Data, Arden Hill, Minn., 1975.[11]J.Y. Yamour, “Instruction Scan for an Early Resolution of a Branch Instruction”, IBM Technical Disclosure Bull., Vol. 23, No. 6, pp: 2600-2604, November 1980.[12]P. Chow and M. Horowitz, “Architectural Tradeoffs in The Design of MIPS-X”, Proceeding of 14th Annual International Symposium on Computer Architecture, pp: 300-308, June 1987.[13]K.F. Lee and A.J. Smith, “Branch Prediction Strategies and Branch Target Buffer Design”, IEEE Transaction on Computer, pp: 6-22, January 1984.[14]T.Y. Yeh and Y.N. Patt, “A Comparison of Dynamic Branch Predictors That Use Two Levels of Branch History”, Proceeding of the 20th Annual International Symposium on Computer Architecture, pp: 257-266, 1993.[15]C. Young, N. Gloy and M. D. Smith. “A Comparative Analysis of Schemes for Correlated Branch Prediction”, Proceedings of The 22th Annual International Symposium on Computer Architecture, pp. 276-286, 1995.[16]A. R. Talcott, M. Nemirovsky and R. C. Wood, “The Influence of Branch Prediction Table Interference on Branch Prediction Scheme Performance”, International Conference on Parallel Architectures and Compilation Techniques, 1995.[17]P.Y. Chang, E. Hao, T. Y. Yeh and Y. N. Patt, “Branch Classification: A New Mechanism for Improving Branch Predictor Performance”, Proceedings of The 27th Annual AACM/IEEE International Symposium on Microarchitecture, pp: 22-31, 1994.[18]S. McFarling, “Combining Branch Predictors”, Technical Report TN-36, Digital Western Research Laboratory, June 1993.[19]P. Y. Chang, M. Evers, and Y. N. Patt, “Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference”, IEEE Proceedings of PACT ’96, pp: 48-57, 1996.[20]A. Riseman and C.C. Foster, “The Inhibition of Potential Parallelism by Conditional Jumps”, IEEE Transactions on Computer, Vol. C-12, pp: 1405-1411, December 1972.[21]W. Chu, S. Vassiliadis, J.G. Delgado-Frias, “The Multi-Associative Branch Target Buffer: A Cost Effective BTB Mechanism”, Microprocessing And Microprogramming 41, pp: 211-225, 1995.[22]H. Perleberg and A.J. Smith, “Branch Target Buffer Design and Optimization”, IEEE Transaction on Computer, Vol. 42, No. 4, pp: 396-412, April 1993.[23]J. Smith, “A Comparative Study of Set Associative Memory Mapping Algorithms and Their Use for Cache and Main Memory”, IEEE Transactions on Software Engineer, pp: 121-130, March 1978.[24]G. Cragon, Branch Strategy Taxonomy and Performance Models, IEEE Computer Society Press.[25]T. Pan, K. So and J.T. Rahmeh, “Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation”, Proceedings of 5th Annual International Conference of Architecture Support for Programming Languages and Operation Systems, pp: 76-84, October 1992.[26]R. Talcott, W. Yamamoto, M.J. Serrano, R.C. Wood and M. Nemirovsky, “The Impact of Unresolved Branches on Branch Prediction Scheme Performance”, IEEE Transaction on Computer, pp: 12-21, 1994.