SIMD and SWAR Techniques

Edit 0 83 …
Home * Programming * SIMD and SWAR Techniques
250px-SIMD.svg.png
x86, x86-64, as well as PowerPC and Power ISA v.2.03 processors provide Single Instructions on Multiple Data (SIMD), namely on vectors of floats, doubles or various integers, bytes, words, double words or quad words, available through assembly and compiler intrinsics. SIMD-applications related to computer chess cover bitboard computations and fill-algorithms like Dumb7Fill and Kogge-Stone Algorithm, as well as evaluation related stuff, like this SSE2 dot-product of 64 bits by a vector of 64 bytes.

SWAR as acronym for SIMD Within A Register was coined by Hank Dietz and Randy Fisher [1] . It is a processing model which applies SIMD parallel processing across sections of a CPU register, often vectors of smaller than byte-entities are processed in parallel prefix manner.
SIMD [2]

SIMD Instruction Sets


SWAR Arithmetic

To apply addition and subtraction on vectors of bit-aggregates or bit-field structures within a general purpose register, one has to take care carries and borrows don't wrap around. Thus the need to mask of all most significant bits (H) and add in two steps, one 'add' with MSB clear and one add modulo 2 aka 'xor' for the MSB itself. For bytewise (rankwise) math inside a 64-bit register, H is 0x8080808080808080 and L is 0x0101010101010101.
SWAR add z = x + y
    z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)
SWAR average z = (x+y)/2 based on x + y = (x^y) + 2*(x&y)
    z = (x & y) + (((x ^ y) & ~L) >> 1)

Samples

Amazing, how similar these two SWAR- and parallel prefix wise routines are. Mirror horizontally and population count have in common to act on vectors of duos, nibbles and bytes. One swaps bits, duos and nibbles, while the second adds populations of them.
U64 mirrorHorizontal (U64 x) {
    const U64 k1 = C64(0x5555555555555555);
    const U64 k2 = C64(0x3333333333333333);
    const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
    x = ((x & k1) << 1) | ((x >> 1)  & k1);
    x = ((x & k2) << 2) | ((x >> 2)  & k2);
    x = ((x & k4) << 4) | ((x >> 4)  & k4);
    return x;
}
int popCount (U64 x) {
    const U64 k1 = C64(0x5555555555555555);
    const U64 k2 = C64(0x3333333333333333);
    const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
    x =   x             - ((x >> 1)  & k1);
    x =  (x & k2)       + ((x >> 2)  & k2);
    x = ( x             +  (x >> 4)) & k4 ;
    x = (x * C64(0x0101010101010101))>> 56;
    return (int) x;
}

Publications


Manuals

AMD

NXP Semiconductors

Intel


Forum Posts


External Links

x86

Other SIMD

Misc


References

  1. ^ The Aggregate: SWAR, SIMD Within A Register by Hank Dietz
  2. ^ Flynn's taxonomy from Wikipedia
  3. ^ SSE5 from Wikipedia
  4. ^ Georg Hager's Blog | Random thoughts on High Performance Computing
  5. ^ On December 7, 2015, NXP Semiconductors completed its acquisition of Freescale, Freescale from Wikipedia

What links here?

Page Date Edited
Aart Bik Mar 1, 2018
Algorithms May 5, 2017
AltiVec Jun 7, 2016
Array Dec 1, 2016
AVX Mar 7, 2017
AVX-512 Aug 8, 2017
AVX2 Aug 8, 2017
Bitboards Nov 14, 2017
BMI1 Mar 24, 2014
Byte Apr 5, 2013
Color of a Square May 24, 2015
Cray-1 Dec 25, 2017
Critter Jan 25, 2014
Daisuke Takahashi May 23, 2016
Dan Wu Jun 18, 2011
Dictionary Aug 24, 2017
DirGolem Jun 5, 2016
Efficient Generation of Sliding Piece Attacks Nov 5, 2016
Fill by Subtraction Mar 5, 2010
Flipping Mirroring and Rotating Oct 14, 2016
Float Nov 11, 2016
General Setwise Operations Feb 25, 2018
GPU Dec 16, 2017
Hank Dietz May 3, 2011
i860 Aug 21, 2015
Itanium Aug 29, 2015
Jinli Rao May 23, 2016
Kui Dai May 23, 2016
Laser Dec 27, 2017
Matteo Frigo Jan 7, 2016
MMX Jun 5, 2016
Mobility Jan 17, 2018
Neural Networks Mar 12, 2018
Nibble Jan 25, 2015
NoraGrace Nov 23, 2014
OpenCL Aug 29, 2014
Optimization Feb 28, 2018
Pan Chen May 23, 2016
Parallel Prefix Algorithms Jun 22, 2016
Parallel Search Dec 30, 2017
Pigeon Nov 2, 2016
Population Count Sep 3, 2017
PowerPC Oct 6, 2017
Programming Dec 16, 2017
Quad-Bitboards Jan 30, 2017
Richard Vida Aug 11, 2013
Score Apr 14, 2018
SIMD and SWAR Techniques Jun 27, 2017
SIMD techniques Nov 26, 2017
SPARC Jan 17, 2017
SSE Mar 7, 2017
SSE2 Feb 27, 2018
SSE3 Jun 5, 2016
SSE4 Jun 5, 2016
SSE5 Jun 5, 2016
SSSE3 Aug 8, 2017
Stockfish Apr 7, 2018
Tapered Eval Jan 9, 2018
Thread Apr 22, 2018
Wojciech Muła Aug 10, 2017
Word Jan 25, 2015
WyldChess Mar 10, 2018
x86-64 Mar 6, 2018
XOP Aug 8, 2017
Xuecheng Zou May 23, 2016

Up one Level