臺灣博碩士論文加值系統

本篇論文中，我們將快取記憶體過濾器的概念應用到處理器中分支預測器(Branch Predictor)之分支目標緩衝器(Branch Target Buffer)設計。使用過濾器概念可以減少分支目標緩衝器的存取動作以降低動態耗電，本篇論文提出分支目標緩衝器的設計方法，不僅可以維持分支預測的準確度與處理器管線架構高效能運作，並且達到省電的效果。
我們使用內容可定址記憶體(CAM)來設計過濾器，並且使用HSPICE、CACTI等工具來確認過濾器電路不影響處理器管線中指令擷取部分之關鍵電路延遲。根據SimpleScalar/Wattch與SPEC2K等工具為基礎的實驗結果顯示，在不犧牲分支預測準確度與處理器效能的前提下，分支目標緩衝器動作減少達到85%，分支預測單元省電達16% - 55%，分支目標緩衝器省電達18% - 75%。

In this paper we apply Sentry Tag based filter scheme to the design of branch target buffer (BTB) of branch predictor in modern processors. The filter scheme filtrates unnecessary accesses of branch target buffer to reduce dynamic power consumption. The proposed scheme not only maintains high branch prediction accuracy and thus high pipeline utilization for processors, but also attains considerable power saving.
We use Content-Addressable Memory (CAM) to design the filter scheme and utilize HSPICE and CACTI tools to make sure the proposed scheme’s critical path delay of processor instruction fetch of pipeline is not affected. Based on SimpleScalar/Wattch simulators and SPEC2K benchmarks, we show that our scheme can filter up to 85% of branch target buffer accesses, thus reducing the power consumption for branch prediction unit by 16% - 55%, (the power consumption for branch target buffer by 18% - 75%) without compromising prediction accuracy and processor performance.

摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 X
第一章 緒論 1
1.1研究動機與目的 1
1.2研究貢獻 3
1.3論文內容簡述 4
第二章 相關背景知識與文獻探討 5
2.1分支預測單元(Branch Prediction Unit) 5
2.1.1分支預測器(Branch Predictor) 7
2.1.2分支目標緩衝器(Branch Target Buffer) 20
2. 相關文獻 22
2.2.1 NBIC低耗電分支目標緩衝器 22
2.2.2 NBDT低耗電分支目標緩衝器 24
2.2.3 PPD低耗電分支目標緩衝器 25
第三章 過濾器方法 27
3.1傳統四路集合關聯式分支目標緩衝器 27
3.2過濾器方法使用在分支目標緩衝器的原理 29
3.3過濾率與平均存取動作的分析 30
3.3.1平均存取動作的分析 31
3.3.2過濾率的分析 33
3.4過濾器方法硬體電路設計 35
第四章 模擬實驗結果與討論 37
4.1對最長路徑的影響 40
4.2哨兵表額外面積 46
4.3哨兵表過濾效能 48
4.4功率節省效果 51
第五章 結論與未來研究方向 61
參考文獻 62

[1] Chang, Y.-J., Ruan, S.-J. and Lai, F, “Sentry Tag: An Efficient Filter Scheme for Low Power Cache,” In Proc. Seventh Asia-Pacific Computer Systems Architectures Conference (ACSAC2002), Melbourne, Australia., pp. 135-140, 2002.
[2] Y. J. Chang, S. J. Ruan, and F. P. Lai, “Design and analysis of low power cache using two-level filter scheme,” IEEE Transactions on Very Large Scale Integration Systems, vol. 11, pp. 568–580, Aug 2003.
[3] Shuai Wang, Jie Hu, and Sotirios G. Ziavras, “BTB Access Filtering: A Low Energy and High Performance Design.” In Proc. of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI 2008), pp. 81 - 86, April 7-9, 2008.
[4] 胡耀中, 國立交通大學資訊工程學系碩士論文, “Low Power Branch Target Buffer, ”2005.
[5] 喬偉豪, 國立交通大學資訊工程學系博士論文, “Low-Power Branch Target Buffer, ”2008.
[6] D. Parikh, K. Skadron, Y. Zhang, M. Barcella, and M. Stan, “Power issues related to branch prediction, ” In Proc. HPCA-8, pp. 233–44, Feb. 2002.
[7] S. Kaxiras, Z. Hu, and M. Martonosi, “Cache decay: Exploiting generational behavior to reduce cache leakage power, ” Proc. of Int. Symp. Computer Architecture, pp. 240-251, 2001.
[8] K. Flautner, N . S. Kim, S. Martin, D. Blaauw, and T. Mudge, “Drowsy caches: simple techniques for reducing leakage power, ” In Proc. Intl. Symp. Computer Architecture, Alaska, pp. 219-230, May 2002.
[9] Todd M. et al., “SimpleScalar 3.0, ” in http://www.simplescalar.com/
[10] David Brooks, “Wattch Version 1.02, ” in http://www.eecs.harvard.edu/~dbrooks/wattch-form.html
[11] R. Kessler, “The Alpha 21264 microprocessor, ” IEEE Micro, 19(2): pp. 24–36, March/April 1999.
[12] I. Bate and R. Reutemann, “Efficient Integration of Bimodal Branch Prediction and Pipeline Analysis, ” In IEEE Conference on Real-Time Computing Systems and Applications, pp. 39–44, Hong Kong, China. 2005.
[13] T.Y. Yeh and Y. N. Patt, “Two-level adaptive training branch prediction, ” In Proceedings of the 24th Annual International Symposium on Microarchitecture, pp. 51-61, November 1991.
[14] S. McFarling, “Combining branch predictors, ” Digital Equipment Corporation, WRL Tech. Note TN-36, 1993.
[15] E. Sprangle, R. Chappell, M. Alsup, and Y. Patt, “The Agree predictor: Amechanism for reducing negative branch history interference, ” In Proceedings of the 24th Annual International Symposium on Computer Architecture, May 1997.
[16] C.-C. Lee, I.-C. K. Chen, and T. N. Mudge, “The bimode
branch predictor,” in Proceedings of the 30th Annual
ACM/IEEE International Symposium on Microarchitecture,
pp. 4 - 13, Dec 1997.
[17] P. Michaud, A. Seznec, and R. Uhlig, “Trading conflict and capacity aliasing in conditional branch predictors, ” In Proceedings of the 24th Annual International Symposium on Computer Architecture, pp. 292-303, May 1997.
[18] P. Chang, M. Evers, and Y. Patt, “Improving branch prediction accuracy by reducing pattern history table interference,” In Proceedings of the International Conference Parallel Architecture and Compilation Techniques, pp. 48–57, October 1995.
[19] A. Eden and T. Mudge. The YAGS Branch Prediction Scheme. In Proc. 31nd International Symposium on Microarchitecture, pp. 69–77, Nov. 1998.
[20] Daniel A. Jim’enez and Calvin Lin, “Dynamic branch prediction with perceptrons, ” In Proceedings of the 7th Int’l Symposium on High Performance Computer Architecture, pp. 197–206, January 2001.
[21] Amant, Renee St., Daniel A. Jimenez and Doug Burger, “Low - Power, High-Performance Analog Neural Branch Prediction, ” Microarchitecture, MICRO-41, 41st IEEE/ACM International Symposium, pp. 447–458, Nov 2008.
[22] David T. et al., “Cacti 3.2 web interface,” in http://quid.hpl.hp.com:9081/cacti/
[23] 財團法人國家實驗研究院-晶片系統設計中心, http://www.cic.org.tw/cic_v13/
[24] AMRUTUR, B. S. AND HOROWITZ, M. A, “Fast low-power decoders for RAMs,” IEEE Journal of Solid-State Circuits 36, pp. 1506–1515, 2001.
[25] M. Monchiero and G. Palermo, “The Combined Perceptron Branch Predictor, ” Technical Report n. 2004.35, Dept. of Electronics & information Technical Report, Milan, Polytech Institute, Milan, Italy, 2004.
[26] J. Lee and A. J. Smith, “Branch prediction strategies and branch target bu_er design, ” IEEE Computer, pp. 6–22, January 1984.