Acceleration of Data Analytics on Heterogeneous Supercloud Systems

1 Introduction

• The paper identifies accelerator selection as a design challenge involving physical resource constraints and communication costs.Source: §1 · p. 1
• The paper explores recursive, iterative, and blocked computation models for mapping Dense Cholesky Factorization and SVD to heterogeneous systems.The evaluation uses an ARM 48-core CPU and an Ascend 910 AI hardware accelerator.Source: §1 · p. 2
• Performance-estimation models cover computation and communication, alongside load-balancing, parallelism, and scheduling optimizations.Source: §1 · p. 2
• ReDSEa is extended to use the models and select computational tasks as hardware-acceleration candidates.The earlier tool-chain was applied to the Triangular System Solver; this paper extends it to Dense Cholesky Factorization and SVD, which require new models [1].Source: §1 · p. 2

2 Related Work

• Heterogeneous linear-algebra frameworks described here use iterative and blocking approaches, while ReLAPACK uses recursive algorithms but does not model refinement level and expected performance.LaRIS dynamically selects vendor-library kernels and processor architecture at runtime; ReLAPACK makes its tuning assumption for shared-memory architectures.Source: §2 · p. 2
• Models for Dense Cholesky acceleration in homogeneous systems predict refinement and performance, but omit communication costs and report simulations rather than experiments.A similar approach for the same application is followed in.Source: §2 · p. 2
• Heterogeneous SVD studies divide computation into bidiagonalization and bidiagonal SVD, but the cited work lacks automated hardware- and granularity-based estimation or analysis of divide-and-conquer recursion depth.Prior approaches include GPU offloading and CPU-GPU overlap for bidiagonalization, and accelerator offloading in the bidiagonal SVD stage.Source: §2 · p. 3
• Compiler-based estimation and design-space exploration approaches described here do not cover diverse computation models or a broad variety of hardware.The compiler approaches focus mainly on streaming applications, while the cited design-space methods target mainly FPGA devices.Source: §2 · p. 3

3 Compiler Tool-chain

• ReDSEa uses LLVM infrastructure to automate the mapping workflow for applications targeting heterogeneous systems.The tool-chain is based on LLVM Compiler Infrastructure, version 14.0.0 [1].Source: §3 · p. 3

3.1 Compiler Analysis

• LLVM analysis passes estimate computation latency for data-flow-graph tasks, while communication latency is estimated from task data requirements and target bandwidth.Figure 1 shows recursive Cholesky nodes and their refined components.Source: §3.1 · pp. 3–4, Figure 1 · p. 4

3.2 Cost Models

• The cost model combines CPU computation, hardware computation, communication, and synchronization or invocation latency.For mapped tasks, the model considers CPU latency, accelerator critical path, host-device transfers in both directions, and synchronization or invocation overhead.Source: §3.2 · p. 4

3.3 Design Space Exploration

• Branch-and-bound recursively explores acceleration-candidate subsets and returns the minimum-cumulative-latency set within the user-defined resource budget.Source: §3.3 · p. 4

4.1 Dense Cholesky Factorization

• Cholesky factorization computes a lower-triangular factor of a positive-definite matrix, using blocked submatrices and a triangular solve with multiple right-hand sides.The blocked workflow computes the upper block, solves for the middle block, then forms the lower block from products of the middle and lower factors.Source: §4.1 · p. 5

4.2 Accelerated SVD for Heterogeneous Systems

• SVD represents A as UΣV^H and proceeds through bidiagonalization and an SVD of the bidiagonal matrix.The section identifies U and V as unitary and Σ as a real diagonal matrix with non-negative singular values.Source: §4.2 · pp. 5–6

4.2.1 2-Stage Bidiagonalization.

• The two-stage reduction first forms an upper band matrix, then an upper bidiagonal matrix; the first stage removes trailing-matrix dependencies during panel factorization.QR and LQ panels run on the host CPU while trailing-matrix updates are offloaded; the second stage remains primarily on the CPU because of limited parallelism, bandwidth constraints, and cache-optimization needs.Source: §4.2.1 · p. 6

4.2.2 Divide and Conquer (D&C).

• Divide and Conquer recursively splits the bidiagonal matrix, computes subproblem SVDs, and uses Givens rotations and a secular equation to determine singular values.Some computations are offloaded to accelerators while the computation of M and singular values and vectors remains on the host; classic QR SVD replaces Divide and Conquer at fine recursion granularity.Source: §4.2.2 · pp. 6–7

4.2.3 Back-Transformation of Singular Vectors.

• All singular-vector back-transformation steps are offloaded to accelerators because they primarily involve matrix-matrix multiplications.More work in full-to-band reduction increases the first back-transformation stage's computation through additional Householder reflectors.Source: §4.2.3 · p. 7

5.1 Recursive

• Recursive Cholesky keeps CH and triangular-system tasks on the host while offloading GEMM tasks to accelerators.Further refinement exposes more GEMM work, and another stage is applied only when it is projected to benefit performance.Source: §5.1 · pp. 7–8
• In recursive SVD, GEMM tasks for computing B’s singular vectors are accelerated, while the host computes the middle matrix M’s singular values and vectors.Source: §5.1.2 · p. 8

5.2 Iterative

• The iterative model is an alternative after host-side computation granularity is set; for Cholesky it reduces host TS work and exposes more GEMM computation for acceleration.It is described as offering better accelerator utilization with performance equal to or slightly better than the recursive approach, while requiring less engineering effort.Source: §5.2 · p. 9
• For iterative Cholesky at refinement level 4, computation proceeds in four rounds with three GEMM acceleration tasks of varying sizes.The number of rounds equals the refinement level.Source: §5.2 · p. 9, Figure 5 · p. 9
• In iterative bidiagonalization, refinement progressively decomposes tasks; the approach aims to place most bidiagonalization work in the first, full-to-band stage.The second, band-to-bidiagonal stage mainly runs on the host and is less amenable to acceleration.Source: §5.2 · p. 10

5.3 Blocked

• The blocked model targets better load balancing, accelerator use, scheduling, and potential task overlap than recursive or iterative models.Its workflow exposes parallel and overlapping computation of independent tasks.Source: §5.3 · p. 11, §5.3.1 · p. 11

5.3.1 Dense Cholesky Factorization.

• Blocked Cholesky organizes computation into rounds, enabling better load balancing and parallel or overlapping execution of independent tasks.The illustrated refinement-4 example uses two blocks per round and six rounds overall.Source: §5.3.1 · p. 11

5.3.2 Bidiagonalization.

• The blocked model supports simultaneous GEMM tasks on multiple accelerators; SVD’s parallel implementation requires at least three accelerators to match the theoretical critical path.For Cholesky, overlapping is considered when dependencies permit and accelerator capacity and latency criteria are met.Source: §5.3.4 · pp. 12–13

Hardware

• Experiments paired a 48-core Huawei Kunpeng 920 ARM CPU with a Huawei Ascend 910 AI processor containing 32 Da Vinci AI cores.The accelerator’s stated peak performance is 320 TFLOPS.Source: §6 · p. 13

Configuration

• The CPU and accelerator communicated over PCIe, and the experimental input was a square matrix of size 32000.The passage reports 32000² entries.Source: §6 · p. 13

Baseline

• Comparisons used fully optimized multithreaded LAPACK implementations for Dense Cholesky Factorization and SVD on the CPU.Source: §6 · p. 13

7.1 Dense Cholesky Factorization – Model Comparison

• 17x speedup over the optimized 48-core CPU-only baseline is achieved by the blocked-optimized Cholesky strategy.Its latency is 3.8 seconds at refinement 16, versus 65 seconds for the CPU-only baseline at refinement 1.Source: Figure 10 · p. 14, §7.1 · p. 14

7.2 SVD

• Refinement levels 128 and 256 are optimal for combined bidiagonalization stages, as further refinement increases accelerator latency and communication costs.The figure caption identifies refinement 128 as minimizing total latency in its first-versus-second-stage trade-off.Source: §7.2 · p. 14, Figure 11 · p. 15
• 126x speedup is reached by the parallel blocked model for SVD bidiagonalization at refinement levels 128 and 256.Beyond these levels, performance declines as accelerator latency and communication costs rise.Source: §7.2 · pp. 14–15, Figure 12 · p. 15
• Larger SVD input matrices yield greater absolute speedup gains, but peak speedup occurs at the same refinement levels across sizes.The comparison covers matrices with 8,000, 16,000, and 32,000 rows.Source: Figure 12 · p. 15, §7.2 · p. 15
• 5.2x speedup is the Divide-and-Conquer peak at refinement 32, after which CPU computation for SVD plateaus.The phase’s accelerator and communication latencies do not significantly affect overall performance as refinement increases.Source: §7.2 · p. 15, Figure 13 · p. 16
• 88x speedup for end-to-end SVD is achieved by the blocked-optimized model at refinement levels 128 and 256, compared with a fully optimized CPU-only setup.The iterative and blocked models peak at 85x at refinement 128.Source: Figure 14 · p. 16, §7.2 · p. 16
• Back-transformation accelerator latency spikes exponentially at refinement levels between 128 and 1024 as increasingly larger gemm tasks are offloaded.The full-to-band reduction’s computational demand also directly influences the load of the first back-transformation and overall SVD performance.Source: §7.2 · p. 16

• The tool-chain maps Dense Cholesky Factorization and SVD onto a 48-core ARM CPU and Ascend AI accelerator, achieving up to 17x and 88x speedup, respectively, over fully optimized ARM CPU baselines.The performance models are based on recursive, iterative, and blocked computation models.Source: §8 · p. 17