Cello: Co-Designing Schedule and Hybrid Implicit/Explicit Buffer for Complex Tensor Reuse

Raveesh Garg, Michael Pellauer, Sivasankaran Rajamanickam, Tushar Krishna

TL;DR

This paper introduces CELLO, a novel hardware-software co-design for accelerating complex tensor operations found in scientific computing. By introducing a hybrid buffer mechanism (CHORD) and a scheduler (SCORE), CELLO effectively exploits inter-operation reuse in complex dependency graphs, achieving significant speedups and energy efficiency improvements over existing accelerators.

What Problem Does This Paper Address?

Modern high-performance computing (HPC) workloads, particularly in scientific applications like Conjugate Gradient (CG), involve complex chains of tensor operations forming intricate Directed Acyclic Graphs (DAGs). Accelerating these workloads is challenging because:

  1. Skewed Tensor Shapes: Many tensor operations in HPC have highly skewed aspect ratios (e.g., very large in one dimension, small in others). This limits the effectiveness of traditional intra-operation reuse techniques, leading to memory-bound performance and underutilized compute units.
  2. Complex Dependencies: The DAGs of tensor operations in HPC are more complex than those in typical Deep Neural Networks (DNNs). These complexities include delayed downstream dependencies, multiple consumers for the same intermediate tensor, and varying reuse distances.
  3. Ineffective Existing Solutions:
    • Intra-operation optimization: While effective for DNNs with regular tensor shapes, it falls short for skewed HPC tensors.
  4. Inter-operation pipelining: Standard pipelining techniques struggle with complex DAGs, especially when intermediate results are needed much later in the computation (delayed dependencies) or by multiple downstream operations.
  5. Explicit scratchpads: Require complex manual scheduling and buffer allocation, which becomes intractable for large, dynamic DAGs.
  6. Caches: Are too myopic (line-level) and lack the tensor-level awareness needed for efficient reuse in these scenarios.

This gap means that current accelerators often fail to achieve high arithmetic intensity and performance for critical HPC workloads.

Methods

CELLO addresses these challenges through a co-designed hardware-software approach:

  1. SCORE Scheduler: This software component analyzes the tensor operation DAG. It identifies different types of dependencies (Sequential, Pipelineable, Delayed_Writeback, Delayed_Hold, Parallel_Multicast) and determines how to best exploit reuse. Crucially, it can identify delayed downstream dependencies that traditional pipelining misses.
  2. CHORD Buffer: This is a novel hybrid implicit/explicit on-chip buffer mechanism.
  3. Hybrid Nature: It leverages high-level information from SCORE (like tensor start/end addresses and reuse distance/frequency) but manages data placement and replacement using hardware-managed policies. This offloads complexity from the compiler.
  4. Object-Level Granularity: Unlike caches (line-level), CHORD operates at the tensor (object) level, significantly reducing metadata overhead and enabling more intelligent replacement decisions.
  5. Replacement Policies: * PRELUDE: For pipelineable and delayed_hold dependencies, it fills the buffer sequentially and only writes to DRAM if the entire tensor doesn't fit. This prioritizes keeping recently used data.
  6. RIFF: For delayed_writeback dependencies, it considers both reuse distance and frequency to make replacement decisions. It can evict less frequently or less recently used tensor portions to make space for more critical ones, prioritizing reuse.
  7. Co-design: SCORE provides CHORD with coarse-grained metadata, and CHORD's policies make fine-grained, cycle-level decisions. This synergy allows CELLO to manage complex dependencies without exploding the scheduling search space.

Datasets

The paper evaluates CELLO on:

  • Conjugate Gradient (CG) algorithm: Used across various problem sizes and sparsity levels, including 2D/3D problems, computational fluid dynamics, and circuit simulations. Sparse matrices were obtained from the University of Florida Sparse Matrix Collection.
  • BiCGStab algorithm: Another PDE solver.
  • Graph Neural Networks (GNNs): Evaluated on datasets like Cora and Protein.
  • ResNet: A deep learning model, used to study performance with complex DAGs and varying memory bandwidths.

The paper does not introduce new benchmark datasets but uses established HPC and ML workloads to demonstrate CELLO's effectiveness.

Key Insights and Ideas

  • Inter-operation reuse is paramount for HPC: For skewed tensors, exploiting reuse between operations is far more critical than maximizing reuse within a single operation.
  • Delayed dependencies are a major bottleneck: Traditional pipelining fails when intermediate results are needed much later. CELLO's SCORE scheduler and CHORD buffer are designed to handle these delayed writeback and hold scenarios.
  • Hybrid implicit/explicit buffering is key: Offloading complex buffer management to hardware policies (like CHORD's PRELUDE/RIFF) while providing high-level guidance from software (SCORE) dramatically simplifies the problem and improves efficiency.
  • Tensor-level granularity is superior to line-level: Operating on entire tensors for replacement decisions in CHORD is more effective and less overhead-intensive than cache line-level management for these workloads.
  • Frequency and distance matter for replacement: The RIFF policy's consideration of both how often and how soon a tensor is reused is a novel approach to buffer replacement for complex DAGs.

Key Results

  • Performance: CELLO achieves a 4x geomean speedup across various HPC workloads compared to state-of-the-art accelerators.
  • Energy Efficiency: CELLO provides a 4x geomean improvement in energy efficiency. Off-chip energy is reduced by 64% to 83% compared to the best intra-layer baseline.
  • DRAM Access Reduction: CELLO achieves 64% to 83% reduction in DRAM accesses.
  • Area and Energy: CHORD's buffer mechanism has a comparable area to traditional caches but significantly lower energy per access due to avoiding tag comparisons and using a much smaller index table.
  • Scheduling Complexity Reduction: CELLO reduces the buffer allocation search space from over $10^{80}$ to around $10^2$ for complex DAGs, making it practical for every problem instance.

Limitations and Future Work

  • Limitations:
    • The paper focuses on specific HPC workloads (CG, BiCGStab) and GNNs. While demonstrating broad applicability, further evaluation on a wider range of complex DAG applications might be beneficial.
  • The effectiveness of PRELUDE is noted to be sensitive to tensor size relative to on-chip SRAM.
  • Future Work:
    • The authors suggest that ideally, tensor algebra applications would be composed of independently optimized kernels. CELLO's approach of analyzing the entire DAG and composing optimizations is a step towards this.
  • Further exploration of CHORD's policies and their interaction with different memory bandwidths and SRAM sizes is implied by the sensitivity studies.
  • The paper highlights the need for better scheduling and buffer management for complex dependencies, suggesting that CELLO's approach could be extended to other domains facing similar challenges.

Summary updated

Abstract

HPC applications are critical in various scientific domains ranging from molecular dynamics to chemistry to fluid dynamics. Conjugate Gradient (CG) is a popular application kernel used in iterative linear HPC solvers and has applications in numerous scientific domains. However, the HPCG benchmark shows that the peformance achieved by Top500 HPC systems on CG is a small fraction of the performance achieved on Linpack. While CG applications have significant portions of computations that are dense and sparse matrix multiplications, skewed SpMMs/GEMMs in the HPC solvers have poor arithmetic intensities which makes their execution highly memory bound unlike GEMMs in DNNs which have high arithmetic intensity. The problem of low intensity individual skewed GEMMs also exists in various emerging workloads from other domains like Graph Neural Networks, Transformers etc. In this work we identify various reuse opportunities between the tensors in these solver applications to extract reuse in the entire Directed Acyclic Graph of the tensor operations rather than individual tensor operations. These opportunities essentially depend on the dimensions of the tensors and the structure of the tensor dependency graph. We propose a systematic methodology to determine various kinds of reuse opportunities in the graph of operations and determine the loop order and tiling in the interdependent operations. As a result, we propose a novel mapping strategy GOGETA that improves reuse of HPC applications on spatial accelerators. We also propose a data organization strategy in the buffer. Our mapping achieves geomean 6.7x reduction in memory accesses.
BibTeX
@inproceedings{garg2025cello,
  author = {Raveesh Garg and Michael Pellauer and Sivasankaran Rajamanickam and Tushar Krishna},
  title = {{Cello: Co-Designing Schedule and Hybrid Implicit/Explicit Buffer for Complex Tensor Reuse}},
  booktitle = {IPDPS},
  year = {2025},
  doi = {10.1109/ipdps64566.2025.00046},
}
Figure