臺灣博碩士論文加值系統

在最近這幾年中，叢集計算已經成為可以節省成本的計算方法。因為它集合了資源的計算的能力、通訊以及儲存的空間。它同時也被認為是最吸引人的低成本之超級計算平台。分散式共享記憶體提供了方便而且有效率的方法讓程式在Linux叢集式系統上平行化的執行。
在分散式共享記憶體中，由於是使用各台電腦的實體記憶體去形成一個廣域的共享的記憶體，因此共享記憶體是分散在各台電腦上，所以當要存取資料時，便會經常需要到遠端的電腦上去存取所要用到的資料。因此，它造成了遠端存取的效能延遲，這也正是分散式共享記憶體系統負擔的主要因素。現在有許多策略可以用來改善這個問題。而在這些策略當中，先取策略可以有不錯的效能。先取策略可以藉由先取的動作以達到減少遠端存取的延遲進而達到改善這些現象。但是，它卻也增加了擁有頁擁有權的電腦的工作量。而且，在做先取的動作時，其他的電腦必須等待擁有頁擁有權的電腦去傳送先取策略的資料，若是擁有頁擁有權的電腦得傳送先取策略的資料給許多電腦的話，其他電腦將會花費許多時間在等待擁有頁擁有權的電腦上。
因此我們提出一個方法用以減少擁有頁擁有權的電腦的負擔，它是藉由暫時提供一個代理主機去分擔擁有頁擁有權的電腦的工作量，讓擁有頁擁有權的電腦在傳送先取策略的資料時，能夠把工作量分散給其他的電腦，讓其他的電腦能夠代為傳送先取策略的資料。透過這樣的方式可以降低擁有頁擁有權的電腦的工作負擔，達到平衡各台電腦的工作量，以減少等待的時間。

In recent years, the cluster computing technology has become a cost-effective computing infrastructure, because it aggregates resources of computational power, communication and storage. It is also considered a very attractive platform for low-cost supercomputing. Software distributed shared memory（DSM）provides a convenient and effective solution for programming parallel applications on Linux-based Cluster systems.
In distributed shared memory（DSM）systems, it uses physical memories of each computer to form a global shared memory. Otherwise, shared memory is distributed on each computer so it is the common need to access data in remote nodes. Thus, it induces remote access latencies, what is the major factor of overhead for DSM systems. There are many strategies can improve this problem. Prefetching strategies can improve these phenomena by reducing latencies, but it adds workload to home nodes. When proceeding prefetching, other nodes need to wait home node to transfer prefetching data. If home node needs to transfer prefetching data to many nodes, other nodes will spend a lot of time on waiting home node.
We propose a method to reduce overhead of home nodes, by providing an agent home to share the workload of home nodes, by distributing these workloads to other nodes when sending data. That let other nodes can transfer prefetching data for home node. By this way, we can reduce workload of home node, achieve balancing workload of each node, and reduce waiting time.

Chinese Abstract i
English Abstract ii
Acknowledgement iii
Contents iv
List of Tables vi
List of Figures vii

Chapter 1 Introduction..................................................1
1.1 Overview..............................................................2
1.2 Motivation............................................................4
1.3 Objective.............................................................5
1.4 Organization..........................................................6
Chapter 2 Related Work..................................................7
2.1 Related Consistency Models........................................... 8
2.2 Home-based and Homeless Protocol.....................................11
2.3 Adaptive Home-Based Lazy Release Consistency.........................13
2.4 Prefetching Strategies...............................................15
2.4.1 History Prefetching Strategy.......................................16
2.4.2 Aggregate Prefetching Strategy.....................................17
2.4.3 Effective Prefetching Strategy .................. ......... ......... 19
2.5 Comparisons between Our Agent Home Strategy and Other Methods........ 21
Chapter 3 Agent Home Strategy.......................................... 22
3.1 Overview.............................................................22
3.2 Agent Home of Prefetching Strategy...................................24
3.2.1 Concept............................................................ 24
3.2.2 Method............................................................. 26
Chapter 4 Implementation...............................................29
4.1 Memory Organization of JIAJIA........................................29
4.2 System Architecture of JIAJIA........................................30
Chapter 5 Performance Evaluation....................................... 32
5.1 Execution Time .......................................................33
5.2 SEGV Time............................................................35
5.3 Barrier Time.........................................................37
5.4 Communication Time...................................................39
5.5 Transport Message Count..............................................41
Chapter 6 Conclusions and Future Work..................................45
6.1 Conclusion........................................................... 45
6.2 Future Work.......................................................... 45
Reference ................................................................47
Vita.....................................................................51

Appendic A 3DFFT code..................................................52
Appendix B Red-Black SOR code..........................................66
Appendix C IS code.....................................................69
Appendix D LU code.....................................................74

[1]T. Abe and S. Okamoto, “A Moving Home-based Software DSM System,” in the Proceedings of Communication, Computers and Signal Processing, Volume：1, pp. 17-20, Aug 28-30, 2003.
[2]JASON A. CRAWFORD and CLARK M. MOBARRY, “HRUNTING：A Distributed Shared Memory for the BEOWULF Parallel Workstation”, Aerospace Conference, 1998.
[3]J. W. Chung, B. H. Seong, K. H. Park, et al., “Moving home-based lazy release consistency for shared virtual memory systems,” in the Proceedings of the International Conference on Parallel Processing, pp. 282-290, September 1999.
[4]H. CHEONG and A. V. VEIDENBAUM, “A cache coherence scheme with fast selective invalidation,” in the Proceedings of the 15th Annual Symposium on Computer Architecture, pp. 299-307, June 1988
[5]B. Cheung, C. L. Wang, and K. Hwang, “A migrating-home protocol for implementing scope consistency model on a cluster of workstations,” in the Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, pp. 821-827, June 1999.
[6]B. W. L. Cheung, C. L. Wang, and Francis Chi-Moon Lau, “Migrating-Home Protocol for Software Distributed Shared Memory,” Journal of Information Science and Engineering 18, pp. 929-957, 2002.
[7]M.R.Eskicioglu, T.A. Marsland, Weiwu Hu, and Weisong Shi, “Evaluation of the JIAJIA software DSM system on high performance computer architectures,” in the Proceedings of the 32nd Annual Hawaii International Conference on System Sciences（HICSS-32）, Volume Track8, pp, 5-8, Jan. 1999.
[8]J. R. GOODMAN, “Cache Consistency and Sequential Consistency,” Technical Report TR1006, Computer Sciences Department, University of Wisconsin-Madison, Feb. 1991.
[9]W. Hu, W. Shi, and Z. Tang. “JIAJIA：An SVM System Based on a New Cache Coherence Protocol,” in the Proceedings of the High Performance Computing and Networking（HPCN ’99）, pp. 463-472, April 1999.
[10]Weiwu Hu, Weisong Shi, and Zhimin Tang, “Write Detection in Home-based Software DSMs,” in the Proceedings of the EuroPar''99, August 31-September 2, 1999.
[11]Weiwu Hu, Weisong Shi, and Zhimin Tang, “Reducing system overheads in home-based software DSMs,” in the Proceedings of 13th International and 10th Symposium on Parallel and Distributed Processing, pp. 167-173, 12-16 Apr 1999.
[12]W. Hu, W. Shi, and Z. Tang, “Home migration in home based software DSMs,” in the Proceedings of ACM 1st Workshop on Software DSM System, June 1999.
[13]W. Hu, W. Shi, and Z. Tang, “Optimizing Home-Based Software DSM Protocols,” Journal of Networks, Software Tools and applications, Baltzer Science Publishers, 4（3）, pp. 235-242, Jul 2001.
[14]W. Hu, W. Shi, Z. Tang, and M. Li, “A Lock-based Cache Coherence Protocol for Scope Consistency,” Journal of Computer Science and Technology , Vol 13, No. 2, pp. 97-110, 1998.
[15]W. Hu, F. Zhang and H. Liu, “Dynamic Data Prefetching in Home-based Software DSM,” Journal of Computer Science and Technology, May 2001.
[16]Weiwu Hu, Fuxin Zhang, Li Ren, Weisong Shi, and Zhimin Tang, “Running Real Applications on Software DSMs,” in the Proceedings of The Fourth International High Performance Computing in the Asia-Pacific Region, vol.1, pp. 148 -153, 14-17 May, 2000.
[17]Vadim Iosevich and Assaf Schuster, “A Comparison of Sequential Consistency with Home-Based Lazy Release Consistency for Software Distributed Shared Memory,” in the Proceedings of the 18th annual international conference on Supercomputing, pp. 306-315, June 2004.
[18]L. Iftode, J. P. Singh, and K. Li, “Scope Consistency：A Bridge Between Release Consistency and Entry Consistency,” in the Proceedings of the 8th Annual ACM Symposium on Parallel Algorithm and Architectures, June 1996.
[19]Hai Jiang and Chaudhary V., ”MigThread: thread migration in DSM systems,” in the Proceedings of the International Conference on Parallel Processing, pp. 581-588, Aug 18-21, 2002.
[20]P. Keleher, A. L. Cox, and W. Zwaenepowl, “Lazy release consistency for software distributed shared memory,” in the Proceedings of the 19th Annual International Symposium on Computer Architecture, pp. 12-31, 1992.
[21]H. Liu and W. Hu, “A Comparison of Two Strategies of Dynamic Data Prefetching in Software DSM,” Parallel and Distributed Processing Symposium, IEEE Proceedings 15th International, 2001.
[22]Ssu-Hsuan Lu, Chun-Chieh Yang, Hsiao-Hsi Wang, Kuan-Ching Li, “On Design of Agent Home Scheme for Prefetching Strategy in DSM Systems,” in the Proceedings of The 19th IEEE International Conference on Advanced Information Networking and Applications（AINA''2005）, Volume 1, pp. 693-698, March 2005.
[23]Kuo-Jen Wang, On the Design and Implementation of an Effective Prefetch Strategy on DSM System, Providence University, Dept. of Computer Science and Information Management, Master Thesis, Taipei, Taiwan, R.O.C., June 2004.
[24]Song Peng and Speight E., “Utilizing Home Node Prediction to Improve the Performance of Software Distributed Shared Memory,” in the Proceedings of 18th International Parallel and Distributed Processing Symposium, pp. 59 – 68, April 26-30, 2004.
[25]Weisong Shi, Improving the Performance of Software DSM Systems, Chinese Academy of Sciences, Institute of Computing Technology, Dept. of Computer Sciences, Doctor Thesis, Beijing, China, 1999.
[26]A. S. TANENBAUM, Distributed Operating System, PRENTICE HALL INTERNATIONAL EDITIONS, 1995.
[27]A. S. TANENBAUM, Distributed System：Principles and Paradigms, PRENTICE HALL INTERNATIONAL EDITIONS, 2002.
[28]J.F. Tu, Y.H. Wang, and L.H. Wang, “A dynamic data prefetching method of improving the memory latency,” in the Proceedings of International Conference on High Performance Computing in the Asia-Pacific Region, vol.1, pp. 13 -18, 2000.
[29]K. J. Wang, H. H. Wang, and K. C. Li, “On Design of a Prefetching Strategy for DSM System”, in PDPTA''2004 International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, 2004
[30]B. H. Yu, Z. Huang, S. Cranefield, and M. Purvis, “Homeless and Home-based Lazy Release Consistency Protocols on Distributed Shared Memory,” in the Proceedings of the 27th conference on Australasian computer science, Dunedin, New Zealand, vol. 26 , pp. 117-123, 2004.
[31]H. C. Yun, S. K. Lee, J. Lee, and S. Maeng, “An Efficient Lock Protocol for Home-based Lazy Release Consistency,” in the Proceedings of Cluster Computing and the Grid, 2001
[32]Y. Zhou, L. Iftode, and K. Li, “Performance Evaluation of Two Home-based Lazy Release Consistency Protocols for Shared Virtual Memory Systems,” in the Proceedings of the Second USENIX Symposium on Operating System Design and Implementation, pp. 75-88, November 1996.
[33]D. A. RUSLING, “The Linux Kernel,” Website. http://www.linuxhq.com/guides/TLK/tlk.html