4 ms·

Important to note that the datasets used are sparse, and that the key to this algorithm is better exploitation of sparsity. The GPU over CPU advantage is a lot

Important to note that the datasets used are sparse, and that the key to this algorithm is better exploitation of sparsity. The GPU over CPU advantage is a lot lower if you need sparse operations, even with conventional algorithms. "It should be noted that these datasets are very sparse, e.g., Delicious dataset has only 75 non-zeros on an average for input fea- tures, and hence the advantage of GPU over CPU is not always noticeable." In other words, they got a good speedup on their problem, but it might not apply to your problem.

xiphias2 7y ago
I believe that it's so critical here that the dataset is sparse, that it should be in the title of the paper. Like this I view it as clickbait.
- wdobbels 7y ago
  It's not even mentioned in the abstract.
rajesh-s 7y ago
Another thing to note is that sparsity is being leveraged even to build a more efficient version of hardware. A good example of this is the Cerebras Waferscale chip that was announced recently. I'm assuming the author was unaware of developments on the hardware side of things.
thesz 7y ago
WaveNet, if I remember correctly, has 1-from-256 encoding of input features. And 1-from-256 encoding of output features. It is extremely sparse. If you look at language modeling, then things there are even sparsier - typical neural language model has 1-from-several-hundredths-of-thousands for full language (for Russian, for example, it is in range of 700K..1.2M words and it is much worse for Finnish and German) and 1-from-couple-of-tens-of-thousands for byte pair encoded language (most languages have encoding that reduced token count to about 16K distinct tokens, see [1] for such an example). [1] https://bellard.org/nncp/ https://bellard.org/nncp/ The image classification task also has sparcity at the output and, if you implement it as RNN, a sparsity at input (1-from-256 encoding of intensities). Heck, you can engineer you features to be sparse if you want to. I also think that this paper is an example of "if you do not compute you do not have to pay for it", just like in GNU grep case [2]. [2] https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug... Given all that I think it is a paper about combination of very clever things which give excellent results in a synergy.
- stephenroller 7y ago
  Embeddings tables aren't hard on the GPU (being only a lookup table), and the output softmax still requires you do the full matrix-multiply. The label may be sparse, but the computation is far from sparse.
  - yvdriess 7y ago
    The reverse is true, embeddings are both the performance and memory-footprint bottleneck of modern NN models. Check figure 6. of : https://arxiv.org/pdf/1906.00091.pdf https://arxiv.org/pdf/1906.00091.pdf Embeddings are used to lookup sparse features, so you have those pesky data-dependent lookups.
    - zeroxfe 7y ago
      > The reverse is true, embeddings are both the performance and memory-footprint bottleneck of modern NN models. They may be a bottleneck, but the alternative is worse -- you can't fit complex models with large vocabularies into GPU memory using sparse one-hot encodings.
      - thesz 7y ago
        No, you can successfully fit complex models if you use byte-pair or similar encodings (morphessor [1] comes to mind). [1] https://morfessor.readthedocs.io/en/latest/ https://morfessor.readthedocs.io/en/latest/ You also will get much more meaningful embeddings from summing embeddings of part of the word.
      - yvdriess 7y ago
        Surely you mean dense one-hot? Technically, the sparse one-hot encoding is the most efficient in terms of memory footprint. You simply store the non-zero coordinates. The problem in practice for GPUs is that sparse vector/matrix operations are too inefficient. The whole point of something like this paper is to skip the entire 'densification' step and to directly deal with the sparse matrix input as a sparse matrix. The LSH is used in this paper improves on directly using SpMSpV, as that is also inefficient on CPUs, although to a lesser extent than GPUs.
spott 7y ago
Why aren't GPUs better at sparse matrix math? Generally, sparse operations are memory bandwidth limited, but GPUs/TPUs still have much faster memory than CPUs and more memory bandwidth in general (roughly a factor of 4 or so between the latest cpus and gpus).
- wbl 7y ago
  Sparsity breaks the spatial coherence GPUs like. Scatter gather pays a penalty vs direct.
- jcranmer 7y ago
  Sparse matrix math basically boils down to indirect array references: A[B[i]]. GPUs generally trade off memory bandwidth for latency, relying on being able to do a lot of work to hide that memory latency. But because there's no work between the first and second load, you are no longer able to hide the memory latency of the second load with extra work. CPUs, by contrast, have a thorough caching hierarchy that tends to focus on minimizing memory latency, so it doesn't take as long to do the second load compared to a GPU.
  - l33tman 7y ago
    Yeah on the GPU you need to get your threads to ideally load consecutive memory locations for each thread to utilize the memory bandwidth properly. Random-indexing blows this out of the water. I guess that you could pre-process on the CPU though to pack the sparse stuff for better GPU efficiency..
  - vchak1 7y ago
    You can solve around this by using cuckoo or robin hood hashing. See for example: https://www.researchgate.net/scientific-contributions/14806416_Dan_A_Alcantara https://www.researchgate.net/scientific-contributions/148064...

xiphias2 7y ago

I believe that it's so critical here that the dataset is sparse, that it should be in the title of the paper. Like this I view it as clickbait.

wdobbels 7y ago
It's not even mentioned in the abstract.

rajesh-s 7y ago

Another thing to note is that sparsity is being leveraged even to build a more efficient version of hardware. A good example of this is the Cerebras Waferscale chip that was announced recently. I'm assuming the author was unaware of developments on the hardware side of things.

thesz 7y ago

WaveNet, if I remember correctly, has 1-from-256 encoding of input features. And 1-from-256 encoding of output features. It is extremely sparse. If you look at language modeling, then things there are even sparsier - typical neural language model has 1-from-several-hundredths-of-thousands for full language (for Russian, for example, it is in range of 700K..1.2M words and it is much worse for Finnish and German) and 1-from-couple-of-tens-of-thousands for byte pair encoded language (most languages have encoding that reduced token count to about 16K distinct tokens, see [1] for such an example). [1] https://bellard.org/nncp/ https://bellard.org/nncp/ The image classification task also has sparcity at the output and, if you implement it as RNN, a sparsity at input (1-from-256 encoding of intensities). Heck, you can engineer you features to be sparse if you want to. I also think that this paper is an example of "if you do not compute you do not have to pay for it", just like in GNU grep case [2]. [2] https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug... Given all that I think it is a paper about combination of very clever things which give excellent results in a synergy.

stephenroller 7y ago
Embeddings tables aren't hard on the GPU (being only a lookup table), and the output softmax still requires you do the full matrix-multiply. The label may be sparse, but the computation is far from sparse.
- yvdriess 7y ago
  The reverse is true, embeddings are both the performance and memory-footprint bottleneck of modern NN models. Check figure 6. of : https://arxiv.org/pdf/1906.00091.pdf https://arxiv.org/pdf/1906.00091.pdf Embeddings are used to lookup sparse features, so you have those pesky data-dependent lookups.
  - zeroxfe 7y ago
    > The reverse is true, embeddings are both the performance and memory-footprint bottleneck of modern NN models. They may be a bottleneck, but the alternative is worse -- you can't fit complex models with large vocabularies into GPU memory using sparse one-hot encodings.
    - thesz 7y ago
      No, you can successfully fit complex models if you use byte-pair or similar encodings (morphessor [1] comes to mind). [1] https://morfessor.readthedocs.io/en/latest/ https://morfessor.readthedocs.io/en/latest/ You also will get much more meaningful embeddings from summing embeddings of part of the word.
    - yvdriess 7y ago
      Surely you mean dense one-hot? Technically, the sparse one-hot encoding is the most efficient in terms of memory footprint. You simply store the non-zero coordinates. The problem in practice for GPUs is that sparse vector/matrix operations are too inefficient. The whole point of something like this paper is to skip the entire 'densification' step and to directly deal with the sparse matrix input as a sparse matrix. The LSH is used in this paper improves on directly using SpMSpV, as that is also inefficient on CPUs, although to a lesser extent than GPUs.

spott 7y ago

Why aren't GPUs better at sparse matrix math? Generally, sparse operations are memory bandwidth limited, but GPUs/TPUs still have much faster memory than CPUs and more memory bandwidth in general (roughly a factor of 4 or so between the latest cpus and gpus).

wbl 7y ago
Sparsity breaks the spatial coherence GPUs like. Scatter gather pays a penalty vs direct.
jcranmer 7y ago
Sparse matrix math basically boils down to indirect array references: A[B[i]]. GPUs generally trade off memory bandwidth for latency, relying on being able to do a lot of work to hide that memory latency. But because there's no work between the first and second load, you are no longer able to hide the memory latency of the second load with extra work. CPUs, by contrast, have a thorough caching hierarchy that tends to focus on minimizing memory latency, so it doesn't take as long to do the second load compared to a GPU.
- l33tman 7y ago
  Yeah on the GPU you need to get your threads to ideally load consecutive memory locations for each thread to utilize the memory bandwidth properly. Random-indexing blows this out of the water. I guess that you could pre-process on the CPU though to pack the sparse stuff for better GPU efficiency..
- vchak1 7y ago
  You can solve around this by using cuckoo or robin hood hashing. See for example: https://www.researchgate.net/scientific-contributions/14806416_Dan_A_Alcantara https://www.researchgate.net/scientific-contributions/148064...