PaperlayerView exact revision on arXiv

Source-linked AI summary

Helix: A Unified Programmable Accelerator for Diverse Krylov Subspace Solvers

Wei Chen, Yizhi Yuan, Linghao Song

arXiv:2610.21096v1cs.ARcs.DC

TL;DR

Krylov accelerators often specialize in one solver or require solver-specific hardware configurations, despite practical use of different solvers for different matrix structures. Helix combines programmable primitive kernels, datapaths, and a domain compiler to support diverse solvers on a unified FPGA architecture. Across eight solvers, it sustains 47.5 −96.9% of RTX PRO 6000 throughput while improving energy efficiency and throughput per unit peak memory bandwidth.

  • Problem

    Existing FPGA Krylov accelerators support a single solver or use solver-specific hardware configurations, although different matrix structures call for different solvers.

    Source: §I · p. 1

  • Method

    Helix builds programmable kernels around common Krylov primitives, coordinates them with programmable datapaths, and compiles solver descriptions into optimized mappings for a unified architecture.

    Source: §I · p. 2

  • Results

    Across eight solvers, Helix sustains 47.5 −96.9% of RTX PRO 6000 throughput, with 2.29−4.66× higher energy efficiency and 1.89 −3.85× higher throughput per unit peak memory bandwidth.

    Source: §I · p. 2

  • Takeaways & Limitations

    Helix demonstrates that FPGA specialization can support an algorithm family while retaining high performance and programmability, with programmable control adding only 0.25%-0.57% runtime overhead.

    Source: §VIII · pp. 12–13

Abstract

from arXiv · show

Domain-specific accelerators deliver high performance and energy efficiency through specialization but often lack support for extensible algorithm families. Existing FPGA accelerators for Krylov subspace methods, which iteratively solve sparse linear systems, typically support a single solver or require separate hardware configurations. Helix follows a systematic algorithm-family design methodology that first abstracts common computational primitives from diverse Krylov solvers and builds the architecture around efficient, programmable primitive kernels. Helix then introduces programmable datapaths to coordinate these primitives. Its architecture decouples hardware implementation from solver-specific execution, enabling HBM reuse and zero solver-switching latency. Finally, Helix provides a DSL compiler that efficiently maps different solvers onto the architecture while optimizing vector-operation performance for each solver. We prototype Helix on a Xilinx Alveo U55C FPGA and evaluate Helix's practicality and performance by using it to compile and execute eight solvers. Helix achieves up to 7.91x and 1.16x speedups over Xilinx XcgSolver and the state-of-the-art FPGA accelerator Callipepla, respectively, both of which support only JPCG. Across the eight solvers, Helix sustains 47.5% - 96.9% of the throughput of an NVIDIA RTX PRO 6000 GPU while delivering 2.29x - 4.66x higher energy efficiency and 1.89x - 3.85x higher throughput per unit peak memory bandwidth. The programmable components incur 0.25% - 0.57% execution-time overhead and 4.7% LUT and 4.0% FF overhead, demonstrating negligible overhead for programmability.

I. INTRODUCTION

Helix addresses the mismatch between evolving algorithm families and hardware that is costly to adapt by designing a programmable accelerator for diverse Krylov solvers. Its primitive-based architecture and compiler support solver reuse while preserving performance.

I. INTRODUCTION

  • The broader challenge is that hardware evolves more slowly than software algorithm ecosystems, making support for new algorithms costly to add and deploy.This motivates accelerator designs that support algorithm families rather than isolated algorithms.Source: §I · p. 1
  • Existing FPGA Krylov accelerators specialize in one solver or switch solver-specific hardware configurations, coupling architecture to solver implementations and underusing HBM channels when operands are inactive.Adding a solver can require hardware redesign or a different configuration.Source: §I · p. 1
  • Helix abstracts common Krylov primitives into programmable kernels, coordinates them with programmable datapaths, and uses a custom compiler to map solvers according to data dependencies.The compiler searches for an optimized schedule, while an analytical performance model and compiler estimate performance across architecture configurations.Source: §I · pp. 1–2
  • Helix enables HBM reuse across vectors from different stages and zero solver-switching latency through its unified programmable architecture.The design balances stage-based operation fusion with data parallelism to improve memory-bandwidth utilization.Source: §I · p. 2
  • On eight solvers, Helix achieves up to 7.91× and 1.16× speedups over Xilinx XcgSolver and Callipepla, respectively, which support JPCG only.It sustains 47.5 −96.9% of RTX PRO 6000 throughput, with 2.29−4.66× higher energy efficiency and 1.89 −3.85× higher throughput per unit peak memory bandwidth.Source: §I · p. 2

II. BACKGROUND

Krylov solvers use different recurrence relations but share computational building blocks. The section illustrates these common primitives across representative solvers and shows MINRES iteration operations.

A. Krylov subspace methods

  • Krylov methods iteratively solve large sparse linear systems; despite different recurrence relations, they construct solutions using SpMV and vector updates.The methods cover symmetric positive-definite, symmetric-indefinite, and nonsymmetric systems.Source: A. Krylov subspace methods · p. 2
  • CG, MINRES, and BiCGSTAB share SpMV, vector operations, reductions, and scalar control despite their different recurrence relations.Helix uses a Jacobi preconditioner implemented as element-wise vector multiplication because the diagonal inverse can be precomputed.Source: A. Krylov subspace methods · p. 2, Figure 1 · p. 2

MINRES

  • The MINRES iteration includes vector updates, norm calculations, rotations, and updates to the solution and residual-related vectors.The figure uses colors to distinguish common computational primitives across CG, BiCGSTAB, and MINRES.Source: MINRES · p. 2, Figure 1 · p. 2

B. Related Work

Prior Krylov accelerators often tie FPGA hardware to a fixed solver flow, while Helix combines reusable programmable primitives with HBM mapping and data movement designed for diverse solvers.

B. Related Work

  • XcgSolver and Callipepla statically assign HBM channels to operands for CG, while Helix maps logical operands across shared physical channels to improve bandwidth utilization.This mapping jointly optimizes operation fusion and data parallelism.Source: B. Related Work · pp. 2–3
  • Acamar switches pre-generated solver bitstreams in microseconds and uses static HLS kernels for dense vector operations, whereas Helix uses instruction-level programmability with zero switching latency.Acamar primarily targets SpMV parallelism; Helix optimizes execution of the entire solver.Source: B. Related Work · p. 3

III. HELIX HARDWARE ARCHITECTURE

  • Helix builds its architecture around programmable kernels for vector operations, SpMV, scalar operations, and control, coordinated by programmable datapaths.The instruction-driven computation units begin executing when their corresponding data arrives.Source: §III · p. 3

A. Architecture Components

  • Each FP64 VPRU performs element-wise or reduction operations and routes intermediate vectors; horizontal replication supports stage-level fusion, while vertical replication supports data parallelism.A VPRU processes eight FP64 vector elements per cycle to match the 512-bit HBM interface.Source: A. Architecture Components · p. 3
  • Helix’s window-based SpMV streams scheduled nonzeros from HBM while keeping irregular vector reads and partial-sum accumulation on chip.Multiple SpMV units process different matrix rows in parallel and reuse input-vector elements through chain-based broadcast.Source: A. Architecture Components · pp. 3, 5
  • The Scalar PU tracks operand validity to issue scalar operations when inputs are ready, while the hierarchical controller separates computation and memory-access instruction decoding.The controller’s independent second-level decoders shorten the control critical path compared with a centralized decoder.Source: A. Architecture Components · p. 5
  • Vector LSUs support unidirectional vectors for reading or writing and bidirectional vectors for write-after-read or self-updating within a stage.A bidirectional architectural vector uses twice as many HBM channels as a unidirectional one.Source: A. Architecture Components · p. 5
  • For window-based SpMV, the Matrix Load Unit reads preprocessed per-window, per-PE streams from HBM, with window pointers embedded in each stream’s head packet.Scheduled streams interleave independent updates to meet read-after-write dependency distances, inserting no-ops when needed.Source: A. Architecture Components · p. 5

B. Coordination of Primitives

Helix routes data between vector and SpMV units and synchronizes branches and vector writes through programmable instructions.

B. Coordination of Primitives

  • VPRU datapaths forward vectors to SpMV units and route multiple streams among downstream VPRUs, allowing intermediate vector data reuse.VECALU_CTRL.spmv_WrVec handles forwarding between VPRUs and SpMV units; Bypass Vecs Mask forwards streams to downstream VPRUs.Source: B. Coordination of Primitives · p. 5
  • FP64 conditional branches stall the instruction-fetch controller until the Scalar PU returns a comparison, while write-response instructions synchronize vector writes across LSUs.The compiler places write-response collection and read instructions so other stage instructions do not stall unnecessarily.Source: B. Coordination of Primitives · p. 5

IV. HELIX’S COMPILATION PIPELINE

Helix’s custom compiler turns C-style DSL solver descriptions into executable instructions while optimizing execution-stage schedules and vector allocation. Its three-phase pipeline supports reusable solver programming without sacrificing performance.

IV. HELIX’S COMPILATION PIPELINE

  • Helix’s Python compiler maps C-style DSL descriptions to execution binaries and optimizes stage schedules for high performance.It does so without relying on MLIR/LLVM infrastructure or existing transformation passes.Source: §IV · pp. 5–6
  • Three compilation phases parse and validate operations, schedule them into StageIR, then allocate registers, encode instructions, and emit a binary.The scheduling phase also allocates architecture vectors and inserts stage barriers; infeasible allocations trigger further stage splitting.Source: §IV · pp. 5–6, Figure 3 · p. 6
  • Helix’s C-syntax DSL exposes primitive interfaces for SpMV and vector operations, letting users express solver operations without architecture or compiler expertise.Its interfaces resemble numerical-library calls.Source: §IV · p. 6, Figure 3 · p. 6
  • Stage scheduling groups operations into execution stages, exposing opportunities for operation fusion and intermediate-vector reuse.Stages are separated at natural boundaries such as reductions.Source: §IV · p. 6, Figure 3 · p. 6
  • Graph coloring assigns logical vectors consistently to heterogeneous architectural vectors; when allocation fails, legal stage splits preserve dependencies until allocation succeeds.Shortest-path search finds a feasible schedule with the minimum number of execution stages because each split adds one stage.Source: §IV · p. 6

V. ARCHITECTURE OPTIMIZATIONS

Helix reuses HBM channels across stages while balancing data reuse against data parallelism. A performance model estimates solver-specific configurations because stage activity and dependencies vary.

V. ARCHITECTURE OPTIMIZATIONS

  • Helix reuses HBM channels across stages and balances data reuse with data parallelism to improve memory-bandwidth utilization.A fixed channel allocation sized for a stage with 15 vectors can leave channels idle in a stage with 4, while sizing for 4 sacrifices fusion and reuse opportunities.Source: A. Stage-Level Operation Fusion and… · p. 7
  • The best balance of data parallelism and HBM set size varies with solver data dependencies, so Helix uses a performance model to estimate configurations.The model uses compiler-derived stage counts to evaluate combinations of parallelism and HBM set size.Source: A. Stage-Level Operation Fusion and… · p. 7
  • Three sets of five HBM channels illustrate one possible balance between data reuse and parallelism.The example is contrasted with allocating either 15 channels to match the most active stage or 4 to match the less active stage.Source: A. Stage-Level Operation Fusion and… · p. 7

B. Performance Model

Helix models solver latency across vector and SpMV operations to select architectural configurations. A fast implementation checker complements the model by evaluating FPGA resource feasibility before lengthy implementation runs.

B. Performance Model

  • The performance model estimates solver performance across data-parallelism and HBM-set configurations, representing HBM-set sizes through unidirectional and bidirectional vector counts.Bidirectional vectors use twice the channels of unidirectional vectors to support simultaneous reads and writes.Source: B. Performance Model · p. 7
  • Iteration latency combines vector-only stages with SpMV operations, accounting for tiled matrix and vector processing while omitting negligible scalar and control latency.The model derives vector-stage counts from the compiler schedule and separates SpMV input/output stages from vector-only stages.Source: B. Performance Model · p. 7

Design Space Exploration with Fast Implementation Check

  • A fast implementation checker estimates module and interconnect resource use across configurations, enabling feasibility checks in tens of minutes rather than Vivado runs lasting tens of hours.It generates resource utilization from configurations in Python within a second and passes it to AutoBridge’s pre-floorplan scheduler.Source: Design Space Exploration with Fast… · p. 7
  • The selected architecture is evaluated for JPCG, MINRES, and BiCGSTAB, with the explored architectural configuration summarized in Table II.The evaluated FPGA platforms’ frequency, memory capacity, peak bandwidth, and runtime power are summarized in Table III.Source: Design Space Exploration with Fast… · p. 7, Table II · p. 7, Table III · p. 7

VI. EVALUATION

Helix is evaluated on a Xilinx Alveo U55C against FPGA and GPU baselines across eight Krylov solvers and 29 sparse SPD matrices. The evaluation includes solver switching without bitstream-change latency.

A. Evaluation Methodology

  • Eight representative solvers spanning six recurrence families test shared-architecture programmability across diverse Krylov algorithms.The solvers cover SPD, symmetric-indefinite, and nonsymmetric systems and use different combinations of vector, SpMV, and scalar operations.Source: A. Evaluation Methodology · p. 8, Table IV · p. 8
  • Evaluation uses 29 sparse SPD matrices from SuiteSparse, with dimensions from 2.9K to 1M and 99K to 40M nonzeros.The matrices span six application areas, including structural mechanics, electromagnetics, and fluid flow.Source: A. Evaluation Methodology · p. 8
  • Solver runs stop at residual norm below 10^-12 or 20K iterations; total solution time is compared when both systems converge, otherwise kernel time per iteration is used.The stated comparison criterion is based on whether both Helix and the baseline converge within the iteration limit.Source: A. Evaluation Methodology · p. 8
  • Helix’s speedup over XcgSolver reaches 7.91× maximum and 2.62× geometric mean; XcgSolver cannot complete five workloads because of insufficient memory capacity.The comparison uses the U55C FPGA, where both FPGA baselines are implemented.Source: A. Evaluation Methodology · p. 7, Figure 4 · p. 8
  • Users can switch solvers without switching latency when a selected solver fails to converge, without changing the bitstream.The FPGA comparison includes XcgSolver and Callipepla, while an NVIDIA RTX PRO 6000 GPU is compared across all eight solvers.Source: A. Evaluation Methodology · pp. 7–8

B. Performance Evaluation

Helix is compared with FPGA systems that support only JPCG and with a GPU across workloads and eight Krylov solvers. Its results vary with workload size, vector-operation share, and the opportunities for operation fusion.

B. Performance Evaluation

  • 7.91× maximum speedup over XcgSolver and 1.16× maximum overall solver speedup over Callipepla; Helix also performs better on 22 of 29 workloads against Callipepla.XcgSolver could not complete five workloads because of insufficient memory capacity.Source: B. Performance Evaluation · p. 8, Figure 5
  • 1.52× is Helix’s maximum VecOps speedup over Callipepla, approaching a 1.50× theoretical bound as matrix size increases.Helix schedules JPCG’s vector operations in four stages using two parallel VPRU sets; Callipepla uses three stages.Source: B. Performance Evaluation · pp. 8–9, Figure 5
  • Helix achieves 8.6% speedup on bodyy4, where VecOps account for 83.4% of execution time, versus 1.2% on nd6k, where VecOps account for 11.1%.Source: B. Performance Evaluation · p. 9
  • 5.69× is Helix’s maximum speedup over the GPU on small workloads; its speedup decreases as workloads grow and become more memory-bound.Helix’s VecOps speedup contributes substantially to overall improvement, which the authors attribute to its optimized stage schedule.Source: B. Performance Evaluation · p. 9
  • Across eight solvers, Helix’s geometric-mean speedups over the GPU range from 0.475× to 0.969×.Fig. 6(d) summarizes the overall speedup distributions.Source: B. Performance Evaluation · p. 9, Figure 6 · p. 10
  • 3.17× is SYMMLQS’s stage reduction ratio, versus 1.30× for PIDR2, whose complex dependency graph limits fusion and yields the lowest solver speedup.The ratios compare GPU vector-operation counts with Helix VecOps stages.Source: B. Performance Evaluation · p. 9, Figure 6 · p. 10

C. Throughput, Energy and Memory-Bandwidth Efficiency

Helix’s throughput, energy efficiency, and bandwidth-normalized throughput are compared with FPGA baselines and a GPU. The section also evaluates compiler stage splitting, including its effect on two solvers.

C. Throughput, Energy and Memory-Bandwidth Efficiency

  • 2.62× higher geometric-mean throughput, 2.06× higher geometric-mean energy efficiency, and 2.06× higher geometric-mean bandwidth-normalized throughput are reported over XcgSolver.Against Callipepla, Helix improves throughput by 4% but reduces energy efficiency by 4% and bandwidth-normalized throughput by 3%; Helix-10CH exceeds Callipepla in throughput and energy efficiency with the same HBM channels.Source: C. Throughput, Energy and… · pp. 10–11
  • 47.5%–96.9% of GPU throughput, 2.29×–4.66× higher energy efficiency, and 1.89×–3.85× higher throughput normalized by peak memory bandwidth are reported across evaluated solvers.Helix has about one-quarter of the GPU’s peak memory bandwidth; the authors attribute its higher bandwidth efficiency to stage-based operation fusion and customized dataflow execution.Source: C. Throughput, Energy and… · p. 11

D. Evaluation of stage-splitting strategy

  • 33.33% and 18.18% fewer stages yield 1.233× and 1.129× speedups for SYMMLQS and PCR, respectively, with search-based splitting.The search-based strategy considers future conflicts as well as the current one; gains are minimal in other solvers.Source: D. Evaluation of stage-splitting… · p. 11, Table VI · p. 11

E. Latency and Hardware Overhead of Instruction Control

Helix’s programmable controller adds little runtime and hardware overhead, while solver switching requires changing instructions rather than reconfiguring solver-specific hardware. The implementation uses distributed FPGA resources and meets timing constraints.

E. Latency and Hardware Overhead of Instruction Control

F. Solver-switching Latency

  • Zero measured latency is reported for both solver-switching approaches: jumping to another instruction-ROM address or launching pipelined solver kernels.In the latter approach, instruction transfer overlaps transfer of the current solver’s results.Source: F. Solver-switching Latency · p. 11
  • The largest instruction transfer, PIDR2’s 7.23KB, is estimated at 0.458µs and is fully hidden by result transfer.The passage gives 15.8 GB/s per direction for the U55C PCIe link and a 23.2KB final solution for the smallest workload.Source: F. Solver-switching Latency · p. 11

G. Resource Utilization and Physical Layout

H. Convergence Behavior

Helix, Callipepla, and XcgSolver show consistent convergence behavior with one another, while comparisons with the GPU reveal some matrix-specific differences. The discussion compares Helix with CGRA and TPU approaches, and the conclusion presents Helix as a programmable accelerator for diverse Krylov solvers.

H. Convergence Behavior

  • Helix, Callipepla, and XcgSolver converge or fail to converge on the same workloads, while Helix and the GPU differ on some matrices.Different accumulation orders may propagate rounding differences across iterations; FP32 matrix values may also contribute to the GPU differences.Source: H. Convergence Behavior · p. 12, Table VIII · p. 12

VII. DISCUSSION

  • 1.36×–15.36× per-iteration speedups over TPU v6e-1 are reported for JPCG, with a 3.15× geometric mean.The comparison uses FP32 for TPU SpMV and VecOps and TPU-provided templates; the authors believe Plasticine could be comparable with the same HBM configuration, though datapath hops may make it slightly slower.Source: §VII · p. 12

VIII. CONCLUSION

  • Helix combines a unified programmable FPGA architecture with a Krylov solver compiler and sustains 47.5%–96.9% of GPU throughput, with higher energy and bandwidth-normalized efficiency.The programmable controller adds 0.25%–0.57% runtime overhead; the authors frame the work as extending hardware specialization to algorithm families.Source: §VIII · pp. 12–13
Loading 2610.21096v1…