Overview of the fastest CPU RNNs implementation
RNNs and particularly LSTM and GRU made a significant contribution to deep learning applications.

They are the default go-to tool for natural language processing, are heavily explored in reinforcement learning, many visual+text combined tasks and time-series prediction (though in competition with WaveNets)

CuDNN implementation is already heavily optimized however CPU implementation should be the fastest possible as well.

### General overview

- [GRU Paper](https://arxiv.org/pdf/1412.3555.pdf)
- [CS231n 2017 - lecture 10](http://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture10.pdf)
- [Colah tutorial](https://colah.github.io/posts/2015-08-Understanding-LSTMs/)
- [Towards Data Science](https://towardsdatascience.com/understanding-gru-networks-2ef37df6c9be)
- [Tensorflow vs PyTorch/CuDNN](https://discuss.pytorch.org/t/grucell-is-different-in-pytorch-and-tensorflow/6630)
    Tensorflow
    ```
    r = sigmoid(W_{ir} x + b_{ir} + W_{hr} h + b_{hr}) 
    z = sigmoid(W_{iz} x + b_{iz} + W_{hz} h + b_{hz})
    n = tanh(W_{in} x + b_{in} +  W_{hn} (r * h) + b_{hn}))
    h' = (1 - z) * n + z * h
    ```
    PyTorch equations
    ```
    r = sigmoid(W_{ir} x + b_{ir} + W_{hr} h + b_{hr}) 
    z = sigmoid(W_{iz} x + b_{iz} + W_{hz} h + b_{hz})
    n = tanh(W_{in} x + b_{in} + r * (W_{hn} h + b_{hn}))
    h' = (1 - z) * n + z * h
    ```
    Note that in the paper equations are:
    ```
    r = sigmoid(W_{ir} x + b_{ir} + W_{hr} h + b_{hr}) 
    z = sigmoid(W_{iz} x + b_{iz} + W_{hz} h + b_{hz})
    n = tanh(W_{in} x + b_{in} +  W_{hn} (r * h) + b_{hn}))
    h' = (1 - z) * h + z * n
    ```
    And CuDNN
    ```
    it = σ(Wi * xt + Ri * ht-1 + bWi + bRu)
    rt = σ(Wr * xt + Rr * ht-1 + bWr + bRr)
    h't = tanh(Wh * xt + rt ◦ (Rh * ht-1 + bRh) + bWh)
    ht = (1 - it)◦h't + it◦ht-1
    ```

### Readable implementation
- [WildML - GRU](http://www.wildml.com/2015/10/recurrent-neural-network-tutorial-part-4-implementing-a-grulstm-rnn-with-python-and-theano/)
- [Pure Numpy GRU](https://github.com/NervanaSystems/neon/blob/a10f90546d2ddae68c3671f59ba9b513158a91f1/tests/gru_ref.py) implementation used by Intel Nervana Neon for testing
- [Neon GRU test suite](https://github.com/NervanaSystems/neon/blob/a10f90546d2ddae68c3671f59ba9b513158a91f1/tests/test_gru.py)
- [Neon implementation](https://github.com/NervanaSystems/neon/blob/a10f90546d2ddae68c3671f59ba9b513158a91f1/neon/layers/recurrent.py#L541-L791)
- [PyTorch implementation](https://github.com/pytorch/pytorch/blob/1c01eabd3cc8402e6de815245774278af3ad0c7f/torch/nn/_functions/rnn.py)
- [CuTorch fused RNN implementation](https://github.com/pytorch/pytorch/blob/f9fd82d8933639a8cf20a029c7fa47fff8fdb93d/aten/src/THCUNN/generic/FusedRNNKernel.cu)
- [Torch implementation of LSTM by jcjohnson](https://github.com/jcjohnson/torch-rnn/blob/master/LSTM.lua)
- [Official Torch RNN](https://github.com/torch/rnn)
- [Theano RNN](https://github.com/lipiji/rnn-theano)
- [Lasagne/Theano official implementation](https://github.com/Lasagne/Lasagne/blob/master/lasagne/layers/recurrent.py#L1137)
- [Tensorflow tutorial for GRU](https://www.data-blogger.com/2017/08/27/gru-implementation-tensorflow/)
- [MXNet high-level API](https://github.com/apache/incubator-mxnet/blob/251ae71a20d8318ab20f4c19520f74b881fdf3ff/example/speech_recognition/stt_layer_lstm.py)

### "Unreadable" C++ implementations (static graphs)
- [Caffe RNN](https://github.com/BVLC/caffe/blob/master/src/caffe/layers/rnn_layer.cpp)
- PaddlePaddle [LSTM](https://github.com/PaddlePaddle/Paddle/blob/24509f4af942bb250564756ad636691c7921e1df/paddle/gserver/layers/LstmLayer.cpp) and [GRU](https://github.com/PaddlePaddle/Paddle/blob/24509f4af942bb250564756ad636691c7921e1df/paddle/gserver/layers/GatedRecurrentLayer.cpp)
- Tensorflow [LSTM](https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/rnn/kernels/lstm_ops.h) and [GRU](https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/rnn/kernels/gru_ops.h)
- [Mxnet](https://github.com/apache/incubator-mxnet/blob/master/src/operator/rnn-inl.h)

### Benchmarks

Unfortunately only GPU benchs are available:

- https://github.com/glample/rnn-benchmarks
- https://github.com/stefbraun/rnn_benchmarks

### Optimized implementations
- [GRU4Rec in Theano](https://github.com/hidasib/GRU4Rec), apparently [this was 170x faster than Tensorflow code](https://stackoverflow.com/questions/40916777/tensorflow-170-times-slower-than-theano-for-rnn-implementation)
- [Nvidia on how to optimize RNNs](https://devblogs.nvidia.com/optimizing-recurrent-neural-networks-cudnn-5/) and [paper](https://arxiv.org/pdf/1604.01946.pdf).
- Baidu Research:
    - [in-depth part 1](https://svail.github.io/rnn_perf/)
      - Combine across timesteps the multiplications by weights
      - Gemm NN and Gemm TN do not have the same speed (including for CUBLAS)
    - [part 2 on Graph optimization](https://svail.github.io/diff_graphs/)
      - Concatenation across timesteps and gates
      - Moving the Reset Gate
      - Saving activation
    - Persistent RNNs for small batches with weights in GPU registers
      - [Paper](http://proceedings.mlr.press/v48/diamos16.pdf)
      - [blog](https://svail.github.io/persistent_rnns/)
      - [keynote](http://on-demand.gputechconf.com/gtc/2016/presentation/s6673-greg-diamos-persisten-rnns.pdf).
- Yandex (Russian Search Engine) [Faster-RNNLM
](https://github.com/yandex/faster-rnnlm)
    - Focus on the One Billion Word Benchmark and can process about 250k words per second with 8 threads at 3.3 Ghz
- [Paper with 3 variants of GRU with less parameters](https://arxiv.org/pdf/1701.05923.pdf), Rahul Dey and Fathi M. Salem
    - See also [Wikipedia](https://en.wikipedia.org/wiki/Gated_recurrent_unit)

### Note on biases and equations

The various implementations do not agree on biases, and the equations chosen.

  - WildML has 1 bias per equation, Keras and Neon too.
  - Chainer, Torch and CuDNN have 2 biases.

To allow loading weights on both CPU and GPU, it would be best to use the same equations as CuDNN.

List of relevant issues:
  - [PyTorch forum: Redundant biases for LSTM](https://discuss.pytorch.org/t/redundant-biases-in-lstm-definition/5668)
  - [Keras: weights on GPU cannot be reused on CPU](https://github.com/keras-team/keras/issues/8860) and solutions (i.e. redoing a CPU layer):
    - [LSTM](https://github.com/keras-team/keras/pull/8307)
    - [GRU](https://github.com/keras-team/keras/pull/9112)
