Responsive image
博碩士論文 etd-0728109-115706 詳細資訊
Title page for etd-0728109-115706
論文名稱
Title
CDPthread: 以POSIX-Thread為基礎之分散式運算環境
CDPthread: A POSIX-Thread Based Distributed Computing Environment
系所名稱
Department
畢業學年期
Year, semester
語文別
Language
學位類別
Degree
頁數
Number of pages
162
研究生
Author
指導教授
Advisor
召集委員
Convenor
口試委員
Advisory Committee
口試日期
Date of Exam
2009-07-20
繳交日期
Date of Submission
2009-07-28
關鍵字
Keywords
作業系統、執行序、分散式共享記憶體、分散式系統、多執行序
operating system, distributed system, POSIX, distributed shared memory, thread, multi-thread
統計
Statistics
本論文已被瀏覽 6243 次,被下載 1605
The thesis/dissertation has been browsed 6243 times, has been downloaded 1605 times.
中文摘要
因為單一電腦的運算能力有限,還有基於成本的考量,分散式的設計近年來越來越受歡迎。而在這個領域其中一個最熱門的研究主題就是Distributed Shared Memory(DSM)系統。DSM 系統的研究中,大部分的人都致力於發展新的函式庫或是新的語言來達到更好的效能。因此,程式設計師必須去學習這些新的函式庫或是新的語言。更重要的是,他們必須去處理資料在分散式環境同步的問題。本篇論文我們提出了一個與POSIX-Thread環境相容的系統,使用者對於系統中的分散屬性可以完全忽略。
Abstract
Due to the limitation of single machine’s computing power, and the aspect of cost, distributed design is getting more and more popular nowadays. The Distributed Shared Memory (DSM) system is one of the most hot topics in this area. Most people are dedicated on designing a library or even a new language, in order to gain higher performance on DSM systems. As a consequence, the programmers are required to learn a new library or language. Even more, they have to handle synchronizations for the distributed environment. In this paper, we propose a design that is compatible with POSIX-Thread Environment. The distributed nature of the system described herein is totally transparent to the programmers.
目次 Table of Contents
Chapter 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Distributed Parallel Computing Environments . . . . . . . . . . . . . . . . . 2
1.3 Distributed POSIX Thread Environment . . . . . . . . . . . . . . . . . . . . 2
Chapter 2 Related Works 3
2.1 MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 DSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Various Page Based DSM systems . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 POSIX Thread-like DSM systems . . . . . . . . . . . . . . . . . . . . . . . 4
2.5 POSIX Thread Compatible DSM systems . . . . . . . . . . . . . . . . . . . 5
Chapter 3 Basic Environment of CDPthread 6
3.1 Development Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.3 Software Dependency . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Running Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 4 Linux Memory Management 10
4.1 Virtual Memory of X86 Architecture . . . . . . . . . . . . . . . . . . . . . . 10
4.1.1 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.2 Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.1.3 Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1.4 Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Process Address Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Function Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 Stack Address Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 GNU libc malloc Implementation . . . . . . . . . . . . . . . . . . . . . . . 22
4.5.1 The brk() System Call . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5.2 The mmap() System Call . . . . . . . . . . . . . . . . . . . . . . . . 23
4.6 Stack Address for Multi-thread Environment . . . . . . . . . . . . . . . . . . 24
Chapter 5 CDPthread Implementation 25
5.1 CDPthread: Communication Layer . . . . . . . . . . . . . . . . . . . . . . . 25
5.1.1 Message Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.1.2 Communication Protocol . . . . . . . . . . . . . . . . . . . . . . . . 26
5.1.3 Receiving Message . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.1.4 Sending Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 CDPthread: Loader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3 CDPthread: Execution Engine . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.1 Memory Layout of Execution Engine . . . . . . . . . . . . . . . . . 33
5.3.2 Starting User Program in Execution Engine . . . . . . . . . . . . . . 37
5.3.3 Run-time Environment of Execution Engine . . . . . . . . . . . . . . 38
5.4 CDPthread: Control Server . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.5 CDPthread: Memory Synchronization Facilities . . . . . . . . . . . . . . . . 40
Chapter 6 Experimental Results 43
Chapter 7 Conclusion and Future Work 53
7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Appendix A Partial Source Code for the Communication Protocol of CDPthread 59
Appendix B Partial Source Code for the Execution Engine of CDPthread 86
參考文獻 References
[1] IEEE, “Standard for information technology - portable operating system interface (posix). shell and utilities,” IEEE Std 1003.1, 2004 Edition The Open Group Technical
Standard. Base Specifications, Issue 6. Includes IEEE Std 1003.1-2001, IEEE Std 1003.1-2001/Cor 1-2002 and IEEE Std 1003.1-2001/Cor 2-2004. Shell, pp. –, 2004.
[2] C. Amza, A. L. Cox, H. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel, “Treadmarks: Shared memory computing on networks of workstations,” IEEE Computer, vol. 29, pp. 18–28, 1996.
[3] A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. S. Sunderam, “Pvm: Parallel virtual machine,” in A Users Guide and Tutorial for Network Parallel Computing, pp. –, 1994.
[4] A. Bode, J. Dongarra, T. L. 0002, and V. S. Sunderam, eds., Parallel Virtual Machine - EuroPVM’96, Third European PVM Conference, M‥unchen, Germany, October 7-9, 1996, Proceedings, vol. 1156 of Lecture Notes in Computer Science, Springer, 1996.
[5] M. Bubak, J. Dongarra, and J. Wasniewski, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 4th European PVM/MPI Users’ Group Meeting, Crakow, Poland, November 3-5, 1997, Proceedings, vol. 1332 of Lecture Notes in Computer Science, Springer, 1997.
[6] H. Lu, H. Dwarkadas, A. L. Cox, and W. Zwaenepoel, “Quantifying the performance differences between pvm and treadmarks,” Journal of Parallel and Distributed Computing, vol. 43, pp. 65–78, 1997.
[7] V. N. Alexandrov and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 5th European PVM/MPI Users’ Group Meeting, Liverpool, UK, September 7-9, 1998, Proceedings, vol. 1497 of Lecture Notes in Computer Science, Springer, 1998.
[8] J. Dongarra, E. Luque, and T. Margalef, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 6th European PVM/MPI Users’ Group Meeting, Barcelona, Spain, September 26-29, 1999, Proceedings, vol. 1697 of Lecture Notes in Computer Science, Springer, 1999.
[9] J. Dongarra, P. Kacsuk, and N. Podhorszki, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 7th European PVM/MPI Users’ Group Meeting, Balatonf‥ured, Hungary, September 2000, Proceedings, vol. 1908 of Lecture Notes in Computer Science, Springer, 2000.
[10] Y. Cotronis and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 8th European PVM/MPI Users’ Group Meeting, Santorini/ Thera, Greece, September 23-26, 2001, Proceedings, vol. 2131 of Lecture Notes in Computer Science, Springer, 2001.
[11] D. Kranzlm‥uller, P. Kacsuk, J. Dongarra, and J. Volkert, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 9th European PVM/MPI Users’ Group Meeting, Linz, Austria, September 29 - October 2, 2002, Proceedings, vol. 2474 of Lecture Notes in Computer Science, Springer, 2002.
[12] J. Dongarra, D. Laforenza, and S. Orlando, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface,10th European PVM/MPI Users’ Group Meeting, Venice, Italy, September 29 - October 2, 2003, Proceedings, vol. 2840 of Lecture Notes in Computer Science, Springer, 2003.
[13] D. Kranzlm‥uller, P. Kacsuk, and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM/MPI Users’ Group Meeting, Budapest, Hungary, September 19-22, 2004, Proceedings, vol. 3241 of Lecture Notes in Computer Science, Springer, 2004.
[14] B. D. Martino, D. Kranzlm‥uller, and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 12th European PVM/MPI Users’ Group Meeting, Sorrento, Italy, September 18-21, 2005, Proceedings, vol. 3666 of Lecture Notes in Computer Science, Springer, 2005.
[15] B. Mohr, J. L. Tr‥aff, J. Worringen, and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 13th European PVM/MPI User’s Group Meeting, Bonn, Germany, September 17-20, 2006, Proceedings, vol. 4192 of Lecture Notes in Computer Science, Springer, 2006.
[16] F. Cappello, T. H′erault, and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 14th European PVM/MPI User’s Group Meeting, Paris, France, September 30 - October 3, 2007, Proceedings, vol. 4757 of Lecture Notes in Computer Science, Springer, 2007.
[17] A. L. Lastovetsky, T. Kechadi, and J. Dongarra, eds., Recent Advances in Parallel Virtual Machine and Message Passing Interface, 15th European PVM/MPI Users’ Group Meeting, Dublin, Ireland, September 7-10, 2008. Proceedings, vol. 5205 of Lecture Notes in Computer Science, Springer, 2008.
[18] K. L. Johnson, “High-performance all-software distributed shared memory,” tech. rep., Cambridge, MA, USA, 1996.
[19] K. Li and P. Hudak, “Memory coherence in shared virtual memory systems,” ACM Trans. Comput. Syst., vol. 7, no. 4, pp. 321–359, 1989.
[20] M. Tam and D. Farber, “Capnet-an approach to ultra high speed network,” pp. 955–961 vol.3, Apr 1990.
[21] N. C. J. Brett D. Fleisch, Randall L. Hyde, “Mirage+: A kernel implementation of distributed shared memory on a network of personal computers,” Software: Practice and Experience, vol. 24, no. 10, pp. 887–909, 1994.
[22] F. Mueller, “Distributed shared-memory threads: Dsm-threads,” in In Workshop on Run-Time Systems for Parallel Programming, pp. 31–40, 1997.
[23] M. Pizka and C. Rehn, “Murks - a posix threads based dsm system,” in Proceedings of the International Conference on Parallel and Distributed Computing Systems, pp. 642–648, 2001.
[24] C. Eckert and M. Pizka, “Improving resource management in distributed systems using language-level structuring concepts,” J. Supercomput., vol. 13, no. 1, pp. 33–55, 1999.
[25] H. L‥of, Z. Radovic, and E. Hagersten, “Throom - supporting posix multithreaded binaries on a cluster,” in Euro-Par (H. Kosch, L. B‥osz‥orm′enyi, and H. Hellwagner, eds.), vol. 2790 of Lecture Notes in Computer Science, pp. 760–769, Springer, 2003.
[26] E. Hagersten and M. Koster, “Wildfire: a scalable path for smps,” pp. 172–181, Jan 1999.
[27] Intel 64 and IA-32 Architectures Software Developer’s Manual, vol. 1. Intel Corporation, November 2007.
[28] Intel 64 and IA-32 Architectures Software Developer’s Manual, vol. 2a. Intel Corporation, November 2007.
[29] Intel 64 and IA-32 Architectures Software Developer’s Manual, vol. 2b. Intel Corporation, November 2007.
[30] Intel 64 and IA-32 Architectures Software Developer’s Manual, vol. 3a. Intel Corporation, November 2007.
[31] Intel 64 and IA-32 Architectures Software Developer’s Manual, vol. 3b. Intel Corporation, November 2007.
電子全文 Fulltext
本電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
論文使用權限 Thesis access permission:校內校外完全公開 unrestricted
開放時間 Available:
校內 Campus: 已公開 available
校外 Off-campus: 已公開 available


紙本論文 Printed copies
紙本論文的公開資訊在102學年度以後相對較為完整。如果需要查詢101學年度以前的紙本論文公開資訊,請聯繫圖資處紙本論文服務櫃台。如有不便之處敬請見諒。
開放時間 available 已公開 available

QR Code