Data Parallelism
Data parallelism is doing the same operation on many pieces of data in the same time.
Processors do this using SIMD (Single Instruction, Multiple Data).
SIMD
SIMD is a hardware feature that allows to work on vectors of numbers at once.
Difference between SIMD and Multithreading
Multithreading: Here multiple instructions are done at the same time.
SIMD: One instruction is applied on multiple data values.
The %xmmn registers for floating point operations are the SIMD registers in x86-64. We
have only been using the lower 64 bits, but there was more we could use.
Just like %rax, %eax, %ax and %al are different size aliases for general purpose registers,
for the SIMD registers, the %xmmn refer to 128 bit registers. The %ymmn registers are 256
bit extensions. Like %xmm6 is the lower 128 bits of 128 bits of %ymm6.
AVX (Advanced Vector Extension)
Earlier CPUs only had 128 bit = 16 bytes SIMD registers called XMM registers. With the
advent of AVX the width doubled. AVX introduced YMM registers which can hold 256 bits =
32 bytes.
Now uptil now we used int32 instead if int64 and float instead of double which gave minor
benefit. But with AVX now twice as many will fit in the SIMD registers, so one instruction
can operate on twice as many.
SIMD Instruction
Here is the syntax
Aligned memory loads might be slightly faster. But for safety, using unaligned versions is
recommended unless alignment is guaranteed.
Why Array of Structs are Hard for SIMD
Having to work with an array of struct or class values would be difficult as we do not have
the memory layout er need. For example: If we want to do some calculation on many of
those values (e.g. adjust the colour balance of all of all pixels in an image), it's hard to get
all of the red values into a SIMD register to start working with them.
There are gather instructions (vgatherdps) but they are slow and complicated.
Summing an Array with SIMD
We will be summing an array of double with the floating-point SIMD instructions. When
loading data into the ymmn registers, we’ll read 32 adjacent bytes from memory. Then we
can do vector operations to add up columns.
We start we the Scalar Double Version (double_sum_1) and SIMD Double Version
(double_sum_2)
Scalar Doubler version is simply conversion to handle double values from integers
values. “vxorpd” is XOR,
and XORing a register with itself set itseld to all bits 0 = 0.0 for %xmm0 here. Then simply
we run a loop moving 8 bytes ahead to handle each value and add the value to xmm0
using “addsd”(add scalar double). Each double is 8 bytes in size.
SIMD Double Version here we use ymm0 to return the result which is twice the capacity of
xmm0. Start with setting ymm0 to 0.0 by XORing with itself. We start looping until the
counter is equal to length of the array. We every loop we move 32 bytes ahead as we pick
and compute 4 values together. We increment the counter by 4. The 4 value addition is
done by vector addition “vaddpd” .
Every element in ymm0 is a partial sum. Now we need to perform horizontal sum to get the
final sum of the array given.
After exiting the loop we go to the ds2_return section:
Right now we have %ymm0 as:
“vextractf128” extracts the UPPER 128 bits into %xmm1, and the LOWER 128 bits go into
%xmm0.
Now we add the two xmmn registers using “vaddpd”:
Now we want to add these two cells and store it in xmm0, but this cannot be done directly
and need to store the second element of xmm0 at the first position of xmm1 and the first
element of xmm0 at the second position of xmm1. We need to do this so that we can
perform the addition of cell 1 and 2 to get the final sum.
This is called shuffling, we simply copied the data from xmm0 into xmm1 but shuffled it.
This is done using: . $0b01 tells that place second
element of xmm0 at the first position of xmm1 and first element of xmm0 at second
position of xmm1.
After the shuffling xmm1 = [(d+h+l) + (b+f+j), (c+g+k) + (a+e+i)]. Now we perform
SCALAR add to get the final sum using: . It is important to see
that we are using vaddsd and not vaddpd. Vaddsd only adds the lowest double of a register
whereas vaddpd operates on the whole SIMD, which would take into account 2 doubles for
xmmn, 4 in ymmn.
We use vaddpd after extraction to get: xmm0 =
After shuffling we have xmm1 = [(d+h+l) + (b+f+j), (c+g+k) + (a+e+i)].
Therfore after , this would set xmm0[0] = xmm0[0] +
xmm1[0]. Which is the required result. And we know when returning the xmm0 though
xmmn registers are 128 bit in size but only lower 64 bits are returned hence we get the
final sum returned.
float_sum_1 is very similar to double_sum_1 and the entire explanation works, the only
change here is we move 4 bytes forward at each loop iteration instead of 8 as a float has a
size of 4 bytes. Also we use “addss” for scalar add of float. Also we use “vxorps” for floats.
float_sum_2 is very similar to double_sum_2, here also we move 32 bytes each loop
iteration but because we are using a float we calculate 8 floats each iteration. To add the
bunch of 8 floats that is SIMD operation we use “vaddps”.
Assume after coming out of the loop we have:
Now we extract the UPPER 128 bits to xmm1 and lower to xmm0. Therefore, xmm1 looks
like:
We simply add xmm0 and xmm1 to get new xmm0:
Now we will shift (or push forward. We can see pushing values after (b+f) over the cliff and
we do not now and we don’t care what values get filled in place of (a+e) and (b+f)) first 2
values of xmm0:
Next we simply add xmm0 to xmm1 to get new xmm0:
we again push forward:
Now we add xmm0 and xmm1 for the last time to get the final sum:
We do not care about the other values as the lowest 64 bits will be returned which is
a+b+c+d+e+f+g+h.
The complete process of horizontal add is:
Vectorclass Library
Vectorclass library is a C++ wrapper for SIMD. The library provides C++ types to represent
values packed into the SIMD registers. The 256-bit-wide types we're most interested in:
Operator Overloading
The above code produces:
Now acc += numbers; is equivalent to assembly code:
Now acc = [0,1,2,3,4,5,6,7]
Then acc = acc * numbers; is equivalent to assembly code:
acc =
Printing values
Error
This would give an error because operator+= is only for the same type operands.
Like Vec8f += Vec8f
Vec4d += Vec4d
.load()
The method can load values from a memory location into a SIMD register (the vmovupd
instruction or similar). They are a pointer to the corresponding number/type of values.
.Store()
This writes the contents of a SIMD vector back to normal memory like an array of floats,
doubles or ints.
It is the reverse of .load().
Lets say we have an empty array called addr. If we want to put some data from out SIMD
register into this array then:
Assume that the register has some values in there already: