SSE2 (Streaming SIMD Extensions 2) and further
x86- or
x86-64 streaming
SIMD extensions, like
SSE3,
SSSE3,
SSE4 and AMD’s announced
SSE5, as major enhancement to
SSE, provide an instruction set on 128-bit registers, namely on
vectors of four
floats or two
doubles, as well since SSE2 as vectors of 16
bytes, eight
words, four
double words or two
quad words[1]. In 64-bit mode there are 16 xmm registers available, xmm0..xmm15, in 32-bit mode only eight, xmm0..xmm7. SSE is explicitly available through
C-Compiler intrinsics [2] or (inline)
assembly. Some compiler implicitly use SSE-float and double instructions for floating point data types, others even provide automatic SSE2 vectorization, while processing
arrays of various integer types. SSE- and SSE2-intrinsic functions are available in
Visual C[3] or
Intel-C[4].
Since 128-bit xmm registers may treated as vector of 16 bytes, shifting techniques such as
one step in all eight directions can be done more efficiently with respect to wraps from a- to the h-file or vice versa. It is recommend to write a own SSE2-wrapper class with overloaded operators in C++ to encapsulate a vector of two bitboards.
Veritcal steps as usual with 64-byte shift a rank each:
Unfortunately there is no byte-wise shift in the SSE2-instruction set (as well as MMX), but using byte-wise parallel add avoids using the wrap masks, which need otherwise load from memory or computed. Applying the wraps mask takes two instructions.
This is how the east direction are computed based on parallel byte-wise add. Either one or two SSE2-instructions:
West directions need a leading not A-file and take three instructions each:
The
dot product[5] of a vector of
bits by a weight vector of
bytes might be used in determining
mobility for
evaluation purposes. The vector of bits is a bitboard of all squares attacked by one (or multiple) piece(s), while the the weight vector considers the “importance” of
squares, like center control, or even
square controls near the opponent
king, e.g. by providing 64 weight vectors for each king square.
The 64-bit times 64-byte dot product implements a kind of weighted
population count similar than following loop approach, but completely unrolled and
branchless:
The SSE2 routine expands a bitboard as a vector of 64 bits into 64-bytes inside four 128-bit xmm registers, and performs the multiplication with the byte-vector by bitwise ‘and’, before it finally adds all bytes together. The bitboard is therefor manifolded eight times with a sequence of seven unpack and interleave instructions to remain the same expanded byte-order of the bits from the bitboards, before to mask and compare them with a vector of bytes with one appropriate bit set each.
The dot product is designed for unsigned weights in the 0..63 range, so that vertical bytewise adds of the four weights can not overflow. Nevertheless, three PADDUSB - packed add unsigned byte with saturation instructions (
_mm_adds_epu8) are used to limit the maximum four byte sum to 255 to make the routine more “robust” for cases with average weights greater than 63. The horizontal add of both
quad words of the 128-bit xmmregister is performed by the PSADBW - packed sum of absolute differences of bytes into a word instruction (
_mm_sad_epu8) with zero, while the final add of the two resulting
word sums in the high and low quad word of the xmm register is done with general purpose registers.
Following proposal of a
SWAR-Popcount combined with a dot product might be quite competitive on recent
x86-64 processors with a throughput of up to three simd-instructions per cycle [7][8] . It determines the cardinalities of eight bitboards, multiplies them with a corresponding weight, a signed 16-bit
word, to finally add all together as integer. However,
Wojciech Muła’sSSSE3 PopCnt would save some more cycles, even more with doubled or fourfold register widths using
AVX2 or
AVX-512.
C++ quite efficiently allows to wrap all the intrinsics and to write classes with appropriate operators overloaded - the proposal here overloads + and - operators for byte- or rank-wise arithmetic, shifts work on 64-bit entities as often used in mentioned SSE2-routines or
Kogge-Stone fill-stuff. A base class for the memory layout and two derivations provide to implement routines with SSE2 or general purpose instructions - or any other available SIMD-architecture like
AltiVec. For instance a
quad-bitboard attack-getter: