因為單一電腦的運算能力有限，還有基於成本的考量，分散式的設計近年來越來越受歡迎。而在這個領域其中一個最熱門的研究主題就是Distributed Shared Memory(DSM)系統。DSM 系統的研究中，大部分的人都致力於發展新的函式庫或是新的語言來達到更好的效能。因此，程式設計師必須去學習這些新的函式庫或是新的語言。更重要的是，他們必須去處理資料在分散式環境同步的問題。本篇論文我們提出了一個與POSIX-Thread環境相容的系統，使用者對於系統中的分散屬性可以完全忽略。

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.

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

[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.