Integer Addition

Listing 2-1 begins with the declaration of a C++ structure named XmmVal , which is declared in the header file XmmVal.h. This structure contains a publicly accessible anonymous union whose members correspond to the packed data types that can be used with a 128-bit wide x86-AVX operand. Note that XmmVal is declared using the alignas(16) specifier. This specifier instructs the C++ compiler to align each instance of an XmmVal on a 16-byte boundary. When an x86 processor executes an x86-AVX instruction that references an operand in memory, maximum performance is achieved when the operand is aligned on its natural boundary (e.g., 16-, 32-, or 64-byte boundaries for 128-, 256-, or 512-bit wide data types, respectively). Some x86-AVX instructions require their operands to be properly aligned, and these instructions will raise an exception if they attempt to access a misaligned operand in memory. You will learn more about this later. The structure XmmVal also contains several member functions that format the contents of an XmmVal variable for streaming to std::cout. The source code for these member functions is not shown in Listing 2-1 but is included in the software download package. Structure XmmVal is used in this example and in later source code examples to demonstrate x86-AVX SIMD operations.

The next file in Listing 2-1, Ch02_01.h, incorporates the requisite C++ function declarations for this source code example. Note that the function declarations in this header file use the previously defined XmmVal structure. Also note that file Ch02_01.h begins with a short comment block that includes its name to make it identifiable in the listing.

The file Ch02_01.cpp is next. This file contains the function main() and two other static functions named AddI16() and AddU16(). Function AddI16() begins its execution by initializing two XmmVal variables with packed 16-bit signed integer data. This is followed by a call to the function AddI16_Iavx(), which performs packed 16-bit signed integer addition. The remaining code in AddI16() displays the results calculated by AddI16_Iavx(). The function AddU16() is almost identical to AddI16() except that it uses unsigned instead of signed integers.

The final file in Listing 2-1 is Ch02_01_fcpp.cpp. This file contains two SIMD calculating functions named AddI16_Iavx() and AddU16_Iavx(). Near the top of this file is an #include statement for the header file immintrin.h. This file contains the declarations for the C++ SIMD intrinsic functions that are used in Ch02_01_fcpp.cpp. Function AddI16_Iavx() begins its execution with a call to _mm_load_si128 (). This C++ SIMD intrinsic function loads the contents of argument a into a_vals. Note that a_vals is declared as an __m128i, which a 128-bit wide C++ SIMD intrinsic type of 8-, 16-, 32-, or 64-bit integers. The _mm_load_si128 () function requires its source operand to be properly aligned on a 16-byte boundary. This requirement is satisfied by the alignas(16) specifier that was used in the declaration of XmmVal . Another call to _mm_load_si128 () is then employed to initialize b_vals.

Following SIMD variable initialization, AddI16_Iavx() employs the C++ SIMD intrinsic function _mm_add_epi16 (), which performs packed 16-bit integer addition using operands a_vals and b_vals. The result of this addition is saved in an __m128i variable named c1_vals. The ensuing call to _mm_adds_epi16 () also performs packed 16-bit integer addition but carries out its calculations using saturated instead of wraparound arithmetic. The final two code statements of AddI16_Iavx() employ the C++ SIMD intrinsic function _mm_store_si128 (). This function saves a 128-bit wide packed integer value to the specified target buffer, which must be aligned on 16-byte boundary.

Other C++ SIMD intrinsic functions are available for packed integer addition. You can use the C++ intrinsic function _mm_add_epi8(), _mm_add_epi32(), or _mm_add_epi64() to perform packed addition using 8-, 32-, or 64-bit wide signed or unsigned integers. You can also use the function _mm_adds_epi8() or _mm_adds_epu8() to carry out packed saturated addition using 8-bit signed or unsigned integers. Note that distinct C++ SIMD intrinsic functions are used for wraparound and saturated integer addition since these operations can generate different results as explained in Chapter 1.

Integer Subtraction

The organization of the source code in example Ch02_02 parallels the previous example. In the file Ch02_02.cpp, the function SubI32() initializes XmmVal variables a and b using 32-bit signed integers. It then calls SubI32_Iavx(), which performs the packed subtraction. Function SubI64() is akin to SubI32() but uses 64-bit signed integers.

You can use the C++ SIMD intrinsic function _mm_sub_epi8() or _mm_sub_epi16() to perform packed subtraction using 8- or 16-bit wide signed or unsigned integers, respectively. To perform saturated packed subtraction, you can use the C++ SIMD intrinsic function _mm_subs_epi8(), _mm_subs_epi16(), _mm_subs_epu8(), or _mm_subs_epu16().

Integer Multiplication

In file Ch02_03.cpp, the C++ function MulI16() contains code that initializes XmmVal variables a and b using 16-bit signed integers. It then calls MulI16_Iavx(), which performs the packed integer multiplication. The results are then streamed to std::cout. The other two static functions in Ch02_03.cpp, MulI32a() and Mul32b(), perform similar initialization tasks for 32-bit packed integer multiplication and then call MulI32a_Iavx() and MulI32b_Iavx(), respectively.

Recall that when performing integer multiplication, the product of two n-bit wide integers is always 2n bits. When performing packed integer multiplication, additional processing is sometimes necessary to form the final products as you will soon see. Function MulI16_Iavx() starts with two _mm_load_si128 () calls that initialize XmmVal variables a and b. It then employs the C++ SIMD intrinsic function _mm_mullo_epi16 () to perform packed 16-bit integer multiplication. This function returns an __m128i value that contains only the low-order 16 bits of each 32-bit product. Function MulI16_Iavx() then uses the C++ SIMD intrinsic function _mm_mulhi_epi16 () to calculate the high-order 16 bits of each 32-bit product. The next function call, _mm_unpacklo_epi16 (), interleaves the four low-order 16-bit integer elements of source operands temp_lo and temp_hi to form 32-bit integer products. The subsequent call to _mm_unpackhi_epi16 () performs a similar operation using the four high-order 16-bit integer elements of the same source operands. Figure 2-1 illustrates the product calculation that MulI16_Iavx() employs.

Function MulI32a_Iavx() highlights one method of performing packed 32-bit signed integer multiplication. This function uses the C++ SIMD intrinsic function _mm_mullo_epi32 () to calculate the low-order 32 bits of each product. The packed 32-bit integer products are then saved using _mm_store_si128 (). This technique is suitable when calculating multiplicative products that will not exceed the value limits of a 32-bit signed integer.

Function Mul32b_Iavx() demonstrates another technique for calculating products using packed 32-bit signed integers. Following the initialization of a_vals and b_vals, Mul32b_Iavx() uses the C++ SIMD intrinsic function _mm_mul_epi32 () to calculate a.m_I32[0] * b.m_I32[0] and a.m_I32[2] * b.m_I32[2]. Note that _mm_mul_epi32 () computes complete 64-bit products. The subsequent _mm_srli_si128 () and _mm_srli_si128 () calls right shift a_vals and b_vals by 4 bytes (zeros are shifted in). The reason for these shifts is that _mm_mul_epi32 () carries out its calculations using only the even numbered elements of its two operands. The right shift operations facilitate calculation of the products a.m_I32[1] * b.m_I32[1] and a.m_I32[3] * b.m_I32[3] by the ensuing call to _mm_mul_epi32 () as shown in Figure 2-2. The final 64-bit products are then extracted from temp1 and temp4 using a series of calls to _mm_extract_epi64 (). The constant that is specified in each _mm_extract_epi64 () call designates which 64-bit integer to extract from the 128-bit wide source operand.

Bitwise Logical Operations

Shift Operations

Pixel Minimum and Maximum

The first file in Listing 2-6 is Ch02_06.h. This file contains the requisite function declarations and a few miscellaneous constants. Note that the function declarations use the fixed-width integer type uint8_t, which is defined in the header file <cstdint>. Some programmers (including me) prefer to use the fixed-width integer types in SIMD calculating functions since it eschews the size ambiguities of the standard C++ integer types char, short, int, long, and long long.

The next file in Listing 2-6, Ch02_06_misc.cpp, contains a simple function named InitArray(). This function fills an array of 8-bit unsigned integers using random values. The actual filling of the array is performed by a template function named MT::FillArray(), which is defined in the header file MT.h. The driver function for this example is named CalcMinMaxU8() and is defined in Ch02_06.cpp. Near the top of CalcMinMaxU8() is the statement AlignedArray <uint8_t> x_aa(n, 16). This statement dynamically allocates an n element array of uint8_t integers that is aligned on a 16-byte boundary. The source code for both MT.h and AlignedMem.h (which contains the template class AlignedMem<T>) is not shown in Listing 2-6 but is included in the software download package.

The principal calculating functions for example Ch02_06 are defined in the file Ch02_06_fcpp.cpp. The first function in this module, CalcMinMaxU8_Cpp(), finds the minimum and maximum value in an array of uint8_t integers. This function is coded using typical C++ statements sans any C++ SIMD intrinsic functions and will be used later for comparison and benchmarking purposes. Note that prior to the start of the for-loop, two error checks are performed. The first error check ensures that n is not equal to zero and an integral multiple of 16. Requiring n to be an integral multiple of 16 is not as restrictive as it might appear since the number of pixels in a digital camera image is often an integral multiple of 64 due to the processing requirements of the JPEG algorithms. Later examples will include additional code that can process arrays of any size. The second error check ensures that the source pixel buffer x is properly aligned on a 16-byte boundary.

The SIMD counterpart function to CalcMinMaxU8_Cpp() is named CalcMinMaxU8_Iavx(). This function starts its execution by validating n for size and x for proper alignment. The next statement uses the C++ SIMD intrinsic function _mm_set1_epi8 () to set each 8-bit element in min_vals to 0xFF. This is also known as a broadcast operation. Unlike the non-SIMD min-max function, the for-loop in CalcMinMaxU8_Iavx() maintains 16 intermediate pixel minimums as it sweeps through pixel buffer x and the variable min_val holds these values. The next statement uses _mm_setzero_si128 () to initialize each 8-bit element in max_vals to 0x00. This variable holds intermediate pixel maximums during execution of the for-loop.

Immediately before the start of the for-loop, the constant variable num_simd_elements is set to 16 and represents the number of pixels processed during each iteration of the for-loop. This is the reason for requiring n to be an integral multiple of 16. The for-loop itself begins with a call to _mm_load_si128 () that loads 16 8-bit unsigned integer elements from pixel buffer x into x_vals. The next statement uses the C++ SIMD function _mm_min_epu8 () to update the intermediate minimum values maintained in min_vals. This function compares the two 128-bit wide operands of 8-bit unsigned integers and returns an __m128i value that contains the minimum value of each element compare as shown in Figure 2-3. The C++ SIMD intrinsic function _mm_max_epu8 () performs the corresponding 8-bit unsigned integer packed maximum compare and is also shown in Figure 2-3.

Following execution of the for-loop, packed variables min_vals and max_vals contain the final 16 minimum and maximum values, respectively. The true pixel minimum and maximum value is one of the elements in these variables. To find the true minimum and maximum values, both min_vals and max_vals must be reduced to a single scalar value. For min_vals, this is accomplished using a series of _mm_srli_si128 () and _mm_min_epu8 () calls as shown in Figure 2-4. The code that reduces max_vals to a scalar value is almost identical except that it uses the C++ SIMD intrinsic function _mm_max_epu8 () instead. Following each reduction operation, CalcMinMaxU8_Iavx() employs _mm_extract_epi8 () to extract the final 8-bit unsigned integer value.

The final function in Listing 2-6 is named CalcMinMaxU8_bm(). This function contains code that measures the execution times of functions CalcMinMaxU8_Cpp() and CalcMinMaxU8_Iavx(). Most of the timing measurement code is encapsulated in a C++ class named BmThreadTimer . This class includes two member functions, BmThreadTimer::Start() and BmThreadTimer::Stop(), that implement a simple software stopwatch. Class BmThreadTimer also includes a member function named BmThreadTimer::SaveElapsedTimes(), which saves the timing measurements to a comma-separated text file. The source code for class BmThreadTimer is not shown in Listing 2-6 but included as part of the source code download package.

The values shown in Table 2-3 were computed using the CSV file execution times (500 runs of each algorithm) and the Excel spreadsheet function TRIMMEAN(array,0.10). In example Ch02_06, the C++ SIMD intrinsic function implementation of the pixel minimum-maximum algorithm clearly outperforms the standard C++ version by a wide margin. It is not uncommon to achieve significant speed improvements when using C++ intrinsic functions, especially by algorithms that can fully exploit the SIMD parallelism of an x86 processor. You will see additional examples of accelerated algorithmic performance throughout the remainder of this book.

The benchmark timing measurements cited in this book provide reasonable approximations of function execution times. They are intended to provide some insights regarding the performance of a function coded using standard C++ statements vs. a function coded using C++ SIMD intrinsic functions. Like automobile fuel economy and mobile device battery runtime estimates, software performance benchmarking is not an exact science and subject to a variety of uncontrollable factors. It is also important to keep mind that this book is an introductory primer about x86 SIMD programming and not benchmarking. The source code examples are structured to hasten the study of x86 SIMD programming techniques. In addition, the Visual C++ options described earlier were selected mostly for practical reasons and may not yield optimal performance in all cases. Both Visual C++ and GNU C++ include a plethora of code generation options that can affect performance. Benchmark timing measurements should always be construed in a context that is correlated with the software’s purpose. The methods described in this section are generally worthwhile, but measurement results occasionally vary. Appendix A contains additional information about the software tools used to develop the source code examples in this book.

Pixel Mean Intensity

The organization of the code in this example is similar to Ch02_06. File Ch02_07_misc.cpp contains two functions, CheckArgs() and InitArray(), which perform argument checking and array initialization, respectively. Note that the size of the source array must be an integral multiple of 64 and aligned on a 16-byte boundary. The function CheckArgs() also verifies that the number of array elements n is less than g_NumElementsMax. This size restriction enables the C++ SIMD code to perform intermediate calculations using packed 32-bit unsigned integers without any safeguards for arithmetic overflows.

Calculation of an array mean is straightforward; a function must sum the elements of the array and then divide this sum by the total number of elements. The function CalcMeanU8_Cpp() accomplishes this using a simple for-loop and scalar floating-point division.

The C++ SIMD counterpart function is named CalcMeanU8_Iavx(). Following argument validation using CheckArgs(), CalcMeanU8_Iavx() initializes variables packed_zero and pixel_sums_u32 to all zeros. The former variable is employed by the for-loop to perform unsigned integer size promotions, and the latter maintains four 32-bit unsigned integer intermediate sum values. The main for-loop is next. Note that each for-loop iteration processes 64 array elements since the index variable i is incremented by num_simd_elements * 4. The reason for doing this is that it reduces the number of 8-bit to 32-bit unsigned integer size promotions required to calculate the final pixel sum.

The first executable statement of the for-loop sets pixel_sums_u16 to zero. This variable holds eight 16-bit unsigned integer sums. The _mm_load_si128 () call that follows loads 16 pixels into the variable pixel_vals_u8. The next two statements employ the C++ SIMD intrinsic functions _mm_unpacklo_epi8 () and _mm_unpackhi_epi8 () to size-promote the pixel values from 8 bits to 16 bits. Following this size promotion task, the for-loop executes two _mm_add_epi16 () calls to update the intermediate packed sum value pixel_sums_u16 as shown in Figure 2-5. The for-loop repeats this pixel-load and size-promotion summing sequence three more times. The final code block in the for-loop promotes the 16-bit unsigned integer values in pixel_sums_u16 to 32 bits and adds these values to pixel_sums_u32. The for-loop uses the C++ SIMD intrinsic functions _mm_unpacklo_epi16 () and _mm_unpackhi_epi16 () to carry out the size promotions and _mm_add_epi32() to perform the packed 32-bit addition.