One of the first steps in performance tuning is to verify that the correct answers are being obtained. After the correct answers are obtained, tuning can be done. You can verify answers by initially disabling specific optimizations and limiting default optimizations. This can be accomplished by using specific compiler options and by using debugging tools.

The following compiler options emphasize tracing and porting over performance:

For information about debugging tools that you can use to verify that correct answers are being obtained, see the following:

“About Debugging” in Chapter 2

You can use environment variables to check for heap corruption problems in programs that use glibc  malloc/free dynamic memory management routines.

Set the MALLOC_CHECK_ environment variable to 1 to print diagnostic messages or to 2 to abort immediately when heap corruption is detected.

Overruns and underruns are circumstances in which an access to an array is outside the declared boundary of the array. Underruns and overruns cannot be simultaneously detected. The default behavior is to place inaccessible pages immediately after allocated memory.

Where possible, use code that has already been tuned for optimum hardware performance.

The following mathematical functions should be used where possible to help obtain best results:

Documentation is available for MKL and VML at the following website:

https://software.intel.com/en-us/intel-parallel-studio-xe-support/documentation

Use the following tools to determine what points in your code might benefit from tuning:

For information about other performance analysis tools, see Chapter 2, “Performance Analysis and Debugging”.

This topic describes several Intel compiler options that can optimize performance. In addition to the performance options and processor options that this topic describes, the following options might be useful to you:

For more information about the Intel compiler options, see the following:

https://software.intel.com/en-us/intel-parallel-studio-xe

Use the following options to help tune performance:

The Intel compilers support additional options that are specific to each processor model. To determine the processor used in your system, examine the contents of the /proc/cpuinfo file. For example:

# cat /proc/cpuinfo | grep "model name"
model name      : Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
model name      : Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
model name      : Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
.
.
.

Use the information in Table 5-1 to determine the processor in your SGI system.

The following list shows the processor-specific compiler options:

The processor cache stores recently-used information in a place where it can be accessed quickly. This topic uses the following terms to describe cache performance tuning:

There are several actions you can take to help tune cache performance:

The following topics pertain to memory management:

In order to efficiently use multiple processors on a system, tasks have to be found that can be performed at the same time. There are two basic methods of defining these tasks:

When tuning for performance, first assess the amount of code that is parallelized in your program. Use the following formula to calculate the amount of code that is parallelized:

p=N(T(1)-T(N)) / T(1)(N-1)

In this equation, T(1) is the time the code runs on a single CPU and T(N) is the time it runs on N CPUs. Speedup is defined as T(1)/T(N).

If speedup/N is less than 50% (that is, N>(2-p)/(1- p)), stop using more CPUs and tune for better scalability.

You can use one of the following to display CPU activity:

Next, focus on using one of the following parallelization methodologies:

http://www.openmp.org/wp/openmp-specifications

% cat place_nested
firsttask cpu=0
thread name=a.out oncpu=0 cpu=4 noplace=1 exact onetime thread name=a.out oncpu=0
cpu=1-3 exact thread name=a.out oncpu=4 cpu=5-7 exact

% dplace -p place_nested a.out
Master thread 0 running on cpu 0
Master thread 1 running on cpu 4
Nested thread 0 of master 0 gets task 0 on cpu 0 Nested thread 1 of master 0 gets task 1 on cpu 1
Nested thread 2 of master 0 gets task 2 on cpu 2 Nested thread 3 of master 0 gets task 3 on cpu 3
Nested thread 0 of master 1 gets task 0 on cpu 4 Nested thread 1 of master 1 gets task 1 on cpu 5
Nested thread 2 of master 1 gets task 2 on cpu 6 Nested thread 3 of master 1 gets task 3 on cpu 7

If the parallel version of your program is slower than the serial version, false sharing might be occurring. False sharing occurs when two or more data items that appear not to be accessed by different threads in a shared memory application correspond to the same cache line in the processor data caches. If two threads executing on different CPUs modify the same cache line, the cache line cannot remain resident and correct in both CPUs, and the hardware must move the cache line through the memory subsystem to retain coherency. This causes performance degradation and reduction in the scalability of the application. If the data items are only read, not written, the cache line remains in a shared state on all of the CPUs concerned. False sharing can occur when different threads modify adjacent elements in a shared array. When two CPUs share the same cache line of an array and the cache is decomposed, the boundaries of the chunks split at the cache line.

If you suspect false sharing, take one of the following actions:

If false sharing is a problem, try the following solutions:

You can use several different environment variables to assist in performance tuning. For details about environment variables used to control MPI behavior, see the mpi(1) man page.

Several OpenMP environment variables can affect the actions of the OpenMP library. For example, some environment variables control the behavior of threads in the application when they have no work to perform or are waiting for other threads to arrive at a synchronization semantic. Other environment variables can specify how the OpenMP library schedules iterations of a loop across threads. The following environment variables are part of the OpenMP standard:

In addition to the preceding environment variables, Intel provides several OpenMP extensions, two of which are provided through the use of the KMP_LIBRARY variable.

The KMP_LIBRARY variable sets the run-time execution mode, as follows:

If your program generates a segmentation fault immediately upon execution, you might need to increase KMP_STACKSIZE. This is the private stack size for threads. The default is 4 MB. You may also need to increase your shell stacksize limit.

You can distribute the work your program does over multiple CPUs. However, there is always some part of the program's logic that has to be executed serially, by a single CPU. This sets the lower limit on program run time.

Suppose there is one loop in which the program spends 50% of the execution time. If you can divide the iterations of this loop so that half of them are done in one CPU while the other half are done at the same time in a different CPU, the whole loop can be finished in half the time. The result is a 25% reduction in program execution time.

The mathematical treatment of these ideas is called Amdahl's law, for computer pioneer Gene Amdahl, who formalized it. There are two basic limits to the speedup you can achieve by parallel execution:

Tuning for parallel execution comes down to doing the best that you are able to do within these two limits. You strive to increase the parallel fraction, p, because in some cases even a small change in p (from 0.8 to 0.85, for example) makes a dramatic change in the effectiveness of added CPUs.

Then you work to ensure that each added CPU does a full CPU's work and does not interfere with the work of other CPUs. In the SGI UV architectures this means coding to accomplish the following:

If half the iterations of a loop are performed on one CPU, and the other half run at the same time on a second CPU, the whole loop should complete in half the time. For example, consider the typical C loop in Example 5-1.

for (j=0; j<MAX; ++j) {
   z[j] = a[j]*b[j];
} 

The compiler can automatically distribute such a loop over n CPUs (with n decided at run time based on the available hardware), so that each CPU performs MAX/n iterations.

The speedup gained from applying n CPUs, Speedup(n), is the ratio of the single-CPU execution time to the n-CPU execution time: Speedup(n) = T(1) ÷ T(n). If you measure the single-CPU execution time of a program at 100 seconds, and the program runs in 60 seconds with two CPUs, Speedup (2) = 100 ÷ 60 = 1.67.

This number captures the improvement from adding hardware. T(n) ought to be less than T(1). If it is not, adding CPUs has made the program slower, and something is wrong. So Speedup(n) should be a number greater than 1.0, and the greater it is, the better. Intuitively you might hope that the speedup would be equal to the number of CPUs (twice as many CPUs, half the time) but this ideal can seldom be achieved.

You expect Speedup(n) to be less than n, reflecting the fact that not all parts of a program benefit from parallel execution. However, it is possible, in rare situations, for Speedup(n) to be larger than n. When the program has been sped up by more than the increase of CPUs it is known as superlinear speedup.

A superlinear speedup does not really result from parallel execution. It comes about because each CPU is now working on a smaller set of memory. The problem data handled by any one CPU fits better in cache, so each CPU runs faster than the single CPU can. A superlinear speedup is welcome, but it indicates that the sequential program was being held back by cache effects.

There are always parts of a program that you cannot make parallel, where code must run serially. For example, consider the loop. Some amount of code is devoted to setting up the loop and allocating the work between CPUs. This housekeeping must be done serially. Then comes parallel execution of the loop body, with all CPUs running concurrently. At the end of the loop comes more housekeeping that must be done serially. For example, if n does not divide MAX evenly, one CPU must execute the few iterations that are left over.

Concurrency cannot speed up the serial parts of the program. Let p be the fraction of the program's code that can be made parallel (p is always a fraction less than 1.0.) The remaining fraction (1-p) of the code must run serially. In practical cases, p ranges from 0.2 to 0.99.

The potential speedup for a program is proportional to p divided by the CPUs you can apply, plus the remaining serial part, 1-p. As an equation, this appears as Example 5-2.

                  1 
Speedup(n) = ----------- 
             (p/n)+(1-p) 

Suppose p = 0.8; then Speedup (2) = 1 / (0.4 + 0.2) = 1.67, and Speedup(4)= 1 / (0.2 + 0.2) = 2.5. The maximum possible speedup, if you could apply an infinite number of CPUs, would be 1 / (1-p). The fraction p has a strong effect on the possible speedup.

The reward for parallelization is small unless p is substantial (at least 0.8). To put the point another way, the reward for increasing p is great no matter how many CPUs you have. The more CPUs you have, the more benefit you get from increasing p. Using only four CPUs, you need only p= 0.75 to get half the ideal speedup. With eight CPUs, you need p= 0.85 to get half the ideal speedup.

There is a slightly more sophisticated version of Amdahl's law that includes communication overhead. This version shows that if the program has no serial part and you increase the number of cores, the following occurs:

The equation is as follows:

Speedup(n) = n/(1+ a*( n-1) + n*(tc/ ts))

The preceding equation uses the following variables:

If a=0 and tc=0, there is no serial part and no communication. In this case, as in a trivial parallelization program, you see a linear speedup.

You do not have to guess at the value of p for a given program. Measure the execution times T(1) and T(2) to calculate a measured Speedup(2) = T(1) / T(2). The Amdahl's law equation can be rearranged to yield p when Speedup (2) is known, as in Example 5-3.

     2    SpeedUp(2) - 1 
p = --- * -------------- 
     1      SpeedUp(2)  

Suppose you measure T(1) = 188 seconds and T(2) = 104 seconds.

SpeedUp(2) = 188/104 = 1.81 
p = 2 * ((1.81-1)/1.81) = 2*(0.81/1.81) = 0.895 

In some cases, the Speedup(2) = T(1)/T(2) is a value greater than 2; in other words, a superlinear speedup. When this occurs, the formula in Example 5-3 returns a value of p greater than 1.0, which is clearly not useful. In this case, you need to calculate p from two other more realistic timings, for example T(2) and T(3). The general formula for p is shown in Example 5-4, where n and m are the two CPU counts whose speedups are known, n>m.

                Speedup(n) - Speedup(m)
p  =  ------------------------------------------- 
   (1 - 1/n)*Speedup(n) - (1 - 1/m)*Speedup(m) 

For more information about superlinear speedups, see the following:

“Understanding Superlinear Speedup”

You can use the calculated value of p to extrapolate the potential speedup with higher numbers of CPUs. The following example shows the expected time with four CPUs, if p=0.895 and T(1)=188 seconds:

Speedup(4)= 1/((0.895/4)+(1-0.895)) = 3.04 
T(4)= T(1)/Speedup(4) = 188/3.04 = 61.8 

The calculation can be made routine using the computer by creating a script that automates the calculations and extrapolates run times.

These calculations are independent of most programming issues such as language, library, or programming model. They are not independent of hardware issues because Amdahl's law assumes that all CPUs are equal. At some level of parallelism, adding a CPU no longer affects run time in a linear way. For example, on some architectures, cache-friendly codes scale closely with Amdahl's law up to the maximum number of CPUs, but scaling of memory intensive applications slows as the system bus approaches saturation. When the bus bandwidth limit is reached, the actual speedup is less than predicted.

On an SGI UV system, the following two transfer methods facilitate MPI communication between processes:

The MPI library chooses the transfer method depending on internal heuristics, the type of MPI communication that is involved, and some user-tunable variables. When using the GRU to transfer data and messages, the MPI library uses the GRU resources it allocates via the GRU resource allocator, which divides up the available GRU resources. It allocates buffer space and control blocks between the logical processors being used by the MPI job.

The MPI library chooses buffer sizes and communication algorithms in an attempt to deliver the best performance automatically to a wide variety of MPI applications, but user tuning might be needed to improve performance. The following are some application performance problems and some ways that you might be able to improve MPI performance:

SGI supports several MPI performance tools. You can use the following tools to enhance or troubleshoot MPI program performance:

For more information about the MPI performance tools, see the following: