在計算網格上，使用者程式往往需要使用大量的記憶體來存放資料，因此單一計算節點經常無法滿足使用者程式的記憶體需求。針對此問題，過去的研究常會利用遠端節點的記憶體來暫時存放程式的資料，藉以降低存取硬碟所付出的代價。然而這些研究所提出的遠端分頁機制並沒有考慮網路的延遲時間，因此無法確保遠端分頁一定會有效地改善程式的效能。另一方面，當記憶體伺服器的擁有者在執行程式，過去的遠端分頁機制往往會將客戶端的記憶體分頁全部遷移至其他記憶體伺服器。雖然這種策略可以有效避免記憶體競爭，但也可能會增加分頁遷移的次數，進而導致使用者程式的效能降低。為了解決上述的這些問題，本篇論文提出了一個新的遠端分頁機制。此機制除了會根據網路延遲與可用的記憶體空間來選擇適當的記憶體伺服器以進行遠端分頁外，也會動態地調整記憶體伺服器的記憶體使用量，讓使用者的工作可以有效地利用記憶體伺服器的閒置實體記憶體，並且避免與資源擁有者的程式競爭記憶體資源。

User’s programs on computational grids often need to access large amount of data which cannot be stored with the memory capacity of a single node. To resolve this problem, the past researches proposed the remote paging technique which utilize memories of the remote nodes for data storage. Although the proposed schemes can reduce the cost of accessing the hard disks, they didn’t take the network latency into consideration. This makes no guarantee for the performance improvement of remote paging. Furthermore, as the owner of memory server is competing for the memory space, the past remote paging scheme would migrate all memory pages of the currently executing program to another memory server. Although this scheme can avoid the competition of memory resources, it also increases the frequency of memory page migration which leads to poor performance of user programs. To address this problem, this thesis has proposed a new remote paging scheme. It selects suitable memory servers according to network latency and available memory space. This scheme can dynamically adapt the amount of memory used by the memory server, so that the free memory of the memory server can be utilized more effectively by the user’s job as well as avoiding the competition of memory resources from the owner’s programs.

中文摘要...........................................................................................................................i
英文摘要..........................................................................................................................ii
誌謝................................................................................................................................iii
目錄................................................................................................................................iv
圖目錄...............................................................................................................................v
表目錄............................................................................................................................vii
第一章 概論................................................................................................................- 1 -
1.1 研究背景與動機........................................................................- 1 -
1.2 研究目的...................................................................................- 3 -
1.3 論文架構...................................................................................- 3 -
第二章 相關文獻探討與回顧...............................................................................- 4 -
第三章 分頁遷移與記憶體伺服器選擇之演算法..................................................- 12 -
3.1系統架構..................................................................................- 12 -
3.2記憶體伺服器選擇之演算法.....................................................- 16 -
3.2.1 記憶體伺服器端..........................................................................- 18 -
3.2.1 用戶端............................................................................................- 19 -
3.3分頁選擇之演算法...................................................................- 19 -
第四章 效能測試......................................................................................................- 23 -
4.1 實驗環境與方法......................................................................- 23 -
4.2 遠端分頁系統的效能評估.......................................................- 26 -
4.2.1 實驗一：Correction of Server-Selection Condition.............- 26 -
4.2.2 實驗二：Effectiveness of Page Migration.............................- 28 -
4.2.3 實驗三：全部與部分分頁遷移的效能比較..........................- 34 -
4.2.4 實驗四：Effectiveness of Server Selection based on Network Latency......................................................................................................- 39 -
4.2.4 實驗五：Effectiveness of Adaptive Remote Paging under Dynamic Change in Network Latency.................................................- 43 -
第五章 結論與未來工作..........................................................................................- 47 -
參考文獻....................................................................................................................- 48 -

[1]A. Acharya, S. Koussih and S. Setia, “Dodo: A User-level System for Exploiting Idle Memory in Workstation Clusters”, in HPDC ’99, August 1999
[2]Eric A. Anderson and Jeanna M. Neefe, “An exploration of network RAM”, Technical report,Computer Science Division, UC Berkeley, December 1994
[3]M. Baker, R. Buyya, and D. Laforenza, “Grids and Grid Technologies for Wide-Area Distributed Computing,” Software: Practice and Experience, Vol. 32, Issue 15, pp. 1437-1466, 2002.
[4]R. Buyya and M. Murshed, “GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing,” Concurrency and Computation: Practice and Experience, Vol. 14, Issue 13-15, pp. 1175-1220, 2002.
[5]A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke, “The Data Grid: Towards an Architecture for the Distributed Management and Analysis of Large Scientific Datasets,” Journal of Network and Computer Applications, Vol. 23, Issue 3, pp. 187-200, 2000.
[6]R. Chu, N. Xiao, Y. Zhuang, Y. Liu, and X. Lu, “A Distributed Paging RAM Grid System for Wide-Area Memory Sharing,” 20th International Parallel and Distributed Processing Symposium, 2006.
[7]E. Elmroth and J. Tordsson, “A Grid Resource Broker Supporting Advance Reservations and Benchmark-Based Resource Selection,” State-of-the-art in Scientific Computing, Lecture Notes in Computer Science, Springer-Verlag, 2005.
[8]I. Foster, C. Kesselman, and S. Tuecke “The Anatomy of the Grid: Enabling Scalable Virtual Organizations,” International Journal of High Performance Computing Applications, Vol. 15, No. 3, pp. 200-222, 2001.
[9]I. Foster and C. Kesselman, “The Grid2: Blueprint for a New Computing Infrastructure,” Morgan Kaufmann Publishers, 2004.
[10]M.J. Feeley, W.E. Morgan, E.P. Pighin, A.R. Karlin, H.M. Levy, and C.A.Thekkath. “Implementing Global Memory Management in a Workstation Cluster,” 15th ACM Symposium on Operating Systems Principles, pp. 201-212, 1995.
[11]M. Hines, K.Gopalan and M. Lewandowsky, “Anemone: Adaptive Network Memory Engine”, poster for NSDI, 2nd Symposium on Network Systems Design and Implementation, Summer 2005.
[12]M. R. Hines, J. Wang, and K. Gopalan, “Distributed Anemone: Transparent Low-Latency Access to Remote Memory,” 13th International conference on High Performance Computing, pp. 509–521, 2006.
[13]S. Liang, R. Noronha, and D.K. Panda, “Swapping to Remote Memory over InfiniBand: An Approach using a High Performance Network Block Device,” IEEE International Conference on Cluster Computing, pp. 1-10, 2005.
[14]E. Markatos and G. Dramitinos, “Implementation of a Reliable Remote Memory Pager,” USENIX 1996 Annual Technical Conference, pp. 177-190, 1996.
[15]T. Newhall, S. Finney, K. Ganchev, and M. Spiegel, “Nswap: A Network Swapping Module for Linux Clusters,” International Conference on Parallel and Distributed Computing, Lecture Notes in Computer Science, pp. 1160-1169, 2003.
[16]J. Oleszkiewicz ,L. Xiao, and Y. Liu, "Parallel Network RAM: Effectively Utilizing Global Cluster Memory for Large Data-Intensive Parallel Programs", 33rd International Conference on Parallel Processing (ICPP 2004), Montreal, August, 2004.
[17]S. Pakin and G. Johnson, “Performance Analysis of a User-level Memory Server,” IEEE International Conference on Cluster Computing, pp. 249-258, 2007.
[18]G. Sun, H. Tang, M. Chen, and J. Fan, “A Scalable Dynamic Network Memory Service System,” High-Performance Computing in Asia-Pacific Region, 2005.
[19]P. Werstein, X. Jia, and Z. Huang, “A Remote Memory Swapping System for Cluster Computers,” 8th International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 75-81, 2007.
[20]N. Xiao, Y. Zhao, and W. Fu, “Skyhawk Grid System,” Asia Pacific Web, pp. 1045-1048, 2005
[21]王柏森，“一個再使用者階層上支援格網運算的遠端分頁系統”，碩士論文，國立高雄應用科技大學，2009
[22]HD Tune: http://www.hdtune.com/
[23]Nistnet: http://snad.ncsl.nist.gov/nistnet/