進階搜尋


下載電子全文  
系統識別號 U0026-2208201201421400
論文名稱(中文) 使用條件旗標預測機制增進亂序執行處理器之效能
論文名稱(英文) Using Condition Flag Prediction to Improve the Performance of Out-of-Order Processors
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 100
學期 2
出版年 101
研究生(中文) 徐子軒
研究生(英文) Tzu-Hsuan Hsu
學號 q36981026
學位類別 碩士
語文別 中文
論文頁數 37頁
口試委員 指導教授-陳中和
口試委員-蘇文鈺
口試委員-陳培殷
口試委員-紀新洲
口試委員-林泰吉
中文關鍵字 亂序執行處理器  if-conversion  條件旗標預測 
英文關鍵字 out-of-order execution  if-conversion  condition flag prediction 
學科別分類
中文摘要 亂序執行處理器架構與if-conversion,這兩項對於增進程式執行效率都是非常普遍且重要的技術。If-conversion可以有效減少程式碼中條件分支的使用,降低分支預測錯誤懲罰對效能的影響,在一般管線處理器中可以得到很大的好處。但是當亂序執行處理器執行if-conversion所轉換出來的程式時,會發生暫存器重覆命名的問題。這是個必須要解決的問題,否則處理器將無法正確的執行指令。若是消極地暫停處理器管線,避免錯誤的情況發生,反而會造成效能低落。
在這篇論文中,我們基於ARM指令集架構的特性,設計一個預測條件旗標的機制與硬體架構,我們動態儲存指令最近幾次寫入條件旗標的歷史紀錄,並設計一個條件旗標的選擇機制從歷史紀錄中選擇最有可能的旗標作為預測結果。這個方法解決了暫存器重覆命名的問題。並且平均有5.89%的效能增益。
英文摘要 In high-performance processor architecture, out-of-order execution and if-conversion are two very common techniques for performance improvement. If-conversion is a compiler technique that reduces the misprediction penalties caused by conditional branches. Using if-conversion on the out-of-order execution architecture creates a register naming problem. If there are multiple updates of the same register of different conditions and if the condition flags have not been resolved, then it is unknown which physical register should be mapped on to the architectural register. To deal with this problem, one approach could simply stall the renaming unit until the condition flag is resolved, however this would cause great performance degradation.
Predicting condition flag is an effective approach to address this problem. In this thesis, we propose a new scheme to predict the condition flag based on the ISA of ARM. By storing two most recent unique condition flag values for each instruction dynamically in the run time, and by using a condition flag selector when a condition flag-updating instruction reaches the renaming unit, we can predict the outcome of the condition flag-updating instruction. The approach enables an efficient implementation of if-conversion for our out-of-order processor to deal with the multiple definition problem.
To design the condition flag predictor, we use the concept of branch prediction to implement our flag selector and we combine a threshold value to the basic condition flag prediction mechanism. We have simulated benchmark programs in different threshold value and have evaluated a popular branch predictors in our flag selector. We show that our approach is able to achieve an IPC performance increase of 5.89%.
論文目次 摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第1章 序論 1
1.1 研究動機 1
1.2 研究貢獻 2
1.3 論文編排 2
第2章 背景知識 3
2.1 亂序執行處理器架構 3
2.2 暫存器重新命名 4
2.3 If-conversion 5
2.4 ARM指令集架構 6
2.5 Out-of-order processors with condition execution 8
2.5.1 Multiple register definitions 8
2.5.2 相關解決方法 9
第3章 Condition Flag Prediction 12
3.1 Flag value locality 12
3.2 The condition flag prediction scheme 14
3.2.1 Condition flag value table 14
3.2.2 Flag selector for condition flag predictor 14
3.2.3 Operation of condition flag predictor 15
3.3 Confidence threshold 18
第4章 實驗環境與實驗結果分析 21
4.1 環境架設 21
4.2 測試程式與執行 22
4.3 實驗數據與結果分析 23
4.3.1 Condition flag predictor 24
4.3.2 Effect of condition stall 27
第5章 結論與未來展望 34
5.1 結論 34
5.2 未來展望 35
參考文獻 36



參考文獻 [1] J. E. Smith, and G. S. Sohi, “The Microarchitecture of Superscalar Processors,” Proceedings of the IEEE, vol. 83, pp. 1609-1624, Dec. 1995.
[2] R. M. Tomasulo, “An Efficient Algorithm for Exploiting Multiple Arithmetic Units,” IBM J. Research and Development, vol. 11, pp. 25-33, Jan. 1967.
[3] J. L. Hennessy, and D. A. Patterson, “Computer Architecture ― A Quantitative Approach,” 3rd edition, Morgan Kaufmann Publishers, San Francisco, 2003.
[4] J. R. Allen, K. Kennedy, C. Porterfield, and Joe Warren, “Conversion of control dependence to data dependence,“ POPL ’83 Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages Page 177 – 189.
[5] ARM Corporation, “ARM Architecture Reference Manual.”
[6] P. H. Wang, H. Wang, R. M. Kling, K. Ramakrishnan, and J. P. Shen, “Register Rename and Scheduling for Dynamic Execution of Predicated Code,” High-Performance Computer Architecture(HPCA 7th), pp.15-25, Jan. 2001.
[7] M. Stephenson, Lixin Zhang and R. Rangan, “Lightweight predication support for out of order processors,” HPCA ’09 Proceedings of the 2009 IEEE 15th International Symposium on High Performance Computer Architecture.
[8] E. Quinones, J-M. Parcerisa, and A. Gonzalez, “Selective Predicate Prediction for Out-of-Order Processors,” ICS ’06 Proceedings of the 20th annual international conference on Supercomputing.
[9] E. Quinones, J-M. Parcerisa, and A. Gonzalez, “Improving Branch Prediction and Prediction and predicated Execution in Out-of-Order Processors,” HPCA ’07 Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture.
[10] W. Chuang and B. Calder, “Predicate prediction for efficient out-of-order execution,” ICS ’03 Proceedings of the 17th annual international conference on Supercomputing.
[11] J.-W. Lin, “Design, analysis, and implementation of a parameter-based out-of-order superscalar microprocessor conforming to ESL methodology,” Master Thesis, Dept. of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, Jul. 2008.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2015-09-03起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2015-09-03起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw