SLIDE : I N D EFENSE OF S MART A LGORITHMS OVER H ARDWARE

ACCELERATION FOR L ARGE -S CALE D EEP L EARNING S YSTEMS

Beidi Chen 1 Tharun Medini 1 James Farwell 2 Sameh Gobriel 2 Charlie Tai 2 Anshumali Shrivastava 1

A BSTRACT
Deep Learning (DL) algorithms are the central focus of modern machine learning systems. As data volumes
arXiv:1903.03129v2 [[Link]] 1 Mar 2020

keep growing, it has become customary to train large neural networks with hundreds of millions of parameters
to maintain enough capacity to memorize these volumes and obtain state-of-the-art accuracy. To get around the
costly computations associated with large models and data, the community is increasingly investing in specialized
hardware for model training. However, specialized hardware is expensive and hard to generalize to a multitude of
tasks. The progress on the algorithmic front has failed to demonstrate a direct advantage over powerful hardware
such as NVIDIA-V100 GPUs. This paper provides an exception. We propose SLIDE (Sub-LInear Deep learning
Engine) that uniquely blends smart randomized algorithms, with multi-core parallelism and workload optimization.
Using just a CPU, SLIDE drastically reduces the computations during both training and inference outperforming
an optimized implementation of Tensorflow (TF) on the best available GPU. Our evaluations on industry-scale
recommendation datasets, with large fully connected architectures, show that training with SLIDE on a 44 core
CPU is more than 3.5 times (1 hour vs. 3.5 hours) faster than the same network trained using TF on Tesla V100 at
any given accuracy level. On the same CPU hardware, SLIDE is over 10x faster than TF. We provide codes and
scripts for reproducibility.

1 I NTRODUCTION risky because they require significant investment and time to

develop. Moreover, dedicated hardware caters to a specific
Deep Learning (DL) has become a topic of significant inter- algorithm for which they are designed. Thus, change in the
est in the research community. The last few years have seen state-of-the-art algorithms can render specialized hardware
a remarkable growth of using DL to significantly improve less effective in the future. However, for the case of DL, this
the state-of-the-art in many applications, particularly image, investment is justified due to the lack of significant progress
text classification, and speech recognition. in the algorithmic alternatives for years.
The Need for Hardware Acceleration: Vast amounts of Unsuccessful Alternatives to Matrix Multiplication: On
data powered by the exponential increase in computing ca- the orthogonal side, there have been several works on replac-
pabilities have been instrumental in the success of DL. More ing the costly matrix multiplication with cheaper algorithmic
notably, with the advent of the powerful Graphic Processing alternatives (Le Gall, 2014). Unfortunately, we have seen
Unit (GPU) (Owens et al., 2008), training processes of the minimal practical benefits from the algorithmic front. So far,
DL models have been drastically accelerated. there has been no demonstration, even remotely, that a smart
Fast Matrix Multiplication has been heavily researched for algorithmic implementation in any form can outperform the
the past several decades. We are now reaching a limit on advantages of hardware acceleration.
speeding up matrix multiplication further. Furthermore, Exploiting Adaptive Sparsity in Neural Networks: In
the need for astronomical size neural networks and un- popular frameworks like Tensorflow (TF), Sampled Soft-
precedented growth in the data volumes have worsened max (Jean et al., 2015) is deployed to approximate the full
this problem. As a result, the community is heavily invest- softmax efficiently. While sampled softmax offers computa-
ing in dedicated hardware to take DL further beyond this tional savings, it has high estimation bias (Blanc & Rendle,
point (Jouppi et al., 2017). Designing dedicated hardware is 2018). This leads to poor convergence behavior which is
1
Rice University 2 Intel Corporation. Correspondence to: Beidi empirically verified in our experiments in section 5. In this
Chen <[Link]@[Link]>. paper, we will exploit the idea of adaptive sparsity (Blanc &
Rendle, 2018) or adaptive dropouts (Ba & Frey, 2013). The
Proceedings of the 3 rd MLSys Conference, Austin, TX, USA, idea stems from several recent observations (Makhzani &
2020. Copyright 2020 by the author(s).
Frey, 2015; 2013) that we can accurately train neural net-
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

works by selectively sparsifying most of the neurons, based sis of SLIDE using Intel VTune Performance Analyzer
on their activation, during every gradient update. (Srivas- and show that memory-bound inefficiencies reduce for
tava et al., 2014) has also shown that selective sparsification SLIDE with an increasing number of cores while it is the
can in-fact be superior in accuracy due to implicit regulariza- opposite for TF-CPU.
tion. However, selective sparsification does not directly lead • Our analysis suggests that SLIDE is a memory-bound
to computational savings. (Spring & Shrivastava, 2017b) application, prone to some bottlenecks described in ap-
shows the first possibility of an algorithmically efficient so- pendix D. With careful workload and cache optimizations
lution by employing Locality Sensitive Hash (LSH) tables (eg. Transparent Hugepages) and a data access pattern
to identify a sparse set of neurons efficiently during each (eg. SIMD instructions), we further speed up SLIDE by
update. The proposed algorithm has an added advantage of roughly 1.3x, making the overall speed up to 3.5x faster
making the gradient update HOGWILD style parallel (Recht than TF-GPU and over 10x faster than TF-CPU.
et al., 2011). Such parallelism does not hurt convergence be-
cause extremely sparse and independent updates are unlikely 2 L OCALITY S ENSITIVE H ASHING
to overlap and cause conflicts of considerable magnitude.
Despite all the niceness presented, current implementation Our paper is based on several recent and classical ideas in
of (Spring & Shrivastava, 2017b) fails to demonstrate that Locality Sensitive Hashing (LSH) and adaptive dropouts
the computational advantage can be translated into a faster in neural networks. LSH is a family of functions with the
implementation when directly compared with hardware ac- property that similar input objects in the domain of these
celeration of matrix multiplication. In particular, it is not functions have a higher probability of colliding in the range
clear if we can design a system that can effectively leverage space than non-similar ones. A popular technique for ap-
the computational advantage and at the same time compen- proximate nearest-neighbor search uses the underlying the-
sate for the hash table overheads using limited (only a few ory of Locality Sensitive Hashing (Indyk & Motwani, 1998).
cores) parallelisms. In this paper, we provide the first such In formal terms, consider H to be a family of hash functions
implementation for large fully connected neural networks. mapping RD to some set S.

1.1 Our Contributions Definition 2.1 (LSH Family) A family H is called

(S0 , cS0 , p1 , p2 )-sensitive if for any two points x, y ∈ RD
Our main contributions are as follows: and h chosen uniformly from H satisfies the following:

• We show the first C++ OpenMP based system SLIDE • if Sim(x, y) ≥ S0 then P r(h(x) = h(y)) ≥ p1
with modest multi-core parallelism on a standard CPU • if Sim(x, y) ≤ cS0 then P r(h(x) = h(y)) ≤ p2
that can outperform the massive parallelism of a powerful
Typically, for approximate nearest-neighbor search, we need
V100 GPU on a head-to-head time-vs-accuracy compari-
p1 > p2 and c < 1 to hold. An LSH allows us to construct
son. This unique possibility is because the parallelism in
data structures that give provably efficient query time algo-
SLIDE is naturally asynchronous by design. We have our
rithms for the approximate nearest-neighbor problem with
code and benchmark scripts for reproducibility1 .
the associated similarity measure.
• We make several novel algorithmic and data-structural
choices in designing the LSH based sparsification to One sufficient condition for a hash family H to be an LSH
minimize the computational overheads to a few memory family is that the collision probability P rH (h(x) = h(y))
lookups only (truly O(1)). At the same time, it does not should be a monotonically increasing with the similarity, i.e.
affect the convergence of the DL algorithm. The imple-
mentation further takes advantage of the sparse gradient P rH (h(x) = h(y)) = f (Sim(x, y)), (1)
updates to achieve negligible update conflicts, which cre-
ates ideal settings for Asynchronous SGD (Stochastic where f is a monotonically increasing function. In fact,
Gradient Descent) (Recht et al., 2011). These contribu- most of the popular known LSH families, such as Simhash
tions could be of independent interest in both the LSH (Gionis et al., 1999) and WTA hash (Yagnik et al., 2011;
and DL literature. Chen & Shrivastava, 2018), satisfy this strong property. It
• We provide a rigorous evaluation of our system on two can be noted that Equation 1 automatically guarantees the
large benchmark datasets involving fully connected net- two required conditions in the Definition 2.1.
works. We show that SLIDE, on a modest CPU can be It was shown in (Indyk & Motwani, 1998) that having an
up to 2.7x faster, in wall clock time, than the best possi- LSH family for a given similarity measure is sufficient for ef-
ble alternative with the best possible choice of hardware, ficiently solving nearest-neighbor search in sub-linear time.
at any accuracy. We perform a CPU-efficiency analy-
The Algorithm: The LSH algorithm uses two parameters,
1
[Link] (K, L). We construct L independent hash tables. Each
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems
LSH as Samplers
This sampling view of LSH was the key for the algorithm
h1 hk Buckets
h1 proposed in paper (Spring & Shrivastava, 2017b) that shows
00 00 …
00 01
… the first possibility of adaptive dropouts in near-constant
RD
h2
00 10 Empty time, leading to efficient backpropagation algorithm.
… … …
…
h1, h2 : R D → {0,1,2,3} 11 11
2.1.1 MIPS Sampling
Figure 1. Schematic diagram of LSH. For an input, we obtain hash Recent advances in maximum inner product search (MIPS)
codes and retrieve candidates from the respective buckets. using asymmetric locality sensitive hashing has made it
possible to sample large inner products. Given a col-
lection C of vectors and query vector Q, using (K, L)-
hash table has a meta-hash function H that is formed by parameterized LSH algorithm with MIPS hashing (Shrivas-
concatenating K random independent hash functions from tava & Li, 2014a), we get a candidate set S. Every element
the collection F. Given a query, we collect one bucket in xi ∈ C gets sampled into S with probability pi , where pi
from each hash table and return the union of L buckets. is a monotonically increasing function of Q · xi . Thus, we
Intuitively, the meta-hash function makes the buckets sparse can pay a one-time linear cost of preprocessing C into hash
and reduces the number of false positives, because only valid tables, and any further adaptive sampling for query Q only
nearest-neighbor items are likely to match all K hash values requires few hash lookups.
for a given query. The union of the L buckets decreases
the number of false negatives by increasing the number Algorithm 1 SLIDE Algorithm
of potential buckets that could hold valid nearest-neighbor 1: Input: data X, iterations n, batch size B
items. The candidate generation algorithm works in two 2: Output: θ
phases [See (Spring & Shrivastava, 2017a) for details]: 3: Initialize weights wl for each layer l
4: Create hash tables HTl , functions hl for each layer l
1. Pre-processing Phase: We construct L hash tables from 5: Compute hl (wla ) for all neurons
the data by storing all elements x. We only store pointers 6: Insert all neuron ids a, into HTl according to hl (wla )
to the vector in the hash tables because storing whole 7: for i = 1 : n do
data vectors is very memory inefficient. 8: Input0 = Batch(X, B)
2. Query Phase: Given a query Q; we search for its 9: for l = 1 : Layers do
nearest-neighbors. We report the union from all of the 10: Sl = Sample(Inputl−1 , HTl , hl ) (Algorithm 2)
buckets collected from the L hash tables. Note that we 11: Activation = Forward Propagation (Inputl−1 , Sl )
do not scan all the elements but only probe L different 12: Inputl = Activation
buckets, one bucket for each hash table. 13: end for
After generating the set of potential candidates, the nearest- 14: for l = 1 : Layers do
neighbor is computed by comparing the distance between 15: Backpropagation (Sl )
each item in the candidate set and the query. 16: end for
17: end for
2.1 LSH for Estimation and Sampling 18: return θ

Although LSH provides provably fast retrieval in sub-linear

time, it is known to be very slow for accurate search because Algorithm 2 Algorithm for LSH Sampling
it requires very large number of tables, i.e. large L. Also, 1: Input: Q, HT , h
reducing the overhead of bucket aggregation and candidate 2: Output: Sl (a set of active neurons on layer l)
filtering is a problem on its own. Consequent research led 3: Compute h(Q).
to the sampling view of LSH (Spring & Shrivastava, 2017b; 4: for t = 1 : L do
Chen et al., 2018; 2019; Luo & Shrivastava, 2018) that 5: S = S∩ Query(hl (Ql ), HTlt )
alleviates costly searching by efficient sampling, as shown 6: end for
in figure 1. It turns out that merely probing a few hash 7: return S
buckets (as low as 1) is sufficient for adaptive sampling.
Observe that an item returned as a candidate from a (K, L)-
parameterized LSH algorithm is sampled with probability 3 P ROPOSED S YSTEM : SLIDE
1 − (1 − pK )L , where p is the collision probability of LSH
3.1 Introduction to the overall system
function (sampling probability is monotonic in p). Thus,
with LSH algorithm, the candidate set is adaptively sampled Before introducing SLIDE in details, we define important
where the sampling probability changes with K and L. notations: 1) B: input batch size 2) Nlj : Neuron j in layer l
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Neuron
Network 1 Layer BatchSize

…
1 1 Hash Table 1 Hash Table L Active Inputs

2 2 2 5 ℎ"" … ℎ"# Buckets ℎ"$ … ℎ#$ Buckets 1 1 0 1 ……

3 3 3 00 … 00 1 9 … 00 … 00 1 … Activation for each Inputs

…
4 4 4 9
00
00
…
…
01
10
2 …

Empty
… 00
00
…
… 01
10
9
Empty
…
2 0.1 0.2

Accumulated Gradients
0.5 ……

5 Hidden 1 Hidden 2 … … … … … … …
5 … Active Inputs
0.3 0.8 0.7 ……

…
…
Input 11 … 11 … 11 … 11 …
Weights
-0.3 0.8 -0.5 …
Output
Previous Layer Size

Figure 2. Architecture: The central module of SLIDE is Network. The network is composed of few-layer modules. Each layer module is
composed of neurons and a few hash tables into which the neuron ids are hashed. Each neuron module has multiple arrays of batch size
length: 1) a binary array suggesting whether this neuron is active for each input in the batch 2) activation for each input in the batch 3)
accumulated gradients for each input in the batch. 4) The connection weights to the previous layer. The last array has a length equal to the
number of neurons in the previous layer.

Forward Pass
3) xl : inputs for layer l in the network 4) wla : weights for
ath neuron in layer l 5) hl : hash functions in layer l 6) Nal : 1 |1 1 |3
H1 2 | 2,4 H2 2 | 1,4
the set of active neurons in layer l for the current input.
3|3 3|2
1
Initialization: Figure 2 shows the modular structure of
1

…
SLIDE and algorithm 1 shows the detailed steps. Every 1 1
2 2 2 5
layer object contains a list of neurons and a set of LSH 3 3 3

…
sampling hash tables. Each hash table contains ids of the 4 4 4 9
5 Hidden 1 Hidden 2
neurons that are hashed into the buckets. During the net-

…
Input
work initialization, the weights of the network are initialized Output
randomly. Afterwards, K × L LSH hash functions are ini-
Figure 3. Forward Pass: Given an input, we first get the hash code
tialized along with L hash tables for each of the layers. For
H1 for the input, query the hash table for the first hidden layer,
instance, the example network in Figure 2 maintains hash and obtain the active neurons. We get the activations for only this
tables in two hidden layers as well as the output layer. The set of active neurons. We do the same for the subsequent layers
details of using various hash functions are discussed in ap- and obtain a final sparse output. In practice, we use multiple hash
pendix A. The LSH hash codes hl (wla ) of the weight vectors tables per layer.
of neurons in the given layer are computed according to the
hash functions. The id a of the neuron is saved into the The above-described operations are performed sequentially
hash buckets mapped by the LSH function hl (wla ). This in every layer, starting from the very first layer where the
construction of LSH hash tables in each layer is a one-time input is the data itself. Even in the output layer, which has
operation which can easily be parallelized with multiple softmax activation, only neurons sampled from hash tables
threads over different neurons in the layer independently. are treated as active neurons. For softmax, for every active
k
exo wo
Sparse Feed-Forward Pass with Hash Table Sampling: neuron, we compute its output as σ(Nok ) = P k
xo wo
.
Na e
In the feed-forward phase, given a single training instance, o
Note that the normalizing constant for softmax is no longer
we compute the network activation until the final layer,
the sum over all neurons but only the active ones.
which gives us the output. In SLIDE, instead of calcu-
lating all the activations in each layer, the input to each layer Sparse Backpropagation or Gradient Update: The back-
xl is fed into hash functions to compute hl (xl ). The hash propagation step follows the feed-forward step. After com-
codes serve as a query to retrieve ids of active (or sampled) puting the output of the network, we compare it with the
neurons from the matching buckets in hash tables. For ex- known label of the input and backpropagate the errors layer-
ample, in the figure 3, h1 (x1 ) is first computed and then by-layer to calculate the gradient and update the weights.
used to retrieve N12 and N14 as the active neurons. Only the Here we use the classical backpropagation message passing
activations of active neurons are calculated and passed on as type implementation rather than vector multiplication based.
the inputs to the next layer. The other activations, like those For every training data instance, after updating the weights
of N11 and N13 , are directly treated as 0 and never computed. of any given neuron, the neuron propagates the partial gra-
We describe our design choices that reduce the sampling dients (using error propagation) back to only active neurons
overheads significantly in section 4.1. in previous layers via the connected weights. As a result,
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

we never access any non-active neuron or any non-active 3.2 Details of Hash Functions and Hash Tables
weight, which is not part of the feed-forward process on a
SLIDE provides a natural trade-off between the efficiency
given input. This process ensures that we take full advan-
of retrieving active neurons and the quality of the retrieved
tage of sparsity. Our computation over each input is only
ones. To facilitate this, we have three tunable parameters
of the order of active neurons and weights rather than the
K, L, B. As mentioned in section 2, L serves as the number
total number of parameters. It should be noted that if we
of hash tables. To determine which bucket to choose, we use
compute activation for s < 1 fraction of neurons in each
K hash codes for each hash table. Hence, SLIDE generates
layer (on an average), the fraction of weights that needs to
K × L randomized hash functions all belonging to one hash
be updated is s2 only, which is a significant reduction when
family for each layer. In every bucket in a hash table, the
s is small (as is the case for our experiments).
number of entries is limited to a fixed bucket size. Such a
Update Hash Tables after Weight Updates: After the limit helps with the memory usage and also balances the
weights are updated, we need to modify the positions of load on threads during parallel aggregation of neurons.
neurons in the hash tables accordingly. Updating neurons
typically involves deletion from the old bucket followed by In our implementation of SLIDE, we support four types of
an addition to the new bucket, which can be expensive. We hash functions from LSH family: 1) Simhash 2) WTA hash
discuss several design tricks that we use to overcome this 3) DWTA hash and 4) Minhash respectively. Each of these
overhead of updating hash tables in section 4.2. hash families preserves different similarities and hence is
useful for various scenarios. We discuss the implementa-
OpenMP Parallelization across a Batch: For any given
tion details of Simhash and DWTA hash below and others
training instance, both the feed-forward and backpropaga-
in appendix A. SLIDE also provides the interface to add
tion operations are sequential as they need to be performed
customized hash functions based on need.
layer by layer. SLIDE uses usual Batch Gradient Descent
with Adam optimizer, where the batch size is generally in Simhash (Gionis et al., 1999): SimHash is a popular LSH
the order of hundreds. Each data instance in the batch runs for the cosine similarity measure. We use K × L number
in a separate thread and its gradients are computed in par- of random pre-generated vectors with components taking
allel. To ensure the independence of computation across only three values {+1, 0, −1}. The reason behind using
different threads, every neuron stores two additional arrays, only +1s and −1s is for fast implementation. It requires
each of whose length is equal to the batch size. These arrays additions rather than multiplications, thereby reducing the
keep track of the input specific neuron activations and error computation and speeding up the hashing process. To fur-
gradients. Every input is assigned an id, which can be used ther optimize the cost of Simhash in practice, we can adopt
as an index to locate its activation (or error gradient) on any the sparse random projection idea (Li et al., 2006). A simple
neuron. Besides, we also have a bit array at each neuron to implementation is to treat the random vectors as sparse vec-
determine whether the particular input activates a neuron or tors and store their nonzero indices in addition to the signs.
not. This small memory overhead is negligible for CPUs For instance, let the input vector for Simhash be in Rd . Sup-
but it ensures that the gradient computation is independent pose we want to maintain 1/3 sparsity, we may uniformly
across different instances in the batch. generate K ∗ L set of d/3 indices from [0, d − 1]. In this
The extreme sparsity and randomness in gradient updates al- way, the number of multiplications for one inner product
low us to asynchronously parallelize the accumulation step operation during the generation of the hash codes would
of the gradient across different training data without leading simply reduce from d to d/3. Since the random indices are
to a considerable amount of overlapping updates. SLIDE produced from one-time generation, the cost can be ignored.
heavily capitalizes on the theory of HOGWILD (Recht et al., DWTA hash (Chen & Shrivastava, 2018): DWTA hash
2011), which shows that a small amount of overlap is tol- transforms the input feature space into binary codes such
erable. It does not hurt the convergence even if we resolve that the Hamming distance in the resulting space closely cor-
the concurrent updates randomly. Thus, after independently relates with rank similarity measure for sparse data. We gen-
computing the gradients, each thread pushes the updates erate KLmd number of permutations and every permutation
directly to the weights asynchronously. This asynchronous is split into md
bins. DWTA loops through all the nonzero
update avoids synchronization during batch accumulation (NNZ) indices of the sparse input. For each of them, we up-
which is otherwise sequential in the batch. date the current maximum index of the corresponding bins
In section 5.3, we observe that due to this asynchronous according to the mapping in each permutation. It should be
choice, we obtain near-perfect scaling of our implemen- noted that the number of comparisons and memory lookups
tation with an increasing number of cores. Such perfect in this step is O(N N Z ∗ KLmd ), which is significantly more
scaling is particularly exciting because even highly opti- efficient than simply applying WTA hash to sparse input.
mized implementation of TF on CPUs shows poor scaling For empty bins, the densification scheme proposed in (Chen
behavior with increasing cores beyond 16 cores. & Shrivastava, 2018) is applied.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems
Table 1. Statistics of the datasets
MIPS Strategies Feature Dim Feature Sparsity Label Dim Training Size Testing Size
Delicious-200K 782,585 0.038 % 205,443 196,606 100,095
Amazon-670K 135,909 0.055 % 670,091 490,449 153,025
10 1

Vanilla Sampling 4.2 Updating Overhead

Time

TopK Sampling
10 2 Hard Thresholding We introduce the following heuristics for addressing the
expensive costs of updating the hash tables:
10 3 1) Recomputing the hash codes after every gradient update is
2000 3000 4000 5000 6000 7000 computationally very expensive. Therefore, we dynamically
# Samples
change the update frequency of hash tables to reduce the
Figure 4. Time consumed (in seconds) for various sampling strate- overhead. Assume that we update the hash tables for the
gies for retrieving active neurons from hash tables. first time after N0 iterations. Let t − 1 be the number of
times the hash tables have already been updated. We apply
exponential decay on the update frequency
Pt−1 such that the tth
4 R EDUCING OVERHEAD hash table update happens on iteration i=0 N0 eλi , where
λ is a tunable decay constant. The intuition behind this
4.1 Sampling Overhead scheme is that the gradient updates in the initial stage of the
The key idea of using LSH for adaptive sampling of neurons training are larger than those in the later stage, especially
is sketched in section 3.1. We have designed three strategies while close to convergence.
to sample neurons with large activation: 1) Vanilla Sampling 2) SLIDE needs a policy for adding a new neuron to a bucket
2) Topk Sampling 3) Hard Thresholding. We introduce them when it is already full. To solve such a problem, we use
here and discuss their utility and efficiency in appendix B. the same solution in (Wang et al., 2018) that makes use
Vanilla Sampling: Denote βl as the number of active of Vitters reservoir sampling algorithm (Vitter, 1985) as
neurons we target to retrieve in layer l. After computing the replacement strategy. It was shown that reservoir sam-
the hash codes of the input, we randomly choose a table pling retains the adaptive sampling property of LSH tables,
and only retrieve the neurons in its corresponding bucket. making the process sound. Additionally, we implement a
We continue retrieving neurons from another random table simpler alternative policy based on FIFO (First In First Out).
until βl neurons are selected or all the tables have been 3) For Simhash, the hash codes are computed by hsign
w (x) =
looked up. Let us assume we retrieve from τ tables in total. sign(wT x). During backpropagation, only the weights con-
Formally, the probability that a neuron Nlj gets chosen is, necting the active neurons across layers get updated. Only
P r(Nlj ) = (pK )τ (1 − pK )L−τ , where p is the collision those weights contribute to the change of wT x. Therefore,
probability of the LSH function that SLIDE uses. The time we can also memorize the result of wT x besides the hash
0
complexity of vanilla sampling is O(βl ). codes. When x ∈ Rd gets updated in only d out of d di-
0 0

TopK Sampling: In this strategy, the basic idea is to ob- mensions, where d  d, we only need O(d ) rather than
tain those neurons that occur more frequently among all O(d) addition operations to compute the new hash codes.
L hash tables. After querying with the input, we first re-
trieve all the neurons from the corresponding bucket in 5 E VALUATIONS
each hash table and aggregate their frequencies across all
hash tables. The frequencies are sorted, and only the neu- In this section, we’re going to empirically investigate
rons with top βl frequencies are selected. This requires SLIDE’s performance on multiple fronts such as: 1) SLIDE
additional O(|Nla |) space for maintaining the hashmap and against TF-GPU with V100s 2) SLIDE against TF-CPU 3)
O(|Nla | + |Nla |log|Nla |) time for both sampling and sorting. SLIDE’s adaptive sampling against sampled softmax (plain
random sampling) 4) Scalability against TF-CPU with CPU
Hard Thresholding: In this strategy, we bypass the sort- core count 5) Effect of batch size 6) Benefits of Design
ing step in TopK sampling by selecting neurons that ap- Choices. While we focus on evaluating the basic aspects
pear at least m times in the retrieved buckets. Here, the of SLIDE, we additionally perform several CPU optimiza-
probability that a neuron Nlj gets chosen is, P r(Nlj ) = tions like support for Kernel Hugepages to reduce cache
PL L

K i K L−i
i=m i (p ) (1 − p ) . misses which improve SLIDE’s performance by ≈ 30%.
The optimization details are given in appendix D and the
Figure 4 is a preview of the empirical efficiency comparison
improvement in performance is shown in section 5.4.
of above three strategies shown in appendix B. We see that
Vanilla sampling is a lot more time efficient than the other Fully-Connected Large Architecture: Fully connected
two strategies at the cost of sample quality. networks are common in most applications. To show
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Delicious-200K Delicious-200K Amazon-670K Amazon-670K

0.45 0.45 SLIDE CPU SLIDE CPU
0.30 TF-GPU 0.30 TF-GPU
TF-CPU
0.40 0.40 0.25 0.25
Accuracy

Accuracy

Accuracy

Accuracy
0.20 0.20
0.35 0.35
0.15 0.15
0.30 0.30 0.10 0.10
SLIDE CPU
TF-GPU SLIDE CPU 0.05 0.05
0.25 TF-CPU 0.25 TF-GPU
102 103 102 103 103 104 105 103 104
Time (s) Iterations Time (s) Iterations

Figure 5. It shows the comparison of SLIDE (in red) against TF-GPU (in blue) and TF-CPU (in black). The x-axis is plotted in log scale
to accommodate the otherwise slow TF-CPU curve. We notice that the time required for convergence is 2.7x lower than that of TF-GPU.
When compared against iterations, the convergence behavior is identical, which confirms that the superiority of SLIDE is due to algorithm
and implementation and not due to any optimization bells and whistles.

SLIDE’s real advantage, we will need large networks where to the full softmax. We use the optimized Sampled Softmax
even a slight decrease in performance is noticeable. Thus, functionality provided in TF-GPU. This comparison sheds
the publicly available extreme classification datasets, requir- light on the necessity of LSH based input dependent adap-
ing more than 100 million parameters to train due to their tive sampling compared to static sampling scheme which is
extremely wide last layer, fit this setting appropriately. For the only other alternative in practice.
these tasks, most of the computations (more than 99%) are
Hyper Parameters: For both the datasets, we adopt the
in the final layer.
same model architecture in (Yen et al., 2018). We choose
Datasets: We employ two large real datasets, Delicious- the standard fully connected neural network with one hid-
200K and Amazon-670K, from the Extreme Classification den layer of size 128. We choose a batch size of 128 for
Repository (Kush Bhatia). Delicious-200K dataset is a sub- Delicious-200K dataset and 256 for Amazon-670K dataset
sampled dataset generated from a vast corpus of almost as the input dimension for the former is very large. We run
150 million bookmarks from Social Bookmarking Systems all algorithms until convergence. To quantify the superiority
([Link]). Amazon-670K dataset is a product to product of SLIDE over other baselines, we also use the same opti-
recommendation dataset with 670K labels. The statistics of mizer, Adam (Kingma & Ba, 2014) by varying the initial
the datasets are included in Table 5. step size from 1e−5 to 1e−3 which leads to better conver-
gence in all experiments. For SLIDE, we maintain the hash
Infrastructure: All the experiments are conducted on a
tables for the last layer, where we have a computational bot-
server equipped with two 22-core/44-thread processors (In-
tleneck of the models. For specific LSH setting, we choose
tel Xeon E5-2699A v4 2.40GHz) and one NVIDIA Tesla
Simhash, K = 9, L = 50 for Delicious dataset and DWTA
V100 Volta 32GB GPU. The server has an Ubuntu 16.04.5
hash, K = 8, L = 50 for Amazon-670k dataset. We update
LTS system with the installation of TF-GPU 1.12. We com-
the hash tables with an initial update period of N0 = 50
piled TF-CPU 1.12 from source with GCC5.4 in order to
iterations and then exponentially decaying (section 4.2).
support FMA, AVX, AVX2, SSE4.1, and SSE4.2 instruc-
tions, which boost the performance of TF-CPU by about Main Results: We show the time and iteration wise com-
35%. SLIDE is written in C++ and compiled under GCC5.4 parisons for SLIDE vs TF GPU/CPU in Figure 5. Note that
with OpenMP flag. The most exciting part is that SLIDE the x-axis is in log-scale, and all the curves have a long flat
only uses vanilla CPU thread parallelism and yet outper- converged portion when plotted on a linear scale indicat-
forms TF-GPU (V100) by a large margin in performance. ing clear convergence behavior. Red, blue and black lines
represent the performance of SLIDE, TF-GPU, TF-CPU,
Baselines: We benchmark the tasks with our system SLIDE,
respectively. We can see from the plots that SLIDE on CPU
and compare against highly optimized TF framework for
achieves any accuracy faster than TF on V100. TF-GPU
both CPU and GPU. Specifically, the comparison is between
is always faster than TF-CPU which is expected. It should
the same tasks, with the exact same architecture, running
be noted that these datasets are very sparse, e.g., Delicious
on TF-CPU and TF-GPU. The optimizer and the learning
dataset has only 75 non-zeros on an average for input fea-
hyperparameters (details later) were also the same to avoid
tures, and hence the advantage of GPU over CPU is not
unfair comparisons. Most of the computations in our archi-
always noticeable.
tecture are in the softmax layer. Hence, to corroborate the
advantage of adaptive sampling (Yen et al., 2018) vs vanilla SLIDE is around 1.8 times faster than TF-GPU on Delicious
sampling, we also compare against the popular sampled 200k. On the larger Amazon 670k dataset, where we need
softmax algorithm (Jean et al., 2015) which is a fast proxy more computations, the gains are substantially more. SLIDE
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

lyzer tool, the Intel VTune Performance Analyzer (Malladi,

Table 2. Core Utilization
8 16 32 2009). Table 2 exhibits the results for core utilization com-
Tensorflow-CPU 45% 35% 32% parison between both frameworks using 8, 16, 32 threads for
SLIDE 82% 81% 85% the above tasks. We can see that for TF-CPU, the utilization
is generally low (< 50%). It further decreases with more
Tensorflow-CPU Inefficiencies Ratio in CPU Usage SLIDE Inefficiencies Ratio in CPU Usage threads. For SLIDE, the core utilization is stable (around
0.6 0.6
0.5 0.5
80%) across all threads presented in the table 2.
0.4 0.4
0.3 0.3
Figure 6 presents the distribution of inefficiencies in CPU
0.2 0.2 usage for TF-CPU and SLIDE. Based on core utilization,
0.1 0.1
0 0
the overall inefficiencies of TF-CPU is much more than
8 Threads 16 Threads 32 Threads 8 Threads 16 Threads 32 Threads those of SLIDE. Figure 6 provides a detailed distribution
Front-End Bound Memory Bound Retiring Bound Core Bound Front-End Bound Memory Bound Retiring Bound Core Bound
of different types of inefficiencies. It is obvious that being
memory-bound is a major issue for any number of threads
Figure 6. Inefficiencies in CPU Usage: Memory-bound inefficien- in the histogram. The biggest bottleneck is that a significant
cies (orange bars) are the most significant ones for either algorithm. fraction of execution pipeline slots are stalled due to demand
For TF-CPU, memory-bound inefficiency rises with an increasing memory load and store. Observe that the higher the number
number of cores. For SLIDE, the memory bottleneck reduces
of cores TF-CPU uses, the more memory-bound it gets.
with an increasing number of cores. Hence, SLIDE takes better
advantage of higher CPU cores, as observed in section 5.3. On the other hand, the higher the number of cores SLIDE
uses, the less memory-bound it becomes. Recall that the
critical advantage of SLIDE is that it has a lot fewer active
is around 2.7 (2 hrs vs. 5.5 hrs) times faster than TF-GPU. neurons and sparse gradient updates. Naturally, memory
Most of the computational benefits of SLIDE come from accesses are a lot fewer than TF-CPU due to very sparse
sampling a small subset of active neurons in the output layer. memory accesses within each thread. Our choice of using
After a few iterations into the training process, the average extra arrays to separate the computations of each thread with
number of neurons sampled in the output layer for Delicious- asynchronous gradient updates (section 3.1) across all the
200K is ≈ 1000. Similarly, for Amazon-670K, we sample threads ensures that simple OpenMP parallelism is sufficient
≈ 3000 neurons. With fewer than 0.5% of active neurons, to get near-peak utilization.
SLIDE outperforms TF-GPU on time by a huge margin
on either dataset. It is interesting to note that even after 5.1 Comparison with other Heuristics
compiling TF-CPU with AVX2 instructions, it is nowhere
close to the performance of SLIDE or TF-GPU (SLIDE is During the full softmax process in training on Tensorflow,
8x faster than TF-CPU). Therefore, it is exciting to note for every training instance, it needs to compute logits (out-
that without any rigorous optimization in our prototype, put of the last layer before applying softmax function) for
SLIDE outperforms both baselines using smart randomized all classes. This step is followed by computing the softmax
algorithms with OpenMP parallelism. (normalized sigmoid) of logits. In extreme classification
tasks (with a large number of classes), computing these
For Iteration vs. Accuracy plots in Figure 5, we can ob- logits gets expensive. Therefore, there has been a line of re-
serve that SLIDE achieves the same accuracy per iteration search working on reducing this cost (Mikolov et al., 2013;
even though it adaptively selects neurons in some layers. Bengio et al.; Gutmann & Hyvärinen, 2010). The most com-
This observation confirms that adaptively selecting neurons mon methods are sampling-based (static sampling weights)
and performing asynchronous SGD does not hurt the con- methods which shortlist a candidate set of classes for ev-
vergence from an optimization perspective. The plot also ery batch of training data. By doing this, the number of
confirms that the advantage of SLIDE is not due to any computed logits gets reduced significantly. Due to its popu-
bells and whistles in the optimization process as the conver- larity, Tensorflow supports an optimized implementation of
gence with iteration has very similar behavior. For this plot, sampled softmax (Jean et al., 2015).
we only show TF-GPU as the curve for TF-CPU would be
identical because the optimization algorithm is the same. We explore how sampled softmax on Tensorflow-GPU per-
forms compared to SLIDE. LSH sampling process in SLIDE
Since SLIDE performs much fewer computations and mem- is principally very similar to the process of sampled softmax
ory accesses on the last layer, each iteration is faster than but with sampling probabilities changing dynamically with
the baselines. This is the critical reason why SLIDE outper- inputs. We adopt the exact same settings in the previous
forms other baselines when compared on wall-clock time. section for the experiments. Recall that the average num-
Inefficiency Diagnosis: We profile and analyze TF-CPU ber of sampled classes for SLIDE for both the datasets is
and SLIDE by a state-of-the-art parallel performance ana- ≈ 0.5%. For sampled softmax, we try a various number of
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Delicious-200K Delicious-200K Amazon-670K Amazon-670K

0.45 0.45 SLIDE CPU SLIDE CPU
0.40 0.40 0.30 TF-GPU SSM 0.30 TF-GPU SSM
0.35 0.35 0.25 0.25
0.30 0.30 0.20 0.20
Accuracy

Accuracy

Accuracy

Accuracy
0.25 0.25
0.15 0.15
0.20 0.20
0.15 0.15 0.10 0.10
0.10 SLIDE CPU 0.10 SLIDE CPU 0.05 0.05
0.05 TF-GPU SSM 0.05 TF-GPU SSM
0.00 0.00
102 103 102 103 104 102 103 104 103 104 105
Time (s) Iterations Time (s) Iterations

Figure 7. It shows the comparison of SLIDE (in red) against the popular Sampled Softmax heuristic (in green). The plots clearly establish
the limitations of Sampled Softmax. On Amazon-670K dataset, we notice that Sampled Softmax starts to grow faster than SLIDE in the
beginning stages of training but saturates quickly to lower accuracy. SLIDE starts to grow slowly but attains much higher accuracy than
Sampled Softmax. SLIDE has the context of choosing the most informative neurons at each layer. Sampled Softmax always chooses a
random subset of neurons in the final layer. This reflects in the superior performance of SLIDE over Sampled Softmax.

samples. However, with a comparable number of samples, In figure 8, we observe that SLIDE outperforms Tensorflow-
sampled softmax leads to poor accuracy. We empirically GPU by a significant margin irrespective of the batch size.
observe that we have to sample 20% of the total number of This observation could be attributed to the fact that SLIDE
classes to obtain any decent accuracy. performs very few computations per instance. Our data
structures allow us to process all samples in a batch in
The results are shown in Figure 7. The red lines represent
parallel, and the gradient updates are made asynchronously
SLIDE, and the green lines represent sampled softmax on
among threads as described in section 3.1, which enables
Tensorflow-GPU. We can see that both time and iteration
effective use of parallel threads and it reflects in superior
wise, the red lines outperform the green lines significantly.
performance over Tensorflow. It is interesting to note that
Sampled softmax uses static sampling strategies which are
the gap between SLIDE and Tensorflow widens as the batch
fast compared to SLIDE which in contrast uses adaptively
size grows from 64 to 256.
changing hash tables for input specific dynamic sampling.
Unfortunately, the uninformative static sampling of softmax
leads to poor accuracy as shown in the plot. Noted that in 5.3 Scalability Tests
these plots, sampled softmax uses significantly more neu- In this section, we try to understand the effect of increasing
rons than SLIDE and still shows poor convergence behavior. CPU cores on the scalability of SLIDE and Tensorflow-CPU.
Figure 7 clearly confirms the need for adaptive sampling Besides, we intend to know the number of cores SLIDE
of neurons (in proportion to input dependent activation) for needs to outperform Tensorflow. As mentioned before, our
sparsifying neural networks in order to retain good conver- machine has 44 cores, and each core can have 2 threads.
gence. This phenomenon supports our choice of LSH based However, we disable multithreading and the effective num-
adaptive sampling. ber of threads and cores is the same. Hence, we interchange-
ably use the words “threads” and “cores” from here on. We
benchmark both frameworks with 2, 4, 8, 16, 32, 44 threads.
5.2 Effect of Batch Size
For the different number of threads, we run the same clas-
Batch size is a crucial parameter that can affect the training
sification experiments on SLIDE and Tensorflow-CPU for
speed and model quality in Machine Learning. In general, a
both datasets and clock the corresponding convergence time.
large batch size may help in reducing the training time per
Figure 9 presents the results. The red, blue, black lines
epoch as we process more gradient updates at a time (Goyal
represent SLIDE, Tensorflow-GPU, and Tensorflow-CPU,
et al., 2017). But large batches are known to be bad from
respectively. It should be noted that the blue line is flat
optimization perspective as they reduce the generalization
because GPU computations were done on V100 with thou-
capability (Keskar et al., 2016). In the case of extreme clas-
sands of cores and are mostly oblivious about the number
sification datasets, the number of computations performed
of CPU cores. When the number of cores increases, the
is huge owing to large input dimension and a large number
convergence time for both SLIDE and Tensorflow-CPU
of classes. Hence, a larger batch size may not necessarily
starts to decrease. This decrease is expected due to the ben-
translate into faster training per epoch. To clarify this, we
efits brought by more parallelism on each training batch.
study the effect of varying batch size on the results. We
For Delicious dataset, the red line and the black line cross
choose the larger Amazon-670k dataset for this task. Please
each other at around 8 cores, which means that with more
note that when the batch size is larger than the number of
than 8 cores, SLIDE can beat Tensorflow-CPU. The red
threads, the default scheduling type of OpenMP is static.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Amazon-670K, Batch_Size=64 Amazon-670K, Batch_Size=128 Amazon-670K, Batch_Size=256

0.35
0.30 SLIDE CPU SLIDE CPU SLIDE CPU
TF-GPU 0.30 TF-GPU 0.30 TF-GPU
0.25 TF-GPU SSM TF-GPU SSM TF-GPU SSM
0.25 0.25
0.20
0.20 0.20
Accuracy

Accuracy

Accuracy
0.15 0.15
0.15
0.10 0.10
0.10
0.05 0.05
0.05
0.00 0.00
0.00
102 103 104 102 103 104 102 103 104
Time (s) Time (s) Time (s)

Figure 8. Performance of SLIDE vs. Tensorflow-GPU vs. Sampled Softmax at different batch sizes. SLIDE outperforms the baselines at
all batch sizes. As the batch size gets larger, the gap between SLIDE and TF-GPU gets wider.

Delicious-200K Amazon-670K Amazon-670K Delicious-200K

SLIDE SLIDE 0.45
TF-CPU 105 TF-CPU 0.30
TF-GPU TF-GPU
0.25 0.40
Convergence Time

Convergence Time

Accuracy

Accuracy
0.20
0.35
0.15

0.10 0.30
103 SLIDE-CPU SLIDE-CPU
SLIDE-CPU Optimized SLIDE-CPU Optimized
104 0.05
TF-GPU 0.25 TF-GPU
21 22 23 24 25 21 22 23 24 25 103 104 102 103
# Cores # Cores Time (s) Time (s)

Figure 9. Scalability Tests: Comparison of performance gains with Figure 10. Impact of Hugepages and SIMD Optimization: The
the number of CPU cores for SLIDE (in red ) vs. Tensorflow- comparison of training time for optimized version of SLIDE
CPU (in black) vs. Tensorflow-GPU (in blue). The blue line against a plain version of SLIDE and TF-GPU. We can see that
is flat because the performance of TF-GPU does not depend on SLIDE-Optimized is roughly 1.3x faster than the un-optimized
CPU cores. We notice that the convergence time drops steeply for one on both datasets (x-axis is log scale).
SLIDE compared to TF-CPU/GPU. On Delicious-200K dataset,
SLIDE beats TF-CPU with just 8 cores and TF-GPU with less
than 32 cores. Similarly, on Amazon-670K dataset, SLIDE beats
TF-CPU with just 2 cores and TF-GPU with just 8 cores. We notice that Cache-Optimized SLIDE (in green) is ≈ 1.3
times faster than basic SLIDE (in red). Since we already
have a 2.7x speed-up over TF-GPU on Amazon-670K, it
and blue lines intersect between 16 and 32 cores. Hence, translates to 3.5x speedup over TF-GPU and a 10x speedup
with fewer than 32 cores, SLIDE outperforms Tensorflow- over TF-CPU.
GPU on Delicious dataset. Similarly, for larger Amazon
dataset, the red and black line never intersect, and the red In appendix D.1, we measure the impact of HugePages
and blue line intersects on 8 cores. This means that SLIDE on various CPU-counter metrics like TLB miss rates and
beats Tensorflow-GPU with as few as 8 CPU cores and PageFaults. Concisely, we notice that HugePages reduces
Tensorflow-CPU with as few as 2 CPU cores. the misses by a large margin.

5.4 Additional Speedup with Threading Model and 6 C ONCLUSION AND F UTURE W ORK
Platform Micro-architecture
We provide the first evidence that a smart algorithm with
In this section, we perform several CPU optimizations out- modest CPU OpenMP parallelism can outperform the best
lined in appendix D to reduce cache misses. We first install available hardware NVIDIA-V100, for training large deep
Hugepages package for Ubuntu, which offers 2MB and learning architectures. Our system SLIDE is a combination
1GB cache pages in addition to default 4KB ones. We of carefully tailored randomized hashing algorithms with
pre-allocate 1000 2MB Hugepages and 10 1GB Hugepages the right data structures that allow asynchronous parallelism.
which are found to be enough for both Delicious-200K and We show up to 3.5x gain against TF-GPU and 10x gain
Amazon-670K datasets. To resolve the issue of the false against TF-CPU in training time with similar precision on
sharing for OpenMP mutli-thread, we give a provision to popular extreme classification datasets. Our next steps are to
our data structures to align on cache line boundaries. Be- extend SLIDE to include convolutional layers. SLIDE has
sides using Hugepages, we also used SIMD instructions unique benefits when it comes to random memory accesses
(specifically, Intel-AVX) to facilitate per thread batching. and parallelism. We anticipate that a distributed imple-
In figure 10, we compare the benefit of aforementioned op- mentation of SLIDE would be very appealing because the
timizations against an un-optimized SLIDE and TF-GPU. communication costs are minimal due to sparse gradients.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

7 ACKNOWLEDGEMENTS Hasabnis, N. Auto-tuning tensorflow threading model for

CPU backend. CoRR, abs/1812.01665, 2018. URL
The work was supported by NSF-1652131, nsf-bigdata [Link]
1838177, AFOSR-YIPFA9550-18-1-0152, Amazon Re-
search Award, and ONR BRC grant for Randomized Nu- Indyk, P. and Motwani, R. Approximate nearest neigh-
merical Linear Algebra. bors: towards removing the curse of dimensionality. In
Proceedings of the thirtieth annual ACM symposium on
R EFERENCES Theory of computing, pp. 604–613. ACM, 1998.

Ba, J. and Frey, B. Adaptive dropout for training deep neural Jean, S., Cho, K., Memisevic, R., and Bengio, Y. On using
networks. In Advances in Neural Information Processing very large target vocabulary for neural machine transla-
Systems, pp. 3084–3092, 2013. tion. In Proceedings of the 53rd Annual Meeting of the
Association for Computational Linguistics and the 7th
Basu, A., Gandhi, J., Chang, J., Hill, M., and Swift, M.
International Joint Conference on Natural Language Pro-
Efficient virtual memory for big memory servers. In
cessing (Volume 1: Long Papers), volume 1, pp. 1–10,
International Symposium on Computer Architecture, pp.
2015.
237–248, 2013.

Bengio, Y. et al. Quick training of probabilistic neural nets Jouppi, N. P., Young, C., Patil, N., Patterson, D., Agrawal,
by importance sampling. G., Bajwa, R., Bates, S., Bhatia, S., Boden, N., Borchers,
A., et al. In-datacenter performance analysis of a tensor
Blanc, G. and Rendle, S. Adaptive sampled softmax with processing unit. In 2017 ACM/IEEE 44th Annual Inter-
kernel based sampling. In International Conference on national Symposium on Computer Architecture (ISCA),
Machine Learning, pp. 589–598, 2018. pp. 1–12. IEEE, 2017.

Chen, B. and Shrivastava, A. Densified winner take all (wta) Karakostas, V., Unsal, O., Nemirovsky, M., Cristal, A.,
hashing for sparse datasets. In Uncertainty in artificial and Swift, M. Performance analysis of the memory
intelligence, 2018. management unit under scale-out workloads. In Inter-
national Symposium on Workload Characterization, pp.
Chen, B., Shrivastava, A., and Steorts, R. C. Unique entity 1–12, 2014.
estimation with application to the syrian conflict. THE
ANNALS, 2018. Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy,
M., and Tang, P. T. P. On large-batch training for deep
Chen, B., Xu, Y., and Shrivastava, A. Fast and accurate
learning: Generalization gap and sharp minima. arXiv
stochastic gradient estimation. In Advances in Neural
preprint arXiv:1609.04836, 2016.
Information Processing Systems, pp. 12339–12349, 2019.

Corbet, J. Transparent huge pages in 2.6.38. Kingma, D. P. and Ba, J. Adam: A method for stochastic
[Link] 2011. optimization. arXiv preprint arXiv:1412.6980, 2014.

Gionis, A., Indyk, P., and Motwani, R. Similarity search Kumar, A., Soltis, D., Esmer, I., Yoaz, I., and Kottapalli, S.
in high dimensions via hashing. In Proceedings of the The new intel xeon scalable processor(formerly skylake-
25th International Conference on Very Large Data Bases, sp). In Hot Chips, 2017.
VLDB ’99, pp. 518–529, San Francisco, CA, USA, 1999.
Morgan Kaufmann Publishers Inc. ISBN 1-55860-615- Kush Bhatia, Kunal Dahiya, H. J. Y. P. M. V. The ex-
7. URL [Link] treme classification repository: Multi-label datasets and
id=645925.671516. code. [Link]
XC/[Link]#Prabhu14.
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P.,
Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and Le Gall, F. Powers of tensors and fast matrix multiplication.
He, K. Accurate, large minibatch sgd: Training imagenet In Proceedings of the 39th international symposium on
in 1 hour. arXiv preprint arXiv:1706.02677, 2017. symbolic and algebraic computation, pp. 296–303. ACM,
2014.
Gutmann, M. and Hyvärinen, A. Noise-contrastive esti-
mation: A new estimation principle for unnormalized Li, P., Hastie, T. J., and Church, K. W. Very sparse random
statistical models. In Proceedings of the Thirteenth Inter- projections. In Proceedings of the 12th ACM SIGKDD
national Conference on Artificial Intelligence and Statis- international conference on Knowledge discovery and
tics, pp. 297–304, 2010. data mining, pp. 287–296. ACM, 2006.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Luo, C. and Shrivastava, A. Scaling-up split-merge mcmc Vitter, J. S. Random sampling with a reservoir. ACM
with locality sensitive sampling (lss). arXiv preprint Transactions on Mathematical Software (TOMS), 11(1):
arXiv:1802.07444, 2018. 37–57, 1985.

Makhzani, A. and Frey, B. K-sparse autoencoders. arXiv Wang, Y., Shrivastava, A., Wang, J., and Ryu, J. Random-
preprint arXiv:1312.5663, 2013. ized algorithms accelerated over cpu-gpu for ultra-high
dimensional similarity search. In ACM SIGMOD Record,
Makhzani, A. and Frey, B. J. Winner-take-all autoencoders. pp. 889–903. ACM, 2018.
In Advances in neural information processing systems,
pp. 2791–2799, 2015. Wicaksono, B., Tolubaeva, M., and Chapman, B. Detecting
false sharing in openmp applications using the darwin
Malladi, R. K. Using intel R vtune performance analyzer
framework. In Lecture Notes in Computer Science, pp.
events/ratios & optimizing applications. http:/software.
282–288, 2011.
intel. com, 2009.
Yagnik, J., Strelow, D., Ross, D. A., and Lin, R.-s. The
Meng, J. and Skadron, K. Avoiding cache thrashing due to
power of comparative reasoning. In 2011 International
private data placement in last-level cache for manycore
Conference on Computer Vision, pp. 2431–2438. IEEE,
scaling. In International Conference on Computer Design,
2011.
pp. 283–297, 2009.
Yen, I. E.-H., Kale, S., Yu, F., Holtmann-Rice, D., Kumar, S.,
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and
and Ravikumar, P. Loss decomposition for fast learning
Dean, J. Distributed representations of words and phrases
in large output spaces. In International Conference on
and their compositionality. In Advances in neural infor-
Machine Learning, pp. 5626–5635, 2018.
mation processing systems, pp. 3111–3119, 2013.

Owens, J. D., Houston, M., Luebke, D., Green, S., Stone,

J. E., and Phillips, J. C. Gpu computing. 2008. A D IFFERENT H ASH F UNCTIONS
Recht, B., Re, C., Wright, S., and Niu, F. Hogwild: A lock- Signed Random Projection (Simhash) : Refer (Gionis
free approach to parallelizing stochastic gradient descent. et al., 1999) for explanation of the theory behind Simhash.
In Advances in neural information processing systems, We use K × L number of random pre-generated vectors
pp. 693–701, 2011. with components taking only three values {+1, 0, −1}. The
reason behind using only +1s and −1s is for fast imple-
Shrivastava, A. and Li, P. Asymmetric lsh (alsh) for sub- mentation. It requires additions rather than multiplications,
linear time maximum inner product search (mips). In thereby reducing the computation and speeding up the hash-
Advances in Neural Information Processing Systems, pp. ing process. To further optimize the cost of Simhash in
2321–2329, 2014a. practice, we can adopt the sparse random projection idea (Li
Shrivastava, A. and Li, P. Densifying one permutation et al., 2006). A simple implementation is to treat the random
hashing via rotation for fast near neighbor search. In vectors as sparse vectors and store their nonzero indices in
International Conference on Machine Learning, pp. 557– addition to the signs. For instance, let the input vector for
565, 2014b. Simhash be in Rd . Suppose we want to maintain 1/3 spar-
sity, we may uniformly generate K ∗ L set of d/3 indices
Spring, R. and Shrivastava, A. A new unbiased and efficient from [0, d − 1]. In this way, the number of multiplications
class of lsh-based samplers and estimators for partition for one inner product operation during the generation of the
function computation in log-linear models. arXiv preprint hash codes would simply reduce from d to d/3. Since the
arXiv:1703.05160, 2017a. random indices are produced from one-time generation, the
cost can be safely ignored.
Spring, R. and Shrivastava, A. Scalable and sustainable
deep learning via randomized hashing. In Proceedings Winner Takes All Hashing (WTA hash) : In SLIDE,
of the 23rd ACM SIGKDD International Conference on we slightly modify the WTA hash algorithm from (Yagnik
Knowledge Discovery and Data Mining, pp. 445–454. et al., 2011) for memory optimization. Originally, WTA
ACM, 2017b. takes O(KLd) space to store the random permutations Θ
given the input vector is in Rd . m << d is a adjustable
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., hyper-parameter. We only generate KLmd rather than K ∗ L
and Salakhutdinov, R. Dropout: a simple way to prevent permutations and thereby reducing the space to O(KLm).
d
neural networks from overfitting. The Journal of Machine Every permutation is split into m parts (bins) evenly and
Learning Research, 15(1):1929–1958, 2014. each of them can be used to generate one WTA hash code.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Computing the WTA hash codes also takes O(KLm) oper- we retrieve from τ tables in total. Formally, the probability
ations. that a neuron Nlj gets chosen is,
Densified Winner Takes All Hashing (DWTA hash) : As P r(Nlj ) = (pK )τ (1 − pK )L−τ , (2)
argued in (Chen & Shrivastava, 2018), when the input vector
is very sparse, WTA hashing no longer produces represen- where p is the collision probability of the LSH function that
tative hash codes. Therefore, we use DWTA hashing, the SLIDE uses. For instance, if Simhash is used,
solution proposed in (Chen & Shrivastava, 2018). Similar
(wj )T x
 
to WTA hash, we generate KLm d number of permutations cos−1 ||wj ||l ·||xl ||
d l 2 l 2
and every permutation is split into m bins. DWTA loops p=1− .
through all the nonzero (NNZ) indices of the sparse input. π
For each of them, we update the current maximum index From the previous process, we can see that the time com-
of the corresponding bins according to the mapping in each plexity of vanilla sampling is O(βl ).
permutation.
TopK Sampling: In this strategy, the basic idea is to obtain
It should be noted that the number of comparisons and those neurons that occur more frequently among all L hash
memory lookups in this step is O(N N Z ∗ KLm d ), which is tables. After querying with the input, we first retrieve all
significantly more efficient than simply applying WTA hash the neurons from the corresponding bucket in each hash
to sparse input. For empty bins, the densification scheme table. While retrieving, we use a hashmap to keep track
proposed in (Chen & Shrivastava, 2018) is applied. of the frequency with which each neuron appears. The
hashmap is sorted based on the frequencies, and only the
Densified One Permutation Minwise Hashing(DOPH):
neurons with top βl frequencies are selected. This requires
The implementation mostly follows the description of
additional O(|Nla |) space for maintaining the hashmap and
DOPH in (Shrivastava & Li, 2014b). DOPH is mainly de-
O(|Nla | + |Nla |log|Nla |) time for both sampling and sorting.
signed for binary inputs. However, the weights of the inputs
for each layer are unlikely to be binary. We use a thresh- Hard Thresholding: The TopK Sampling could be expen-
olding heuristic for transforming the input vector to binary sive due to the sorting step. To overcome this, we propose
representation before applying DOPH. The k highest values a simple variant that collects all neurons that occur more
among all d dimensions of the input vector are converted than a certain frequency. This bypasses the sorting step and
to 1s and the rest of them become 0s. Define idxk as the also provides a guarantee on the quality of sampled neurons.
indices of the top k values for input vector x. Formally, Suppose we only select neurons that appear at least m times
in the retrieved buckets, the probability that a neuron Nlj
(
1, if i ∈ idxk .
Threshold(xi ) = gets chosen is,
0, otherwise.
L
X
P r(Nlj ) L
(pK )i (1 − pK )L−i ,


We could use sorting algorithms to get the top k indices, but = i (3)
it induces at least O(dlogd) overhead. Therefore, we keep i=m
a priority queue with indices as keys and the corresponding Figure 11 shows a sweep of curves that present the relation
data values as values. This requires O(dlogk) operations. between collision probability of hl (wlj ) and hl (xl ) and the
probability that neuron Nlj is selected under various values
B R EDUCING THE S AMPLING OVERHEAD of m when L = 10. We can visualize the trade-off between
collecting more good neurons and omitting bad neurons by
The key idea of using LSH for adaptive sampling of neurons
tweaking m. For a high threshold like m = 9, only the
with large activation is sketched in ‘Introduction to over-
neurons with p > 0.8 have more than P r > 0.5 chance of
all system’ section in the main paper. We have designed
retrieval. This ensures that bad neurons are eliminated but
three strategies to sample large inner products: 1) Vanilla
the retrieved set might be insufficient. However, for a low
Sampling 2) Topk Sampling 3) Hard Thresholding. We first
threshold like m = 1, all good neurons are collected but
introduce them one after the other and then discuss their
bad neurons with p < 0.2 are also collected with P r > 0.8.
utility and efficiency. Further experiments are reported in
Therefore, depending on the tolerance for bad neurons, we
section C.
choose an intermediate m in practice.
Vanilla Sampling: Denote βl as the number of active
neurons we target to retrieve in layer l. After computing the C D ESIGN C HOICE C OMPARISONS
hash codes of the input, we randomly choose a table and only
retrieve the neurons in that table. We continue retrieving In the main paper, we presented several design choices in
neurons from another random table until βl neurons are SLIDE which have different trade-offs and performance
selected or all the tables have been looked up. Let us assume behavior, e.g., executing MIPS efficiently to select active
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

Trade off for Frequency Thresholding Table 3. Time taken by hash table insertion schemes
1.0 Insertion to HT Full Insertion
Reservoir Sampling 0.371 s 18 s
0.8 FIFO 0.762 s 18 s

0.6
Pr

0.4 m=1
m=3 Figure 12 presents the results. The blue, red and green dots
0.2 m=5 represent Vanilla sampling, TopK thresholding, and Hard
m=7
m=9
thresholding respectively. It shows that the TopK thresh-
0.0 olding strategy takes magnitudes more time than Vanilla
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
p
sampling and Hard thresholding across all number of sam-
ples consistently. Also, we can see that the green dots are
Figure 11. Hard Thresholding: Theoretical selection probability just slightly higher than the blue dots meaning that the time
P r vs the collision probabilities p for various values of frequency complexity of Hard Thresholding is slightly higher than
threshold m (eqn. 3). High threshold (m = 9) gets less number Vanilla Sampling. Note that the y-axis is in log scale. There-
of false positive neurons but misses out on many active neurons. fore when the number of samples increases, the rates of
A low threshold (m = 1) would select most of the active neurons change for the red dots are much more than those of the
along with lot of false positives. others. This is not surprising because TopK thresholding
strategy is based on sorting algorithms which has O(nlogn)
MIPS Strategies running time. Therefore, in practice, we suggest choos-
ing either of Vanilla Sampling or Hard Thresholding for
10 1 efficiency. For instance, we use Vanilla Sampling in our
extreme classification experiments because it is the most
efficient one. Furthermore, the difference between iteration
Vanilla Sampling
wise convergence of the tasks with TopK Thresholding and
Time

TopK Sampling
10 2 Hard Thresholding Vanilla Sampling are negligible.

C.2 Addition to Hashtables

10 3 SLIDE supports two implementations of insertion policies

for hash tables described in section 3.1 in main paper. We
2000 3000 4000 5000 6000 7000
# Samples profile the running time of the two strategies, Reservoir
Sampling and FIFO. After the weights and hash tables ini-
Figure 12. Sampling Strategies: Time consumed (in seconds) for tialization, we clock the time of both strategies for insertions
various sampling methods after retrieving active neurons from of all 205,443 neurons in the last layer of the network, where
Hash Tables. 205,443 is the number of classes for Delicious dataset. Then
we also benchmark the time of whole insertion process in-
neurons, adopting the optimal policies for neurons insertion cluding generating the hash codes for each neuron before
in hash tables, etc. In this section, we substantiate those inserting them into hash tables.
design choices with key metrics and insights. In order to
better analyze them in more practical settings, we choose The results are shown in Table C.2. The column “Full Inser-
to benchmark them in real classification tasks on Delicious- tion” represents the overall time for the process of adding all
200K dataset. neurons to hash tables. The column “Insertion to HT” repre-
sents the exact time of adding all the neurons to hash tables
excluding the time for computing the hash codes. Reservoir
C.1 Evaluating Sampling Strategies
Sampling strategy is more efficient than FIFO. From an al-
Sampling is a crucial step in SLIDE. The quality and quan- gorithmic view, Reservoir Sampling inserts based on some
tity of selected neurons and the overhead of the selection probability, but FIFO guarantees successful insertions. We
strategy significantly affect the SLIDE performance. We observe that there are more memory accesses with FIFO.
profile the running time of these strategies, including Vanilla However, compared to the full insertion time, the benefits
sampling, TopK thresholding, and Hard thresholding, for of Reservoir Sampling are still negligible. Therefore we
selecting a different number of neurons from the hash tables can choose either strategy based on practical utility. For
during the first epoch of the classification task. instance, we use FIFO in our experiments.
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

D T HREADING M ODEL AND P LATFORM dation. Much previous work (e.g., (Wicaksono et al., 2011))
M ICRO - ARCHITECTURE have tried to detect and resolve the issue of false sharing for
O PTIMIZATION OpenMP multi-threads mainly using compiler optimizations
and hardware performance counters. However, generally
Our experimental analysis shows that SLIDE is a memory- speaking, carefully allocating data structures and aligning
bound workload. We show that a careful workload optimiza- them on cache line boundaries (e.g., by padding) signifi-
tion to design a threading model and a data access pattern to cantly reduce the false sharing opportunities. We chose to
take into consideration the underlying platform architecture use the later alternative for SLIDE.
leads to a significant performance boost.
Address Translation and Support for Kernel
OpenMP and Cache Optimizations: A key metric for Hugepages: Virtual memory provides applications
the identification of memory and cache performance bottle- with a flat address space and an illusion of sufficiently large
necks in a multi-threaded application, e.g., SLIDE, is the and linear memory. The addressed memory is divided into
number of data misses in the core private caches. This is a fixed-size pages, and a page table is used to map virtual
significant source of coherence traffic, potentially making pages to physical ones. The address lookup is accelerated
the shared bus a bottleneck in a symmetric multiprocessor using Translation Lookaside Buffers (TLBs).
(SMP) architecture, thus increasing memory latency.
Since SLIDE is a workload with a large memory footprint,
OpenMP provides a standard, easy to use model for scaling the performance of virtual memory paging can suffer due
up a workload among all the available platform cores. The to stagnant TLB sizes. TLB address translation is on the
master thread forks a specified number of worker threads processors critical path. It requires low access times which
to run concurrently, and by default, threads are kept un- constrain TLB size (and thus, the number of pages it holds).
bound and are spread across available cores, if any. Gen- On a TLB miss, the system must walk the page table, which
erally speaking, an inclusive last level cache (LLC) can may incur additional cache misses. Recent studies show
improve data sharing, because a new thread created to run that workloads with large memory footprints can experience
on a remote core, can probably find a copy of a shared data a significant performance overhead due to excessive page
structure in the LLC, this is especially true if the accesses table walks (Karakostas et al., 2014; Basu et al., 2013).
are mostly read-only, and ignoring the effect of evictions
We employ Hugepages for SLIDE, which is a technology
overhead from private core caches (Meng & Skadron, 2009).
for x86-64 architectures to map much larger pages than the
With the new trend in CPU architecture of a non-inclusive
default 4KB normal-sized pages on the orders of 2 MB to
LLC (e.g. Intel’s Skylake architecture (Kumar et al., 2017))
1 GB. Use of huge pages (Transparent Hugepages and lib-
multi-threaded workloads can operate on larger data per
hugetlbfs (Corbet, 2011)) increases TLB reach substantially,
thread (due to increased L2 size). However, due to the new
and reduces the overhead associated with excessive TLB
design of a non-inlusive LLC remote thread missing on a
misses and table walks.
shared data structure can cause cache thrashing, invalidation,
and bouncing of shared data among cores. We noticed that Vector Processing, Software Pipelining, and Prefetch-
SLIDE is prone to this bottleneck. ing: We further use software optimization techniques to
improve workload performance in SLIDE. In particular,
Fortunately, OpenMP provides a control for thread affinity
we use Vector processing which is capable of exploiting
where a mask is set by an affinity preference and checked
data-level parallelism through the use of Single-Instruction-
during runtime for possible locations for a thread to run.
Multiple-Data (SIMD) execution, where a function is called
When threads are accessing mostly private independent data
with a batch of inputs instead of an individual input (e.g.,
items, it is best to scatter these among the available possi-
the function to update a large matrix of weights in the back-
ble cores for an almost linear speedup with the available
propagation phase). The implementation uses SIMD instruc-
cores due to no data dependency. On the other hand, if
tions (e.g., Intel AVX (Kumar et al., 2017)) to implement
these threads are accessing items in a shared data struc-
the update to multiple weights simultaneously. Implement-
ture, it is generally better to schedule these threads in a
ing a software pipeline is an excellent way to hide memory
more compact packing (using the OpenMP Affinity=close)
latency for memory-bound workloads. Our implementation
where threads are scheduled closer (same CPU socket) as
divides the processing of data items into stages of a pipeline,
the master thread.
where explicit software prefetch stage (using, for example,
Furthermore, CPU caches are arranged into cache lines. x86 PREFETCHT0 instruction set) is followed by a process-
Multiple threads updating data items that happen to co- ing stage(s). The data items that are accessed in the future
locate into the same cache line (called false sharing) can are prefetched into the core caches in advance to the time
also cause cache thrashing, since these updates need to be se- when they are needed to get processed. In particular, for
rialized to ensure correctness, leading to performance degra- a vector processing of updating of N weights, a software
 SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

implementation can prefetch weight Wi+d (where d is the we observe that the benefits of using more cores are not
depth of the pipeline) while updating weight Wi , as a result, obvious after 16 cores for Tensorflow-CPU. Coincidentally,
when it is time to process weight Wi+d it is already in the a very recent work (Hasabnis, 2018) introduces the hardness
CPU cache. of finding the optimal parameter settings of Tensorflows
threading model for CPU backends. It argues that getting
D.1 Measuring the Impact of Transparent Hugepages the best performance from a CPU needs manual, tedious
and time-consuming tuning and it still may not guarantee
In table 4, we show the results for examining the impact of the best performance. While analyzing the scalability and
Transparent Hugepages on various CPU-counter metrics. core utilization of Tensorflow-CPU can be an independent
A direct benefit of employing Transparent Hugepages is research interest, we explore a small aspect of it in the fol-
the drastic reduction in TLB miss rate. For example, the lowing paragraphs.
first row in table 4 shows that the TLB load miss rate for
data reduces from 5.12% to 0.25%. Similarly, TLB load Delicious-200K Amazon-670K
TF-CPU 6 × 100
TF-CPU
101
miss rate for instruction also decreases from 56.12% to SLIDE SLIDE

20.96%. Consequently, we expect a huge reduction in page 4 × 100

3 × 100
table walks (PTW) incurred due to TLB misses. This is

Ratio

Ratio
2 × 100
corroborated in rows 3 and 4 of table 4. We see that the
ratios of CPU cycles spent by PTWs caused by data and
100 100
instruction TLB misses have reduced from 7.74% to 0.72% 21 22 23 24 25 21 22 23 24 25
# Cores # Cores
and 0.02% to 0.015% respectively. As mentioned in section
D, TLB misses cause expensive main memory reads. Using
Hugepages, we reduce the memory reads caused by data and
Figure 13. Scalability Tests: Comparison of performance gains
instruction TLB misses from 3, 062, 039/s to 749, 485/s with the number of CPU cores for SLIDE (in red ) vs. Tensorflow-
and 12, 060/s and 11, 580/s respectively. Finally, we also CPU (in black) vs. Tensorflow-GPU (in blue). The blue line
report the reduction in page faults (which can possibly occur is flat because the performance of TF-GPU does not depend on
when there is a TLB miss) from 32, 548/s to 26, 527/s. CPU cores. We notice that the convergence time drops steeply for
SLIDE compared to TF-CPU/GPU. On Delicious-200K dataset,
SLIDE beats TF-CPU with just 8 cores and TF-GPU with less
Metric Without With
than 32 cores. Similarly, on Amazon-670K dataset, SLIDE beats
Hugepages Hugepages
TF-CPU with just 2 cores and TF-GPU with just 8 cores. The
dTLB load miss rate 5.12% 0.25% 2nd and 4th plots compare the ratio of the convergence time at a
iTLB load miss rate 56.12% 20.96% various number of CPU cores to the minimum time required (when
PTW dTLB-miss 7.74% 0.72% we use all 44 CPU cores).
PTW iTLB-miss 0.02% 0.015%
RAM read dTLB-miss 3, 062, 039/s 749, 485/s
RAM read iTLB-miss 12, 060/s 11, 580/s
PageFault 32, 548/s 26, 527/s

Table 4. Comparison of various CPU-counter metrics for both

cases; with and without using Transparent Hugepages.

E M ORE DISCUSSION ON SCALABILITY

Moreover, based on the statistics collected through experi-
ments as mentioned above, we show the ratio of convergence
time with the different number of cores to the minimum con-
vergence time (using 44 cores). The results are exhibited in
Figure 13. Again, the red line represents SLIDE, and the
black line represents Tensorflow-CPU. When the number
of cores increases, that ratio decreases for both SLIDE and
Tensorflow-CPU. However, it is explicit that the ratio drops
more drastically for the red line than the black line. This
behavior concludes that the scalability of SLIDE is much
better than that of Tensorflow-CPU. Moreover, in the plot,