4 ms·

The observed throughput for the scalar code is a lot less than memory speed. A Zen 2/3 has a theoretical memory bandwidth of 51.2 GB/s, so should still be fast

The observed throughput for the scalar code is a lot less than memory speed. A Zen 2/3 has a theoretical memory bandwidth of 51.2 GB/s, so should still be fast enough for the theoretical case I make. The observed memory slowdown is for the vector code, it does multiple iterations, that is why. The switching between read and write part doesn't make much sense, there is no such switch in cache, and the memory controller takes care of chunking memory access reasonably. Reading and writing is double the operations of just reading of course, but we have covered that already. What I'm suggesting that the code might do is: At every cycle, read data on location i and location i-1, add them together, store the result on location i. This is problematic because not only do we get an extra read, it also happens on a cache location that was just written to. There is a guard for preventing this unnecessary read, but it might have failed due to not being accessed as the same pointer with the same offset. We still keep it in cache, so a cost of 2 extra cycles per iteration seems reasonable.

dahart 5y ago
> This is problematic because not only do we get an extra read I don't understand why you're speculating on this. The author provided the assembly that only has 1 read. FWIW, I just tested this on my machine. I get the following results: Intel Core i7-7800 3.5Ghz / Ubuntu 20 / g++ 9.3.0 Rolled loop : 2.08 Gflops | 16.7 GB/s bandwidth 8-unrolled loop : 2.48 Gflops | 19.8 GB/s bandwidth Here's the unrolled assembly (8 iters), with -O3: .L3: addl (%rdi), %eax addq $32, %rdi movl %eax, -32(%rdi) addl -28(%rdi), %eax movl %eax, -28(%rdi) addl -24(%rdi), %eax movl %eax, -24(%rdi) addl -20(%rdi), %eax movl %eax, -20(%rdi) addl -16(%rdi), %eax movl %eax, -16(%rdi) addl -12(%rdi), %eax movl %eax, -12(%rdi) addl -8(%rdi), %eax movl %eax, -8(%rdi) addl -4(%rdi), %eax movl %eax, -4(%rdi) cmpq %rdi, %rdx jne .L3
- NohatCoder 5y ago
  Okay that was a bad guess. I see in the previous chapter that the processor is only clocked at 2 GHz, the results still feel a bit low, but certainly way more reasonable in that light. I still wonder exactly where the extra clock cycles go.
  - dahart 5y ago
    If the article was based on a 2GHz processor, then I think I might have been making some bad guesses too. ;) Doesn’t the prefetch solution providing almost 2x mean that on average cache misses in the baseline naive method are costing almost half the cycles? I forgot to say above, but my data point was using a 1GB array, so well above where the author’s cliff dropping off due to being out of cache. I assume the whole reason he’s getting higher perf with arrays < 16MB is because he initialized the array right before computing the prefix sum.
sereja 5y ago
A single CPU core usually can't saturate the memory bandwidth (because it would require more pending memory operations than the scheduler can handle). If you use all cores, it will approach the theoretical limit. https://en.algorithmica.org/hpc/cpu-cache/sharing/ https://en.algorithmica.org/hpc/cpu-cache/sharing/
- dahart 5y ago
  That doesn’t explain the baseline behavior, since the article’s single-core prefetching is improving perf dramatically.

dahart 5y ago

> This is problematic because not only do we get an extra read I don't understand why you're speculating on this. The author provided the assembly that only has 1 read. FWIW, I just tested this on my machine. I get the following results: Intel Core i7-7800 3.5Ghz / Ubuntu 20 / g++ 9.3.0 Rolled loop : 2.08 Gflops | 16.7 GB/s bandwidth 8-unrolled loop : 2.48 Gflops | 19.8 GB/s bandwidth Here's the unrolled assembly (8 iters), with -O3: .L3: addl (%rdi), %eax addq $32, %rdi movl %eax, -32(%rdi) addl -28(%rdi), %eax movl %eax, -28(%rdi) addl -24(%rdi), %eax movl %eax, -24(%rdi) addl -20(%rdi), %eax movl %eax, -20(%rdi) addl -16(%rdi), %eax movl %eax, -16(%rdi) addl -12(%rdi), %eax movl %eax, -12(%rdi) addl -8(%rdi), %eax movl %eax, -8(%rdi) addl -4(%rdi), %eax movl %eax, -4(%rdi) cmpq %rdi, %rdx jne .L3

NohatCoder 5y ago
Okay that was a bad guess. I see in the previous chapter that the processor is only clocked at 2 GHz, the results still feel a bit low, but certainly way more reasonable in that light. I still wonder exactly where the extra clock cycles go.
- dahart 5y ago
  If the article was based on a 2GHz processor, then I think I might have been making some bad guesses too. ;) Doesn’t the prefetch solution providing almost 2x mean that on average cache misses in the baseline naive method are costing almost half the cycles? I forgot to say above, but my data point was using a 1GB array, so well above where the author’s cliff dropping off due to being out of cache. I assume the whole reason he’s getting higher perf with arrays < 16MB is because he initialized the array right before computing the prefix sum.

sereja 5y ago

A single CPU core usually can't saturate the memory bandwidth (because it would require more pending memory operations than the scheduler can handle). If you use all cores, it will approach the theoretical limit. https://en.algorithmica.org/hpc/cpu-cache/sharing/ https://en.algorithmica.org/hpc/cpu-cache/sharing/

dahart 5y ago
That doesn’t explain the baseline behavior, since the article’s single-core prefetching is improving perf dramatically.