PaperlayerView exact revision on arXiv

Source-linked AI summary

DimmWitted: A Study of Main-Memory Statistical Analytics

Ce Zhang, Christopher Ré

arXiv:1403.7550v3cs.DBcs.LGmath.OCstat.ML

TL;DR

The paper asks how access order and replication should be chosen for first-order statistical analytics in NUMA main memory, where statistical and hardware efficiency can diverge. It studies these tradeoffs with DimmWitted across access methods and sharing granularities, finding that NUMA-aware choices can make at least one popular task at least 100× faster than competitor systems.

  • Problem

    Existing statistical analytics systems select particular access and replication points despite a broader tradeoff between statistical efficiency and hardware efficiency on NUMA machines.

  • Method

    DimmWitted studies row-wise, column-wise, and column-to-row access together with model and data replication for first-order methods across datasets, models, and architectures.

  • Results

    At least one popular task runs at least 100× faster than competitor systems using DimmWitted’s novel points in the access-method and replication tradeoff space.

  • Takeaways & Limitations

    Analytics-engine designers may benefit from supporting multiple access methods and NUMA-aware replication choices rather than treating NUMA machines as only distributed systems or SMP.

  • Takeaways & Limitations

    The system assumes analytics inputs and an initial model fit the stated main-memory task interface, and competitor comparisons include overheads for fault tolerance, work distribution, and scheduling.

Abstract

from arXiv · show

We perform the first study of the tradeoff space of access methods and replication to support statistical analytics using first-order methods executed in the main memory of a Non-Uniform Memory Access (NUMA) machine. Statistical analytics systems differ from conventional SQL-analytics in the amount and types of memory incoherence they can tolerate. Our goal is to understand tradeoffs in accessing the data in row- or column-order and at what granularity one should share the model and data for a statistical task. We study this new tradeoff space, and discover there are tradeoffs between hardware and statistical efficiency. We argue that our tradeoff study may provide valuable information for designers of analytics engines: for each system we consider, our prototype engine can run at least one popular task at least 100x faster. We conduct our study across five architectures using popular models including SVMs, logistic regression, Gibbs sampling, and neural networks.

1. INTRODUCTION

DimmWitted studies how access methods and replication trade statistical efficiency against hardware efficiency for first-order analytics on NUMA machines. It identifies design points that can substantially outperform conventional choices, including over 100× faster convergence or runtime for some tasks.

  • Motivation: DimmWitted argues that existing analytics systems under-utilize commodity hardware, sometimes by two orders of magnitude, motivating broader design exploration.The paper develops a storage abstraction and cost model intended to select nearly optimal access methods across datasets, models, and machine configurations.
  • Research Scope: The study frames statistical analytics as a tradeoff between statistical efficiency and hardware efficiency because robust iterative methods tolerate some memory incoherence.It examines access methods, model replication, and data replication rather than treating NUMA machines only as distributed systems or SMP machines.
  • Access Methods: For some tasks, DimmWitted’s novel access methods reduce time to converge to a given loss by up to 100×.The study covers row-wise, column-wise, and column-to-row access methods, which can have similar statistical efficiency but radically different wall-clock performance.
  • Model Replication: PerNode model replication exploits faster last-level-cache communication and can be an order of magnitude faster than alternative sharing granularities.Batching writes across sockets reduces communication and processor stalls, producing over 10× runtime improvement for some workloads.
  • Data Replication: Fully replicating immutable data four ways can reach the same loss almost 4× faster than sharding for some tasks.Replication provides non-redundant statistical information across nodes, reducing estimate variance, whereas sharding can produce skewed partitions.
  • System Evaluation: At least one popular task runs at least 100× faster than competitor systems with DimmWitted’s NUMA-aware tradeoff choices.The prototype is evaluated across multiple real datasets, models, and architectures.

2. BACKGROUND

DimmWitted models first-order statistical analytics on NUMA machines through explicit choices of memory coherence, access order, and data/model replication. Its execution plan assigns local data, model replicas, and access methods to cores while supporting row-wise, column-wise, and column-to-row computation.

  • Analytics Model: First-order methods repeatedly scan immutable data while updating a mutable model, with convergence checks requiring additional dataset scans.The paper uses epochs to denote complete passes over the data.
  • Memory Models: DimmWitted exposes coherence and storage layout as separate memory-model choices for implementing statistical analytics methods.Its prototype can configure memory regions as coherent or incoherent and vary the sharing scope from per-thread to per-machine.
  • Access Methods: The engine supports row-wise access over examples, column-wise access over individual features, and column-to-row access over nonzero entries in sparse matrices.These paths correspond respectively to methods such as gradient descent, stochastic coordinate descent, and Gibbs sampling or nonlinear SVMs.
  • Access Methods: DimmWitted can reorder row or column iteration, typically with some randomness, allowing one prototype to represent diverse access patterns.Figure 2 classifies popular implementations by their access method.
  • Execution: An execution plan assigns each core a data subset, a model replica, and an access method, grouping physically local replicas into locality groups.Figure 4 illustrates this engine organization.
  • NUMA Architecture: NUMA machines place cores and caches near local DRAM while connecting nodes through interconnects, making locality and remote-memory traffic central execution concerns.The paper reports QPI bandwidth as high as 25.6GB/s and describes Figure 3 as summarizing the tested machines.

3. THE DIMMWITTED ENGINE

DimmWitted exposes access-method, model-replication, and data-replication choices, then evaluates their statistical and hardware tradeoffs on NUMA machines. Its results show that no access method or replication strategy dominates: the best choice depends on data, model, and hardware conditions.

  • System Overview: The engine represents each task with row-wise, column-wise, or column-to-row functions that update a supplied model, allowing the optimizer to select among access and replication strategies.Its tradeoff space covers access-method selection, model replication, and data replication, with choices evaluated by epochs to convergence and time per epoch.
  • Access Methods: DimmWitted’s access methods have similar statistical efficiency, but their per-epoch hardware costs differ by up to 10× and favor different methods under different data sparsity conditions.Row-wise access is up to 6× faster when the cost ratio is small, whereas column-wise access is up to 3× faster when the ratio is large, due respectively to data reads and write contention.
  • System Overview: DimmWitted’s implementation is reported as 3–100× faster than GraphLab and Spark, while existing systems’ fixed design points work well for some models but not all.The comparison excludes overheads such as Spark fault tolerance and distributed execution, which the authors say would obscure the tradeoffs under study.
  • Model Replication: PerNode provides a hardware-efficient compromise: it is 23× faster per epoch than PerMachine and 1.5× slower than PerCore on SVM over RCV1.PerMachine generates 11× more cross-node DRAM requests than PerNode, while PerMachine generally converges in fewer epochs because its single replica sees more information per step.
  • Model Replication: For SGD-based models, PerNode usually performs best, whereas SCD-based models usually favor PerMachine because denser SGD updates make PerMachine less hardware-efficient.This rule reflects the interaction between update density, synchronization, and NUMA locality rather than a universally best replication granularity.
  • Data Replication: FullReplication trades higher per-epoch cost for faster convergence: on Reuters SVM within 1% of the loss, it uses 10× fewer epochs and is 5× faster overall than Sharding.At high-error regions, however, FullReplication can use more epochs and have comparable execution time; its advantage comes from each replica seeing more data.

4. EXPERIMENTS

Experiments show that choosing access methods, model replication, and data replication jointly can substantially improve convergence and throughput on NUMA machines. DimmWitted consistently outperforms competitors, with gains explained by different tradeoff choices rather than only implementation details.

  • 4.2 End-to-End Comparison: DimmWitted always converges to the target loss faster than competitors, reaching up to 10× speedups over Hogwild! and more than two orders of magnitude over GraphLab and Spark.For LP and QP, it is more than two orders of magnitude faster than Hogwild! and MLlib, while reaching up to 3× speedups over GraphLab and GraphChi.
  • 4.2 End-to-End Comparison: DimmWitted’s advantage over Hogwild! reflects replication choices: Hogwild! incurs 11× more cross-node DRAM requests, whereas DimmWitted incurs 11× more local DRAM requests.For SVM, LR, and LS, DimmWitted also benefits from stochastic gradient and PerNode replication instead of MLlib’s batch gradient descent and PerCore design.
  • 4.2 End-to-End Comparison: A 240× speedup over MLlib on Forest at 1% loss combines 60× fewer epochs with 4× faster epochs, and the epoch advantage persists after matching implementations.The matched implementation is only 3× faster than MLlib, indicating that the main difference is the selected tradeoff point rather than low-level implementation differences.
  • 4.2 End-to-End Comparison: DimmWitted achieves the highest throughput in the parallel-sum comparison, including a 1.6× advantage over Hogwild!.The experiment uses a simple update function and all cores on one machine.
  • 4.3 Tradeoff Choices: The best access method depends on the model: DimmWitted selects row-wise access for SVM, LR, and LS, and column-wise access for LP and QP.On LP and QP, column-wise access is more efficient than the row-wise approach used by MLlib and Hogwild!, while DimmWitted’s per-epoch time is up to 3× faster than GraphLab and GraphChi.
  • 4.3.2 Model Replication: Neither PerMachine nor PerNode dominates across workloads: PerNode is 12× faster for SVM on RCV1, whereas PerMachine is at least 14× faster for LP on Amazon.Relative performance depends on socket count and update sparsity; at 1% sparsity PerMachine wins, while denser updates favor PerNode.
  • 4.3.3 Data Replication: FullReplication is never substantially worse than Sharding and can be dramatically better, so it is preferable when sufficient memory is available.At 100% loss, both converge in one epoch and Sharding may be 2–5× faster because it examines less data.

5. EXTENSIONS

The extensions apply DimmWitted’s tradeoffs beyond the core supervised-learning workloads. Gibbs sampling and deep neural networks both gain substantial performance from selecting suitable access and replication strategies.

  • Extensions: The extensions show that the same access and replication tradeoffs apply to Gibbs sampling and deep neural networks, not only to the core benchmark models.The paper reports significant speed increases over classical implementation choices for both applications.
  • Gibbs Sampling: DimmWitted achieves 4× the sample throughput of PerMachine for Gibbs sampling using the algorithm’s column-to-row access pattern.Gibbs sampling’s main operation over factor graphs is a column-to-row access.
  • Neural Networks: For a seven-layer MNIST neural network, DimmWitted uses PerNode and FullReplication instead of the classical PerMachine and Sharding choices, achieving more than an order-of-magnitude improvement.The network contains 0.12 billion neurons and 0.8 million parameters.

6. RELATED WORK

Related work spans statistical analytics, data-mining optimization, shared-memory multiprocessors, and main-memory databases. DimmWitted differs by studying statistical and hardware efficiency together across a broader tradeoff space.

  • Statistical Analytics: Existing statistical analytics frameworks improve task performance but generally implement only one point in DimmWitted’s tradeoff space, whereas DimmWitted studies the space itself.The related systems include Mahout, MLI, GraphLab, and MADLib.
  • Data Mining Algorithms: Prior data-mining work optimizes hardware efficiency through locality, data placement, cache-conscious techniques, and replication or locking schemes.These studies address algorithms such as association-rule mining, decision trees, K-means, and neural networks.
  • Data Mining Algorithms: DimmWitted’s focus differs from earlier replication and locking work because it includes statistical efficiency and lock-free execution.Earlier work considered hardware efficiency but not how choices affect statistical convergence.
  • Shared-memory Multiprocessor Optimization: Shared-memory multiprocessor research contributes locality and computation- or data-decomposition ideas, including locality groups that also inspire DimmWitted.The related work connects these ideas to Legion and earlier compiler techniques for shared-memory machines.
  • Main-memory Databases: Main-memory database research revisits classical tradeoffs such as joins and shuffling on modern multi-socket, large-memory architectures.This work provides architectural context but addresses database processing rather than DimmWitted’s statistical-analytics tradeoffs.

7. CONCLUSION

The paper studies access-method, model-replication, and data-replication tradeoffs for statistical analytics on main-memory NUMA machines. Its prototype shows that exploiting new points in this space can produce at least 100× gains on a popular task.

  • Conclusion: A DimmWitted prototype can run at least one popular statistical-analytics task at least 100× faster than competing systems by exploiting novel tradeoff points.The conclusion identifies access methods, model replication, and data replication as the studied dimensions.

A. IMPLEMENTATION DETAILS

DimmWitted’s implementation choices connect hardware efficiency with statistical analytics, covering data placement, storage format, access order, and related design tradeoffs.

  • A. IMPLEMENTATION DETAILS: DimmWitted evaluates worker-data collocation, dense versus sparse storage, and row- versus column-major layout as hardware-efficiency choices.The implementation also situates these choices within prior systems, database, HPC, DSL, and optimization work.
  • A. IMPLEMENTATION DETAILS: Column-major storage causes 9× more L1 data load misses than Row-major storage for row-wise matrix-vector access.The passage attributes this to cache-line utilization and prefetching limitations for strided accesses.
  • A. IMPLEMENTATION DETAILS: DimmWitted treats hardware efficiency and statistical efficiency as joint concerns for first-order statistical analytics.Its related-work framing distinguishes this combination from prior work focused on individual hardware or algorithmic techniques.

C.1 MoreDetailedTuningInformationforSpark

The Spark comparison is tuned across statistical and hardware parameters, then decomposed to distinguish convergence differences from framework overhead. These experiments show that DimmWitted’s advantage is not explained by implementation language alone.

  • C.1 MoreDetailedTuningInformationforSpark: Spark’s step size and batch size produce more than 100× variation in time to converge to the same loss, across 28 tested combinations.The tuning grid contains 7 step sizes and 4 batch sizes.
  • C.1 MoreDetailedTuningInformationforSpark: DimmWitted’s C++ batch-gradient implementation converges in within 5% as many epochs as MLlib, runs each epoch 3–7× faster, yet remains 20–39× slower than DimmWitted.This comparison follows MLlib’s algorithm with the same step size and batch size across architectures.
  • C.1 MoreDetailedTuningInformationforSpark: On Forest, DimmWitted reaches 1% loss in 1 epoch, versus 63 epochs for MLlib and 64 for the C++ implementation.MLlib spends 0.9 seconds scheduling and 1.8 seconds enumerating and computing across its 64 epochs.
  • C.1 MoreDetailedTuningInformationforSpark: On Music, setting Spark’s SPARK MEM parameter to 48GB yields 7× speedup over 1GB for parallel-sum throughput.The study evaluates 540 hardware-parameter combinations to characterize this sensitivity.
  • C.1 MoreDetailedTuningInformationforSpark: Delite stops scaling beyond one socket, while DimmWitted’s PerCore strategy scales more linearly than PerNode and PerMachine.The comparison uses logistic regression on Music with local2 and varies thread counts.

C.3 Scalability Experiments

DimmWitted’s scalability experiment uses subsampled ClueWeb datasets to measure per-epoch cost as the number of examples increases.

  • C.3 Scalability Experiments: The scalability dataset contains 500 million examples, 100K features per example, and 4 billion non-zero elements.It is constructed from ClueWeb for a least-squares model predicting PageRank scores from URL features.
  • C.3 Scalability Experiments: Per-epoch time grows almost linearly with the number of examples on ClueWeb 2009.The experiment compares datasets formed from 1%, 10%, and 50% of the 500-million-example corpus.

C.4 Importance Sampling as a Data Replication Strategy

Importance sampling extends DimmWitted’s replication strategies to datasets whose examples have unequal importance. On Music, its benefit depends on the error tolerance and resulting sample count.

  • C.4 Importance Sampling as a Data Replication Strategy: The original Sharding and FullReplication schemes assume that all data tuples are equally important.Importance sampling addresses settings where examples such as those characterized by leverage scores differ in importance.
  • C.4 Importance Sampling as a Data Replication Strategy: DimmWitted samples each worker’s examples with probability proportional to a row’s leverage score, using 2ε^-2d log d samples per epoch.For general loss functions, the leverage score is used heuristically rather than as a guaranteed loss-approximation criterion.
  • C.4 Importance Sampling as a Data Replication Strategy: Importance0.1 is 3× faster than FullReplication for 10% loss, while Importance0.01 is slower because its lower tolerance requires more samples.Importance0.1 processes 10% of the data, whereas Importance0.01 processes the same number of tuples as FullReplication.

D.1 Gibbs Sampling

DimmWitted supports Gibbs sampling on general factor graphs by representing graph connectivity as column-to-row matrix access and running independent chains across NUMA nodes. On local2, its general implementation is 3.7× faster than GraphLab’s hand-coded topic-modeling implementation without application-specific optimization.

  • Gibbs Sampling: Gibbs sampling processes one variable at a time by fetching connected factors and current assignments, then sampling a new value from the conditional probability.The procedure advances to the next randomly selected variable after updating the current assignment.
  • Gibbs Sampling: DimmWitted models factor-graph Gibbs sampling as column-to-row access: rows represent factors, columns represent variables, and nonzero entries represent links.Processing a variable fetches its matrix column and other columns for variables connected to the same factors.
  • Gibbs Sampling: For Gibbs sampling, DimmWitted’s PerNode strategy runs one independent chain per NUMA node and combines all generated samples for estimation.Performance is measured as throughput, defined as samples generated per second.
  • Gibbs Sampling: 3.7× faster on local2, DimmWitted’s general Gibbs-sampling implementation outperforms GraphLab’s hand-coded topic-modeling implementation without application-specific optimization.The comparison uses 100K documents and 20 topics.
  • Deep Neural Networks: For deep neural networks, DimmWitted reuses the same SGD code path within each layer and processes layers in round-robin order.This follows the de facto approach of running SGD separately within each layer.
Loading 1403.7550v3…