5 ms·

The GPU versions are performing surprisingly bad. To even match CPU performance, you need a training set in the tens of millions, and even far beyond that, a do

The GPU versions are performing surprisingly bad. To even match CPU performance, you need a training set in the tens of millions, and even far beyond that, a doubling of speed seems to be the best you can hope for. Compare to, for example, tensorflow, where it isn't uncommon to see a 10x speedup even for moderately-sized training sets. (I say "surprising" in the sense that I'm surprised; I don't know the algorithms used for decision trees, and it may well be that they are less amendable to GPU-parallelization than the NN- and matrix algorithms I've worked with)

alexbeloi 9y ago
In decision trees more than half of the optimization time is spent doing sorting (sorting the set at each node to find the optimal splitting for the key at that node), in neural nets it's almost all matrix multiplies. That's where the speedup difference comes in the CPU v GPU comparison.
- yorwba 9y ago
  There are fast parallel sorting algorithms that should be able to take advantage of GPUs. Maybe they didn't implement them?
  - hoaphumanoid 9y ago
    The LightGBM implementation on GPU is based on this paper: https://arxiv.org/abs/1706.08359 https://arxiv.org/abs/1706.08359 they use several smart techniques to make the computation faster. One is how they create histograms of features that are computed in parallel in the GPU
- insulator 9y ago
  actually, the histogram-based tree learning algorithm doesn't need the sorting. The main cost of it is the memory access. The GPU version is slow (when #data is small) due to the additional memory copy cost between GPU and CPU. I think this issue can be fixed in the future.
- folli 9y ago
  You need to sort it once for each dimension/predictor, after that it's log(n) to find the optimal split.
hoaphumanoid 9y ago
In deep learning, the algorithm that is used, back propagation, is basically a chained matrix multiplication, which is good for the GPU structure. However, for boosted trees the optimization problem is a little bit different, there is a sorting and then a computation of a gradient and hessian. In this case, it is not as efficient for GPU than deep learning.

alexbeloi 9y ago

In decision trees more than half of the optimization time is spent doing sorting (sorting the set at each node to find the optimal splitting for the key at that node), in neural nets it's almost all matrix multiplies. That's where the speedup difference comes in the CPU v GPU comparison.

yorwba 9y ago
There are fast parallel sorting algorithms that should be able to take advantage of GPUs. Maybe they didn't implement them?
- hoaphumanoid 9y ago
  The LightGBM implementation on GPU is based on this paper: https://arxiv.org/abs/1706.08359 https://arxiv.org/abs/1706.08359 they use several smart techniques to make the computation faster. One is how they create histograms of features that are computed in parallel in the GPU
insulator 9y ago
actually, the histogram-based tree learning algorithm doesn't need the sorting. The main cost of it is the memory access. The GPU version is slow (when #data is small) due to the additional memory copy cost between GPU and CPU. I think this issue can be fixed in the future.
folli 9y ago
You need to sort it once for each dimension/predictor, after that it's log(n) to find the optimal split.

hoaphumanoid 9y ago

In deep learning, the algorithm that is used, back propagation, is basically a chained matrix multiplication, which is good for the GPU structure. However, for boosted trees the optimization problem is a little bit different, there is a sorting and then a computation of a gradient and hessian. In this case, it is not as efficient for GPU than deep learning.