PaperlayerView exact revision on arXiv

Source-linked AI summary

SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems

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

arXiv:1903.03129v2cs.DCcs.LG

TL;DR

Large models and growing datasets make training computation costly, while dedicated hardware requires investment and prior algorithmic alternatives had not shown a practical advantage over it. SLIDE combines randomized hashing, sparse computation, and multicore CPU parallelism; the authors report up to 3.5x faster training than TF-GPU and over 10x faster than TF-CPU with similar precision.

  • Problem

    Large models and growing datasets increase training computation, while specialized hardware is costly and algorithmic alternatives had not demonstrated a practical advantage over hardware acceleration.

    Source: §1 · pp. 1–2

  • Method

    SLIDE combines LSH-based adaptive neuron sampling with sparse gradient updates and asynchronous multicore parallelism on CPUs.

    Source: §1 · p. 2, §1.1 · p. 2, §3.1 · p. 5

  • Results

    SLIDE achieves up to 3.5x faster training than TF-GPU and over 10x faster than TF-CPU with similar precision on popular extreme-classification datasets.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The authors demonstrate that a smart algorithm with modest CPU parallelism can outperform a V100 GPU for training large fully connected networks in their evaluated setting.

    Source: §1.1 · p. 2, §6 · p. 10

Abstract

from arXiv · show

Deep Learning (DL) algorithms are the central focus of modern machine learning systems. As data volumes 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 INTRODUCTION

The introduction argues that growing models and datasets make computation a central challenge, while specialized hardware is costly and algorithmic alternatives have not yet demonstrated comparable practical gains. It presents SLIDE as a CPU-based system combining randomized algorithms and parallelism, with contributions in system design and evaluation.

1 INTRODUCTION

  • Specialized hardware requires substantial investment and may become less effective as algorithms change, while matrix-multiplication improvements are approaching limits.The introduction links this pressure to the growth of neural networks and data volumes.Source: §1 · p. 1
  • Prior algorithmic alternatives had shown minimal practical benefits against hardware acceleration, motivating a system that can turn computational savings into faster execution.The introduction identifies hash-table overhead and limited multicore parallelism as challenges for such a system.Source: §1 · pp. 1–2

1.1 Our Contributions

  • SLIDE combines LSH-based sparsification, asynchronous parallelism, and data-structure choices to reduce computation while maintaining convergence.The authors say sparse gradient updates make conflicts negligible and support asynchronous SGD.Source: §1.1 · p. 2
  • SLIDE on a modest CPU is reported up to 2.7x faster in wall-clock time than the best alternative hardware at any accuracy.The contribution statement describes evaluation on two large benchmark datasets with fully connected networks.Source: §1.1 · p. 2
  • Workload and cache optimizations, including Transparent Hugepages and SIMD access patterns, further speed SLIDE by roughly 1.3x, yielding up to 3.5x over TF-GPU and over 10x over TF-CPU.The authors also report that memory-bound inefficiencies decrease for SLIDE as core count increases, while the opposite occurs for TF-CPU.Source: §1.1 · p. 2

2 LOCALITY SENSITIVE HASHING

The section introduces locality-sensitive hashing (LSH), which uses similarity-dependent hash collisions to retrieve candidate items without scanning the full collection. It then applies LSH sampling to select neurons adaptively, including through maximum inner product search (MIPS).

2 LOCALITY SENSITIVE HASHING

  • LSH hash families make similar items more likely to collide, enabling data structures for sub-linear approximate-neighbor queries.The section states that collision probability increases monotonically with similarity.Source: §2 · p. 2
  • The (K, L) LSH procedure concatenates K hash functions per table and retrieves the union of candidates from L queried buckets.K reduces false positives by making buckets sparser; L reduces false negatives by increasing the number of potential buckets.Source: §2 · pp. 2–3

2.1 LSH for Estimation and Sampling

  • For accurate nearest-neighbor search, conventional LSH can require many tables; the sampling view instead finds that probing as few as one bucket can suffice for adaptive sampling.A candidate is sampled with probability 1 − (1 − p^K)^L, which varies with the LSH collision probability.Source: §2.1 · p. 3

2.1.1 MIPS Sampling

  • MIPS hashing samples each collection vector with probability increasing in its inner product with the query, after a one-time linear preprocessing of the collection.Further adaptive sampling for a query requires only a few hash lookups.Source: §2.1.1 · p. 3
  • SLIDE uses the sampled neurons as active sets in its layer-wise training procedure, applying forward propagation and backpropagation to those sets.The supplied algorithm initializes per-layer hash tables and samples a set of active neurons for each layer.Source: §2.1.1 · p. 3

3 PROPOSED SYSTEM: SLIDE

SLIDE uses LSH tables to select active neurons and compute only their activations and associated weights, while sparse gradients support asynchronous CPU parallelism. The system also supports several LSH hash families and reports near-perfect scaling as core count increases.

3.1 Introduction to the overall system

  • LSH queries select active neurons layer by layer; only their activations are computed and passed forward, while other activations are treated as zero.The sampled output layer also uses only active neurons in its softmax normalization.Source: §3.1 · p. 4
  • By avoiding non-active neurons and weights, SLIDE computes in proportion to active units; activating fraction s of neurons means updating fraction s^2 of weights on average.The system modifies hash-table positions after weight updates to reflect changed neuron weights.Source: §3.1 · p. 5
  • Per-input activation and error-gradient arrays let batch instances compute independently, and sparse gradient updates are applied asynchronously to avoid sequential batch accumulation.The section invokes HOGWILD-style updates, stating that a small amount of overlap is tolerable and does not hurt convergence.Source: §3.1 · p. 5
  • SLIDE reports near-perfect scaling as core count increases, unlike optimized TF on CPUs, which scales poorly beyond 16 cores.The section attributes its parallel design to asynchronous gradient updates across training instances.Source: §3.1 · p. 5

3.2 Details of Hash Functions and Hash Tables

  • SLIDE supports Simhash, WTA, DWTA, and Minhash; Simhash uses sparse random projections to reduce hash-code computation.With one-third sparsity, the described inner-product work falls from d to d/3 multiplications.Source: §3.2 · p. 5

4 REDUCING OVERHEAD

The section addresses the overheads of sampling neurons and updating LSH tables. It compares three sampling strategies and describes update-frequency, bucket-replacement, and hash-recomputation choices.

4.1 Sampling Overhead

  • Vanilla sampling retrieves neurons from randomly chosen hash-table buckets until the target β_l is met or all tables have been queried.Its stated time complexity is O(β_l).Source: §4.1 · p. 6
  • TopK sampling selects the β_l neurons appearing most often across queried buckets, while hard thresholding bypasses sorting by retaining neurons appearing at least m times.The TopK description gives O(|N_a_l|) time for sampling and sorting; the hard-threshold passage describes its selection rule.Source: §4.1 · p. 6
  • Vanilla sampling is much faster than TopK and hard thresholding, but at the cost of sample quality.The section identifies Figure 4 as a preview of the empirical efficiency comparison.Source: §4.1 · p. 6

4.2 Updating Overhead

  • SLIDE reduces hash-table update overhead by exponentially increasing the interval between updates as training proceeds.The schedule starts after N0 iterations; the stated intuition is that gradient updates are larger early in training than near convergence.Source: §4.2 · p. 6
  • When a bucket is full, SLIDE uses reservoir sampling or a simpler FIFO replacement policy; for sparse weight changes, it can update Simhash codes in O(d′) rather than O(d) additions.The reservoir-sampling approach is described as retaining LSH's adaptive sampling property.Source: §4.2 · p. 6

5 EVALUATIONS

On the evaluated large recommendation datasets, SLIDE reaches accuracy faster than TensorFlow on V100 GPUs, while using sparse adaptive sampling to reduce last-layer work. The experiments examine that comparison, sampled softmax, batch size, CPU-core scaling, and CPU optimizations.

5 EVALUATIONS

  • 2.7x lower time to convergence than TF-GPU; on Amazon-670K, SLIDE takes 2 hours versus 5.5 hours, while matching convergence per iteration.The comparison uses the same architecture, optimizer, and learning hyperparameters; SLIDE samples about 0.5% of active output neurons.Source: Figure 5 · p. 7, §5 · pp. 7–8
  • Memory-bound inefficiency rises with more cores for TF-CPU but falls for SLIDE, which maintains around 80% core utilization across the reported thread counts.SLIDE’s sparse memory accesses and per-thread arrays with asynchronous updates are cited as supporting near-peak utilization.Source: §5 · p. 8, Figure 6 · p. 8

5.1 Comparison with other Heuristics

  • Sampled softmax needs 20% of classes for decent accuracy, while SLIDE’s input-dependent adaptive sampling outperforms it in time and convergence.SLIDE samples about 0.5% of classes; sampled softmax uses significantly more neurons yet shows poor convergence behavior.Source: §5.1 · pp. 8–9

5.2 Effect of Batch Size

  • SLIDE outperforms TF-GPU across batch sizes, and the gap widens as batch size grows from 64 to 256.The authors attribute this to fewer computations per instance and parallel batch processing with asynchronous gradient updates.Source: §5.2 · p. 9, Figure 8 · p. 10

5.3 Scalability Tests

  • SLIDE beats TF-GPU on Delicious-200K with fewer than 32 CPU cores and on Amazon-670K with 8; it beats TF-CPU with about 8 and 2 cores, respectively.The CPU-core thresholds differ by dataset; the GPU comparison is against a flat V100 performance line.Source: §5.3 · pp. 9–10, Figure 9 · p. 10

5.4 Additional Speedup with Threading Model and Platform Micro-architecture

  • ≈1.3x faster than basic SLIDE after cache and SIMD optimizations, yielding 3.5x speedup over TF-GPU and 10x over TF-CPU.The reported optimizations include Hugepages, cache-line alignment, and Intel-AVX SIMD instructions.Source: §5.4 · p. 10, Figure 10 · p. 10

6 CONCLUSION AND FUTURE WORK

SLIDE combines tailored randomized hashing and asynchronous CPU parallelism, and the conclusion reports faster training than GPU- and CPU-based TensorFlow. The appendix describes hashing variants designed for different input and memory conditions.

6 CONCLUSION AND FUTURE WORK

  • SLIDE reports up to 3.5x gain against TF-GPU and 10x gain against TF-CPU in training time with similar precision.The conclusion also says the system uses modest CPU OpenMP parallelism and tailored randomized hashing with data structures that allow asynchronous parallelism.Source: §6 · p. 10
  • Planned next steps are extending SLIDE to convolutional layers and exploring distributed implementation, which the authors expect to benefit from minimal communication costs due to sparse gradients.The conclusion also identifies random memory accesses and parallelism as distinctive benefits of SLIDE.Source: §6 · p. 10

A DIFFERENT HASH FUNCTIONS

  • Sparse random projection reduces Simhash inner-product work from d to d/3 multiplications at one-third sparsity, with random indices generated once.The random vectors use components from {+1, 0, −1}; the passage says using +1s and −1s enables additions rather than multiplications.Source: A DIFFERENT HASH FUNCTIONS · p. 12
  • The WTA modification stores KLm/d permutations rather than KL permutations, reducing storage from O(KLd) to O(KLm), with hash computation also taking O(KLm) operations.The input dimension is d and m is an adjustable hyperparameter much smaller than d.Source: A DIFFERENT HASH FUNCTIONS · pp. 12–13
  • DWTA addresses sparse inputs where WTA may not produce representative codes by processing nonzero indices and densifying empty bins.The method updates maximum indices in mapped bins for each nonzero input index.Source: A DIFFERENT HASH FUNCTIONS · p. 13
  • DOPH thresholds a weighted input to binary form by setting its k highest values to 1 and the rest to 0 before hashing.The selected top-k indices are maintained with a priority queue requiring O(dlogk) operations rather than sorting at O(dlogd).Source: A DIFFERENT HASH FUNCTIONS · p. 13

B REDUCING THE SAMPLING OVERHEAD

The section presents vanilla, TopK, and hard-threshold sampling strategies for retrieving active neurons from LSH tables. They trade sampling overhead against selection behavior.

B REDUCING THE SAMPLING OVERHEAD

  • The sampling strategies are introduced as ways to retrieve large inner products efficiently after identifying active neurons through LSH.The section presents vanilla, TopK, and hard thresholding and points to later experiments on their utility and efficiency.Source: B REDUCING THE SAMPLING OVERHEAD · p. 13
  • Vanilla sampling randomly queries hash tables until it selects the target β_l neurons or exhausts the tables, with time complexity O(β_l).It retrieves from a total of τ tables; a neuron's selection probability depends on its LSH collision probability p.Source: B REDUCING THE SAMPLING OVERHEAD · p. 13
  • TopK sampling counts each neuron's appearances across the L tables and selects the β_l most frequent, adding hashmap space and sampling-and-sorting time proportional to the candidate set.The candidate-set size is represented as |N_a_l| in the supplied passages.Source: B REDUCING THE SAMPLING OVERHEAD · p. 13
  • Hard thresholding selects neurons appearing at least m times, avoiding TopK's sorting step; increasing m reduces false positives but can miss active neurons.With L = 10, m = 9 gives neurons with collision probability p > 0.8 more than 0.5 selection probability, while m = 1 gives neurons with p < 0.2 more than 0.8 selection probability.Source: B REDUCING THE SAMPLING OVERHEAD · p. 13

C DESIGN CHOICE COMPARISONS

This section frames design-choice comparisons on a real classification task and includes figures about hard-threshold selection and sampling time.

C DESIGN CHOICE COMPARISONS

  • The section benchmarks SLIDE design choices on the Delicious-200K real classification task to examine their trade-offs and performance behavior.The stated design choices include efficient MIPS for selecting active neurons and policies for inserting neurons into hash tables.Source: C DESIGN CHOICE COMPARISONS · pp. 13–14
  • For hard thresholding, m = 9 reduces false-positive neurons but misses many active neurons, whereas m = 1 selects most active neurons along with many false positives.The figure describes theoretical selection probability Pr against collision probability p for different frequency thresholds m.Source: Figure 11 · p. 14
  • Figure 12 reports time in seconds for different sampling methods after active neurons are retrieved from hash tables.Source: Figure 12 · p. 14

C.1 Evaluating Sampling Strategies

The evaluation profiles sampling overhead during the first epoch of a classification task. TopK thresholding is much slower than the other strategies, while vanilla sampling is recommended for efficiency.

C.1 Evaluating Sampling Strategies

  • The comparison profiles vanilla sampling, TopK thresholding, and hard thresholding while varying the number of neurons selected during the first epoch.The passage says iteration-wise convergence differences between TopK thresholding and vanilla sampling are negligible.Source: §C.1 · p. 14
  • TopK thresholding takes magnitudes more time than vanilla sampling and hard thresholding across all sample counts.The figure's y-axis is logarithmic, and the passage attributes TopK's higher cost to sorting.Source: §C.1 · p. 14
  • Hard thresholding takes slightly more time than vanilla sampling, so the authors recommend vanilla sampling as the most efficient option for their extreme-classification experiments.Source: §C.1 · p. 14

C.2 Addition to Hashtables

The section compares Reservoir Sampling and FIFO for inserting Delicious neurons into hash tables, finding Reservoir Sampling more efficient but the difference negligible against full insertion time.

C.2 Addition to Hashtables

  • The timing test inserts all 205,443 Delicious output-layer neurons, measuring both hash-table insertion alone and the full process including hash-code generation.The full-insertion measure includes generating each neuron's hash codes; insertion-only excludes that step.Source: §C.2 · p. 14
  • Reservoir Sampling is more efficient than FIFO, but its advantage is negligible compared with the full insertion time.The authors therefore choose between them based on practical utility and use FIFO in their experiments.Source: §C.2 · p. 14

D THREADING MODEL AND PLATFORM MICRO-ARCHITECTURE OPTIMIZATION

SLIDE is memory-bound, so the section describes threading, cache, and workload choices intended to match its access patterns to the CPU platform. It also uses vector processing and software pipelining to improve performance.

D THREADING MODEL AND PLATFORM MICRO-ARCHITECTURE OPTIMIZATION

  • Workload optimization of threading and data-access patterns that account for the platform architecture significantly boosts SLIDE's performance.The experimental analysis characterizes SLIDE as memory-bound.Source: D THREADING MODEL AND PLATFORM… · p. 15
  • On non-inclusive last-level caches, remote-thread misses on shared data can cause cache thrashing, invalidation, and bouncing; SLIDE is susceptible to this bottleneck.OpenMP affinity can scatter threads accessing private data or pack threads accessing shared structures closer to the master thread.Source: D THREADING MODEL AND PLATFORM… · p. 15
  • SLIDE reduces false sharing by aligning and allocating data structures on cache-line boundaries, including padding.The section describes false sharing as concurrent updates to data items on the same cache line, which can require serialization.Source: D THREADING MODEL AND PLATFORM… · p. 15
  • Large memory footprints can trigger costly TLB misses and page-table walks, so SLIDE employs Hugepages to increase TLB reach and reduce that overhead.The implementation uses pages larger than the default 4KB pages, ranging from 2 MB to 1 GB.Source: D THREADING MODEL AND PLATFORM… · p. 15
  • SLIDE uses SIMD vector processing to update multiple weights at once and software prefetching to bring future data into CPU caches before processing.The pipeline places explicit prefetching before processing stages to hide memory latency.Source: D THREADING MODEL AND PLATFORM… · pp. 15–16

D.1 Measuring the Impact of Transparent Hugepages

Transparent Hugepages reduce TLB misses, page-table-walk costs, memory reads caused by TLB misses, and page faults in the reported CPU-counter measurements.

D.1 Measuring the Impact of Transparent Hugepages

  • With Transparent Hugepages, data TLB load miss rate falls from 5.12% to 0.25%, and instruction TLB load miss rate falls from 56.12% to 20.96%.Table 4 compares CPU-counter metrics with and without Transparent Hugepages.Source: §D.1 · p. 16, Table 4 · p. 16
  • With Transparent Hugepages, CPU-cycle ratios for page-table walks fall from 7.74% to 0.72% for data TLB misses and from 0.02% to 0.015% for instruction TLB misses.The passage attributes the expected reduction in page-table walks to fewer TLB misses.Source: §D.1 · p. 16
  • Memory reads caused by data TLB misses fall from 3,062,039/s to 749,485/s, while instruction TLB-miss reads fall from 12,060/s to 11,580/s.The passage also reports page faults falling from 32,548/s to 26,527/s.Source: §D.1 · p. 16

E MORE DISCUSSION ON SCALABILITY

SLIDE's convergence-time ratio improves more sharply as CPU cores increase than Tensorflow-CPU's, and SLIDE reaches lower convergence times with fewer cores on both reported datasets.

E MORE DISCUSSION ON SCALABILITY

  • SLIDE's convergence-time ratio drops more sharply with increasing cores than Tensorflow-CPU's, indicating better scalability.The ratio is convergence time at each core count relative to the minimum time using all 44 cores.Source: E MORE DISCUSSION ON SCALABILITY · p. 16, Figure 13 · p. 16
  • SLIDE beats Tensorflow-CPU with 8 cores on Delicious-200K and 2 cores on Amazon-670K, and beats Tensorflow-GPU with fewer than 32 and 8 cores, respectively.Tensorflow-CPU's benefits from additional cores are not obvious after 16 cores.Source: Figure 13 · p. 16, E MORE DISCUSSION ON SCALABILITY · p. 16

Related papers

Loading 1903.03129v2…