臺灣博碩士論文加值系統

隨著超純量(superscalar)微處理器同一時脈執行指令的數量越來越多,因此我們對於抓取(fetch)指令的方法有更多的要求,而蹤跡快取記憶體(trace cache)將邏輯上連續的指令,放置成實體上的連續位置,因而滿足這些要求,並且允許在同一時脈抓取多個指令區塊(basic block)去執行.
我們建議一個蹤跡預測器(next trace predictor),此預測器將蹤跡(traces)視為一個基本單位並且明顯的去預測一連串的蹤跡.此預測器收集路徑歷史(path history)以及全域歷史(global history),並且基於這些歷史資料去做預測.
除了一個基本的預測器之外,我們更提升原有版本的預測器成為第二版預測器,用以降低在預測表(prediction table)中由於化名(aliasing)所產生的干擾(interference),並進一步提高預測準確率.
最後用C++寫成一個蹤跡預測器,利用模擬工具(Shade)針對SPCEint95的標竿程式做蹤跡模擬,並調整各種不同的硬體參數,以求得到最好的預測準確率.

The increasing widths of superscalar processors are placing greater demands upon the fetch mechanism. The trace cache meets these demands by placing logically contiguous instructions in physically contiguous storage. It is capable of supplying multiple fetch blocks each cycle.
Predicting multiple branches per cycle means paying a penalty in prediction accuracy. We propose a next trace predictor that treats the traces as basic units and explicitly predicts sequences of traces. The predictor collects histories of paths and global histories of branches and makes predictions based on these histories.
The basic predictor (no tag) is enhanced to a second configuration (with tag) that reduces performance losses due to aliasing in the prediction table. Overall, the predictor yields about a 45.9% reduction in misprediction rate and a 40.9% reduction in hardware cost on the average when compared with the most aggressive previously proposed, next-trace-prediction method.

Chapter 1. Introduction 1
1.1 Background and Motivation 1
1.2 Organization of this thesis 4
Chapter 2. Related Work 5
2.1 The mechanism for fetching multiple basic blocks 5
2.1.1 The trace cache 5
2.2 The branch prediction mechanisms 8
2.2.1 Pattern History Table (PHT) with two-bit counter 8
2.2.2 The correlated predictor 8
2.3 The multiple branch prediction mechanisms 10
2.4 The path-based next trace prediction mechanism 12
2.4.1 Correlated predictor 12
2.4.2 Hybrid predictor 13
Chapter 3. Next trace predictors based on path and global history 15
3.1 The mechanism of naming traces 15
3.2 Correlated predictor architecture 17
3.2.1 Updating timing of history register 19
3.2.2 Index generation mechanism 19
3.2.3 Updating timing of trace ID prediction table 21
3.3 Enhanced predictor architecture 22
Chapter 4. Simulation methodology 24
4.1 Simulation environment 24
4.1.1 Experiment Platform 24
4.1.2 Simulation tools 24
4.1.2.1 Shade 25
4.1.2.2 SpixTools 25
4.2 Trace selection 27
4.3 Benchmarks 28
4.3.1 Benchmark summary 29
Chapter 5. Experimental Results 31
5.1 Experiment descriptions 31
5.2 Performance 33
5.2.1 Correlated predictor performance (no tag) 33
5.2.2 Enhanced predictor performance (with tag) 38
5.2.3 Performance comparison 43
5.2.4 The impact of global history 48
5.2.5 The predicted rate and the right-predicted rate 53
Chapter 6. Conclusion 58
Bibliography 59

[1] E. Rotenberg, S. Bennett, and J. E. Smith, "Trace cache: a low latency approach to high bandwidth instruction fetching," in Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture, December 1996.
[2] Q. Jacobson, E. Rotenberg, and J. E. Smith, "Path-based Next Trace Prediction." In Proceedings of the 30th International Symposimu on Microarchitecture, December 1997.
[3] J. E. Smith, "A Study of Branch Prediction Strategies," in Proceedings of the 8th International Symposium on Computer Architecture, May 1981.
[4] T. Conte, K. Menezes, P. Mills and B. Patel, "Optimization of Instruction Fetch Mechanisms for High Issue Rates," in Proceedings of the 22nd International Symposium on Computer Architecture, June 1995.
[5] S. Dutta and M. Franklin, "Control Flow Prediction with Tree-Like Subgraphs for Superscalar Processors," in Proceedings of the 28th International Symposium on Microarchitecture, December 1995.
[6] T.-Y. Yeh, D. Marr and Y. Patt, "Increasing the Instruction Fetch Rate via Multiple Branch Prediction and a Branch Address Cache," in Proceedings of the 7th ACM International Conference on Supercomputing, July 1993.
[7] S. Patel, D. Friendly and Y. Patt, "Critical Issues Regarding the Trace Cache Fetch Mechanism." University of Michigan Technical Peport CSE-TR-335-97, 1997.
[8] S.-T. Pan, K. So and J. Rahmeh, "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation," in Proceedings of the 5th International Conference on Architecture Suport for Programming Languages and Operating Systems, October 1992.
[9] T.-Y. Yeh and Y. Patt, "Two-Level Adaptive Branch Prediction," In Proceedings of 24th International Symposium on Microarchitecture, November 1991.
[10] S. McFarling, "Combining Branch Predictors," Technical Note TN-36, Western Research Laboratory, DEC, June 1993.
[11] R. Nair, "Dynamic Path-Based Branch Correlation," in Proceedings of the 28th International Symposium on Microarchitecture, December 1995.
[12] Q. Jacobson, S. Bennett, N. Sharms and J. E. Smith, "Control Flow Speculation in Multiscalar Processors," in Proceedings of the 3rd International Symposium on High-Performance Computer Architecture, February 1997.
[13] "Introduction to Shade," Sun Microsystems, Inc, V5.33A, June 1997.
[14] "Introduction to SpixTools," Sun Microsystems, Inc, V5.33A, Feb 1993.
[15] B. Black, B. Rychlik and J. P. Shen, "The Block-based Trace Cache," in Proceedings of the 32th International Symposium on Microarchitecture, December 1999.
[16] 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, May 1992.
[17] E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt, "The agree predictor: A Mechanism for Reducing Negative Branch History Interference," in the Porceedings of the 24th Annual International Symposium on Computer Architecture, June 1997.
[18] S. Sechrest, C.-C Lee, and T. Mudge, "Correlation and aliasing in dynamic branch predictors," in the Proceedings of the 23nd Annual International Symposium on Computer Architecture, May 1996.
[19] P. Michaud, A. Seznec, and R. Uhlig, "Trading Conflict and Capacity Aliasing in Conditional Branch Predictors," in the Proceedings of the 24th Annual International Symposium on Computer Architecture, June 1997.