5 ms·

That's a good news! About that, two days ago I modified the implementation of neural networks inside Neural Redis in order to use AVX2. It was a pretty interest

by antirez 10y ago

That's a good news! About that, two days ago I modified the implementation of neural networks inside Neural Redis in order to use AVX2. It was a pretty interesting experience and in the end after modifying most of it, the implementation is 2x faster compared to the vanilla C implementation (already optimized to be cache obvious). I never touched AVX or SSE in the past, so this was a great learning experience. In 30 minutes you can get 90% of it, but I think that to really do great stuff you need to also understand the relative cost of every AVX operation. There is an incredible user at Stack Overflow that replies to most AVX / SSE questions, if you check the AVX / SSE tag you'll find it easily. However I noticed that when there were many load/store operations to do, there was no particular gain. See for example this code: #ifdef USE_AVX __m256 es = _mm256_set1_ps(error_signal); int psteps = prevunits/8; for (int x = 0; x < psteps; x++) { __m256 outputs = _mm256_loadu_ps(o); __m256 gradients = _mm256_mul_ps(es,outputs); _mm256_storeu_ps(g,gradients); o += 8; g += 8; } k += 8*psteps; #endif What I do here is to calculate the gradient after I computed the error signal (error * derivative of the activation function). The code is equivalent to: for (; k < prevunits; k++) *g++ = error_signal*(*o++); Any hint about exploiting AVX at its max in this use case? Thanks. Ok probably this was more a thing for Stack Overflow, but too late, hitting enter.

dfbrown 10y ago
I would try unrolling 2-4 iterations of the loop. Multiple sequential loads isn't much slower than a single load, so batching your loads and stores together will let you do more arithmetic operations for each time you hit memory.
YZF 10y ago
It might help to try and squeeze more work between the load and the store. E.g. do two of these in parallel (load/load/mul/mul/store/store). Think about latency vs. throughput, the load and the stores may have high latency but also high throughput so you need to be issuing more of them concurrently (without any dependencies between them). Just off the top of my head.
- nkurz 10y ago
  Actually, in most cases instruction ordering isn't really a factor on modern Intel processors. They operate "out of order" (often abbreviated OoO), which means that they execute instructions (µops really) from a "reorder buffer" as soon as dependencies are satisfied. Since the loads have no dependencies, they will already execute several (possibly many) iterations ahead of the multiplies and stores. The latency of the store doesn't matter to use, since we aren't immediately using the result. This doesn't mean that you won't see a benefit from your suggestion, but if you do it will probably be from the reduced loop overhead rather than the improved concurrency.
  - YZF 10y ago
    I'm aware of out of order execution but my experience is that at least with SSE/AVX instruction ordering does matter... The loads do have a dependency on the address for example. Anyways, some experimentation will help, even loop unrolling doesn't always behave the way you'd think.
    - nkurz 10y ago
      The loads do have a dependency on the address for example. Sort of. They depend on the address, but there is nothing that prevents the address from being calculated ahead of time. So what happens is that both the loads and the addition get executed multiple iterations ahead of the multiplication. While we tend to think of one iteration completing before the next begins, from the processors point of view it's just a continuous stream of instructions.
      - gpderetta 10y ago
        Loops (especially FP loops) are often dependency chains limited wich prevents OoO execution. Unrolling (and using multiple accumulators) help create multiple independent chains that can be executed in parallel. Edit: for this specific loop the only dependency is on the iteration variables whih is not an issue here, as the loop should only be limited by load/store bandwith, assuming proper scheduling and induction variable elimination from the compiler.
makmanalp 10y ago
I'm not the most experienced, so I may be talking out of my ass. I imagine that what you're hitting is IO. Getting stuff from lower levels of the hierarchy is slow. To benefit from vector ops, you want your operators to be already in registers. The question is, I wonder whether you're hitting the bandwidth limit of that operation, basically. If not, I wonder if there is something that helps you help the hardware prefetch. You might also want to try and see if unrolling the loop helps, gets rid of the iteration conditionals, but I guess you're adding more instructions, so perhaps more instruction cache misses. Also, are the pointers to where you're grabbing the block of vectors aligned? Looks like it could be. Try something like _mm256_load_ps perhaps.
- antirez 10y ago
  The problem I've is exactly lack of alignment... unfortunately why the vectors themselves are aligned, the way I need to jump inside the vectors is not... Padding would complicate quite a bit the implementation so I was not sure if implement it or not, also I'm not sure about the effects on the cache... I wonder what's the penalty of loadu vs load, maybe that's the problem indeed. Thanks.
deleted 10y ago
[deleted]
nkurz 10y ago
This should be a very fast loop. If the input and output are larger than cache, you should be limited by RAM bandwidth. And if your outputs and gradients fit in L1 cache, it should be possible to get your loop down to single cycle per iteration: load, multiply, store, increment, and test can all execute in the same cycle. It will probably be difficult to convince a compiler to produce the necessary code, though, and if you do, it will likely be specific to that particular compiler and flags. If you want to make this as fast as it can be, the first step is to measure what you do have, and see how fast it is in terms of cycles per iteration. Then you'll want to look at the generated assembly, and what the compiler has done to your carefully crafted loop. The better you've optimized it to begin with, the more likely that it will have done something to make it worse. If you want guaranteed performance on your target platform, you need to lock down the assembly. The fastest loop structure here will involve using a single negative offset, so that you can increment it by 8 and test if you have reached zero. This allows the addition and loop test to "fuse" into a single µop (ADD-JNZ). The loads will be (end_outputs + neg_offset), and the stores (end_gradients + neg_offset). Unrolling should not be necessary if you can get the right assembly. In the absence of making it "perfect", though, you may benefit by unrolling it a few times, although your compiler is probably already doing this. You might try to encourage the compiler to generate a single instruction "load-multiply" instruction by using a dereferenced pointer in the multiply. The processor is limited to decoding 4 instructions per cycle, and depending on what the compiler produces, saving an instruction per iteration here might avoid this bottleneck. And as someone else mentioned, it will help if your inputs and outputs are 32B aligned. In particular, stores that cross 4KB boundaries can be expensive enough to slow down the whole algorithm (although I think this has gotten better on Skylake). It shouldn't be a big difference, though, unless everything else is extremely optimized. I explore it here: http://www.agner.org/optimize/blog/read.php?i=415#419 http://www.agner.org/optimize/blog/read.php?i=415#419
- antirez 10y ago
  Thanks you for the interesting advices. Unfortunately no 32B alignment. The start address of the weights vectors is aligned, but the problem is that as I jump from here to there to get the weights, the alignment is broken. I bet that if I analyze the way I loop trough the weights, I can figure out a way to make this whole thing a linear aligned access. Probably that's my starting point! Thank you. I'll make sure to try different cycles numbers and unrolling, I don't want to reach the level of writing the assembler, but to have at least a good speedup for what's possible. About RAM bandwidth, basically it depends a lot on the neural network size, for small/medium networks it's all inside L1, for very large not, and of course the bigger they are, the slower to train, the more interesting to get the speedup. Thanks.
qb45 10y ago
> However I noticed that when there were many load/store operations to do, there was no particular gain. See for example this code: You may be running out of cache/memory bandwidth, compare your throughput with numbers from benchmarks or "Software Optimization Manual" of your CPU. If you are on Linux, try perf stat -d ./whatever which reports, among other things, the rate of cache and memory hits, obtained from hardware "performance counters". > _mm256_loadu_ps Some years ago and with SSE, unaligned was slower than aligned. On some chips only if the address happened to really be unaligned, on others in every case. Not sure how it is with AVX.
- zbjornson 10y ago
  On recent processors (last few years), as long as you're not crossing a cache line, unaligned is essentially the same as aligned in terms of performance.
  - 737774 10y ago
    Oh wow - how is that achieved? I've spent my career in mobile and didn't know this was true on desktop
    - stephencanon 10y ago
      This is true on modern mobile CPUs, too. ARMv8 doesn't even have explicit aligned vector loads.
  - antirez 10y ago
    Oh! That's super interesting, so I know there is no point in trying to improve the alignment too much. I'll try anyway if I can make the whole operation a linear scan but if there is no big penalty, to add padding among weights looks like a bad idea.
    - qb45 10y ago
      > That's super interesting, so I know there is no point in trying to improve the alignment too much. Typical x86 cache line size is 64B, AVX registers are 32B. When your o pointer isn't 32B-aligned, you are loading across cache line boundary every second time. If nkurz is right and this loop can run 1 iteration per cycle, misalignemnt probably slows it down to 2i/3c. Benchmark this loop if you want to know. Of course it only matters if the array is still in L1, maybe L2 (?). edit: Not exactly 2i/3c, see http://www.agner.org/optimize/blog/read.php?i=415#423 http://www.agner.org/optimize/blog/read.php?i=415#423
gok 10y ago
Assuming this is your code: https://github.com/antirez/neural-redis/blob/master/nn.c https://github.com/antirez/neural-redis/blob/master/nn.c You're really just implementing a vector*matrix multiply. You probably want to just use BLAS's sgemv routine. On macOS, link Accelerate and use cblas_sgemv(); on Linux consider installing Intel MKL or OpenBLAS. If you're just looking to learn what a reasonably state-of-the-art SGEMV kernel looks like for a modern chip like Haswell, check out OpenBLAS's code: https://github.com/xianyi/OpenBLAS/blob/develop/kernel/x86_64/sgemv_n_microk_haswell-4.c https://github.com/xianyi/OpenBLAS/blob/develop/kernel/x86_6...
- deleted 10y ago
  [deleted]
- ajtulloch 10y ago
  https://github.com/Maratyszcza/NNPACK/blob/master/src/x86_64-fma/blas/sgemm.py https://github.com/Maratyszcza/NNPACK/blob/master/src/x86_64... (from https://github.com/Maratyszcza/NNPACK https://github.com/Maratyszcza/NNPACK) is also a pretty reasonable AVX2 GEMM implementation written in a Python assembler, it's a bit easier to follow than the OpenBLAS kernels and has very reasonable performance vs OpenBLAS/MKL. I second the guidance to just use a BLAS library. I'd guess you'd see a 2-10x speedup at least. It looks like you're only implementing a classical MLP library (which is fine for learning, but not the best choice for something like this, integrating VW into Redis would be a much better choice IMO).
  - genericpseudo 10y ago
    VW is the business. Strongly recommended.
- antirez 10y ago
  That sounds a great advice, I'll check this library. I've the feeling that the fact I've non aligned addresses in the current weights scheme will be a problem and padding will be required. That's why I used AVX "loadu" that deals with non aligned addresses, but perhaps I'm paying a lot of performances because of this. Thanks. EDIT: apparently on modern CPUs that's not the case and magically LOADU can be as fast as LOAD.
deleted 10y ago
[deleted]

by antirez 10y ago

dfbrown 10y ago

I would try unrolling 2-4 iterations of the loop. Multiple sequential loads isn't much slower than a single load, so batching your loads and stores together will let you do more arithmetic operations for each time you hit memory.

YZF 10y ago

It might help to try and squeeze more work between the load and the store. E.g. do two of these in parallel (load/load/mul/mul/store/store). Think about latency vs. throughput, the load and the stores may have high latency but also high throughput so you need to be issuing more of them concurrently (without any dependencies between them). Just off the top of my head.

nkurz 10y ago
Actually, in most cases instruction ordering isn't really a factor on modern Intel processors. They operate "out of order" (often abbreviated OoO), which means that they execute instructions (µops really) from a "reorder buffer" as soon as dependencies are satisfied. Since the loads have no dependencies, they will already execute several (possibly many) iterations ahead of the multiplies and stores. The latency of the store doesn't matter to use, since we aren't immediately using the result. This doesn't mean that you won't see a benefit from your suggestion, but if you do it will probably be from the reduced loop overhead rather than the improved concurrency.
- YZF 10y ago
  I'm aware of out of order execution but my experience is that at least with SSE/AVX instruction ordering does matter... The loads do have a dependency on the address for example. Anyways, some experimentation will help, even loop unrolling doesn't always behave the way you'd think.
  - nkurz 10y ago
    The loads do have a dependency on the address for example. Sort of. They depend on the address, but there is nothing that prevents the address from being calculated ahead of time. So what happens is that both the loads and the addition get executed multiple iterations ahead of the multiplication. While we tend to think of one iteration completing before the next begins, from the processors point of view it's just a continuous stream of instructions.
    - gpderetta 10y ago
      Loops (especially FP loops) are often dependency chains limited wich prevents OoO execution. Unrolling (and using multiple accumulators) help create multiple independent chains that can be executed in parallel. Edit: for this specific loop the only dependency is on the iteration variables whih is not an issue here, as the loop should only be limited by load/store bandwith, assuming proper scheduling and induction variable elimination from the compiler.

makmanalp 10y ago

I'm not the most experienced, so I may be talking out of my ass. I imagine that what you're hitting is IO. Getting stuff from lower levels of the hierarchy is slow. To benefit from vector ops, you want your operators to be already in registers. The question is, I wonder whether you're hitting the bandwidth limit of that operation, basically. If not, I wonder if there is something that helps you help the hardware prefetch. You might also want to try and see if unrolling the loop helps, gets rid of the iteration conditionals, but I guess you're adding more instructions, so perhaps more instruction cache misses. Also, are the pointers to where you're grabbing the block of vectors aligned? Looks like it could be. Try something like _mm256_load_ps perhaps.

antirez 10y ago
The problem I've is exactly lack of alignment... unfortunately why the vectors themselves are aligned, the way I need to jump inside the vectors is not... Padding would complicate quite a bit the implementation so I was not sure if implement it or not, also I'm not sure about the effects on the cache... I wonder what's the penalty of loadu vs load, maybe that's the problem indeed. Thanks.

deleted 10y ago

[deleted]

nkurz 10y ago

This should be a very fast loop. If the input and output are larger than cache, you should be limited by RAM bandwidth. And if your outputs and gradients fit in L1 cache, it should be possible to get your loop down to single cycle per iteration: load, multiply, store, increment, and test can all execute in the same cycle. It will probably be difficult to convince a compiler to produce the necessary code, though, and if you do, it will likely be specific to that particular compiler and flags. If you want to make this as fast as it can be, the first step is to measure what you do have, and see how fast it is in terms of cycles per iteration. Then you'll want to look at the generated assembly, and what the compiler has done to your carefully crafted loop. The better you've optimized it to begin with, the more likely that it will have done something to make it worse. If you want guaranteed performance on your target platform, you need to lock down the assembly. The fastest loop structure here will involve using a single negative offset, so that you can increment it by 8 and test if you have reached zero. This allows the addition and loop test to "fuse" into a single µop (ADD-JNZ). The loads will be (end_outputs + neg_offset), and the stores (end_gradients + neg_offset). Unrolling should not be necessary if you can get the right assembly. In the absence of making it "perfect", though, you may benefit by unrolling it a few times, although your compiler is probably already doing this. You might try to encourage the compiler to generate a single instruction "load-multiply" instruction by using a dereferenced pointer in the multiply. The processor is limited to decoding 4 instructions per cycle, and depending on what the compiler produces, saving an instruction per iteration here might avoid this bottleneck. And as someone else mentioned, it will help if your inputs and outputs are 32B aligned. In particular, stores that cross 4KB boundaries can be expensive enough to slow down the whole algorithm (although I think this has gotten better on Skylake). It shouldn't be a big difference, though, unless everything else is extremely optimized. I explore it here: http://www.agner.org/optimize/blog/read.php?i=415#419 http://www.agner.org/optimize/blog/read.php?i=415#419

antirez 10y ago
Thanks you for the interesting advices. Unfortunately no 32B alignment. The start address of the weights vectors is aligned, but the problem is that as I jump from here to there to get the weights, the alignment is broken. I bet that if I analyze the way I loop trough the weights, I can figure out a way to make this whole thing a linear aligned access. Probably that's my starting point! Thank you. I'll make sure to try different cycles numbers and unrolling, I don't want to reach the level of writing the assembler, but to have at least a good speedup for what's possible. About RAM bandwidth, basically it depends a lot on the neural network size, for small/medium networks it's all inside L1, for very large not, and of course the bigger they are, the slower to train, the more interesting to get the speedup. Thanks.

qb45 10y ago

> However I noticed that when there were many load/store operations to do, there was no particular gain. See for example this code: You may be running out of cache/memory bandwidth, compare your throughput with numbers from benchmarks or "Software Optimization Manual" of your CPU. If you are on Linux, try perf stat -d ./whatever which reports, among other things, the rate of cache and memory hits, obtained from hardware "performance counters". > _mm256_loadu_ps Some years ago and with SSE, unaligned was slower than aligned. On some chips only if the address happened to really be unaligned, on others in every case. Not sure how it is with AVX.

zbjornson 10y ago
On recent processors (last few years), as long as you're not crossing a cache line, unaligned is essentially the same as aligned in terms of performance.
- 737774 10y ago
  Oh wow - how is that achieved? I've spent my career in mobile and didn't know this was true on desktop
  - stephencanon 10y ago
    This is true on modern mobile CPUs, too. ARMv8 doesn't even have explicit aligned vector loads.
- antirez 10y ago
  Oh! That's super interesting, so I know there is no point in trying to improve the alignment too much. I'll try anyway if I can make the whole operation a linear scan but if there is no big penalty, to add padding among weights looks like a bad idea.
  - qb45 10y ago
    > That's super interesting, so I know there is no point in trying to improve the alignment too much. Typical x86 cache line size is 64B, AVX registers are 32B. When your o pointer isn't 32B-aligned, you are loading across cache line boundary every second time. If nkurz is right and this loop can run 1 iteration per cycle, misalignemnt probably slows it down to 2i/3c. Benchmark this loop if you want to know. Of course it only matters if the array is still in L1, maybe L2 (?). edit: Not exactly 2i/3c, see http://www.agner.org/optimize/blog/read.php?i=415#423 http://www.agner.org/optimize/blog/read.php?i=415#423

gok 10y ago

Assuming this is your code: https://github.com/antirez/neural-redis/blob/master/nn.c https://github.com/antirez/neural-redis/blob/master/nn.c You're really just implementing a vector*matrix multiply. You probably want to just use BLAS's sgemv routine. On macOS, link Accelerate and use cblas_sgemv(); on Linux consider installing Intel MKL or OpenBLAS. If you're just looking to learn what a reasonably state-of-the-art SGEMV kernel looks like for a modern chip like Haswell, check out OpenBLAS's code: https://github.com/xianyi/OpenBLAS/blob/develop/kernel/x86_64/sgemv_n_microk_haswell-4.c https://github.com/xianyi/OpenBLAS/blob/develop/kernel/x86_6...

deleted 10y ago
[deleted]
ajtulloch 10y ago
https://github.com/Maratyszcza/NNPACK/blob/master/src/x86_64-fma/blas/sgemm.py https://github.com/Maratyszcza/NNPACK/blob/master/src/x86_64... (from https://github.com/Maratyszcza/NNPACK https://github.com/Maratyszcza/NNPACK) is also a pretty reasonable AVX2 GEMM implementation written in a Python assembler, it's a bit easier to follow than the OpenBLAS kernels and has very reasonable performance vs OpenBLAS/MKL. I second the guidance to just use a BLAS library. I'd guess you'd see a 2-10x speedup at least. It looks like you're only implementing a classical MLP library (which is fine for learning, but not the best choice for something like this, integrating VW into Redis would be a much better choice IMO).
- genericpseudo 10y ago
  VW is the business. Strongly recommended.
antirez 10y ago
That sounds a great advice, I'll check this library. I've the feeling that the fact I've non aligned addresses in the current weights scheme will be a problem and padding will be required. That's why I used AVX "loadu" that deals with non aligned addresses, but perhaps I'm paying a lot of performances because of this. Thanks. EDIT: apparently on modern CPUs that's not the case and magically LOADU can be as fast as LOAD.

deleted 10y ago

[deleted]