4 ms·

There's a lot of information out there, but what's most useful depends on your goals and current level of knowledge. If you haven't read them yet, Agner Fog's

• p1esk 10y ago
  Wow, great resources! Do you have any suggestions about learning parallelization techniques? Like which one is better: MPI, OpenMP, Cilk, pthreads? My field is machine learning, and I've been using high level libraries until now, but I'd like to learn how to write something in C that does not suck in terms of speed.
  • nkurz 10y ago
    I'm less knowledgeable about parallelization, so wouldn't want to make a recommendation. But I've used each of those a little bit, and would gently suggest that OpenMP might be a good starting point for exploration. I was impressed by how easy it was to incorporate, and the performance seemed good to the extent that I used it. My naive first impressions were that MPI was clunky, required expertise to get good results, and should be reserved for when you need to run on multiple machines; Cilk was slick, had a nice syntax, but as of two years ago was still for early adopters; and OpenMP was a happy medium of syntax, support, and performance, making it a good default if you were trying to utilize multiple cores and processors on a single machine. pthreads is the underlying thread implementation used on Linux, and the others are higher level interfaces that run on top of this. You should understand the basics of how pthreads works for intuition on how the others will perform, but unless you need something out-of-the-ordinary you probably shouldn't implement anything with it directly.
    • p1esk 10y ago
      Thanks! I'll try OpenMP then. One more question if you don't mind: I played with AVX a little bit yesterday, and tried to speed up matrix multiplication in my C code for a simple neural network. Specifically, I transposed the second matrix so both matrices have the same second dimension, and therefore I could do row/row dot product instead of row/column dot product. This change in itself gained me about 15% improvement, I'm guessing because it's more cache friendly. But I mainly did this so I can use AVX mul_ps intrinsic for the dot product. Then, to sum up the resulting array, I used horizontal add intrinsic in a recursive manner. I compiled this code with -mavx2 flag for my Broadwell Xeon CPU. The code is here: https://github.com/michaelklachko/NN/blob/master/avx_dot_standalone.c https://github.com/michaelklachko/NN/blob/master/avx_dot_sta... Unfortunately, the code actually got slightly slower! If I take the original code and compile it with clang-3.9 and -Ofast and -march=native (just like you suggested in your earlier comment), it becomes about 10 times faster. So I wonder, when compiling with these flags, does clang actually use those AVX instructions that I tried to do manually? When you say "compiler does vectorization", what do you mean exactly? I'm also not clear what's the difference between aligned and unaligned AVX load/store instructions, in terms of performance.
      • nkurz 10y ago
        I took a quick look at your code on Skylake. Looks reasonable, although your recursive approach to horizontal summation probably isn't what you want. Rather than writing and re-reading you probably want to "accumulate" the sums into two YMM registers, then add these, then horizontal sum once. Not all instructions have the same cost, and horizontal addition is more costly than addition or multiplication. Look at Agner's instruction tables for Broadwell for details: http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf. It's initially hard to figure out what the columns mean, but worth the effort. Going further, you can probably use the "FMA" (Fused Multiply Add) instructions, which are essentially designed for dot products. You can do two of these per cycle, each of which does a multiplication and addition of a YMM vector. I compiled this code with -mavx2 flag for my Broadwell Xeon CPU. I can't remember the details of -march for Clang, but I recall that there is some oddity with older versions that -march=native on Broadwell requires -mavx2 in addition. But to get the correct instruction set, I think it needs both flags. In most cases (always for icc and gcc), -march=native is all you need. when compiling with these flags, does clang actually use those AVX instructions that I tried to do manually Yes, exactly that. Modern optimizing compilers look at the code you've written, and (when asked politely and all the stars aline) rewrite it to do something equivalent using the vector instructions. In many cases, you can get the same performance with simple scalar code as with vector intrinsics if the compiler cooperates, but it can be tricky to write the scalar code in a manner that the compiler is willing to vectorize. It's easy and worthwhile to look at the assembly generated by the compiler. It's difficult to understand at first, but it's a great way to learn, and you should be doing it for any loop where the performance really matters. Figure out "objdump -d" use "perf record / perf report", or compile to assembly with -S. Take a look at the fast compiler generated code to see what it's doing, then figure out if you can make it faster. I'm also not clear what's the difference between aligned and unaligned AVX load/store instructions, in terms of performance. A deep morass, but worth looking into. Agner covers it pretty well. On current x64, there is essentially no difference in speed between the aligned and unaligned instructions when using aligned data. The aligned instructions crash when they encounter unaligned data, and the unaligned instructions continue but might be slowed down. My general rule for modern Intel processors would be to try very hard to align your data if you can, but always use the unaligned instructions if they exist. Unaligned stores are typically much worse than unaligned reads. But apart from unaligned stores that cross 4KB boundaries, vector instructions are usually still a win if your algorithm allows them.