請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49641完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 洪士灝(Shih-Hao Hung) | |
| dc.contributor.author | Wei-Cheng Lin | en |
| dc.contributor.author | 林偉晟 | zh_TW |
| dc.date.accessioned | 2021-06-15T11:39:18Z | - |
| dc.date.available | 2026-12-31 | |
| dc.date.copyright | 2017-03-09 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-15 | |
| dc.identifier.citation | [1] Avx/sse. https://software.intel.com/sites/landingpage/IntrinsicsGuide/.
[2] Cuda toolkit documentation. http://docs.nvidia.com/cuda/ cuda-c-programming-guide/#axzz4ENJIBSwa. [3] KSM Configurations. https://access.redhat.com/documentation/en-US/ Red_Hat_Enterprise_Linux/6/html/Virtualization_Administration_Guide/ chap-KSM.html. [4] KSM Features. https://kernelnewbies.org/Linux_2_6_32# head-d3f32e41df508090810388a57efce73f52660ccb. [5] KSM Performance Problem. http://lwn.net/Articles/330589/. [6] Kvm. http://www.linux-kvm.org/page/Main_Page. [7] OpenCL Overview . https://www.khronos.org/opencl/. [8] Power Systems Memory Deduplication. http://www.redbooks.ibm.com/ redpapers/pdfs/redp4827.pdf. [9] System profiler. http://sysprof.com/. [10] E. I. ARCANGELI, A. and C. WRIGHT. Increasing memory density by using ksm. In Proceedings of the Linux Symposium, pages 19–28. Linux Symposium, 2009. [11] M. R. M. H. K. Miller, F. Franz and F. Bellosa. Xlh: More effective memory deduplication scanners through cross-layer hints. In Proceedings of the 2013 USENIX conference on Annual Technical Conference, pages 279––290. USENIX, 2013. [12] K. J. KLOSTER, J.F. and A. MEJLHOLM. Determining the use of interdomain shareable pages using kernel introspection. In Tech. rep., Aalborg University, pages 1–82. Aalborg University, 2007. [13] Z. M. H. L.Chen, Z.Wei and Y.Bao. Cmd: classification-based memory deduplication through page access characteristics. In ACM SIGPLAN/SIGOPS Int. Conf. Virtual Execution Environments, pages 65–76. ACM, 2014. [14] M. D. H. S. MIŁ´OS, G. and M. FETTERMAN. Satori: Enlightened page sharing. In Annual Technical Conference, San Diego, CA, USA, pages 1–14. USENIX, 2009. [15] C. WALDSPURGER. Memory resource management in vmware esx server. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation, pages 1–15. USENIX, 2002. [16] W.Sun and R.Ricci. Augmenting operating systems with the gpu. In Technical report, University of Utah, pages 1–5. University of Utah, 2010. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49641 | - |
| dc.description.abstract | KSM 是一個附加於KVM 上Linux kernel 的模組，用於合併KVM上跨虛擬機器之間所擁有相同重複的頁面，並釋放已經被合併後的頁面，節省虛擬機器所使用頁面數量，以達到最好的記憶體使用率。現行的KSM 中，必須賴以kernel thread daemon”ksmd” 循序不間斷停地在可被合併的記憶體區域中做搜尋頁面的動作，並且找出可合併的頁面加以合併，雖然可以省下記憶體使用空間，卻也增加了CPU工作量的負擔。本論文找出KSM 演算法中所佔比例較高的函式，第一為頁面比對、第二為頁面校驗和運算，我們嘗試針對這兩個函式下去最佳化。頁面比對所使用的方式是必須先將兩個頁面透過映射至實體記憶體上bit by bit 的做比對，最差情況則是當兩個頁面相同時，必須比對完整頁面的大小4KB，我們採用原先就已存在於KSM 演算法中各個頁面所算出的校驗和，使用比對頁面的校驗和的方式達到整體流程的加速。頁面的校驗和運算則是採用jhash2 此種哈希函數來算出各個頁面之校驗和，此函式是個複雜數學運算，因此會占用不少的CPU 使用量在運算上，我們使用GPGPU，SIMD (single instruction multiple data)架構之硬體加速器來輔助我們一次計算大量頁面的校驗和，但是由於KSM 是存在於kernel space 中的process，又一般GPGPU 程式語言OpenCL 或是CUDA 之Runtime API 及library 只允許在user space 中所使用，因此我們參考其他論文並使用，KGPU 一個可於kernel space 中使用GPGPU 的框架，來協助最佳化頁面的校驗和運算。 | zh_TW |
| dc.description.abstract | KSM which is a Linux kernel module attached to the KVM hypervisor used for merging duplicate page across different virtual machines and release merged pages in order to achieve the best memory utilization. Existing KSM must periodically scan the mergable memory area and identify the identical pages to merge via kernel thread daemon ”ksmd”. Although memory usage is reduced, CPU usage is increased. This thesis analyzed KSM and found the hotsopts of KSM algorithm. The first is page comparison and the second is page’s checksum calculation. We tried to optimize for these two functions. Page comparison may firstly map two pages onto physical memory and compare page’s content bit by bit . Comparing two identical pages is the worst situation because must compare full page of size 4KB. We use comparing page’s checksums in order to accelerate KSM algorithm. Page’s checksum calculation is computed by a hash function - jhash2. This function is a complex mathematical operation so that it takes a certain CPU usage in operation. We use GPGPU, a SIMD (single instruction multiple data) architecture of hardware accelerator to help us calculate the checksums f a large number of pages concurrently. But due to the KSM is a process in the kernel space. GPGPU programming language OpenCL or CUDA runtime API and library are support only in user space. So we reference other papers and use. KGPU, a framework for GPGPU can be used in kernel space to optimize the page’s checksum calculation. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T11:39:18Z (GMT). No. of bitstreams: 1 ntu-105-R03922129-1.pdf: 1919530 bytes, checksum: ac06e9184e4e13e1be205e6cd2f6e30d (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Background and Related Work 3 2.1 Linux Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Process Management . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Memory Management . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 KSM Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 KVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 KSM Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 KSM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.4 Detail in Stable Tree and Unstable Tree . . . . . . . . . . . . . . 12 2.2.5 KSM Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 Content Based Page Sharing . . . . . . . . . . . . . . . . . . . . 14 2.3.2 GPGPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.3 KGPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Framework and Implementation 19 3.1 Page Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Memcmp_pages . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Framework 1 – Checksum Optimization . . . . . . . . . . . . . . 20 3.2 Page’s Checksum Calculation . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 Cal_chekcksum . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Framework 2 – Checksum + KGPU Optimization . . . . . . . . . 23 4 Evaluation 25 4.1 Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Experiment Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.1 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.2 Dynamic/No Sleep . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2.3 Static/No Sleep . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.4 Why Framework 1 is better than Framework 2 at Static/No Sleep? 28 4.2.5 Dynamic/Sleep 20ms . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2.6 Static/Sleep 20ms . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Conclusion and Future work 31 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Bibliography 33 | |
| dc.language.iso | en | |
| dc.subject | KGPU | zh_TW |
| dc.subject | KSM | zh_TW |
| dc.subject | 虛擬機器 | zh_TW |
| dc.subject | KGPU | en |
| dc.subject | Virtual Machine | en |
| dc.subject | KSM | en |
| dc.title | Linux 內核相同頁面合併之效能探討 | zh_TW |
| dc.title | On the Performance of Linux Kernel Samepage Merging | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 廖世偉(Shih-wei Liao),涂嘉恆(Chia-Heng Tu),李曜琮(YUE-CONG LI) | |
| dc.subject.keyword | KSM,虛擬機器,KGPU, | zh_TW |
| dc.subject.keyword | KSM,Virtual Machine,KGPU, | en |
| dc.relation.page | 34 | |
| dc.identifier.doi | 10.6342/NTU201602447 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-16 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 1.87 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。