為了提高系統效能，現今的電腦系統結合了多核心的中央處理單元(CPU)和多重的硬體加速處理器(Accelerator)來更有效率的執行應用程式，此為異質性系統運算。為了更進一步的提升異質性系統運算的效能，HSA基金會提出了一個新架構名為異質系統架構(Heterogeneous System Architecture,HSA)，意在提升異質系統的效能。為了更加有效利用此一架構，我們嘗試將其虛擬化，若有了虛擬化技術，可以使其不管是在效能或是安全上都能有所提升。
為此在本篇論文中，我們為HSA提出了一個系統虛擬化的架構。基於此架構下，我們提出了數個圖形運算單元(GPU)的排程方法以有效使用GPU去提升系統虛擬化效能。另外，我們實作了GPU的環境切換(context switch)，並將其運用在GPU的排程中，嘗試更進一步提升GPU效能。最後，我們也實作了一個圖形運算單元的時間計算基準，以檢測排程優劣。
實驗結果得知，在有context switch的功能下，GPU的排程效率較佳，對於系統虛擬化的GPU效能亦能有所提升。

Heterogeneous computing has been proposed to incorporate specialized processing capabilities (e.g. GPU, DSP and FPGA) in order to handle particular tasks. However, there are some drawbacks of current heterogeneous computing. In order to improve the performance, HSA foundation proposed the Heterogeneous System Architecture (HSA). In this thesis work, we investigate on the techniques for virtualizing an HSA platform to support various types of usages with virtual machines.
We first delivered a system that emulates system virtualization of HSA. Second, we proposed some GPU scheduling policies of HSA to utilize the GPU. Third, we implement the GPU context switch and apply to scheduling policies. Finally, We designed a simple timing model to evaluate GPU scheduling policies. Experimental results show that GPU scheduling polices with context switch are important, and better policies increase the performance of GPU for HSA virtualizaion.

Acknowledgments i
中文摘要 ii
Abstract iii
1 Introduction 1
1.1 Motivations 1
1.2 Thesis Organization 4
2 Background and Related Work 5
2.1 Heterogeneous Programming Frameworks 5
2.2 Heterogeneous System Architecture (HSA) 5
2.3 HSAemu 6
2.3.1 Modules of HSAemu 6
2.3.2 Execution Flow of HSAemu 8
3 Framework and Implementation 10
3.1 System Virtualization of HSA 11
3.1.1 HSAemu on HSAemu 12
3.1.2 Sending Software Interrupt Instructions in x86 Platforms 13
3.1.3 Pass AQL Packets from Guest HSAemu to Host HSAemu 14
3.2 GPU Scheduling 15
3.2.1 Baseline 15
3.2.2 Multi-Queue 16
3.2.3 CU Groups 16
3.2.4 Hybrid (CU Groups + Multi-Queue) 17
3.2.5 Design issues 18
3.3 GPU Context Switch 18
3.3.1 Simulation Flow of FastSim 18
3.3.2 Simulation Flow of FastSim with Context Switch 19
3.3.3 Preserve the State of FastSim 20
3.3.4 Scheduling Policy with Context Switch 22
3.4 Timing Model 22
4 Experimental Results 25
4.1 Experimental Setup 25
4.2 System Virtualization of HSA 26
4.2.1 Emulation Throughput 26
4.3 GPU Scheduling Policy 27
4.3.1 Waiting Time 28
4.3.2 Throughput 33
4.3.3 Turnaround Time 34
4.3.4 Summary 36
5 Conclusion and Future Work 37
Bibliography 39

[1] Jiun-Hung Ding, Wei-Chung Hsu, Bai-Cheng Jeng, Shih-Hao Hung and Yeh-Ching
Chung, “HSAemu – A Full System Emulator for HSA Platforms,” in International
Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS
2014), 2014.
[2] M. Pearce, S. Zeadally, and R. Hunt, “Virtualization: Issues, Security Threats, and
Solutions,” ACM Comput. Surv., vol. 45, no. 2, pp. 17:1–17:39, Mar. 2013. [Online].
Available: http://doi.acm.org/10.1145/2431211.2431216
[3] F. Bellard, “QEMU, a fast and portable dynamic translator,” in Proceedings of the
annual conference on USENIX Annual Technical Conference, ser. ATEC ’05. Berkeley,
CA, USA: USENIX Association, 2005, pp. 41–41. [Online]. Available:
http://dl.acm.org/citation.cfm?id=1247360.1247401
[4] E. Witchel and M. Rosenblum, “Embra: Fast and Flexible Machine Simulation,” in
Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement
and Modeling of Computer Systems, ser. SIGMETRICS ’96. New York, NY, USA:
ACM, 1996, pp. 68–79. [Online]. Available: http://doi.acm.org/10.1145/233013.233025
[5] P. Bohrer, J. Peterson, M. Elnozahy, R. Rajamony, A. Gheith, R. Rockhold, C. Lefurgy,
H. Sha?, T. Nakra, R. Simpson, E. Speight, K. Sudeep, E. Van Hensbergen, and
L. Zhang, “Mambo: A Full System Simulator for the PowerPC Architecture,”
SIGMETRICS Perform. Eval. Rev., vol. 31, no. 4, pp. 8–12, Mar. 2004. [Online].
Available: http://doi.acm.org/10.1145/1054907.1054910
39[6] A. Kivity, Y. Kamay, D. Laor, U. Lublin, and A. Liguori, “KVM: the Linux virtual
machine monitor,” in Proceedings of the Linux Symposium, vol. 1, 2007, pp. 225–230.
[7] L. Shi, H. Chen, and J. Sun, “vCUDA: GPU accelerated high performance computing in
virtual machines,” in Parallel Distributed Processing, 2009. IPDPS 2009. IEEE
International Symposium on, May 2009, pp. 1–11.
[8] V. Gupta, A. Gavrilovska, K. Schwan, H. Kharche, N. Tolia, V. Talwar, and
P. Ranganathan, “GViM: GPU-accelerated Virtual Machines,” in Proceedings of the 3rd
ACM Workshop on System-level Virtualization for High Performance Computing, ser.
HPCVirt ’09. New York, NY, USA: ACM, 2009, pp. 17–24. [Online]. Available:
http://doi.acm.org/10.1145/1519138.1519141
[9] G. Giunta, R. Montella, G. Agrillo, and G. Coviello, “A GPGPU transparent
virtualization component for high performance computing clouds,” in Euro-Par
2010-Parallel Processing. Springer, 2010, pp. 379–391.
[10] J. Duato, A. J. Pena, F. Silla, R. Mayo, and E. S. Quintana-Orti, “rCUDA: Reducing the
number of GPU-based accelerators in high performance clusters,” in High Performance
Computing and Simulation (HPCS), 2010 International Conference on. IEEE, 2010,
pp. 224–231.
[11] B. Gaster, L. Howes, D. Kaeli, P. Mistry, and D. Schaa, Heterogeneous Computing with
OpenCL: Revised OpenCL 1.2 Edition. Elsevier Science, 2012. [Online]. Available:
http://www.google.com.tw/books?id=yyI8jfvi9-8C
[12] “C++ AMP : Language and Programming Model Version 1.2,”
http://download.microsoft.com/download/2/2/9/
22972859-15C2-4D96-97AE-93344241D56C/CppAMPOpenSpeci?cationV12.pdf.
[13] “HSA programmers reference manual version 1.0 provisional ,”
http://www.hsafoundation.com/standards/.
40[14] “HSA Platform System Architecture Speci?cation 1.0 Provisional,”
http://www.hsafoundation.com/standards/.
[15] “HSA Runtime version 1.00 Provisional ,” http://www.hsafoundation.com/standards/.
[16] R. Ubal, B. Jang, P. Mistry, D. Schaa, and D. Kaeli, “Multi2Sim: a simulation
framework for CPU-GPU computing,” pp. 335–344, 2012. [Online]. Available:
http://doi.acm.org/10.1145/2370816.2370865
[17] “The GNU C Library Reference Manual for version 2.19,”
http://www.gnu.org/software/libc/manual/pdf/libc.pdf.