PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Tensor Compression for Large-Scale Scientific Data

Woody Austin, Grey Ballard, Tamara G. Kolda

arXiv:1510.06689v2math.NAcs.DC

TL;DR

Massive scientific simulations create storage and analysis bottlenecks, motivating compression that preserves useful structure. The paper develops a distributed-memory Tucker implementation and demonstrates strong compression and scalable processing on simulation data.

  • Problem

    Scientific simulation data are growing massive enough to create storage, transfer, and analysis bottlenecks, while their multidimensional structure offers an opportunity for compression.

  • Method

    The paper implements distributed-memory Tucker decomposition using parallel tensor operations and data distributions designed for large dense tensors.

  • Results

    The method achieves 50–75% reduction with normalized RMS errors below 10^-6, 99.9% or greater reduction below 10^-2, and processes 15 TB in about a minute.

  • Takeaways & Limitations

    Tucker compression can reduce terabytes to gigabytes or megabytes and support subset reconstruction for analysis on a single laptop.

Abstract

from arXiv · show

As parallel computing trends towards the exascale, scientific data produced by high-fidelity simulations are growing increasingly massive. For instance, a simulation on a three-dimensional spatial grid with 512 points per dimension that tracks 64 variables per grid point for 128 time steps yields 8~TB of data, assuming double precision. By viewing the data as a dense five-way tensor, we can compute a Tucker decomposition to find inherent low-dimensional multilinear structure, achieving compression ratios of up to 5000 on real-world data sets with negligible loss in accuracy. So that we can operate on such massive data, we present the first-ever distributed-memory parallel implementation for the Tucker decomposition, whose key computations correspond to parallel linear algebra operations, albeit with nonstandard data layouts. Our approach specifies a data distribution for tensors that avoids any tensor data redistribution, either locally or in parallel. We provide accompanying analysis of the computation and communication costs of the algorithms. To demonstrate the compression and accuracy of the method, we apply our approach to real-world data sets from combustion science simulations. We also provide detailed performance results, including parallel performance in both weak and strong scaling experiments.

I. INTRODUCTION

Scientific simulations produce massive multidimensional data that can bottleneck storage, transfer, and analysis. The paper introduces a distributed-memory Tucker implementation that exploits low-dimensional structure for compression and scalable processing.

  • Scientific simulation data can require dedicated storage and parallel clusters even for simple a posteriori analysis.
  • Burstiness across spatial locations, times, and variables gives combustion data low-dimensional multilinear structure suitable for Tucker compression.
  • The work presents the first distributed-memory parallel algorithm and implementation for Tucker decomposition of general dense tensors.
  • 50–75% reduction is achieved with normalized RMS errors below 10^-6, while 99.9% or greater reduction has errors below 10^-2.
  • 15 TB can be compressed to 1.5 GB in about a minute, while 12 GB can be compressed to 1 MB in under a second.

B. Tucker Algorithm and Key Kernels

Tucker represents a tensor with a smaller core and mode-specific factor matrices, while ST-HOSVD initializes the factors and HOOI iteratively improves the approximation. The parallel implementation centers on tensor-times-matrix, Gram, and eigenvector computations.

  • Tucker approximates X as a core tensor multiplied by factor matrices along every mode.
  • The reduced representation uses core dimensions R1 × R2 × · · · × RN, with factor matrix U(n) sized In × Rn.
  • ST-HOSVD: ST-HOSVD initializes each factor from leading left singular vectors of progressively reduced unfoldings selected for a user-specified error threshold.
  • HOOI: HOOI alternates across tensor modes to update factor matrices and monotonically improves approximation error without guaranteeing a global minimum.
  • Gram-based computation is motivated by relatively small mode sizes, such as In ≤ 2000, and error tolerances above the square root of machine precision.
  • The parallel algorithms use TTM operations, Gram matrices, and eigenvector calculations as their three key computational stages.

C. Reconstruction

The reconstructed tensor is formed through a sequence of tensor-times-matrix operations. Subtensors can be computed directly without materializing the full reconstruction.

  • The approximate reconstruction is computed from the core and factor matrices using a sequence of TTM operations.
  • Small subtensors can be reconstructed efficiently by using only selected rows of the factor matrices.

III. RELATED WORK

The paper positions its work as the first distributed-memory implementation of Tucker decomposition, extending prior compression and parallel tensor-decomposition research to large dense tensors.

  • The Tucker decomposition has previously been used to compress scientific data such as hyperspectral images and volume-rendering data.
  • This work is presented as the first distributed-memory implementation of a Tucker tensor decomposition.Prior randomized work still required all data to fit on one machine, while shared-memory work addressed dense TTM rather than the full distributed Tucker method.
  • Related parallel decomposition efforts include CP methods for dense or sparse tensors, using coordinate descent, alternating least squares, hypergraph partitioning, or MapReduce.
  • Tensor-train decomposition and parallel tensor contraction provide additional related directions, but their methods differ from the Tucker approach developed here.
  • The proposed system distributes dense tensors by a Cartesian N-way processor grid, with each processor owning a distinct subtensor and factor matrices redundantly distributed across processor columns.The local tensor contains J/P entries, while redundant factor storage is considered negligible because factor matrices are relatively small.

C. Unfolded Tensor Distribution

The method uses a block-distributed tensor whose mode-n unfolding is obtained logically, without redistributing data, and performs local BLAS-based operations on the resulting layout.

  • Unfolding a distributed tensor is purely logical, so the mode-n matrix remains block distributed across a Pn × ˆPn processor grid without data redistribution.The local unfolded tensor is equivalent to unfolding each processor’s local tensor.
  • Interior-mode local layouts consist of row-major subblocks that can be processed independently with BLAS subroutines.Mode 1 uses column-major order, mode 4 uses row-major order, and interior modes use multiple row-major subblocks.
  • The parallel cost analysis uses the α-β-γ model, where message time is α + Wβ and floating-point work costs γ per flop.
  • The tensor-times-matrix operation partitions the local factor matrix into Pn block rows and computes one local product per block row before reducing results across processor columns.Each iteration produces one output block, as illustrated for a 2 × 3 × 2 processor grid.
  • Blocking keeps each intermediate product no larger than the local result tensor, while a single multiplication and reducescatter is possible when K < Jn/Pn.The unblocked optimization reduces latency but does not change computation or bandwidth costs.

C. Parallel Gram Computation

Parallel Gram computation forms the mode-n Gram matrix from distributed tensor blocks, using local BLAS kernels, processor exchanges, and an all-reduce.

  • Each processor column owns a block column of the unfolded tensor and computes intermediate Gram contributions in row blocks.Local Gram products use dsyrk, with multiple calls required for interior-mode layouts.
  • Figure 5 depicts the distribution of the unfolded tensor and Gram intermediates across a 2 × 3 × 2 processor grid.Each processor column computes local matrix-vector products, whose results are summed across each block row.
  • The implementation stores both triangles of the symmetric Gram matrix, leaving a potential factor-of-two storage saving unused.

D. Parallel Eigenvectors Computation

After forming the Gram matrix, the method computes leading eigenvectors by gathering the matrix within processor columns, solving locally, and redistributing row subsets.

  • The Gram matrix is redundantly stored on processor columns, and the eigenvector output uses a compatible block-row distribution.The method assumes mode sizes such as In ≤ 2000, making the eigensolver essentially sequential.
  • Each processor column all-gathers the Gram matrix, computes the eigenvectors locally, and extracts its assigned row block of the output.
  • The large temporary Gram and eigenvector matrices can overlap the corresponding local storage portions.

A. ST-HOSVD

ST-HOSVD’s cost is driven primarily by tensor-times-matrix and Gram computations, with mode ordering and processor-grid choices affecting performance. Eigenvector calculations are typically negligible, while memory remains bounded by reusable iteration storage.

  • ST-HOSVD latency is dominated by tensor-times-matrix operations, whose cost grows with the processor-grid dimensions across modes.
  • TTM and Gram computations dominate ST-HOSVD cost, whereas eigenvector calculations are typically negligible by comparison.Gram also incurs roughly twice the bandwidth cost of TTM, with mode-dependent differences in the product terms.
  • Mode ordering changes the dominant expense because each iteration reduces the working data size, so permutations can optimize computation and communication.The paper evaluates examples of these rearrangements later in the performance study.
  • The implementation reuses local variables between iterations and avoids maintaining temporaries, bounding maximum per-processor storage.
  • HOOI: HOOI’s outer iterations are dominated by multiple-TTM computations, especially the first TTM in each mode, and their ordering can substantially affect runtime.The implementation does not tune all independent ordering choices.

VII. APPLICATION TO DIRECT NUMERICAL SIMULATION DATA IN COMBUSTION SCIENCE

The combustion datasets contain exploitable low-dimensional multilinear structure, but their compressibility varies substantially across datasets. Tucker compression achieves strong reductions at controlled normalized RMS error, with mode-wise eigenvalue decay determining useful reduced dimensions.

  • The study evaluates DNS tensors ranging from a 70 GB HCCI dataset to 520 GB TJLR and 550 GB SP datasets.TJLR is explicitly described as less amenable to compression because of significant downsampling.
  • Given a target error, reduced dimensions are selected from Gram-matrix eigenvalues, and the resulting T-HOSVD error bounds guide the approximation.The eigenvalues correspond to squared singular values of tensor unfoldings.
  • Mode-wise error-curve drop-off determines compressibility, and intersections with a target threshold provide upper bounds on reduced dimensions.For HCCI-628, the curves are evaluated at each mode and reduced dimension.
  • Compression ratios range from 2–37 for TJLR and 5–5600 for SP as the target normalized RMS error changes from 10^-6 to 10^-2.TJLR is the least compressible dataset, while SP is substantially more compressible.

C. Reconstruction Error

For the tested combustion application, HOOI provides little improvement over the ST-HOSVD initialization, making ST-HOSVD alone a likely sufficient reconstruction procedure.

  • Table II reports compression and maximum normalized RMS errors using a 10^-3 error threshold for determining compression ratios.
  • HOOI iterations make little improvement over ST-HOSVD, so ST-HOSVD without HOOI iterations is likely sufficient for this application area.

VIII. PERFORMANCE RESULTS

Performance depends strongly on processor-grid configuration and mode ordering because these choices change communication, local matrix layouts, and the cost of later iterations. The best choices differ between ST-HOSVD and HOOI, and no universally optimal ordering is established.

  • B. Parameter Choice: Processor Grid Configuration: Processor-grid choices affect performance without changing ST-HOSVD flop counts because they alter local matrix dimensions and layouts for sequential kernels.The grid therefore influences both communication and the efficiency of local linear-algebra operations.
  • B. Parameter Choice: Processor Grid Configuration: The first ST-HOSVD iteration consumes at least half of runtime for most processor grids, with Gram dominating and Eigenvectors computation negligible.The first Gram is at least I1/R1 = 4 times more expensive than the first TTM in computation and communication.
  • B. Parameter Choice: Processor Grid Configuration: Setting P1 = 1 gives the best ST-HOSVD processor grids by minimizing communication in the first iteration.With P1 = 1, the first TTM requires no communication, while processor grids with P1 > 6 exceed five times the optimal runtime.
  • B. Parameter Choice: Processor Grid Configuration: The best ST-HOSVD processor grid is not necessarily optimal for HOOI, whose overall choice depends on the number of iterations.Limited tuning suggests choices that work well for ST-HOSVD are often reasonable for HOOI, but not universally optimal.
  • C. Parameter Choice: Mode Ordering: The optimal mode ordering starts with the dimension having the largest compression ratio, because savings in later operations outweigh the more expensive first Gram computation.In the tested case, starting with the second dimension was optimal despite its higher initial cost.

D. Strong Scaling

Strong and weak scaling experiments show that the distributed Tucker implementation reduces runtime and sustains substantial performance across increasing processor counts and data sizes. Performance eventually degrades as communication, small local matrices, and processor-grid tradeoffs become more significant.

  • D. Strong Scaling: On 512 nodes, ST-HOSVD and one HOOI iteration finish in 0.15 seconds at 6.0 and 3.8 TFLOPS, respectively.The same computation takes about 3 seconds on one node, where the methods achieve 67% and 45% of peak performance.
  • D. Strong Scaling: Runtime continues to decrease through 6144 cores, but communication and small local matrix dimensions degrade performance at high processor counts.These effects become important when each core holds only about 1 MB of local tensor data.
  • E. Weak Scaling: A 15 TB data set is processed in 70 seconds at 1296 nodes, with ST-HOSVD and HOOI reaching 17% and 12% of peak performance, respectively.The corresponding aggregate performance is up to 104 TFLOPS.
  • E. Weak Scaling: Weak-scaling performance decreases from 66% and 43% of peak on one node to 17% and 12% on 1296 nodes for ST-HOSVD and HOOI.The experiment keeps data per processor fixed while increasing processor counts and tensor dimensions.
  • E. Weak Scaling: High-processor-count scaling is limited by the difficulty of optimizing one processor grid across computations in different tensor modes.The processor-grid tradeoff is identified as the main reason for performance degradation at scale.
Loading 1510.06689v2…