3 ms·
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
by 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 agoThanks 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.