Explicit Vector Programming – Best Known Methods

Explicit Vector Programming – Best Known Methods

Why do we care about vectorizing applications? The simple answer: Vectorizing improves performance, and achieving high performance can save power. The faster an application can compute CPU-intensive regions, the faster the CPU can be set to a lower power state.

How does vectorizing compare to scalar operations with regard to performance and power? Vectorizing consumes less power than equivalent scalar operations because it performs better: Scalar operations process data per cycle by several times and require more instructions and more cycles to complete.

The introduction of wider vector registers in x86 platforms and the increasing number of cores that support single instruction multiple data (SIMD) and threading parallelism now make vectorization an optimization consideration for developers. This is because vector performance gains are applied per core, so multiplicative application performance gains become possible for more applications. In the past, many developers relied heavily on the compiler to auto-vectorize some loops, but serial constraints of programming languages have hindered the compiler’s ability to vectorize many different kinds of loops.  The need arose for explicit vector programming methods to extend vectorization capability for supporting reductions, vectorizing:

• Outer loops

• Loops with user-defined functions

• Loops that the compiler assumes to have data dependencies, but the developer understood to be benign.

In summary: achieving high performance can also save power!

This document describes high-level best known methods (BKMs) for using explicit vector programming to improve the performance of CPU-bound applications on modern processors with vector processing units.  In many cases, it is advisable to consider structural changes that accommodate both thread-level parallelism and as SIMD-level parallelism as you pursue your optimization strategy.

The following six steps are applicable for CPU-bound applications:

1. Measure baseline application performance.
2. Run hotspots and general exploration report analysis with the Intel® VTune™ Profiler.
3. Determine hot loop/functions candidates to see if they are qualified for SIMD parallelism.
4. Implement SIMD parallelism using explicit vector programming techniques.
5. Measure SIMD performance.
6. [Optional for advanced developers] Generate assembly code and inspect.
7. Repeat!

Step 1.  Measure Baseline Application Performance

You first need to have a baseline for your application’s existing performance level to if your vectorization changes are effective. In addition, you need have a baseline to measure your progress and final application performance relative to your starting point. Understanding this provides some guidance about when to stop optimizing.

Use a release build of your application for the initial baseline, instead of, a debug build. A release build contains all the optimizations in your final application. This is important because you need to understand the loops or “hotspots” in your application are spending significant time. 

A release baseline provides symbol information, and has all optimizations turned on except simd (explicit vectorization) and vec (auto-vectorization). To explicitly turn off simd and auto-vectorization use the following compiler switches: -no-simd –no-vec. (See Intel® C++ Compiler Developer Guide and Reference and Intel® Fortran Compiler Developer Guide and Reference.)

Compare the baseline performance against the vectorized version to get a sense of how well your vectorization tuning approaches theoretical maximum speedup.

It is best to compare the performance of specific loops in the baseline and vectorized version using tools such as the Intel® VTune™ Profiler or Intel® Advisor or embedded print statements.

Step 2. Run hotspots and general exploration report analysis with Intel® VTune™ Profiler

You can use the Intel® VTune™ Profiler to find the most time-consuming functions in your application. The “Hotspots” analysis type is recommended.

Identifying which areas of your application are taking the most time allows you to focus your optimization efforts in those areas where performance improvements will have the most effect. Generally, you want to focus only on the top few hotspots or functions taking at least 10% of your application’s total runtime. Make note of the hotspots you want to focus on for the next step. (Tutorial: Finding Hotspots.)

The general exploration report can provide information about:

• TLB misses (consider compiler profile guided optimization),

• L1 Data cache misses (consider cache locality and using streaming stores),

• Split loads and split stores (consider data alignment for targeted architecture),

• Memory bandwidth,

• Memory latency (consider streaming stores and prefetching) demanded by the application.

This higher level analysis can help you determine whether it is profitable to pursue vectorization tuning.

Step 3: Determine Hot Loop/Functions Candidates Are Qualified for SIMD Parallelism

One key suitability ingredient for choosing loops to vectorize is whether the memory references in the loop are independent of each other. (See Memory Disambiguation inside vector-loops and Requirements for Vectorizable Loops.)

The Intel® Compiler optimization report (or -qopt-report) can tell you whether each loop in your code was vectorized.  Ensure that you are using the compiler optimization level 2 or 3 (-O2 or –O3) to enable the auto-vectorizer. Run the vectorization report and look at the output for the hotspots determined from Step 2. If there are loops in these hotspots that did not vectorize, check whether they have math, data processing, or string calculations on data in parallel (for instance in an array). If they do, they might benefit from vectorization. Move to Step 4, if any vectorization candidates are found.

Data alignment

Data alignment is another key ingredient for getting the most out of your vectorization efforts.  If the Intel® VTune™ Profiler reports split loads and stores, then the application is using unaligned data. Data alignment forces the compiler to create data objects in memory on specific byte boundaries.  There are two aspects of data alignment that you must be aware of:

1. Create arrays with certain byte alignment properties.

2. Insert alignment pragmas/directives and clauses in performance critical regions.

Alignment increases the efficiency of data loads and stores to and from the processor. When targeting the Intel® Supplemental Streaming Extensions 2 (Intel® SSE 2) platforms, use 16-byte alignment that facilitates the use of SSE-aligned load instructions. When targeting the Intel® Advanced Vector Extensions (Intel® AVX) instruction set, try to align data on a 32-byte boundary.  For processors with Intel® AVX-512 instructions, memory movement is optimal on 64-byte boundaries. (See Data Alignment to Assist Vectorization.)

Unit Stride

Consider using unit stride memory (also known as address sequential memory) access and structure of arrays (SoA) rather than arrays of structures (AoS) or other algorithmic optimizations to assist vectorization. Examples are in the Intel C++ Developer Guide (search for Using Structure of Arrays versus Array of Structures). Similar concept applies to Fortran.

As a general rule, it is best to try to access data in a unit stride fashion when referencing memory.  Because this is often good for vectorization and other parallel programming techniques. 

Successful vectorization may hinge on the application of other loop optimizations, such as loop interchange (see information on cache locality), and loop unroll.

It may be worth experimenting to see if inlining a function using –ip or –ipo allows vectorization to proceed for loops with embedded, user-defined functions. This is one alternative approach to using simd-enabled functions; there may be tradeoffs between using one or the other.

Note If the algorithm is computationally bound when performing hotspot analysis, continue pursuing the strategy described in this paper.  If the algorithm is memory-latency bound or memory-bandwidth bound, then vectorization will not help. In such cases, consider strategies like cache optimizations or other memory-related optimizations, or even rethink the algorithm entirely. High level loop optimizations, such as –O3, can look for loop interchange optimizations that might help cache locality issues.  Cache blocking, can also help improve cache locality when applicable. See Loop Optimizations:Where Blocks are Required for methods of cache blocking.

Step 4: Implement SIMD Parallelism Using Explicit Vector Programming Techniques

Explicit vector programming includes features such as the vectorization directives first available with OpenMP* 4.0. These optimizations provide a very powerful and portable way to express vectorization potential in C/C++ applications. OpenMP* 4.0 vectorization directives are also applicable to Fortran applications. These explicit vector programming techniques give you the means to specify which targeted loops to vectorize. Candidate loops for vectorization directives include loops that have too many memory references for the compiler to put in place dependency checks, loops with reductions, loops with user-defined functions, outer loops, among others.

(See Explicit Vector Programming in Fortran for how to enable SIMD features in an application using the OpenMP* 4.0 methodology.)

Here are some common components of explicit vector programming.

SIMD-enabled Functions 

User creation of SIMD-enabled functions is a capability provided beginning with OpenMP* 4.0. SIMD-enabled functions explicitly describe the SIMD behavior of user-defined functions, including how SIMD behavior is altered due to call site dependence. The Intel C++ Compiler Developer Guide and Reference discusses using SIMD-enabled functions. The Intel Fortran Compiler Developer Guide and Reference explains !$OMP DECLARE SIMD (routine-name)

SIMD Loops

The principle with SIMD loops is to explicitly describe the SIMD behavior of a loop, including descriptions of variable usage and any idioms such as reductions. 

Traditionally, only inner loops have been targeted for vectorization. One unique application of the OpenMP* 4.0 #pragma omp simd is that it can be applied to an outer loops.

(See loops Outer Loop Vectorization which describes using #pragma simd in outer loops).

Step 5: Measure SIMD performance

Measure your application’s build configuration runtime performance. If you are satisfied, you are done! Otherwise, inspect the optimization report from -qopt-report-phase=vec for a SIMD vectorization summary and check alignment, unit-stride and using (SoA) versus (AoS), interaction with other loop optimizations, etc.

For a deeper exploration on measuring performance, see How to Benchmark Code Execution Times on Intel®  IA-32 and IA-64 Instruction Set Architectures.

Another approach is to use a family of compiler switches with the template –profile-xxxx. Using the instrumentation method to profile function or loop execution time makes it easy to view where cycles are being spent in your application. The Intel® Compiler inserts instrumentation code into your application to collect the time spent in various locations. Use that data for identifying hotspots that may be candidates for optimization tuning or targeting parallelization.

Another method to measure performance is to re-run the Intel® VTune™ Profiler hotspot analysis after the optimizations are made and compare results.

Optional Step 6: For Advanced Developers - Generate assembly code and do inspection

For those who want to see the assembly code that the compiler generates, and inspect that code to gain insight into how well applications were vectorized, use the compiler switch –S to compile to assembly (.s) without invoking a link step.

Step 7:  Repeat!
Repeat as needed until you achieve the desired performance or no good candidates remain.

Other considerations are applicable for applications that are memory latency-bound or memory bandwidth-bound:

Another Consideration: Streaming stores

Streaming stores are a method of writing data explicitly to main memory bypassing all intermediate caches in instances where you are sure that data being written will not be needed from cache any time soon. Strictly speaking, bypassing all caches is only applicable on Intel® Xeon® processors. -qopt-streaming-stores=keyword enables or disables streaming stores.

Other considerations: Scatter, gather, and compress structures:

Many applications benefit from explicit vector programming efforts. In many cases performance increases over scalar performance can be commensurate with the number of available vector lanes on a given platform. However, some types of coding patterns or idioms limit vectorization performance to a large degree.

Gather and Scatter codes

A[I] = B[Index[i]];    //Gather
A[Index[i]] = b[i];  //Scatter

While gather/scatter vectorization is available on recent Intel® Xeon® platforms, the performance gains from vectorization relying on gather/scatter is often much inferior to use of unit-strided loads and stores inside vector-loops. If there are not enough other profitably vectorized operations (such as multiple, divide, or math calls, …) inside such vector loops, performance may even be lower than serial performance in some cases.  The only possible workaround for such issues is to look at alternative algorithms all together to avoid using gathers and scatters.

Compress and Expand structures

Compress and expand structures are generally problematic. On recent Intel® Xeon® processors, the Intel® Compiler can automatically vectorize loops that contain simple forms of compress/expand idioms. An example of a compress idiom is as follows:

do I =1,N
   if (B(I)>0)
       x= x+1
       A(X) = B(I)
   endif
enddo

In this example, the variable x is updated under a condition. Note that it is incorrect to use the #pragma simd for such compress structures but using #pragma ivdep is okay.

Improve performance of such vectorized loops on Intel® AVX-512 Architecture using the -opt-assume-safe-padding compiler option. (See Common Vectorization Tips.)

Reference Materials

Compiler diagnostic messages

• Intel® Fortran Vectorization Diagnostics – Diagnostic messages from the vectorization report produced by the Intel® Fortran Compiler. To obtain a vectorization report in Intel® Fortran, use the option -qopt-report[=n] (Linux* and macOS* platforms) or /Qopt-report[:n] (Windows* platform).

• Vectorization Diagnostics for Intel® C++ Compiler – Diagnostic messages from the vectorization report produced by the Intel® C++ Compiler. To obtain a vectorization report with the Intel® C++ Compiler, use option -qopt-report[=n] (Linux* and macOS* platforms) or /Qopt-report[:n] (Windows* platform).

Articles

• Vectorization and Optimization Reports – Using compiler option -qopt-report to determine what is (or is not) vectorizing and why (or why not) in your application.

• Requirements for Vectorizable Loops – Requirements for loop vectorization, code snippets, examples, and an advice section.

• Memory Layout Transformations  – Moving from data organized in an AoS to an organization of SoA.

• Data Alignment to Assist Vectorization – Data alignment is a method to force the compiler to create data objects in memory on specific byte boundaries. In addition to creating the data on aligned boundaries, the compiler is able to make optimizations when the data is known to be aligned by 64-bytes.

• Outer Loop Vectorization – Moving the vectorization from an inner level to an outer level using a combination of elemental functions and pragma/directive SIMD.

• The Importance of Vectorization for Intel® Microarchitectures (Fortran Example) – Using the Intel® Fortran Compiler vectorizer to get good performance through effective use of the SIMD hardware and the benefits of threading over many cores.

• Cache Blocking Techniques – Cache Blocking is a technique to rearrange data access to pull subsets (blocks) of data into cache and to operate on block to avoid repeatedly fetching data from memory.

• Memory Layout Transformations – Reorganizing data into an SoA organization for real world applications.

• Common Vectorization Tips – User-defined function-calls inside vector-loops, unit-stride accesses inside elemental functions, and memory disambiguation inside vector loops.

• Intel Guide for Developing Multithreaded Applications – More specific tuning-related information applicable to thread synchronization and memory management.

Documentation

Intel® Advisor

Intel® VTune™ Profiler

Intel, the Intel logo, VTune, and Xeon are trademarks of Intel Corporation in the U.S. and/or other countries.

* Other names and brands may be claimed as the property of others.