Tuning for Success with the Latest SIMD Extensions and Intel® Advanced Vector Extensions 512

#pragma omp simd
for (int i = 0; i < n; i++) {
   #pragma omp ordered simd overlap(B[i])
   {
       A[B[i]]++;
   }
}

This new clause has the following language semantics:

• When execution reaches the ordered simd construct, it evaluates the values of overlap expression B[i] as an r-value, which must yield an integral or pointer value. The implementation must ensure that if two iterations of the enclosing simd loop compute the same values, the iteration with the lower logical iteration number must complete the execution of ordered simd code block before the other iteration starts execution of the same code block.

• Total ordering is not guaranteed by the compiler. It is the programmer’s responsibility to check whether the partial ordering is sufficient for any possible aliasing between stores to A[] and any loads of A[] and B[].

• The ordered simd block specifies the region where overlapping should be checked. Thus, for statements outside of the ordered simd overlap block, the overlap check will not be performed.

• The ordered simd construct with overlap clause may be implemented as an ordered simd construct without the overlap clause.

Conditional Lastprivate

A common case in many programs is that a loop produces the value of its last iteration where the assignment statement is actually executed (i.e., produces a write to a scalar). The value of the scalar will be used after the loop (Figure 10).

int t = 0;
#pragma omp simd lastprivate(t)
for (int i = 0; i < n; i++) {
    t = A[i];
}

int t = 0;
for (int i = 0; i < n; i++) {
    if (A[i] > 0) {
        t = A[i];
    }
}

Both code snippets in Figure 10 can be vectorized, but only the code on the left has explicit support in OpenMP through the lastprivate clause. The lastprivate clause can’t be used for the code on the right because of its semantics. The scalar t gets the value from the last executed iteration of the loop; thus, the t is undefined if the condition A[n-1]>0 is not true. To address this issue, a new modifier, conditional,is proposed and added to the clause lastprivate (Figure 11).

int t = 0;
#pragma omp simd lastprivate(conditional:t)
for (int i = 0; i < n; i++) {
    if (A[i] > 0) { t = A[i]; }
}

Here are the language semantics of the new conditional modifier:

• A list item that appears in a conditional lastprivate clause is subject to the private clause semantics. At the end of the simd construct, the original list item gets the value as if the lexically last conditional assignment happened during scalar execution of the loop.
• The item should not be used if its use happens prior to its definition or it’s outside of the definition’s scope.

Loops with Early Exits

The existing simd vectorization in OpenMP 4.5 does not support loops with more than one exit. For example, a common usage such as finding an index of some elements in an array (Figure 12) can’t be explicitly vectorized properly with the existing simd construct.

for (int i = 0; i < n; ++i) {
    if (A[i] == B[i]) {
        j = i; break;
    }
}
// use of j.

int j = 0;
#pragma omp simd early_exit lastprivate(conditional:j)
for (int i = 0; i < n; i++) {
     if (A[i] == B[i]) { j = i; break; }
}
// use of j.

To address this issue, the Intel Compilers have introduced a new loop-level clause, early_exit, as shown in the right box of Figure 12, with the following semantics:

• Each operation before the last lexical early exit of the loop may be executed as if early exit were not triggered within the simd chunk.
• After the last lexical early exit of the loop, all operations are executed as if the last iteration of the loop was found.
• The last value for linear and conditional lastprivate is preserved with respect to scalar execution.
• The last value for reductions is computed as if the last iteration in the last simd chunk was executed upon exiting the loop.
• The shared memory state may not be preserved with regard to scalar execution.
• Exceptions are not allowed.
• If the innermost loop has an exit out of the simd construction, execution of the innermost loop is similar to if it had been completely unrolled.

Performance Results

Tables 2 through 4 provide performance results of micro-kernel programs for the monotonic, overlap, and early_exit extensions discussed previously. Performance measurement is done on an Intel® system with preproduction Intel Xeon Scalable processors running at 2.1GHz, in a 2-socket configuration with 24x 2666MHz DIMMs. Actual performance on specific configurations can vary. The loops are the examples shown in previous sections. Loop trip count n is 109, data types are all 32-bit integers, vector length is 16, and the compilation command line is icc –xCORE-AVX512. Baseline is scalar execution of the same set of loops.

Table 2 shows the normalized speedup of vectorized compress and expand idioms. In the "all false" column, compress/expand conditions are all false. Compressing stores or expanded loads are completely skipped. Vector evaluation of the condition, and the reduced number of iterations from vectorization, still lead to 1.17x to 1.19x speedup. For the "all true" column, compress/expand conditions are true; thus, all 16 elements are stored/loaded.

Table 2 — Normalized speedup of compress/expand versus scalar execution. Each column has a different number of true conditions.

In the middle columns, 2, 4, 8, or 15 elements of the 16-way vector are compress stored or expand loaded. This table indicates that regardless of the actual number of elements compressed/expanded, the vectorization of these idiomatic patterns is favorable compared to scalar execution. We ran the same experiment using aligned and misaligned compressed-to/expanded-from arrays. As we expected, trending was very similar between aligned and misaligned cases, except for the "all true" extreme, where the aligned cases have better cache line access characteristics.

Table 3 shows the normalized speedup of the vectorized histogram example. On the left, there is no overlap case, which is running 23 percent slower than scalar execution. Consider finding alternatives where the programmer can assert no-overlaps and thus avoid using overlap extension. Sometimes, choosing a shorter vector length may accomplish that. If conflict resolution is required for vector execution to make sense, other parts of the loop need to be highly profitable to vectorize. It’s interesting to note that the eight repeats and full overlap (16 repeats) cases look more favorable than the cases with fewer repeats. This is likely due to register-based repeats in the vector execution catching up the speed of on-memory dependency over scalar execution. For more information on conflict performance, see reference 9 at the end of this article.

Table 3 Normalized speedup of Histogram versus scalar execution. Each column has a different number of conflicts within one vector iteration.

Table 4 shows the normalized speedup of a vectorized search loop example. From left to right, the loop index value at which the match is found increases from 0 to 5,000. A few vector iterations are needed to achieve visible speedups from vectorization of the search loop.

Table 4 — Normalized speedup of Search relative to scalar execution

It’s important to note that standardization for the explicit vectorization techniques we’ve discussed is still in progress. Syntax, semantics, and performance characteristics may be subject to change in future implementations. Some features may remain as Intel-specific extensions.

Best Practices for AVX-512 Tuning

Setting the Baseline

All tuning work should start by setting an appropriate performance baseline. Tuning for Intel Xeon Scalable processors is no different. Let’s assume that the programmer already has an application reasonably tuned for Intel Xeon processors using the –xCORE-AVX2 flag of Intel Compilers 17.0. We recommend starting from the following three binaries using Intel Compilers 18.0:

1. Build the binary with –xCORE-AVX2 (/QxCORE-AVX2 for Windows)
2. Build the binary by replacing –xCORE-AVX2 with –xCORE-AVX512 (/QxCORE-AVX512 for Windows)
3. Build the binary by replacing –xCORE-AVX2 with –xCORE-AVX512 –qopt-zmm-usage=high(/QxCORE-AVX512 /Qopt-zmm-usage=high for Windows)

Although we expect overall performance of binary-B and/or binary-C to be on-par or better than binary-A, it’s still best to double-check.

Read Optimization Reports for the Hotspots

Intel compilers produce an optimization report when compilation is performed with –qopt-report (/Qopt-report for Windows). Before trying to change the behavior of the compiler, it’s best to understand what the compiler has done and what it knows already. Article 1 in the References section at the end of this article is a good intro-
duction to using the optimization report. [Editor’s note: Vectorization Opportunities for Improved Performance with AVX-512 also has a good and more current overview of compiler reports.]

Compare Hot Spot Performance

Responses to the different compilation flag combinations can vary from one hotspot to another. If one hotspot runs fast with binary-B and another hotspot runs fast with binary-C, learning what the compiler did for those cases greatly helps in achieving the best for both.

Fine Tuning for ZMM Usage

For binary-B and binary-C, with the OpenMP simd construct, vector length can be explicitly controlled using the simdlen clause. Try using a larger or smaller vector length on a few hot spots to see how application performance responds. You may need to combine one or more tuning techniques.

Alignment

When you’re using Intel AVX-512 vector load/store instructions, it’s recommended to align your data to 64 bytes for optimal performance6, since every load/store is a cache-line split whenever a 64-byte Intel AVX-512 unaligned load/store is performed, given the cache line is 64 bytes. This is twice as much as the cache-line split rate of Intel® AVX2 code that uses 32-byte registers. A high rate of cache-line split in memory-intensive code may cause a 20 to 30 percent performance degradation. Consider the following struct:

struct RGB_SOA {
__declspec(align(64)) float Red[16];
__declspec(align(64)) float Green[16];
__declspec(align(64)) float Blue[16];
}

The memory allocated for the struct is aligned to 64 bytes, if you use this struct as follows:

RGB_SOA rgb;

However, if a dynamic memory allocation is used as follows, the __declspec annotation is ignored and the 64-byte memory alignment is not guaranteed:

RGB_SOA* rgbPtr = new RGB_SOA();

In this case, you should use dynamic aligned memory allocation and/or redefine the operator new. For AVX-512, align data to 64 bytes when possible using the following approaches:

• Use the _mm_malloc intrinsic with the Intel® Compiler, or _aligned_malloc of the Microsoft* Compiler for dynamic data alignment—e.g.: DataBuf = (float *)_mm_malloc (1024 * 1024 * sizeof(float), 64);
• Use __declspec(align(64)) for static data alignment—e.g.: __declspec(align(64)) float DataBuf[1024*1024];

Data allocation and uses may happen in different subroutines/files. Thus, the compiler working on the data us-age site often does not know that the alignment optimization has been made at the allocation site. __assume_aligned()/ASSUME_ALIGNED is a common assertion to indicate alignment at the data usage site. (See article 2 in the References section of this article and the applicable Intel Compiler Developer Guide and Reference for details.)

To Peel or Not to Peel?

The vectorizer often produces three versions of the same loop:

1. One processing the beginning of the loop (called the peel loop)
2. One for the main vector loop
3. One processing the end of the loop (called the remainder loop)

The peel loop is generated for alignment optimization purposes, but this optimization is a double-edged sword. If the loop trip count is small, it may lower the number of data elements processed by main vector loop. If the compiler chooses a wrong array to peel for, it can worsen the data alignment of the loop execution. The compiler flags –qopt-dynamic-align=F (/Qopt-dynamic-align=F for Windows) can be used to suppress the loop peeling optimization. The pragma vector unaligned can be used on a per-loop basis. The pragma vector aligned is even better if data is all aligned when entering the loop.

Vectorize Peel/Remainder and Short-Trip-Count Loops

The AVX-512 masking allows creation of a vectorized peel and remainder loops and vectorization of the short-trip-count loops. However, the vectorized versions of those special loops may not always result in performance gains, since most of the instructions need to be masked. The main reasons for possible performance problems are restrictions for store forwarding and possible stalls on merge-masked operations, when operation depends on others. In the compiler, the store forwarding issue can be addressed by thorough analysis of data flow and avoiding masking whenever possible. When the store-forwarding issue becomes inevitable, the unmasked version of the loop (e.g., scalar or vectorized loop with a shorter vector length) is preferred. You can avoid stalls on merge-masked operations by trying to use zero-masking operations. The following pragmas make it possible to provide hints to alter the compiler behaviors:

• For remainder loops:
  #pragma vector novecremainder, to not vectorize remainder loops
  #pragma vector vecremainder, to vectorize remainder loop depending on compiler cost model
  #pragma vector always vecremainder, to vectorize remainder loop always
• For short-trip-count loops:
  #pragma vector always, to enforce vectorization
  #pragma novector, to disable vectorization

Gather and Scatter Optimization

The gather and scatter instructions allow us to vectorize more loops. However, the vectorized code may or may not get performance benefits. The performance of loops that contain gather/scatter code depends on the ratio between the number of calculations and the number of data loads/stores and on selecting an optimal vector length for reducing the latency of gather and scatter instructions. A shorter vector length implies less latency of gather/scatter code. Often, a couple of simple optimizations at the source code level can help reduce the number of gather and scatter instructions.

Figure 13 shows the two simple manual gather/scatter optimizations while the compiler is trying to automatically perform these optimizations. The first optimization is to reduce number of gathers/scatters when the results of two gathers/scatters are blended as shown on the left. In this case, blending the indices makes it possible to have one gather instead of two as shown on the right. Note that we can apply the same process to scatter optimization.

The second gather/scatter optimization is an opposite transformation (Figure 14). In this case, a gather is performed with indices resulting from blend of unit-stride linear indices as shown on the left. To improve performance, it’s better to perform two unit-stride loads and then do the blend as shown on the right.

// Two gathers in the loop
float *a, sum = 0; int *b, *c;
… …
for (int i; i < n; i++) {
  if ( pred(x[i]))
      sum += a[b[i]]; // gather
  else
      sum += a[c[i]]; // gather
}

// Optimized with one gather in the loop
for (int i; i < n; i++) {
  int t;
  if ( pred(x[i]))
     t = b[i];
else
   t = c[i];
sum += a[t]; // one gather remain
}

// One gather in the loop
float *a, sum = 0; int a;
for (int i; i < n; i++) {
  int t;
  if (pred(x[i])) {
      t = i + b;
  }
  else {
   t = i;
  }
  sum += a[t]; // gather
}

// Replace gather with unit-stride loads + blending
for (int i; i < n; i++) {
  float s;
  if ( pred(x[i])) {
      s = a[i + b];   // unit stride vector load
  }
  else {
       s = a[i];     // unit stride vector load
  }
  sum += s;
}

Execution Latency Improvement

For loop vectorization, a known issue for compilers is that the loop trip count is unknown at compile time. However, programmers can often predict the trip count and provide a hint to the compiler using #pragma loop count. In some cases, the loop trip count can be predicted approximately based on #pragma unroll information as well. Preferably, the unroll pragma should be used on loops with small enough bodies to decrease number of loop iterations and to increase loop iteration independency, so they can be executed in parallel on out-of-order Intel® architectures to hide execution latency. Loop unrolling is very helpful for computation-bounded loops (i.e., when the computation takes more time than memory accesses). For example, the loop shown in Figure 15 will execute about 45 percent faster when the unroll-factor (UF) is set to 8 compared to a UF equal to 0. The measurement was done for n=1,000.

float *a,*b, *c;
#pragma unroll(8)
#pragma omp simd
for (i= 0; i < n; i++) { 
  if (a[i] > c[i]) sum += b[i] * c[i];
}

Summary and Future Work

We’ve looked at several new simd language extensions for Intel AVX-512 support in Intel Compilers 18.0 for Intel Xeon Scalable processors. We shared and discussed a set of performance optimization and tuning practices for achieving optimal performance with AVX-512. We provided performance results based on microkernels to demonstrate the effectiveness of these new simd extensions and tuning practices. In the future, there are several new simd extensions for C/C++ under consideration for taking full advantage of AVX-512 through OpenMP and the C++ Parallel STL, including inclusive-scan, exclusive-scan, range-based C++ loops, and lambda expression support.

Learn More

• Intel Advanced Vector Extensions 512 >
• Intel Xeon Scalable processors >

References

1. M. Corden. "Getting the Most out of your Intel® Compiler with the New Optimization Reports," Intel Developer Zone, 2014.
2. R. Krishnaiyer. "Data Alignment to Assist Vectorization," Intel Developer Zone, 2015.
3. H. Saito, S. Preis, N. Panchenko, and X. Tian. "Reducing the Functionality Gap between Auto-Vectorization and Explicit Vectorization." In Proceedings of the International Workshop on OpenMP (IWOMP), LNCS9903, pp. 173-186, Springer, 2016.
4. H. Saito, S. Preis, A. Cherkasov, and X. Tian. "Obtaining the Last Values of Conditionally Assigned Privates," OpenMPCon Developer Conference, 2016.
5. H. Saito, "Extending LoopVectorizer: OpenMP4.5 SIMD and Outer Loop Auto-Vectorization," presentation at LLVM Developer Conference, 2016.
6. X. Tian. H. Saito, M. Girkar, S. Preis, S. Kozhukhov, A. Duran. "Putting Vector Programming to Work with OpenMP* SIMD," The Parallel Universe magazine, Issue 22, September 2015.
7. X. Tian, R. Geva, B. Valentine. "Unleash the Power of AVX-512 through Architecture, Compiler and Code Modernization," ACM Parallel Architecture and Compiler Technology, September 11-15, 2016, Haifa, Israel.
8. X. Tian, H. Saito, M. Girkar, S. Preis, S. Kozhukhov, A. G. Cherkasov, C. Nelson, N. Panchenko, R. Geva. Compiling C/C++ SIMD Extensions for Function and Loop Vectorizaion on Multicore-SIMD Processors. IEEE IPDPS Workshops 2012: 2349-23
9. Intel Corporation. "Conflict Detection" In Section 13.16 of Intel® 64 and IA-32 Architectures Optimization Reference Manual, July 2017.