Optimizing Your Volume Slider 2 – SIMD Edition

So, last time we went over three different algorithms for volume scaling, and determined that fixed point math is a very good choice. Not necessarily always the best – what’s the best algorithm for a given task can vary with the available hardware – but what offered a high level of performance in my tests (and likely will in different situations as well). If you haven’t read the previous Optimizing Your Volume Slider post, I would encourage you to do so now.

So, we have an algorithm that seems to work well. Let’s stick it in our sound library and call it a day, right? Well, you could… but this algorithm could be even faster, if we’re willing to go deeper. I know I’ve said ‘learning how the CPU works at a low level will help you write higher level code’ a few times, and now we’re going to be seeing the results of that. However, this isn’t something I can dive straight into the results of first – there are a few things we need to understand before getting to the benchmarking.

First off, the concept of “Single Instruction Multiple Data”, or “SIMD”. It’s a feature of processors that… well, you should be able to guess from the name. How it works is that the processor has a series of extra wide SIMD registers. You can then split a series of data across the registers – say, taking 8 entries from a uint_16t array at once and loading them into an SIMD register. Once you’ve got the register loaded up, you can then perform some operation on all 8 uint_16ts in the SIMD register simultaneously.

How does this make things faster? Because each CPU has multiple separate units capable of performing math, and these units can operate independently. There are a number of considerations in SIMD optimization – for example, if the order of the operations matters, then you can’t use SIMD for them (because SIMD doesn’t guarantee which operation will finish first). If you’re interested in optimization, I encourage you to look further into SIMD – there are many good resources on the subject, and I’ll be more providing a broad overview of SIMD related techniques instead of going into exacting detail.

First off, have a download link for some programs https://drive.google.com/open?id=17IcddmmqKczyRTetmyCfqGF9sny3Nt0f . We’ll be going through them to get a clue on how some of these techniques work, before going into the optimization results in the next blog post.

First off, let’s look at the familiar vol1.c, and with it the first SIMD / vectorization technique. This technique being ‘let gcc do it’. This is the interesting part:

	for (x = 0; x < SAMPLES; x++) {
		// this change causes it to be vectorized
		//ttl = ttl + data[x]%1000;
		ttl=(ttl+data[x])%1000;
	}

The commented code can be vectorized (converted into SIMD instructions), while the uncommented code cannot. Why is that? The answer in this case is pretty simple. The result of (ttl+data[x])%1000 cannot be done out of order or you will get different results. ttl = ttl + data[x]%1000; can be done in any order you want, and ttl will sum up to the same thing at the end.

Moving onwards, let’s check out vol_inline.c. From here on out, there will be little ‘questions’ in the code in comments – knowing the answers to them is important to understanding what’s going on. I’ll be explaining the answers as we move through the two remaining files. Anyway, vol_inline.c does our familiar fixed point math volume scaling, but it does it using C’s ‘inline assembly’ syntax, which allows you to write asm in C files, and have the asm integrate with the C code around it. This way we can directly call SIMD instructions, making sure our program is optimized. It requires learning some new syntax, but in the end it can be a lot less clunky than directly writing asm with an assembler (because gcc can handle things like register assignments for you, allowing you to define variable names for use in asm, etc).

// these variables will be used in our assembler code, so we're going
// to hand-allocate which register they are placed in
// Q: what is an alternate approach?
register int16_t*	cursor 		asm("r20");	// input cursor
register int16_t	vol_int		asm("r22");	// volume as int16_t

The alternate approach would be to just pass them as input/output variables and leave the register allocation at the time up to gcc.

// set vol_int to fixed-point representation of 0.75
// Q: should we use 32767 or 32768 in next line? why?
vol_int = (int16_t) (0.75 * 32768);

32768 is 1000 0000 0000 0000 (or 1 << 15)
32767 is ‭0111 1111 1111 1111 – not a meaningful/useful number for fixed point math.

// Q: what does it mean to "duplicate" values in the next line?
__asm__ ("dup v1.8h,%w0"::"r"(vol_int)); // duplicate vol_int into v1.8h

In this case, it means to store the volume factor into the SIMD register eight times, filling it. It basically ‘duplicates’ the value across the entire SIMD register.

// Q: Why is #16 included in the str line
// but not in the ldr line?	
"str q0, [%[cursor]],#16		\n\t"

Because you want to do this

  1. load values from data array into SIMD register
  2. multiply values in SIMD register by volume factor
  3. store values back into data array
  4. repeat 1-3 with the next set of values

If you incremented after the load, you would load data[0-7], then multiply and store them into data[8-15], which would screw everything up. You want to increment only after you’re done processing the data – after it’s stored back into the array.

// Q: What do these next three lines do?
: [cursor]"+r"(cursor) 
: "r"(cursor)
: "memory"

: [cursor]”+r”(cursor)
This declares an output operand – or in other words, it declares that ‘the asm will modify the cursor variable’. [cursor] allows us to refer to it as [cursor] from within asm. “+r” means ‘we want this stored in a register’ (the “r”), and ‘+’ means we will both read from and write to this register within the asm code.

: “r”(cursor)
This declares an input operand. It declares that we want the value in ‘cursor’ to be avaliable to the asm, and that we will store it in a register (“r”).

: “memory”
This declares that the asm clobbers (modifies) memory. Therefore, the compiler needs to know to reread data from memory after this asm executes.

Next up is vol_intrinsics.c. Intrinsics are a different approach to performing SIMD operations – rather than writing asm directly, they are a series of functions that execute SIMD operations. You don’t have to manually set registers, and as you can see, the code is far more compact:

// Q: What do these intrinsic functions do? 
vst1q_s16(cursor, vqdmulhq_s16(vld1q_s16(cursor), vdupq_n_s16(vol_int)));

And to answer the question, let’s go through them in order.

void vst1q_s16 (int16_t * ptr, int16x8_t val)

This intrinsic stores the contents of an SIMD register to memory. One thing to note is the “int16x8_t” type – it’s a new concept to intrinsics. Basically, it means we’re working with eight 16 bit integers simultaneously – just like we were in the inline asm version.

int16x8_t vqdmulhq_s16 (int16x8_t a, int16x8_t b)

This intrinsic multiplies one int16x8_t by a second int16x8_t, and as you might guess it returns the result as an int16x8_t. It uses the ‘SQDMULH’ instruction to perform this multiplication (just like we did in inline asm). A quick explanation of this instruction: it is a ‘Signed Saturating Doubling Multiply returning High Half’ operation. Which sounds fairly impenetrable, but it’s actually relatively easy to understand if we go through it. ‘Signed’ is self explanatory. ‘Saturating’ means ‘if we overflow, set the number to the max value (vice versa for underflow)’. ‘Doubling Multiply returning High Half’ means this: When multiplying two 16bit integers, you’ll get a 32 bit integer. SQDMULH does this, and then returns the top 16 bits (‘high half’). This means we get the significant bits we care about, and the lower bits are dropped. All put together, this instruction is perfect for scaling audio levels (or brightness levels), almost like it was specifically made for this (and it probably was).

int16x8_t vld1q_s16 (int16_t const * ptr)

This intrinsic loads memory into an SIMD register. Give it a pointer to an int16_t array and it will load 8 int16_ts from that array into an SIMD register. Or in other words, it converts them into an int16x8_t.

int16x8_t vdupq_n_s16 (int16_t value)

This intrinsic duplicates a single int16_t across an SIMD register (so the register will contain 8 copies of the int16_t). Or, in other words, it converts a single int16_t to an int16x8_t.

// Q: Why is the increment below 8 instead of 16 or some other value?
// Q: Why is this line not needed in the inline assembler version
// of this program?
cursor += 8;

To answer the first question, ‘because of how pointer math works’. If you have a pointer to an array of int16_t, and you do ‘pointer +1’, you increment the pointer to the next int16_t. We dealt with 8 int16_ts at once, so we do cursor += 8. For the second question, it’s because of the “str q0, [%[cursor]],#16 \n\t” instruction. See the #16? That means to increment by 16 bytes after each int16_t is stored. However, the intrinsics do not post increment, so we must handle this in the C code if we use intrinsics.

// Q: Are the results usable? Are they accurate?

The results are generally off by 1 compared to other methods of volume scaling. I brought this topic up in the first post, but I feel like it’s worth doing so again. In this case, we’re dealing with audio data intended to be listened to by a human. Human ears will not detect a difference this small. A small rounding error like this will have no audible impact on the results, therefore it is perfectly fine.

Stay tuned for the next post, in which I’ll finally get to the benchmark results.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website with WordPress.com
Get started
%d bloggers like this: