A Probabilistic Perspective on Tiling Sparse Tensor Algebra

---

Review Form:

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The paper presents D2T2, a framework for optimizing static tiling schemes for sparse tensor algebra. The core idea is to move beyond conservative, worst-case tiling by building a probabilistic model based on high-level statistics extracted from the input tensors. This model is used to predict memory traffic for various tile shapes and sizes, enabling a search for a traffic-optimal configuration that does not require specialized hardware. The authors evaluate D2T2 against state-of-the-art methods like Tailors and DRT, claiming significant performance improvements.

However, the work rests on a series of questionable assumptions regarding the statistical independence of tensor structures, and its experimental validation against prior art is methodologically compromised. While the goal is commendable, the rigor of the modeling and evaluation is insufficient to substantiate the paper's primary claims.

Strengths

1. Hardware-Agnostic Approach: The primary conceptual strength is the aim to improve static tiling without mandating specialized hardware support (unlike DRT's dynamic aggregation or Tailors' overflow buffers). This makes the proposed technique potentially more generalizable.
2. Data-Driven Philosophy: The fundamental motivation to use the statistical properties of the input data to inform tiling is sound. Moving away from worst-case (dense) assumptions is a necessary step for efficient sparse computation.
3. Identification of a Correlation Proxy: The introduction of the Corrs statistic (Section 4.4, page 6) to model output reuse is a necessary attempt to patch the model's core assumption of independence. Figure 8 demonstrates a clear, if simplistic, relationship between this metric and optimal tile shape.

Weaknesses

1. Fundamentally Flawed Modeling Assumption: The entire probabilistic model is built on a demonstrably false premise. In Section 4.2 (page 5), the authors state: "We estimate this probability... by assuming that the nonzero structures of A and C are uncorrelated." This assumption of independence is incorrect for a vast majority of real-world sparse computations. For example, in graph analytics (A x A^T), the structures of the input and output are highly correlated. Banded matrices, diagonally-dominant systems, and tensors from physical simulations all exhibit strong structural correlations. The Corrs proxy introduced in Section 4.4 is a limited, pairwise correction that is insufficient to capture the full, complex nature of these dependencies. The authors' own validation in Section 5.3 (page 8) and Figure 5 reveals this weakness, where they admit that for the A x A^T kernel, "the tiles may be correlated, leading to under-estimation of valid intersections." A model that is systematically biased for such a common kernel is not robust.

2. Methodologically Unsound Comparison with DRT: The comparison against DRT in Section 6.2 (page 10) is invalid. The authors use two different backends for the evaluation: DRT's performance is measured using its dedicated simulator, while D2T2's is measured using a TACO-based backend. The justification provided is that "the DRT simulator was unable to map D2T2-generated configurations to micro-tiles for most matrices." This is not a justification; it is a critical confounding variable. The claim that the backends produce comparable results (within <5%) is only validated for the Conservative tiling scheme. This says nothing about their relative performance on the highly non-uniform, rectangular tiles that D2T2 generates. In fact, the DRT simulator's failure to map these tiles suggests a fundamental incompatibility in the execution models, making any direct comparison of traffic numbers meaningless. The reported 1.13x traffic reduction over DRT is therefore an unsubstantiated claim.

3. Insufficient Validation on Higher-Order Kernels: The evaluation of TTM and MTTKRP in Section 6.3 (page 10) is weak. While the paper uses real-world tensors (from Frostt, Facebook), the other operands are random matrices with uniform sparsity. The text states, "we use a random matrix with dimensions T3 × max (T1, T2)". Real-world tensor operations often involve operands that share structural properties. Using random matrices fails to test the model against the structured correlations that are common in these applications and which the model is likely to mis-predict.

4. Misleading Overhead Analysis: The overhead analysis in Section 6.5 (page 11) reports the overhead of statistics collection (9.3%) and optimization (7.9%) relative to the initial tiling time. Tiling is typically a very small fraction of the total end-to-end execution time. Framing the overhead in this manner minimizes its perceived cost. A more transparent analysis would present this overhead as a percentage of the total application runtime for a set of representative problems.

Questions to Address In Rebuttal

1. Please provide a rigorous justification for the uncorrelation assumption that underpins your traffic model (Section 4.2). Given that many important sparse kernels (e.g., A x A^T) explicitly violate this assumption, how can the model be considered general? How does the simple pairwise Corrs statistic (Section 4.4) account for non-local or higher-order correlations present in real-world data?

2. How can the performance claims against DRT (Section 6.2) be considered valid when entirely different execution backends were used? Please provide evidence that the performance characteristics of the TACO and DRT backends are identical for the non-uniform, rectangular tiles generated by D2T2, not just for simple square tiles. Absent this evidence, the comparison must be removed.

3. In Figure 5, the model systematically underestimates traffic for A x A^T. Can the authors provide a more rigorous analysis of this model error and explain why relative accuracy is sufficient for optimization when the absolute error is significant and biased?

4. Why were random matrices used for the evaluation of TTM and MTTKRP in Table 4, rather than leveraging multiple real-world tensors which possess complex, correlated structures that would more rigorously test the model's assumptions?

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

The authors present D2T2 (Data-Driven Tensor Tiling), a framework for generating data-aware, static tiling schemes for sparse tensor algebra computations. The core contribution is a probabilistic modeling approach that uses high-level statistics, extracted efficiently from the input tensors' compressed formats, to predict memory traffic for different tiling configurations. By modeling the probability of access and the expected size of tiled data, D2T2 searches for non-uniform tile shapes and sizes that minimize total memory movement. Crucially, this optimization is performed offline during a pre-processing step, allowing the resulting static tiling scheme to be executed on accelerators without requiring specialized dynamic tiling hardware. The paper demonstrates that this approach can achieve performance superior to state-of-the-art dynamic (DRT) and overflow-based (Tailors) tiling schemes, positioning it as a highly practical solution for a broad range of hardware.

Strengths

1. Elegant and Practical Core Idea: The central thesis—that a probabilistic model of data distribution can inform a superior static tiling scheme—is both powerful and pragmatic. It carves out a valuable and previously underexplored design point between two extremes: overly conservative static tiling (which ignores data properties) and complex hardware-intensive dynamic tiling (which is costly and less portable). This "software-first" approach to data-awareness is the paper's most significant strength.

2. Broad Deployability: By obviating the need for specialized hardware like dynamic tile aggregators (DRT) or overflow-capable buffers (Tailors), the D2T2 framework is immediately applicable to a wide array of existing and future sparse accelerators. The evaluation on the real-world Opal CGRA (Section 6.4, page 10) is a compelling demonstration of this, showing significant speedups on a hardware platform not co-designed with this specific tiling strategy in mind. This greatly enhances the potential impact of the work.

3. Strong Contextualization and Clear Problem Framing: The authors do an excellent job of positioning their work within the broader landscape of sparse tensor computation. The introduction clearly articulates the "utilization problem" and the limitations of prior art. The summary in Table 1 (page 3) is particularly effective, immediately clarifying the trade-offs between different tiling schemes and highlighting D2T2's unique value proposition.

4. Comprehensive Experimental Analysis: The evaluation is thorough. The authors not only compare against relevant state-of-the-art systems on their original benchmarks but also validate their predictive model's accuracy (Section 5.3, page 8), analyze the framework's runtime overhead (Section 6.5, page 11), and perform insightful ablation studies on the importance of different statistics (Section 6.7, page 12). This rigorous approach builds significant confidence in the results.

Weaknesses

1. Model Fidelity on Correlated Data: The model's primary simplification appears to be the assumption of uncorrelated inputs when estimating output traffic. The authors rightly note this leads to under-prediction in cases like A x A^T (Figure 5, page 9), where the input structures are perfectly correlated. While they argue the model still captures relative trends correctly, this is a fundamental limitation. For many real-world problems (e.g., graph analytics involving adjacency matrices and their transposes), such correlations are the norm, not the exception. The "Corrs" statistic is a clever proxy to patch this, but it feels like a heuristic layered on top of a model that doesn't natively handle this phenomenon.

2. Generalizability of the Statistical Framework: The paper introduces a set of key statistics (e.g., PrTileIdx, ProbIndex, Corrs). These appear highly effective for the matrix- and 3-tensor-based kernels evaluated. However, it is less clear how this specific set of statistics would generalize to more complex, higher-order tensor expressions with multiple contraction loops. The concept of Corrs as a 1D correlation over the contracted dimension (Section 4.4, page 6) is intuitive for matrix multiplication, but its extension to, for instance, a tensor-times-matrix operation with two shared indices might require a more sophisticated, multi-dimensional correlation model.

3. Exploration of the Tiling Search Space: The shape optimization is guided by varying a "Reorder Factor (RF)" that controls the tile aspect ratio while preserving area (Section 5.2, page 8). This is a reasonable and practical heuristic. However, the true optimization space of tile shapes is vast. A deeper discussion on why this 1D parameter sweep is a sufficient exploration would be beneficial. It's possible that for some tensor structures, more exotic tile shapes not discoverable through this method could yield even better results.

Questions to Address In Rebuttal

1. On the Impact of Model Correlation: Regarding the model's under-prediction for correlated inputs (Section 5.3), could you elaborate on how this might affect tile shape selection for computations where output reuse is the dominant performance factor? Is it possible that the model, even while capturing the relative trend, might still erroneously prefer an outer-product-like shape (minimizing input re-fetches) when a square-like shape (maximizing output reuse) would have been globally optimal for that specific correlated input pair?

2. On the 'Sweet Spot' for This Approach: A key contribution is enabling data-awareness for static tiling. This implies a trade-off. Could you comment on the data distributions or problem types that define the "sweet spot" for D2T2? Conversely, are there specific sparsity structures (e.g., power-law graphs with extreme variance in degree) where the global statistics used by D2T2 might be misleading, making a fully dynamic, fine-grained approach like DRT inherently superior despite its hardware cost?

3. On the Future of Probabilistic Modeling: Your work successfully applies a probabilistic lens to tiling. Looking forward, how could this modeling framework be extended beyond tiling? For instance, could these same data statistics be used to guide other crucial compiler decisions, such as data layout transformations (e.g., choosing between CSF, COO, etc., on a per-tensor basis) or kernel fusion strategies for sparse computations?

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

The paper presents D2T2, a framework for optimizing static, coordinate-space tiling schemes for sparse tensor algebra computations. The core idea is to leverage a probabilistic model, built from high-level statistics extracted from the input tensors' compressed sparse fiber (CSF) format, to predict memory traffic for various tile shapes and sizes. The framework then searches for a configuration that minimizes this predicted traffic. The authors claim this approach provides a data-driven, static tiling solution that outperforms conservative static methods as well as more complex dynamic (DRT) and aggressive overflow-based (Tailors) schemes, without requiring specialized hardware support.

My analysis focuses exclusively on the novelty of this core idea. While performance modeling for compilers is not new, the specific formulation and application presented here contain genuinely novel elements.

Strengths

1. Novel Heuristic for Output Reuse: The most significant novel contribution is the formulation of the Corrs statistic (Section 4.4, page 6, Equation 11). The idea of estimating output data reuse by measuring the shifted self-intersection of fibers along a contracted dimension is a clever and computationally inexpensive proxy for an otherwise extremely complex phenomenon. To my knowledge, this specific analytical heuristic for guiding tile shape selection in sparse computations is new. Prior work, such as Cohen [6], focused on predicting the final nonzero count of a product, not on modeling traffic for intermediate tiled execution.

2. Identifies and Fills a Clear Gap in the Literature: The paper correctly identifies a gap between (1) overly conservative static tiling, (2) hardware-intensive dynamic tiling (DRT [26]), and (3) aggressive static tiling that requires specialized hardware for buffer overflows (Tailors [40]). D2T2 proposes a solution that resides in a novel design point: a data-aware static tiling scheme that does not require specialized hardware. This positioning itself represents a novel contribution to the design space of sparse tiling strategies.

3. Novel Application of Probabilistic Modeling to Tile Shape: While Tailors [40] uses statistical analysis of data occupancy, its primary goal is to optimize tile size by targeting a specific overflow rate. D2T2’s model is distinct in that it is used to evaluate the trade-offs of different tile shapes (i.e., aspect ratios), as shown in the Gustavson's Matmul example (Section 3, page 3) and the tile shape optimization logic (Section 5.2, page 8). The explicit modeling of how both input re-fetches and output reuse change with tile aspect ratio, guided by statistics like Corrs, is a significant delta over prior art.

Weaknesses

While the core idea is novel, its foundation rests on assumptions and simplifications whose novelty and robustness could be better defended.

1. Reliance on a Standard Independence Assumption: The probabilistic model simplifies the calculation of joint probabilities by assuming that the nonzero structures of different input tensors are uncorrelated (Section 4.2, page 5). This is a common assumption in the field and therefore not novel; however, it is also a known weakness. The model's predictive power is likely degraded in cases of high correlation, such as the A * A^T computation, which is common in graph analytics. The authors show in Figure 5a (page 9) that the model can have high absolute error in these cases, yet they claim it preserves relative trends. The novelty of the work would be strengthened by a more formal analysis of why the relative accuracy is maintained despite the foundational assumption being violated.

2. Limited Novelty in Higher-Order Kernel Modeling: The paper’s novel modeling concepts are most thoroughly developed and validated for SpMSpM. The extension to higher-order kernels like TTM and MTTKRP is presented primarily through experimental results (Table 4, page 10). It is unclear how the core novel idea, the Corrs statistic, is generalized to computations with multiple contracted indices or more complex data dependencies. If the extension is a straightforward application, its novelty is limited. If it required significant new modeling insights, those are not detailed, leaving the novelty of this aspect of the work unsubstantiated.

Questions to Address In Rebuttal

1. The model's utility hinges on its ability to make correct relative comparisons between tile shapes, even when absolute traffic predictions are inaccurate (as seen for A*A^T in Figure 5). Could the authors provide a more rigorous explanation for why the model's ranking of tile configurations remains robust even when the core assumption of tensor independence is strongly violated? Is there an underlying structural property of the model that makes it resilient in this way?

2. Regarding the higher-order tensor kernels (TTM, MTTKRP), could the authors elaborate on how the novel Corrs statistic, or a conceptual equivalent, is applied? For example, in MTTKRP, reductions occur over multiple modes. How is output reuse modeled in this context? Is the model simply a product of pairwise Corrs-like terms, or does it involve a more novel, higher-order correlation statistic?

3. The statistics used by the model, such as PrTileIdx and ProbIndex, are averaged over all tiles. For tensors with highly non-uniform distributions (e.g., a small dense block in a large sparse matrix), such averaging might obscure critical local characteristics. Does this lead to suboptimal tiling choices? Was a more localized statistical model considered, and if so, what was the trade-off in complexity versus benefit?