Matrix factorizations at scale: A comparison of scientific data analytics in spark and C+MPI using three case studies.

Alex Gittens, Aditya Devarakonda, Evan Racah, Michael F. Ringenburg, Lisa Gerhardt, Jey Kottalam, Jialin Liu, Kristyn J. Maschhoff, Shane Canon, Jatin Chhugani, Pramod Sharma, Jiyan Yang, James Demmel, Jim Harrell, Venkat Krishnamurthy, Michael W. Mahoney, PrabhatBigData 2016 · OpenReview

TL;DR

This paper compares the performance of Apache Spark against traditional C+MPI implementations for large-scale matrix factorization tasks on HPC systems. It reveals that while Spark can handle these computations, significant overheads related to scheduling and task management lead to performance gaps, highlighting the need for balanced HPC architectures and optimized I/O for data-intensive analytics.

What Problem Does This Paper Address?

Modern scientific research, from particle physics to climate modeling and bioimaging, generates massive datasets (terabytes to petabytes). Extracting meaningful insights from this data hinges on sophisticated data analytics, particularly matrix factorization techniques. However, traditional high-performance computing (HPC) environments using C and MPI, while powerful, can be complex to program. Apache Spark, a popular distributed computing framework designed for data analytics, offers a more accessible programming model. This paper addresses the critical question of how Spark's performance for these computationally intensive, large-scale scientific matrix factorization tasks compares to established C+MPI implementations on HPC infrastructure, and where the bottlenecks lie.

Methods

The authors implemented three key matrix factorization algorithms – Non-negative Matrix Factorization (NMF), Principal Component Analysis (PCA), and CX decomposition – in both Apache Spark and C+MPI. They focused on "tall-and-skinny" matrices, a common structure in scientific data, which maps well to Spark's data-parallel model.

  • Spark Implementations: Leveraged Spark's MLlib and MLMatrix libraries for linear algebra primitives. For PCA and CX, they used a distributed Gramian multiplication approach. NMF utilized a tall-skinny QR (TSQR) factorization followed by an XRAY algorithm.
  • C+MPI Implementations: Utilized optimized libraries like Intel MKL, Cray LibSci, and ARPACK for linear algebra kernels. They employed a flat MPI configuration for communication.
  • Performance Analysis: Conducted strong scaling experiments on up to 1600 Cray XC40 nodes, measuring running times and breaking them down into components like I/O, computation, task start delay, scheduler delay, and task overheads.

Datasets

The study used three large-scale scientific datasets:

  • Daya Bay Neutrino Experiment: A 1.6 TB sparse matrix from particle physics, suitable for NMF.
  • Climate Modeling (CAM5 and CFSR): Two dense matrices, 2.2 TB (Ocean) and 16 TB (Atmosphere), used for PCA.
  • Mass-Spectrometry Imaging (MSI): A 1.1 TB sparse matrix from bioimaging, used for CX decomposition.

These datasets represent real-world scientific challenges and are significantly larger than typical benchmarks for distributed linear algebra.

Key Insights and Ideas

  • Spark's Scalability vs. HPC: While Spark can execute these complex algorithms on large datasets and scale to many nodes, it incurs significant overheads compared to finely-tuned C+MPI implementations.
  • The Bottleneck is Not Always Computation: For NMF, I/O was the primary bottleneck in both Spark and MPI. However, for PCA, communication and sequential bottlenecks in MPI were significant, while Spark's overheads (scheduling, task management) became dominant.
  • Spark's Scheduler Limitations: Spark's driver-centric task scheduling creates a bottleneck, limiting the number of tasks that can be launched per second. This becomes particularly problematic for iterative algorithms like PCA, which launch many tasks per iteration.
  • I/O is Paramount: Efficient, parallel I/O is crucial for terabyte-scale data analytics. HPC architectures need to be balanced to handle data-intensive workloads effectively, as demonstrated by the saturation of I/O bandwidth in some experiments.
  • Stragglers and Variability: Spark's bulk-synchronous model is susceptible to "straggler" tasks (tasks that take much longer than average), leading to idle cores and reduced efficiency, especially at larger scales.

Key Results

  • Performance Gaps: Spark exhibited performance gaps ranging from 2x to 25x (including I/O) and 10x to 40x (excluding I/O) compared to C+MPI across the tested algorithms and datasets.
  • NMF: Spark's NMF implementation showed good scaling up to 300 nodes, but was still slower than MPI due to overheads. I/O was the dominant factor.
  • PCA: Spark's PCA implementation was significantly slower than MPI, with performance gaps increasing with node count (up to 22x at 500 nodes). This was largely due to scheduler delays and task overheads.
  • CX: Spark's CX decomposition showed good scaling, similar to PCA, indicating the shared linear algebra kernels were the performance drivers.
  • Large-Scale Runs: The study successfully scaled NMF and PCA to 1600 nodes, demonstrating Spark's capability for very large workloads, albeit with performance penalties.

Limitations and Future Work

  • Spark Overhead Mitigation: The authors suggest that improving Spark's scheduling mechanisms, potentially through better integration with MPI-based runtimes or optimizing data copying, could help close the performance gap.
  • Balanced HPC Architectures: The paper emphasizes the need for HPC systems to have balanced I/O capabilities to support data-intensive workloads effectively.
  • Profiling Granularity: The authors note that the granularity of their Spark profiling might have masked some communication overheads, which were likely included in other overhead categories.
  • NMF Science Implications: For NMF, further work is needed to augment input data with non-linear features to handle rotations and translations, and to learn event-specific classifiers from the loadings.
  • PCA Science Implications: For PCA on climate data, understanding the interplay of various timescales and spatial patterns is an ongoing area of investigation.

Summary updated

Abstract

We explore the trade-offs of performing linear algebra using Apache Spark, compared to traditional C and MPI implementations on HPC platforms. Spark is designed for data analytics on cluster computing platforms with access to local disks and is optimized for data-parallel tasks. We examine three widely-used and important matrix factorizations: NMF (for physical plausability), PCA (for its ubiquity) and CX (for data interpretability). We apply these methods to 1.6TB particle physics, 2.2TB and 16TB climate modeling and 1.1TB bioimaging data. The data matrices are tall-and-skinny which enable the algorithms to map conveniently into Spark's data-parallel model. We perform scaling experiments on up to 1600 Cray XC40 nodes, describe the sources of slowdowns, and provide tuning guidance to obtain high performance.
BibTeX
@inproceedings{gittens2016matrix,
  author = {Alex Gittens and Aditya Devarakonda and Evan Racah and Michael F. Ringenburg and Lisa Gerhardt and Jey Kottalam and Jialin Liu and Kristyn J. Maschhoff and Shane Canon and Jatin Chhugani and Pramod Sharma and Jiyan Yang and James Demmel and Jim Harrell and Venkat Krishnamurthy and Michael W. Mahoney and Prabhat},
  title = {{Matrix factorizations at scale: A comparison of scientific data analytics in spark and C+MPI using three case studies.}},
  booktitle = {BigData},
  year = {2016},
  url = {https://openreview.net/forum?id=crXZG4BqEUI},
}

Loading related content...

Figure