臺灣博碩士論文加值系統

　OpenMP API is a widely accepted parallel programming model for shared memory computers. In this paper, we present an implementation of OpenMP API on Teamster-G that is a grid-enabled software distributed shared memory (DSM) system that allows users to run the programs in computational grids. With the support of OpenMP API, Teamster-G can provide programmers to develop grid applications as they do on shared memory computers. Although grid computing allows users to solve large-scale computation problems with individual PCs, workstations or supercomputers on the Internet, but programmers can only use the programming toolkits such as MPICH-G2, Java CoG kits or GridRPC to develop grid applications based on message passing and remote procedure call operations that are complex and cumbersome for the programmers. In order to simplify programming, it is necessary to support a shared-memory programming model on grids. On the other hand, we propose Profiled Multiprocessor Scheduling in OpenMP API to improve load imbalance between the execution nodes they are not identical in computational power.

Contents i
Tables ii
Illustrations iii
Chapter 1 Introduction 1
Chapter 2 Background 5
2.1 OpenMP 5
2.2 Software Distributed Shared Memory System 9
2.2.1 Overview 9
2.2.2. Teamster-G 10
Chapter 3 Design Issues 14
3.1 Source Code Compatibility 14
3.2 Dynamic Load Distribution 18
Chapter 4 Implementation 22
4.1 OpenMP Compiler 22
4.1.1 Initialization of global variables 24
4.1.2 Memory allocation function 25
4.2 OpenMP Runtime Library 26
4.3 Dynamic Load Distribution 29
Chapter 5 Performance 31
5.1 Source Code Compatibility 32
5.2 Application Performance 33
5.3 Performance of Dynamic Load Distribution 36
Chapter 6 Related Works 40
Chapter 7 Conclusions and Future Work 46
Bibliography 48

[1] Foster I, Kesselman C (eds.), “The Grid: Blueprint for a Future Computing Infrastructure,” Morgan Kaufmann: San Francisco, CA, 1999.
[2] Mark Baker, Rajkumar Buyya, Domenico Laforenza, “Grids and Grid Technologies for Wide-Area Distributed computing,” International Journal of Software: Practice and Experience (SPE), Volume 32, Issue 15, pp.1437-1466, 2002.
[3] V. Sunderam, “PVM: A Framework for Parallel Distributed Computing,” Concurrency: Practice and Experience, 2(4), December 1990.
[4] Message-passing Interface Forum, “MPI: A Message-Passing Interface Standard,” International Journal of Supercomputer Applications and High Performance Computing, vol. 8, no. 3/4, Fall/Winter 1994, pp.159-416.
[5] Andrew Birrell, Bruce Nelson, “Implementing Remote Procedure Calls,” ACM Transitions on Computer Systems, 2(1): p35-39, Feb. 1984.
[6] Sun Microsystems Inc., Mountain View, CA. Java Remote Method Invocation Specification, beta draft, 1996.
[7] K. Li, “IVY: A shared virtual memory system for parallel computing,” In Proc. of the 1988 International Conference on Parallel Processing (ICPP'88), vol. 2, pp.94-101.
[8] J. B. Carter, J. K. Bennett, W. Zwaenepoel, “Implementation and Performance of Munin,” In Proc. of 13th ACM Symposium on Operating System Principles, p.152-164, 1994.
[9] E. Speight, J. K. Bennett. “Brazos: A third generation DSM system,” In Proc. of the 1997 USENIX Windows/NT Workshop, pp.95-106, 1997.
[10] The OpenMP Forum. OpenMP C and C++ Application Program Interface, Version 1.0. http://www.openmp.org, Oct. 1998.
[11] The OpenMP Forum. OpenMP Fortran Application Program Interface, Version 1.0. http://www.openmp.org, Oct. 1997.
[12] C. Amza, A. L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, W. Zwaenepoel. “TreadMarks: Shared Memory Computing on Networks of Workstations,” IEEE Computer, 29 (2): p18-28, February 1996.
[13] Honghui Lu, Y. Charlie Hu, Willy Zwaenepoel, “OpenMP on networks of workstations,” In Proc. of the 1998 ACM/IEEE conference on Supercomputing (CDROM), Nov. 1998.
[14] Alex Scherer, Honghui Lu, Thomas Gross, Willy Zwaenepoel, “Transparent Adaptive Parallelism on NOWs using OpenMP,” In Proc. of the 7th ACM SIGPLAN symposium on Principles and practice of parallel programming, May. 1999.
[15] Alex Scherer, Honghui Lu, Thomas Gross, Willy Zwaenepoel, “Transparent Adaptive Parallelism on NOWs using OpenMP,” In Proc. of the 7th ACM SIGPLAN symposium on Principles and practice of parallel programming, May. 1999.
[16] Y. Ojima, M. Sato, H. Harada, Y. Ishikawa, “Performance of Cluster-enabled OpenMP for the SCASH Software Distributed Shared Memory System,” In Proc. of the 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID'03).
[17] Weiwu Hu, Weisong Shi, Zhimin Tang, “JIAJIA: An SVM System Based on A New Cache Coherence Protocol,” In Proc. of the High Performance Computing and Networking (HPCN'99), pp.463-472.
[18] Zhang Feng, Chen Guoliang, Zhang Zhaoqing, “OpenMP on Networks of Workstations for Software DSMs,” In Journal of Computer Science and Technology, Jan. 2002.
[19] Y.Tanaka, M. Matsuda, M. Ando, K. Kazuto, M. Sato, “COMPaS: A Pentium Pro PC-based SMP Cluster and its Experience,” IPPS Workshop on Personal Computer Base4d Networks of Workstations, LNCS 1388, pp. 486-497, 1998.
[20] Mitsuhisa Sato, Shigehisa Satoh, Kazuhiro Kusano, Yoshio Tanaka, “Design of OpenMP Compiler for an SMP Cluster,” In Proc. of the 1st European Workshop on OpenMP (EWOMP'99), pp 32-39, Sep. 1999.
[21] Yang-Suk Kee, Jin-Soo Kim, Soonhoi Ha, “ParADE: An OpenMP Programming Environment for SMP Cluster Systems,” In Supercomputing Conference ‘03, pp.15-21, November, 2003.
[22] Tyng-Yeu Liang, Chun-Yi Wu, Jyh-Biau Chang, Ce-Kuen Shieh, “Teamster-G: A Grid-enabled Software DSM System,” Workshop of DSM'05 at CCGRID 2005. 9-12 May 2005, Cardiff, UK.
[23] OpenMP Architecture Review Board, “OpenMP: Simple, Portable, Scalable SMP Programming,” 1997. http://www.openmp.org/.
[24] Foster I, Kesselman C, “Globus: A Meta-Computing Infrastructure Toolkit,” International Journal of Supercomputer Applications 11(2): pp.115-128, 1997.
[25] Nicholas T. Karonis, Brian R. Toonen, Ian T. Foster, “MPICH-G2: A Grid-enabled implementation of the Message Passing Interface,” Journal of Parallel Distributed Computing, 63(5): p.551-563, 2003.
[26] Von Laszewski G., Foster I., Gawor J., Smith W., Tuecke S, “CoG Kits: A Bridge between High Performance Grid Computing and High Performance Grids,” ACM 2000 Grade Conference. http://www.globus.org/.
[27] K. Seymour, H. Nakada, S. Matsuoka, D. Dongarra, C. Lee and H. Casanova, “GridRPC: A remote procedure call API for Grid Computing,” ICL Technical Report ICL-UT-02-06, Innovative Computing Laboratory, Department of Computer Science, University of Tennessee, June 2002.
[28] David E. Culler, Jaswinder Pal Singh, Anoop Gupta, “Parallel Computer Architecture,” Morgan Kaufmann, San Francisco, CA, 1999.
[29] Ralf S. Engelschall, “GNU Pth - The GNU Portable Threads.” http://www.gnu.org/software/pth/
[30] D. Bailey et al., “The NAS Parallel Benchmarks,” Technical Report RNR-94-07, NASA Ames Research Center, Mar 1994.
[31] J. Bircsak, P. Craig, R. Crowell, J. Harris, C. A. Nelson, C. D. Offner, “Extending OpenMP for NUMA Machines: The Language,” In Proc. of Workshop on OpenMP Applications and Tool (WOMPAT’2000), July 2000. San Diego, USA.
[32] A. Hasegawa, M. Sato, Y. Ishikawa, H. Harada, “Optimization and Performance Evaluation of NPB on Omni/OpenMP Compiler for SCASH, Software Distributed Memory System (in Japanese),” In IPSJ SIG Notes 2001-ARC-142, 2001-HPC-85, pp.181-186, Mar 2001.
[33] J. Merlin, “Distributed OpenMP: Extensions to OpenMP for SMP Clusters,” In Invited Talk, Second European Workshop on OpenMP (EWOMP’00). Edinburgh, Scotland.
[34] D. S. Nikolopoulos, T. S. Papatheodorou, C. D. Polychronopoulos, J. Labarta, E. Ayguade, “Is Data Distribution Necessary in OpenMP?” in Proc. of Supercomputing 2000. Nov 2000. Dallas, TX.
[35] Y. Sakae, S. Matsuoka, M. Sato, H. Harada. “Preliminary Evaluation of Dynamic Load Balancing Using Loop Re-partitioning on Omni/SCASH,” In Proc. of the 3th IEE/ACM International Symposium on Cluster Computing and the Grid/DSM (DSM2003: Distributed Shared Memory on clusters workshop @ CCGrid), pp. 463-470. IEEE/ACM. May 2003. Tokyo, Japan.
[36] Y. Sakae, S. Matsuoka, M. Sato, H. Harada, “Implementation and Evaluation of Dynamic Load Balancing using Loop Re-partitioning and Page Migration on Omni/SCASH,” In 4th International Workshop on OpenMP: Experiences and Implementations (WOMPEI2005), pp. 26-33, January 2005.
[37] H. Harada, Y. Ishikawa, A. Hori, H. Tezuka, S. Sumimoto, T. Takahashi, “Dynamic Home Node Reallocation on Software Distributed Shared Memory System,” In Proc. of IEEE 4th HPC ASIA 2000, pp.158-163. May 2000.