A comparative evaluation of systems for scalable linear algebra-based analytics (2018)

[hammer]

This paper from Anthony Thomas and Arun Kumar at UCSD also has a webpage and GitHub repo ADALabUCSD/SLAB. Additional details are available in their technical report.

Introduction

• The goal of the paper is to benchmark scalable linear algebra systems such as MADlib, Spark MLlib, SystemML, ScaLAPACK, SciDB, TensorFlow, R, and NumPy.
• Other systems considered include RIOT, Oracle R Enterprise, Microsoft’s Revolution R, SparkR, Apache Mahout Samsara, Myria, and SimSQL.
• The benchmark focuses on "LA operations that process the whole dataset in bulk, i.e., in one go in a data-parallel manner."
• pbdR (powered by ScaLAPACK) is their baseline
• Previous benchmarks of in-memory libraries such as BLAS, Eigen, Intel MKL, LAPACK, and ScaLAPACK only cover "simple LA operations"
• This benchmark covers 3 axes of interest
  1. task complexity: 6 common LA operations, 2 pipelines, 4 LA-based data analysis algorithms.
  2. data scale: vary both the number of examples and sparsity of the data matrix.
  3. computation environment: vary the number of CPU cores and cluster nodes. GPUs not included.
• The authors are particularly interested in
  • Inter-operation optimizations (akin to relational query optimization)
  • Ergonomics of the abstractions provided by each library
• pbdR/ScaLAPACK outperforms all other systems in almost all cases on dense data.
• Support for large sparse datasets is still relatively poor.

Background

• pbdR: compiles programs to MPI batch jobs.
• MADlib: some operations, such as eigen or singular value decompositions, require the matrix to fit in single-node memory.
• MLlib: provides three main (physical) datatypes for distributed matrices targeting different data access patterns. The user must select a matrix type explicitly. The operators provided for each type are not consistent. Some operators densify sparse matrices.
• SystemML: offers a “declarative” language called DML. Can transparently switch between local and distributed execution.
  • JH note: the primary developer of SystemML, Matthias Boehm, has forked the project and continues its development as SystemDS.
• TensorFlow: cannot scale bulk LA algorithms, since each individual operator must fit on a single node.
• SciDB: supports a fairly limited set of LA operations (matrix-matrix multiplication and SVD). These operations do not support disk spills, i.e., the data must fit in distributed memory.

Description of tests

MAT: Matrix Operations

• Category (1): Matrix Transpose (TRANS)
• Category (2): Frobenius Norm (NORM)
• Category (3): Gram Matrix (GRM)
• Category (4): Matrix-Vector Multiplication (MVM)
• Category (5): Matrix Addition (ADD)
• Category (6): Matrix Multiplication (GMM)

PIPE: Pipelines and Decompositions

• Multiplication Chain (MMC)
• Singular Value Decomposition (SVD)

ALG: Bulk LA-based ML Algorithms

• Ordinary Least Squares Regression (OLS)
• Logistic Regression (LR)
• Non-negative Matrix Factorization (NMF)
• Heteroscedasticity-Robust Standard Errors (HRSE)

Experimental comparison

• Experiments run on the CloudLab “Clemson” site with c6320 instances.
• OpenStack manages the cluster
• Each OpenStack instance corresponds to a physical node and is allocated 24 CPU cores, 200GB RAM and 800GB of disk.
• All runs are repeated five times.
• The first runtime measurement is discarded (for warming caches).
• Assume that data has been pre-loaded into the appropriate storage medium for each system (e.g. HDFS or an RDBMS) and do not include data loading times in any of our measurements.
• MADlib times include time to write to disk.
• For each system, parameters picked that gave best performance on key LA operations - especially matrix-matrix multiplication.
• More details on tuning in the technical report.

Results for MAT

• SystemML’s ability to transparently switch between local and distributed execution based on its data size estimates is effective.
• PostgreSQL’s hard size limit of 1 GB for arrays is a serious scalability bottleneck for MADlib.
• MLlib always densifies the right operand in GMM, which leads to extra processing overheads.
• TensorFlow’s runtimes are fastest b/c it uses single precision floating point numbers (float) by default, while the other systems all use double precision numbers (double).

Results for PIPE

• MLlib’s strong performance for SVD is due to a novel algorithm (DIMSUM) described in Dimension Independent Matrix Square using MapReduce (2013).

Results for ALG

• For pbdR, it was necessary to hand-optimize the sparse diagonal matrix multiplication in HRSE to avoid out-of-memory errors.
• MADlib does not automate composition of LA operators, which forces all intermediate results to be written to disk and slows iterative algorithms.
• SciDB does not provide an operator for matrix inversion or solving a linear system.
• MLlib linked with a native BLAS library because it yielded substantial performance improvements.

Scalability

• Used Criteo's Terabyte Click Logs to construct two benchmark datasets.
  1. DenseCriteo retains the target and 10 numeric features. Its size as a CSV file is 32 GB.
  2. SparseCriteo retains the target and 4 one-hot encoded categorical variables.
• Scalable LA abstractions, especially on MADlib and MLlib, come at a high performance penalty.
• MADlib and MLlib were either incapable of running due to hard-coded dimensionality limits, or they crashed or timed out.

Analysis and discussion

Algorithm implementation effort

• SystemML and pbdR generally had the most parsimonious code.
• SciDB generally had the most verbose code.
• MLlib’s verbosity is because it does not yet provide a few basic LA operators in its API.

Guidelines for Practitioners

pdbR

• Does not support sparse data.
• Poor support for data I/O; users will likely need to implement custom data readers/writers.
• Does not support fault tolerance or automatic disk spills.
• Supports only a small subset of R’s native ML implementations.
• Best suited for rapidly prototyping new LA-based analysis algorithms at scale.

MLlib

• MLlib often crashed or exhibited very poor performance with default tuning settings.
• Tuning settings were often workload specific.
• Sometimes densifies sparse data during execution, degrading performance.
• Physical data independence is limited as users must manually tune partitioning, caching behavior, and select from a set of matrix data structures supporting inconsistent operators.
• MLlib is best suited to users who require robust support for complex data pre-processing but are happy with canned ML algorithm implementations.

SystemML

• Simpler than MLlib.
• Best suited to users who want to deploy custom LA-based ML algorithms in a production environment where robust feature pre-processing pipelines and fault-tolerance are essential.

MADlib

• Determining the optimal number of segments required manually re-initializing and loading the database which was labor-intensive.
• Suffers from a serious scalability bottleneck due to a hard limit of 1 GB imposed on the maximum size of an array by PostgreSQL.
• MADlib is well suited to users with large RDBMS-resident datasets and who are happy with canned ML algorithm implementations.

SciDB

• Densifies sparse matrices when computing SVD and GMM.
• GMM and SVD are the only major LA operators provided by SciDB in the distributed setting.
• SVD only returns one matrix at a time, so must be called 3 times (?!).
• The community edition of SciDB does not provide any “canned” ML algorithms.
• Requires a lot of implementation effort on the part of the user when performing non-trivial LA-based ML algorithms.

Key takeaways

• Transparently switching between execution in local and distributed mode improves performance and reduces user effort.
• Automatically detecting LA pipeline optimizations such as reordering matrix multiplication chains and multiplication of a dense matrix with a diagonal matrix (as in HRSE) yields performance benefits and reduces user effort.
• Intermediate results should not be needlessly materialized and computations should be pipelined.
• Abstractions that purport to support physical data independence must lead to real reductions in user coding effort.
  • MLlib has too many matrix types with inconsistent APIs that yield dramatically different performance depending on the LA operation.

Open research questions

• Better Support for Large Sparse Data.
• Auto-tuning Data Layout and System Parameters.
• Multi-node “COST” and Parallelism Models: support transparent scalability for hybrid data and task parallelism.
• Including ML Accuracy for Evaluation: should optimize the accuracy-runtime Pareto frontier.

Other related work

• LINPACK benchmark
• PLASMA