Many ways to speed up your program

There are many approaches to make your program run faster. Some approaches are based on using more efficient libraries, others rely on using the standard library and the language in an efficient manner. Other approaches include using more efficient algorithms. But sometimes, even after we’ve applied all the possible optimizations, the code performance is not satisfactory. This is the time where we need to investigate our code and make sure we are using all the available hardware resources in the most efficient manner.

In this post we present software development techniques aimed at using the hardware in an efficient fashion, and we will explore how our Codee tool can help you boost the performance of your code by getting the most out of your hardware.

We will talk about several aspects of efficient hardware utilization:

• using all available CPU cores,
• using accelerators such as GPUs,
• vectorization,
• memory optimizations and
• advanced hardware features.

Distributing workload to multiple CPU cores

CPUs with several cores are now ubiquitous. Even the cheapest phones have at least two CPU cores, laptops will have anywhere between two and eight CPU cores and high-end CPUs will have hundreds of cores. There is a huge potential for parallelism that many programs never exploit.

A very convenient way of making a serial code run on multiple cores is OpenMP. OpenMP is an open standard supported by all major compilers (eg. GCC, CLANG, Intel’s compiler or Microsoft’s compiler). It is supported in C, C++ and Fortran. It allows the user to decorate their code with compiler pragmas that tell the compiler how to perform the distribution to multiple CPU cores. 

Here is an example of a small loop decorated with OpenMP pragmas. The pragmas were added by Codee automatically:

#pragma omp parallel default(none) shared(a, n, result) private(i)
{
    #pragma omp for reduction(+: result) schedule(auto)
    for (i = 0; i < n; i++) {
        result += sqrt(a[i]) / n;
    }
} // end parallel

When the code is executed and the section of the code with the compiler pragmas is reached, the code gets executed by several CPU cores. The compiler takes care of everything needed to run the code – thread creation, data synchronization and thread synchronization.

We wrote extensively about distributing your critical loop to several CPU cores using OpenMP. In the example of the Canny image processing algorithm, the OpenMP version of the program ran 3.4 times faster than the serial version on a system with eight threads. In another example of NP CG benchmark, the program ran 2.7 times faster than the original on a system with four threads.

Codee guides you through the process of optimizing your code by providing  human-readable actionable hints. For instance, it detects computations in your code that can be distributed to multiple CPU cores. If you are interested in doing so using OpenMP, it can also help you speed up those computations by inserting the proper pragmas automatically.

Distributing workload to accelerators

Many modern computer systems also contain accelerator devices that can be used to speed up computation. For example, modern desktops and laptops have GPUs, programmable graphic accelerators that are used for 2D or 3D rendering. High-performance computers often feature an accelerator device to speed up scientific calculations.

Accelerators are part of massively parallel architectures and they are really efficient at solving many types of problems. There are several ways of programming accelerators, low-level such as CUDA and OpenCL; or high-level such as OpenMP or OpenACC. Our product, Codee, helps developers automatically port their codebases to accelerators using OpenACC and OpenMP.

OpenACC is a really simple way to make use of the hardware accelerators. Similar to OpenMP from the previous section, it relies on compiler pragmas and compiler support to compile code that will run on an accelerator. 

Here is an example of a loop with OpenACC directives, automatically generated by Codee, which offloads the execution to a GPU:

double out_result;
double sum = 0.0;

#pragma acc data copyin(N) copy(sum)
{
#pragma acc parallel
    {
#pragma acc loop reduction(+ : sum)
        for (int i = 0; i < N; i++) {
            double x = (i + 0.5) / N;
            sum += sqrt(1 - x * x);
        }
    }  // end parallel
}      // end data

out_result = 4.0 / N * sum;

The above code snippet calculates the value of number π and it is executed on the GPU. It performs all the necessary steps to run on an accelerator: move input data to the accelerator, computations, move the results back to the main memory.

This loop took 0.9 s to finish on a GPU compared to the 2.4 s on a CPU when the variable N was two billion. A good way of using the accelerators!

You can use Codee to detect computations that can be offloaded to accelerator devices such as GPUs. Moreover, it offers optimization recommendations focused on GPUs such as PWR009 and PWR015. It can also help by generating both the OpenMP and OpenACC directives required to distribute the workload to the GPU.

Usage of vectorization capabilities of your CPU

Modern CPUs contain vector units that work on fixed length vectors (e.g. vector of four doubles or vector of eight integers) and can execute a single operation on a vector in one instruction. If vectorization is available, the CPU can e.g. load four doubles from memory, perform four additions and store four results back to memory for the same time it would take to do the same operations on one double.

Compilers will typically create vectorized code automatically, but there are many obstacles to this which we already wrote about. Take for example, a naive matrix multiplication algorithm:

for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
         c[i][j] = 0;
         for (int k = 0; k < n; k++) {
             c[i][j] = c[i][j] + a[i][k] * b[k][j];
         }
     }
}

The compiler will not automatically vectorize the above loop since the access to b[k][j] is not going through the memory sequentially, i.e. the CPU is accessing elements of the matrix b with a stride which is n. A technique called loop interchange can help the performance. Here is the modified source code:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        c[i][j] = 0;
    }
    for (int k = 0; k < n; k++) {
        for (int j = 0; j < n; j++) {
            c[i][j] = c[i][j] + a[i][k] * b[k][j];
        }
    }
}

In this example, we first performed loop fission on loop over j and split it into two loops. The first loop performs the initialization of c[i][j] (line 3), the second loop performs the calculations. Next, we interchanged the loop over j and the loop over k. With this transformation, in the innermost loop we only have constant memory accesses (always accessing the same memory location: a[i][k]) or sequential accesses (accessing neighboring memory locations: c[i][j] and b[k][j]). 

The original code took 14.4 s to execute on a 2400×2400 integer matrix. The modified version took 3.8 s, which is a drastic improvement in speed! All thanks to loop interchange and vectorization.

Just like for multicore CPUs and offloading to the GPUs, Codee can help with vectorization. For instance, it offers hints on how to refactor your code to enable auto-vectorization (eg. PWR020) or how to increase the vectorization performance (eg. PWR019). Additionally it can help you generate vectorization directives for OpenMP or compiler-specific ones (eg. gcc, clang, icc).

Optimizing for the memory subsystem

Modern CPUs are very fast, but the memories they use to load and store data are much slower. Therefore, modern CPUs often have to wait for the data to be fetched from memory. This is especially visible in the case of non-sequential memory access patterns ¹: strided memory access pattern and random memory access pattern. Every effort to decrease the amount of data needed to be fetched from memory, to move to a sequential memory access pattern or increase locality (by accessing data already present in the cache) will yield performance improvements, which can sometimes be significant.

Consider the following example of matrix transposition:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        b[i][j] = a[j][i];
    }
}

From the performance perspective, access to array a[j][i] is inefficient because elements of the array are accessed with a stride n. A technique called loop tiling or loop blocking can help to increase the performance. On modern CPUs, everytime you access an element of an array, a few neighboring elements will be loaded to the data cache and their access will be very cheap. Loop tiling exploits this fact by operating on small blocks of data.

The difference in access patterns can be seen in the following table:

Original loop	Loop tiling with tile size = 2
b[0][0] = a[0][0] b[0][1] = a[1][0] b[0][2] = a[2][0] b[0][3] = a[3][0]	b[0][0] = a[0][0] b[0][1] = a[1][0] b[1][0] = a[0][1] b[1][1] = a[1][1]
b[0][4] = a[4][0] b[0][5] = a[5][0] b[0][6] = a[6][0] b[0][7] = a[7][0]	b[0][2] = a[2][0] b[0][3] = a[3][0] b[1][2] = a[2][1] b[1][3] = a[3][1]

Because of memory caches, access to a[0][0] also makes access to a[0][1] very fast. The tiling version takes advantage of this since it is accessing a[0][1] very soon after it has accessed a[0][0].

The matrix transpose algorithm with loop tiling looks (tile size = 4) like this:

for (int ii = 0; ii < n; ii += 4) {
    for (int jj = 0; jj < n; jj += 4) {
        for (int i = ii; i < (ii + 4); i++) {
            for (int j = jj; j < (jj + 4); j++) {
                b[i][j] = a[j][i];
            }
        }
    }
}

On a matrix of 10000 x 10000 elements it took 860 ms to execute the original algorithm, and 288 ms to execute the loop tiling version.

There are numerous other ways to optimize for the memory subsystems, here are just a few examples:

• Use loop interchange to move to a better memory access pattern.
• Decrease the size of your struct/or class. Remove rarely used members to other structs.
• Move to Struct-of-Arrays. This transformation often results in the loop in question getting vectorized.
• Decrease the size of your random access data structure (e.g. use smaller data types or smaller pointers).

Codee provides hints on how to apply these and other techniques to optimize your code for the memory subsystems, such as the PWR010 or PWR016 recommendations. It also offers several reports to get insights on how memory is used in your code, including memory access patterns.

Optimizing for the CPU’s branch prediction unit

Modern CPUs are optimized to maintain a high throughput of instructions. They follow a pipelined design in which ideally the stream of instructions to process should never be interrupted. Conditional code and branching poses a problem because the instructions to execute following the conditional branch depend on the condition. Thus the next exact branch instructions can not be pipelined because they are not known until the condition instructions are fully evaluated.

To help with this, CPUs have advanced branch prediction units that attempt to predict if the branch is to be taken or not. Based on the prediction, the CPU starts executing the instructions at the predicted destination of the branch so that the computation never stops. If the prediction turned out to be right, this means that the CPU wasn’t sitting idly and has done some work. If it’s wrong, the CPU needs to revert the results of the already executed instructions and start over. Reverting the results that happen as the result of the misprediction means that the CPU will waste some time.

Most of the time the branch predictor works great! It can predict simple branches, like always true or always false, but it can also predict branches that have complex history, e.g. alternating true/false or true hundred times and false once (happens in loops).

Branch predictor works poorly when the branch is unpredictable (happens on random data) and the chance of the condition being true is 50%. In that case you can expect a successful prediction rate of 50%, and this kind of code has many places for improvements.

Take for an example the following code (motivated by the Canny image processing example):

void calculate_hysteresis(int cond[], int in[], int n, int out[]) {
    for (int i = 0; i < n; i++) {
        if (cond[i] > 0) {
            out[in[i]]++;
        }
    }
}

The above loop is non-vectorizable due to a possible data dependency between loop iterations, since i[i] and in[i-1] can refer to the same element of the out array. If the condition cond[i] > 0 is unpredictable with a 50% chance of being true, the CPU will lose many cycles doing useless work.

In these cases we can try making the above code branchless. Here is an example of the same code but without the `if` statement:

void calculate_hysteresis_branchless(int cond[], int in[], int n, int out[]) {
    for (int i = 0; i < n; i++) {
        out[in[i]]+=(cond[i] > 0);
    }
}

For the unpredictable condition, the original version took 516 ms to execute for an array of size 100 million numbers. The branchless version took 123 ms. Branchless implementation is 4.2 times faster.

Codee currently does not emit recommendations related to optimizations for the branch prediction, but we plan to address this in the future as a way of speeding up loops that cannot be optimized using vectorization.

Summary

In this post we presented techniques that allow you to speed up your code by optimally using the available hardware. We started by taking advantage of additional CPUs and accelerator hardware, moved over to using vectorization capabilities of the CPU, explored efficient use of memory subsystem and finished with optimizations for the branch predictor. We gave examples which demonstrate the possibilities of each of these techniques. 

Our Codee can help you there in many ways! It guides you through the process of optimizing your code by providing human-readable actionable hints. It can detect inefficient code that the compiler cannot vectorize automatically and propose fixes as well as inefficient memory access patterns that are slowing down your code. Moreover, it can rewrite your code automatically to take advantage of additional CPU cores and accelerator devices. It is our vision to make it the best tool on the market for writing fast and efficient code! 

Additional Information

All the source code used in the examples is either available in our repository or on the pages where the experiments were originally executed. All the tests for this post were executed on AMD Ryzen 7 4800H CPU with 16 cores, 16 GB of RAM memory and GeForce GTX 1650 Ti GPU on Ubuntu 20.04. We disabled processor frequency scaling in order to decrease runtime variance.

---

1  We wrote extensively about memory access patterns in a post about the Canny image detection algorithm.