臺灣博碩士論文加值系統

同步多重執行緒(Simultaneous Multithreading)是由多重執行緒的一種改良，它能夠在單一時脈週期從不同非相依的程式或是執行緒中擷取多重指令。同步多重執行緒發展主要動機來自多重發派處理器通常在功能單元(Functional Unit)平行化比單一執行緒來得有效，再者，因為暫存器重新命名(register renaming)和動態排程(dynamic scheduling)的緣故，不同執行緒之間所發派的指令可以不需考量指令間的相依性，相依性的問題可由動態排程來處理。
在同步多重執行緒架構下，擷取單元(fetch unit)對於指令的擷取，它必須夠聰明地選擇要從哪些執行緒提取，而目前已有相關研究提出，以改善擷取過程，使得整體效率有所提升。
此外，在SMT架構下，預先擷取(Prefetching)是一種有效提升擷取效能的機制。在此篇論文中, 我們分別用ICOUNT和ICC等擷取策略所產生的優先執行緒資訊作為我們預先擷取機制的參考輸入, 再分別將不同執行緒放入所對應的關聯佇列(Correlation Queue, CQ)中。 我們將利用所提計數機制選出關聯佇列中的預先擷取候選項, 並將所選的預先擷取候選執行緒, 送入一組作為累計所選取預先擷取候選項次數之累加器, 稱之預先擷取計數累加器(Prefetch count Accumulator, PCA)。而後依各選取預先擷取候選項的最高計數累加值, 決定最後預先擷取執行緒, 並經由分支預測機制將預先擷取執行緒中可能用到的指令選出。 在此製定一預先擷取的指令過濾機制, 來判定目前所選出預先擷取指令是否已存在指令快取記憶體, 以決定最後是否真正被預先擷取到預先擷取緩衝區, 以供在擷取階段(fetch stage)時執行緒發生指令誤失時, 可直接從預先擷取緩衝區擷取, 進而節省重新擷取所花費的時間。而以此經由實驗模擬顯示，整體效能最高可增進百分之十二。

Simultaneous Multithread (SMT) is an improvement on multithreading. SMT will fetch multiple instructions from independent programs or threads at single cycle. The key insight that motivates SMT is that modern multiple-issue processors often have more function units available than a single thread can effectively use. Furthermore, with register renaming and dynamic scheduling, multiple instructions from independent threads can be issued without regard to the dependences among them; the resolution of dependences can be handled by the dynamic scheduling capability.
In SMT architecture, the fetch unit of the processor has to be smart enough to know which thread to fetch from. The relative investigations have been studied for a long time, such that the fetch efficiency and the overall performance can be improved.
Besides, the prefetch is also an effective way to boost the fetch performance on the SMT. In this paper, we utilize the information of preferred thread from ICOUNT (Instruction Count) and ICC(Instantaneous Commit Count) as a reference input for the proposed prefetching mechanism, and these threads will enter the different correlation queues (CQs). We will utilize the proposed count mechanism to choose the prefetch candidate in a CQ, and this prefetch candidate into a set of accumulators (called prefetched candidate accumulators, PCAs) as accumulated frequencies of chosen different prefetch candidate. According to the highest value of these accumulators to determine final prefetch thread, and chosen possible instructions in this prefetched thread by branch prediction mechanism. Besides, we will utilize an instruction filtration mechanism to check whether these instructions already stored in instruction cache, then to determine whether or not these instructions will be prefetched into the prefetch buffer. The buffer will provide the instructions when a cache miss occurs. Experimental simulation results show that the overall performance is achieved 12% speedup in maximum.

ACKNOWLEDGEMENTS i
ENGLISH ABSTRACT ii
CHINESE ABSTRACT iii
TABLE OF CONTENTS iv
LIST OF FIGURES v
LIST OF TABLES vii
CHAPTER 1 INTRODUCTION 1
1.1 Simultaneous Multithreading Architecture 2
1.2 The bottlenecks of Simultaneous Multithreading 9
1.3 The Thesis Organization 11
CHAPTER 2 RELATED WORKS 12
CHAPTER 3 INSTRUCTION PREFETCHING MECHANISM FOR SMT 22
3.1 Base Fetch Scheme 22
3.2 The Architecture of Prefetch 23
3.3 Instruction Prefetch Mechanism 23

3.4 Instruction Filtration Mechanism 25

CHAPTER 4 SIMULATION METHODOLOGY 30
CHAPTER 5 SIMULATION RESULTS 33
CHAPTER 6 CONCLUSIONS 57
REFERENCE 59

[1]D. Tullsen, S. Eggers, and H. Levy, “Simultaneous multithreading: Maximizing on-chip parallelism,” In 22nd Annul International Symposium on Computer Architecture, June 1995, Pages 392-403

[2] H. Hirata, K. Kimura, S. Nagamine, Y. Mochizuki, A. Nishimura, Y. Nakase, and T. Nishizawa. An elementary processor architecture with simultaneous instruction issuing from multiple threads. In 19th Annual International Symposium on Computer Architecture, pages 136-145, May 1992

[3]D. Tullsen, S. Eggers, J. Emer, H. Levy, J. Lo, and R. Stamm, “Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading
processor,” In 23rd Annul International Symposium on Computer Architecture, May 1996

[4]S. Eggers, J. Emer, H. Levy, J. Lo, and R. Stamm, and D. Tullsen, “Simultaneous multithreading: A platform for next-generation processors,” IEEE Micro, Sep. 1997, Pages 12-18

[5]D. Tullsen and J. Brown, “Handling Long-latency Loads in a Simultaneous Multithreading Processor” MICRO-34, Dec. 2001, Pages 318-327

[6] K. Luo, M. Franklin, S. Mukherjee, and A. Sezne. Boosting SMT performance by speculation control. In 15th Proceedings of International Parallel and Distributed Processing Symposium (IPDPS)}, 2001.
[7] P.M.W. Knijnenburg, A. Ramirez, F. Latorre, J. Larriba, and M. Valero. Branch classification to control instruction fetch in simultaneous multithreaded architectures. In International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'02), January 10 - 11, 2002

[8] A. El-Moursy, and D. Albonesi. Front-end policies for improved issue efficiency in SMT processors. 9th International Symposium on High-Performance Computer Architecture, pages 31-40, February 2003.

[9] D. Madon, E. Sanchez, and S. Monnier, A Study of a Simultaneous Multithreaded Architecture. In Proceedings of EuroPar'99, Toulouse, Lectures Notes in Computer Science, Volume 1685, Springer-Verlag, pages 716-726, August 31 - September 3 1999.

[10]A. Falcon, A. Ramirez and M. Valero, “A Low-Complexity, High-Performance Fetch Unit for Simultaneous Multithreading Processors,” In Proceedings of the 10th International Symposium on High Performance Computer Architecture, Feb. 2004, Pages 244-254

[11]Goncalves, R.; Navaux, P.; “Improving SMT performance scheduling processes”, Parallel, Distributed and Network-based Processing, 2002. Proceedings. 10th Euromicro Workshop on, 9-11 Jan. 2002 Page(s):327 – 334



[12] Reinman, G.; Calder, B.; Austin, T, “Fetch directed instruction prefetching” Microarchitecture, 1999. MICRO-32. Proceedings. 32nd Annual International Symposium on, 16-18 Nov. 1999 Page(s):16 - 27

[13]T.-R. Yang, and J.-J. Shieh, “Dynamic Fetch Engine Design for Simultaneous Multithreaded Processors”, In Proceedings of the 9th Asia-Pacific Computer Systems Architecture Conference, Sep. 2004, Pages 489-502

[14] Joseph, D.; Grunwald, D., “Prefetching using Markov predictors”, Computers, IEEE Transactions on Volume 48, Issue 2, Feb. 1999 Page(s):121 - 133

[15] Nesbit, K.J.; Smith, J.E.; “Data Cache Prefetching Using a Global History Buffer” High Performance Computer Architecture, 2004. HPCA-10. Proceedings. 10th International Symposium on, 14-18 Feb. 2004 Page(s):96 - 96

[16]Y.-H. Chen, and J.-J. Shieh, “ICC: A Simultaneous Multithreading Fetch Engine” 2005 National Computer Symposium, 15-16 Dec. 2005 Page(s): 59 - 59

[17]D. Madon, E. Sanchez, and S. Monnier, “A Study of a Simultaneous Multithreaded Architecture,” In Proceedings of EuroPar'99, Toulouse, Lectures Notes in Computer Science, Volume 1685, Springer-Verlag, Sep. 1999, Pages 716-726

[18]T. Austin, E. Larson, D. Ernst, “SimpleScalar: an infrastructure for computer system modeling,” IEEE Computer Journal, Feb. 2002, Pages 59-67