3 ms·

I don't get why the baseline is so slow, a read, a write and an add per clock should all be within the capabilities of a modern processor.

dragontamer 5y ago
Because a 64-bit read to L1 or L2 cache takes the same amount of time as a 256-bit (or even 512-bit) SIMD read on a modern Intel or AMD processor. On L3 cache or DDR4, coalesced reads/writes are still more beneficial and 256-bit reads SIMD still has benefits over 64-bit reads, though its less dramatic.
- NohatCoder 5y ago
  It takes 1 read port for 1 clock. Any AVX2-capable processor has at least 1 read and 1 separate write port, therefore we should get 1 processing cycle per clock, the reported number is only around a third of that.
  - deleted 5y ago
    [deleted]
  - dahart 5y ago
    The author assumes an average of (slightly over) 2 instructions per iteration, which means the theoretical limit is a half iteration per clock, assuming no cache misses ever. How can you reduce that to 1 processing cycle per clock in a single thread, is there a load-add-store instruction, or a way to get multiple instructions per clock through a single thread?
    - NohatCoder 5y ago
      All modern high-performance processors do multiple instructions per clock.
      - dahart 5y ago
        There’s a lot of ambiguity behind that statement (fetch, decode, queue, pipeline, etc.) I’m just saying what I read in the article, the peak bandwidth calculation was making the assumption of a peak throughput of one instruction per cycle, according to the author. The best answer might be to profile it yourself and see what happens on your processor, it’s only a few lines of code and looks incredibly easy to do.
        NohatCoder 5y ago
        There is usually a bunch of weird specifics when it comes to calculating performance, but this one happens to be quite simple as we bottleneck on 1 write per clock, and the add instruction latency of 1, so none of the hairy stuff should come into play. Not knowing what cpu compiler and settings are used I can't do much to replicate the test.
        dahart 5y ago
        It would be compelling enough to use the author’s 3-line loop as-is on your processor with your own C or C++ compiler. Or the compiled baseline assembly from the article…
        sereja 5y ago
        It's called superscalar processing. CPUs can execute more than one instruction concurrently on each pipeline stage if there is no dependency between them. In the prefix sum, we can fetch and add the next element simultaneously with the accumulator of the previous iteration is being written back. https://en.algorithmica.org/hpc/pipelining/ https://en.algorithmica.org/hpc/pipelining/
        dahart 5y ago
        That link shows 1 fetch per cycle. “Pipelining does not reduce actual latency”. So your comment fails to explain both multiple fetch per cycle and higher than 1 instruction per cycle throughput on average, which is what we were discussing above.
dahart 5y ago
I think I don’t quite understand why the baseline is so fast. ;) But the article answer this question directly, and has a link to a longer explanation with data… “The reason why unidirectional and bidirectional memory accesses would perform differently is that they share the cache and memory buses and other CPU facilities. In the case of RAM, this causes a twofold difference in performance between the pure read and simultaneous read and write scenarios because the memory controller has to switch between the modes on the one-way memory bus, thus halving the bandwidth. The performance drop is less severe for the L2 cache: the bottleneck here is not the cache bus, so the incrementing loop loses by only ~15%.” https://en.algorithmica.org/hpc/cpu-cache/bandwidth/#directional-access https://en.algorithmica.org/hpc/cpu-cache/bandwidth/#directi...
- NohatCoder 5y ago
  We are not even close to the performance of ram. The cache can do a read and a write per clock, so should be good for 1 iteration per clock. I think what may have happened is that the compiler did exactly what it was instructed to do, read the value that it just wrote to memory. Figuring that it is safe to just keep the intermediate value in a register is one of those simple things that can be surprisingly difficult to a compiler.
  - dahart 5y ago
    > We are not even close to the performance of ram * Late edit up front to add: you are of course absolutely correct that the ram perf has room, this is demonstrated by the article’s speedups. If prefetching works, it means the baseline wasn’t bottlenecked on peak ram bandwidth. The article was assuming that the peak theoretical throughput is instruction limited, not ram limited. Then it demonstrated empirically that ram was somehow slowing it down further from the theoretical peak. Providing a counter example might be better than arguing over various assumptions? We could elaborate with some specifics on the ram speed you’re thinking of? Which kind are we talking about? What is your calculation of the bandwidth of this problem? I assume it’s 8 bytes per iteration (4/read, 4/write), so for a typical processor at, say 3.5Ghz, and one instruction per clock, that would require a ram bandwidth of 28GB/s. That’s higher than most single channel DDR4, right? I think most high end desktops are dual channel and higher ram bandwidth, but I don’t know what the bandwidth is in practice when you plow through memory linearly with minimal compute and no prefetching, the perf in the article doesn’t strike me as being strange. > The cache can do a read and a write per clock, so should be good for 1 iteration per clock. It seems like the data in the article mostly supports that statement, with the caveat that an occasional cache miss will bring the average down a little, and the author claims that switching between read and write every single word is slower than reading large blocks. > I think what may have happened is that the compiler did exactly what it was instructed to do, read the value that it just wrote to memory. I’m not sure I understand what you mean. The code doesn’t read the value after it writes, it writes over the last value read, and then moves to the next address, right? No need to speculate about the compiler, the author included x86 assembly, right? Are you suggesting the hardware might be treating the value as volatile and skipping the cache, and stalling a read? I think that would be a lot slower. Or do you mean something else?

dragontamer 5y ago

Because a 64-bit read to L1 or L2 cache takes the same amount of time as a 256-bit (or even 512-bit) SIMD read on a modern Intel or AMD processor. On L3 cache or DDR4, coalesced reads/writes are still more beneficial and 256-bit reads SIMD still has benefits over 64-bit reads, though its less dramatic.

NohatCoder 5y ago
It takes 1 read port for 1 clock. Any AVX2-capable processor has at least 1 read and 1 separate write port, therefore we should get 1 processing cycle per clock, the reported number is only around a third of that.
- deleted 5y ago
  [deleted]
- dahart 5y ago
  The author assumes an average of (slightly over) 2 instructions per iteration, which means the theoretical limit is a half iteration per clock, assuming no cache misses ever. How can you reduce that to 1 processing cycle per clock in a single thread, is there a load-add-store instruction, or a way to get multiple instructions per clock through a single thread?
  - NohatCoder 5y ago
    All modern high-performance processors do multiple instructions per clock.
    - dahart 5y ago
      There’s a lot of ambiguity behind that statement (fetch, decode, queue, pipeline, etc.) I’m just saying what I read in the article, the peak bandwidth calculation was making the assumption of a peak throughput of one instruction per cycle, according to the author. The best answer might be to profile it yourself and see what happens on your processor, it’s only a few lines of code and looks incredibly easy to do.
      - NohatCoder 5y ago
        There is usually a bunch of weird specifics when it comes to calculating performance, but this one happens to be quite simple as we bottleneck on 1 write per clock, and the add instruction latency of 1, so none of the hairy stuff should come into play. Not knowing what cpu compiler and settings are used I can't do much to replicate the test.
        dahart 5y ago
        It would be compelling enough to use the author’s 3-line loop as-is on your processor with your own C or C++ compiler. Or the compiled baseline assembly from the article…
      - sereja 5y ago
        It's called superscalar processing. CPUs can execute more than one instruction concurrently on each pipeline stage if there is no dependency between them. In the prefix sum, we can fetch and add the next element simultaneously with the accumulator of the previous iteration is being written back. https://en.algorithmica.org/hpc/pipelining/ https://en.algorithmica.org/hpc/pipelining/
        dahart 5y ago
        That link shows 1 fetch per cycle. “Pipelining does not reduce actual latency”. So your comment fails to explain both multiple fetch per cycle and higher than 1 instruction per cycle throughput on average, which is what we were discussing above.

dahart 5y ago

I think I don’t quite understand why the baseline is so fast. ;) But the article answer this question directly, and has a link to a longer explanation with data… “The reason why unidirectional and bidirectional memory accesses would perform differently is that they share the cache and memory buses and other CPU facilities. In the case of RAM, this causes a twofold difference in performance between the pure read and simultaneous read and write scenarios because the memory controller has to switch between the modes on the one-way memory bus, thus halving the bandwidth. The performance drop is less severe for the L2 cache: the bottleneck here is not the cache bus, so the incrementing loop loses by only ~15%.” https://en.algorithmica.org/hpc/cpu-cache/bandwidth/#directional-access https://en.algorithmica.org/hpc/cpu-cache/bandwidth/#directi...

NohatCoder 5y ago
We are not even close to the performance of ram. The cache can do a read and a write per clock, so should be good for 1 iteration per clock. I think what may have happened is that the compiler did exactly what it was instructed to do, read the value that it just wrote to memory. Figuring that it is safe to just keep the intermediate value in a register is one of those simple things that can be surprisingly difficult to a compiler.
- dahart 5y ago
  > We are not even close to the performance of ram * Late edit up front to add: you are of course absolutely correct that the ram perf has room, this is demonstrated by the article’s speedups. If prefetching works, it means the baseline wasn’t bottlenecked on peak ram bandwidth. The article was assuming that the peak theoretical throughput is instruction limited, not ram limited. Then it demonstrated empirically that ram was somehow slowing it down further from the theoretical peak. Providing a counter example might be better than arguing over various assumptions? We could elaborate with some specifics on the ram speed you’re thinking of? Which kind are we talking about? What is your calculation of the bandwidth of this problem? I assume it’s 8 bytes per iteration (4/read, 4/write), so for a typical processor at, say 3.5Ghz, and one instruction per clock, that would require a ram bandwidth of 28GB/s. That’s higher than most single channel DDR4, right? I think most high end desktops are dual channel and higher ram bandwidth, but I don’t know what the bandwidth is in practice when you plow through memory linearly with minimal compute and no prefetching, the perf in the article doesn’t strike me as being strange. > The cache can do a read and a write per clock, so should be good for 1 iteration per clock. It seems like the data in the article mostly supports that statement, with the caveat that an occasional cache miss will bring the average down a little, and the author claims that switching between read and write every single word is slower than reading large blocks. > I think what may have happened is that the compiler did exactly what it was instructed to do, read the value that it just wrote to memory. I’m not sure I understand what you mean. The code doesn’t read the value after it writes, it writes over the last value read, and then moves to the next address, right? No need to speculate about the compiler, the author included x86 assembly, right? Are you suggesting the hardware might be treating the value as volatile and skipping the cache, and stalling a read? I think that would be a lot slower. Or do you mean something else?