Glenn R. Luecke and Wei-Hua Lin

August 16, 2000

1. Introduction

It is well known that writing programs for distributed memory parallel computers is often significantly more difficult than writing programs for shared memory parallel computers. It is also well known that shared memory parallel computers do not scale well to hundreds of processors whereas distributed memory parallel computers can scale well to hundreds of processors. Thus, those who need hundreds of processors to execute their programs are currently forced to write programs for distributed memory computers with MPI [2] instead of writing their programs for shared memory computers with OpenMP [1]. The SGI Origin 2000 is a "hybrid" between shared and distributed memory since memory is physically distributed among nodes (each node has two processors sharing a common memory) but there is a single address space for all memory. Programmers have the option of writing their parallel programs using either OpenMP or MPI on this machine. The purpose of this paper is to investigate the scalability and performance of seven simple OpenMP test programs and to compare their performance with equivalent MPI programs on an SGI Origin 2000.

The SGI Origin 2000 used for this study is a 128-processor machine located in Eagan, Minnesota, with 64 nodes with each node consisting of two 300 MHz MIPS R12000 processors sharing a common memory. This processor has two levels of cache. The primary data-cache and instruction-cache are both two-way set associative, each of size 32*1024 bytes. The 8*1024*1024 byte secondary cache is used for both data and instructions. The communication network is a hypercube for up to 32 processors. For more than 32 processors, multiple hypercubes are interconnected via a CrayLink Interconnect, see [3] for more information. All programs were written in Fortran 90 using version 7.3.1.m, compiled with optimization (O3) and 64 bit mode (-64), and using IRIX 6.5. All tests were run one at a time with nobody else using the machine.

Timing were done by first flushing the caches on all processors by changing the values in the real*8 array flush(8*1024*1024/8). Thus, flush has the size of the secondary cache, 8 Mbytes. The cache was flushed by adding .0000123 to flush; however, any number small enough to prevent floating point overflow would also work. Throughout this paper, p is the number of processors/threads used and ntest is the number of timing tests performed in a single job. ntest was set to 100 for all tests. For the OpenMP tests, the following was used for timing.

integer,parameter :: ntest=100

real*8 :: time(ntest), local_time(p,ntest)

. . .

The following was used to time the MPI tests.

integer,parameter :: ntest=100

real*8 :: time(ntest), local_time(ntest)

. . .

do k = 1, ntest

flush = flush + .0000123 ! flush the cache

call mpi_barrier(mpi_comm_world,ierror)

t = timef()

... MPI code to be timed ...

local_time(k) = timef() - t

call mpi_barrier(mpi_comm_world,ierror)

A(k) = A(k) + flush(k) ! prevent loop splitting

enddo

call mpi_reduce(local_time,time,ntest,mpi_real8,mpi_max,0,mpi_comm_world,ierror)

time = 0.001d0*time ! time in seconds

The first barrier in both of the above code segments is to ensure that all processors reach this point before starting the timing by calling the wall-clock timer. The second barrier is to make sure all processors have completed the "code to be timed". To prevent the compiler from splitting out the cache flushing, the statement "A(k) = A(k) + flush(k)" was added, where A is an array involved in the communication being timed. To prevent the compiler from considering part of all of the "code to be timed" as dead code and eliminating it, later in the program the value of A(1) and flush(1) were written. Each processor/thread records its time in local_time. The maximum over all processors/threads is then stored in the time array.

Figure 1 shows times in seconds for 100 trials for the dot product test with n = 10240 and p = 128, where p is the number of processors used. Notice that there are several "spikes" in the data with the first spike being the first timing. This kind of behavior is typical of the data found for all tests. The first timing usually was significantly longer than most of the other timings (likely due to the additional setup time required for the first call to subroutines and functions), so the time for the first trial was always removed. The other spikes are probably due to the operating system interrupting the execution of the program. The average of the 99 trials (the first trial is removed) is 14.3 milliseconds, which is much longer than most of the other trials. The authors decided to measure times for each operation by first filtering out the spikes as follows. Compute the median value after the first time trial is removed. All times that are greater than 1.8 times this median value are then removed. The authors considerate it to be inappropriate to remove more than 10% of the data. If more than 10% of the data is removed by the above procedure then only the largest 10% of the spikes are removed. Using this procedure, the filtered value for the time for figure 1 is 5.4 milliseconds instead of 14.3 milliseconds.

Figure 1. 100 trials for the OpenMP Dot Product test with n = 10240 and p = 128.

On the SGI Origin 2000, data for MPI programs is local to the executing processor unless there is not enough local memory. When there is not enough local memory, memory on the other nodes is used. There was sufficient local memory for all the tests in this paper. OpenMP is designed for shared memory machines and hence does not contain any data distribution directives. Since the memory on the SGI Origin is not physically shared, SGI provides data distribution directives to allow users to specify how data is placed on processors. If no data distribution directives are used, then data is automatically distributed via the "first touch" mechanism [3] which places the data on the processor where it is first used. Since placement of data can significantly affect performance, data distribution directives were used for each test. There are two sets of data distribution directives available on the Origin: the !$sgi distribute directives, and the !$sgi distribute_reshape directives, see [3]. All tests use the !$sgi distribute_reshape in order to ensure that the data is distributed as specified. To illustrate the difference in performance of OpenMP with and without data distribution directives, test 3 with n = 4*1024*1024/8 was run without data distribution directives. The resulting time was about four times longer without data distribution directives than with data distribution directives.

For all tests p denotes the number of processes/threads used for the test. All floating-point variables are declared as real*8. Unless specified differently, arrays x and y are declared as real*8. The integer variables rank and thread indicate the rank/thread of the executing processor. Except for the ping-pong test, all tests were run with p = 8, 16, 32, 64, and 128. All !$omp do directives are scheduled with the static option to ensure that arrays are distributed as desired. There are three possible scheduling options for !$omp do directives: static, dynamic, and guided. Testing showed that the static option always provided the best performance for the machine used.

The purpose of this test is to compare the performance of OpenMP and MPI implementations of the time for sending messages between "close" and "distant" processors. This was done by measuring the time to ‘ping pong’ array A from processor 0 to processor 1, from processor 0 to processor 2, …, from processor 0 to processor p-1. Each ‘ping pong’ is timed separately, as indicated in section 3. Arrays A and B are block distributed across p processors for the OpenMP implementation. Notice that for both the MPI and OpenMP versions of this test, both processors send A and use B instead of A to receive the message. If A were also used to receive the message, this would place A in the cache of this processor so the subsequent sending of A would likely be faster than the first send.

One must call the barrier twice in the OpenMP code since mpi_recv is blocking. The OpenMP code used is:

real*8 :: A(n*p), B(n*p)

!$sgi distribute_reshape A(block), B(block)

. . .

!$omp parallel shared(A,B) private(thread,i,j,k)

thread = omp_get_thread_num()

do j = 1, p-1

do k = 1, ntest

. . .

t = timef() !! Start Timer

if (thread == j) B(j*n + 1:j*n+n) = A(1:n)

!$omp barrier

if (thread == 0) B(1:n) = A(j*n + 1:j*n + n)

!$omp barrier

local_time(omp_get_thread_num(),k) = timef()-t !! End of Timer

. . .

enddo

enddo

!$omp end parallel

Notice that since A is block distributed among p threads and has n*p elements, A(1:n) is on thread 0 and A(j*n + 1,j*n + n) is on thread j.

The MPI code used is:

real*8 :: A(n), B(n)

. . .

do j = 1, p-1

do k = 1, ntest

. . .

t = timef() !! Start Timer

if (rank == 0) then

call mpi_send (A,n,mpi_real8,j,1, mpi_comm_world,ierr)

call mpi_recv(B,n,mpi_real8,j,2,mpi_comm_world,status,ierr)

endif

if (rank == j) then

call mpi_recv(B,n,mpi_real8,0,2,mpi_comm_world,status,ierr)

call mpi_send (A,n,mpi_real8,0,1, mpi_comm_world,ierr)

endif

local_time(k) = timef() – t !! End of Timer

. . .

enddo

enddo

Figures 2 and 3 contain the results in milliseconds for sending 4 Mbyte and 8 Byte messages, respectively. For a "perfectly" scalable computer, these graphs would be horizontal lines. This is not the case in figures 2 and 3, but the OpenMP version does give graphs that are closer to a horizontal line than the MPI version. Notice that for 4 Mbyte messages the OpenMP version is about 2.5 times slower than the MPI version. For the 8 Byte message, the OpenMP version is a little faster than the MPI version. The authors do not know why the OpenMP version is so slow for large messages.

Figure 3. Test 1 for an 8 Byte message.

real*8 :: A(n*p), B(n*p)

!$sgi distribute_reshape A(block), B(block)

. . .

!$omp parallel private(i, j, k) shared(A, B)

. . .

t = timef() !! Start Timer

j = omp_get_thread_num()

i = modulo(j+1,p)

local_time(omp_get_thread_num(),k) = timef() - t !! End of Timer

!$omp end parallel

For the MPI implementation, processor of rank k sends array A(1:n) to processor (k+1), modulo(p), and receives B(1:n) from processor (k-1), modulo(p); for k = 0, p-1.

real*8 :: A(n), B(n)

. . .

t = timef() !! Start Timer

local_time(k) = timef() – t !! End of Timer

Figures 4 and 5 contain the performance results for the right shift test for 4 Mbyte and 8 Byte messages, respectively. In a "perfectly" scalable computer, all right shifts would be executed concurrently and hence the time would be independent of the number of processors and the graphs would be horizontal lines. The graphs in figure 4 for the 4 Mbyte message are roughly horizontal lines for 32 to 128 processors. However, the MPI implementation for the 8 Byte message is far from a horizontal line and performs significantly worse than the OpenMP implementation. For the 4 Mbyte messages, the MPI implementation is roughly 1.3 times faster than the OpenMP implementation. There appears to be a significant performance problem with SGI’s implementation of mpi_sendrecv for small messages.

Figure 4. Test 2 results in milliseconds for 4 MByte messages.

This test measures the time to sum the components of a one-dimensional array A whose elements are block distributed across p processors in the OpenMP implementation. The following is the OpenMP code.

real*8 :: A(n*p)

!$sgi distribute_reshape A(block)

sum = 0.0

!$omp parallel shared(A,sum)

!$omp do schedule(static),reduction(+:sum)

do j = 1, n*p

sum = sum + A(j)

enddo

!$omp enddo

local_time(omp_get_thread_num(), k) = timef() – t !! End of Timer

. . .

!$omp end parallel

For the MPI implementation, s stores the values of the local sums and sum holds the value of the sum of all components of the array. The MPI code used for this test is.

Figures 6 and 7 contain the performance results for this test for n = 4*1024*1024/8 and n = 1, respectively. Since the "reduction(+:sum)" option was used in the OpenMP implementation, one would expect the OpenMP implementation to perform well compared to the MPI implementation. However, the OpenMP implementation does not scale nearly as well as the MPI implementation for n = 1. They do perform about the same for n = 4*1024*1024/8. The OpenMP code could have also been written by first adding local sums and then updating the global sum variable in a critical region. However, the performance of this modified code is a little worse than when the above code is executed.

Figure 6. Test 3 results in milliseconds for n = 4*1024*1024/8.

Figure 7. Test 3 results in milliseconds for n = 1.

This test compares the performance for calculating the dot product of two arrays x and y using OpenMP and MPI. Elements of x and y are block distributed across p processors for the OpenMP implementation. The OpenMP code used for this test is.

!$sgi distribute_reshape x(block), y(block)

!$omp parallel shared(sum, x, y)

!$omp do schedule(static),reduction(+:sum)

do i =1, n*p

!$omp enddo

local_time(omp_get_thread_num(), k) = timef() – t !! End of Timer

. . .

!$omp end parallel

For the MPI implementation, s stores the values of the local sums and sum holds the value of the dot product of x and y. The MPI code used for this test is.

real*8 :: x(n), y(n)

. . .

s = 0.0

Figures 8 and 9 contain the performance results for this test for n = 80*1024/8 and n = 1, respectively. Notice that the times for n = 80*1024/8 in figure 8 are nearly the same as those for n = 1 in figure 9. This is because the time required for the extra additions is small compared with the rest of the time. In both cases, the MPI implementation performs and scales better than the OpenMP implementation. There appears to be a significant performance problem with OpenMP for this test even though the "reduction(+:sum)" option was used.

Figure 8. Test 4 results in milliseconds for n = 80*1024/8.

Figure 9. Test 4 results in milliseconds for n = 1.

This test compares the performance of OpenMP and MPI implementations of the matrix times vector operation, y = y + Ax, where for the OpenMP implementation A is column block distributed across p processors, x is block distributed, and y is replicated on all processors. The OpenMP version of this test also used the temporary array psum and the code used is:

!$sgi distribute_reshape A(*,block), x(block)

. . .

!$omp parallel shared(A,x,y) private(psum)

t = timef() !! Start Timer

psum=0.0

!$omp do schedule(static)

psum(:) = psum(:) + A(:,j)*x(j)

!$omp enddo

!$omp critical

!$omp end critical

local_time(omp_get_thread_num(), k) = timef() – t !! End of Timer

. . .

!$omp end parallel

The MPI version requires the use of the temporary arrays psum and sum. The following is the MPI version for this test:

Figures 10 and 11 contain the performance results for this test for n = 128 and n = 1, respectively. In both cases, the MPI implementation performs and scales significantly better than the OpenMP implementation. This is likely due to the fact that the critical region in the OpenMP program is executed serially whereas mpi_reduce uses parallelism (probably a binary tree algorithm) for updating y. If OpenMP would allow one to use the "reduction(+:sum)" option for arrays, then vendors would have the opportunity to generate efficient parallel code for the above operation.

Figure 10. Test 5 results in milliseconds for n = 128.

Figure 11. Test 5 results in milliseconds for n = 1.

This test compares the performance of OpenMP and MPI implementations of the sum of two matrices, C = A + B, where for the OpenMP implementation these arrays are column block distributed across p processors. Notice that no communication is required for this test. The OpenMP version of this test is:

real*8,dimension(n,n*p) :: A, B, C

!$sgi distribute_reshape A(*,block), B(*,block), C(*,block)

. . .

!$omp parallel shared(A,B,C) private(j)

. . .

t = timef() !! Start Timer

!$omp do schedule(static)

do j = 1, n*p

C(:,j) = A(:,j) + B(:,j)

enddo

!$omp enddo

local_time(omp_get_thread_num(), k) = timef() – t !! End of Timer

. . .

!$omp end parallel

The MPI version of this test is:

local_time(k) = timef() – t !! End of Timer

Figures 12 and 13 contain the performance results for this test for n = 512 and n = 1, respectively. For this very simple test, one would expect OpenMP and MPI to perform about the same. However, for n = 1, the MPI implementation performs and scales significantly better than the OpenMP implementation.

The MPI version of this test is:

local_time(k) = timef() – t !! End of Timer

Figures 14 and 15 contain the performance results for this test for n = 512 and n = 1, respectively. Notice that in both cases, the MPI implementation scales well and the OpenMP implementation scales very poorly. As in test 5, this poor performance of OpenMP is likely due to the fact that the critical region must be executed serially (as required by the OpenMP specification) whereas mpi_reduce is executed in parallel.

Figure 15. Test 7 results in milliseconds for n = 1.

The purpose of this paper is to investigate the scalability and performance of seven, simple OpenMP test programs and to compare their performance with equivalent MPI programs on an SGI Origin 2000. Since the memory in the SGI Origin 2000 is physically distributed among its nodes, special data distribution directives were used to make sure that the OpenMP implementation had the same data distribution as the MPI implementation. Without specifying the data distribution, performance of the OpenMP implementation would be poorer.

Each test was executed for a large message and a small message making a total of 14 experiments. For 9 of the 14 experiments, the MPI implementations performed and scaled significantly better than the corresponding OpenMP implementation. For 4 of the experiments, the MPI and OpenMP implementations performed roughly the same. For the small message size for the right shift test, the OpenMP implementation performed and scaled significantly better than the corresponding MPI implementation. Therefore, even with carefully specifying data distributions for the OpenMP implementations, 9 of the MPI implementations performed and scaled significantly better than the corresponding OpenMP implementations for these simple tests. Reduction operations are commonly used in scientific calculations. OpenMP allows vendor to optimize reductions for scalars as illustrated in test 4 (although this optimization could be improved on the Origin). However, OpenMP does not allow this optimization for arrays. Without this capability it difficult to write efficient OpenMP implementations of common operations such as matrix-time-vector (test 5) and matrix-time-matrix (test 7). Thus, the authors recommend that the OpenMP standard be enhanced to allow the reduction option for arrays to be used.

1. OpenMP Specification Web Site. http://www.openmp.org.
2. MPI standard Web Site. http://www-unix.mcs.anl.gov/mpi/index.html.
3. J. Fier. Performance Tuning Optimization for Origin 2000 and Onyx 2. Silicon Graphics, 1996. http://techpubs.sgi.com.
4. G. R. Luecke, B. Raffin, and J. J. Coyle. Comparing the Communication Performance and Scalability of a SGI Origin 2000, a cluster of Origin 2000’s and a Cray T3E-1200 using SHMEM and MPI Routines. The Journal of Performance Evaluation and Modeling for Computer Systems, October 1999. http://hpc-journal.ecs.soton.ac.uk/PEMCS/.

We would like to thank Silicon Graphics, Incorporated for giving us access to their Origin 2000 for this study.

Table 1: Test 1 results in milliseconds for an 8 Byte message.

Table 2: Test 1 results in milliseconds for a 4 MByte message.

Table 3: Results of Right Shift Test in milliseconds.

Table 4: Result of Summing Elements of an Array Test.

Table 5: Result of Dot Product Test.

Table 6: Results of Matrix Times Vector Test in millisecond.

Table 7: Results of Matrix Addition Test in milliseconds.

Table 8: Results of Matrix-Matrix Multiplication Test in milliseconds.