Since when is calculating the hash the bottleneck in hash table access?

The bottleneck is the:

  ptr = h(x);    // trivial, ~0.5-2 cycles
  bucket = *ptr; //  --> ~200-300 cycles

edit: reading the paper, it's pointers to the data being stored, so I have to add the following as well:

  el_ptr = bucket[i]
  el = *el_ptr

So that's two dependent random-access loads.

That's a valid point, but it does not solve the question.

Obviously the memory throughput will not be as high as with matrix calculations, but the algorithm could still be optimized for the GPU. GPU's can do random access and have large and fast memories. What is the difference in memory lines? 64-bytes vs 128-bytes?

GPUs have high latency, high throughput memory. Random access is a killer if your calculations are at all serialized

The SLIDE algorithm is not serialized. The only issue is the sparsity.

GPUs would still be faster than CPUs. You describe them as high-latency but their memory latency is comparable to CPUs. That's why ethash mining or equihash mining (workloads bottlenecked by short ≤32-byte random memory reads) is still faster on GPUs than on CPUs. Also see https://news.ycombinator.com/item?id=22505029

32-bytes accesses are not short. 8 bytes (double precision floating point) are shorter and that's makes sparse matrix multiplication hard on GPU.

Also, SHA256(d?) employed by ethash is, actually, quite long - 80 cycles, at the very least (cycle per round). In mining you can interleave mining computation for one header with loading required by computation of mining of another header and, from what I know, this is what CUDA on GPU will do.

The sheer amount of compute power makes ethash mining faster on GPU.

Reads shorter than 64 bytes on a CPU all cost you the same: a packet of 64 bytes on the memory bus, because that's the atom size of modern CPU's DDR4 memory controllers...

On GPUs the atom size is 32/64 bytes. So GPUs are always better than or equal to CPUs when it comes to small reads/writes.

It's true that the compute power of ethash is not negligible, but to give you one more data point: on equihash there is even less compute spent on hashing, and GPUs still dominate CPUs

Forgive me if this should be obvious, but why would a simple read from a pointer take so many cycles?

A slightly more elaborate answer than the sibling post to drive home how much happens on a simple read that is not cached :

- request to L1D cache, misses

- request to L2D cache, misses

- packet is dropped on the mesh network to access L3D, likely misses

- L3D requests load from memory from the memory controller, load is put in queue

- dram access latency ~100-150

- above chain in reverse

This is the best case scenario on miss, because there could be a DTLB miss on the address (which is why huge tables are crucial in the paper) or there could be dirty cache lines somewhere in other cores that trigger the coherency mechanism.

because you have to fetch it from RAM, unless the problem is small enough to fit in cache

Ah, right. I don't know how I forgot about cache and RAM.

> because you have to fetch it from RAM, unless the problem is small enough to fit in cache

... might have to...

Yeah, this is a line of research that's been ongoing for a while and "CPUs not GPUs" seems like of it's rallying cry but this seems involve multiple incomparables - like a combination of apple-to-orange and banana-to-peaches comparisons (different algorithms on different platforms doing different tasks judged according to a different success criteria, jeesh).

The thing is there's no benchmark for just neural-netting. Neural nets do well on a variety of image recognition tasks but the nets that do well as particular trained instances on particular data. And, moreover, it's not just doing well on a benchmark but generalizing well. Essentially, neural nets simply algorithms but paradigms (for good and ill).

Instead of the babble about CPU vs GPU, they should be talking the strengths and weaknesses of their approach to image recognition and related tasks. Their locality sensitive hash approach is certainly interesting and some parts of their approach might hypothetically be useful for dealing with the weaknesses of the neural net approach (fragility, black-box-unexplainability, etc).