Telos: A Dataflow Accelerator for Sparse Triangular Solver of Partial Differential Equations

Review Form:

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors propose Telos, a dataflow accelerator for Sparse Triangular Solve (SpTRSV) targeting structured sparse systems derived from Partial Differential Equations (PDEs). The core contributions are a "plane-parallel pipelining" technique based on an affine coordinate transformation to create parallelizable wavefronts, and a "cross-plane communication aggregation" method to manage data dependencies between processing elements (PEs). While the paper identifies a relevant problem and proposes a dataflow-based solution, its claims of generality and superior performance are not rigorously supported. The evaluation relies on questionable modeling of competing state-of-the-art accelerators, and the proposed techniques appear to be applicable only to a narrow, highly regular class of PDE problems, a limitation that is not sufficiently acknowledged.

Strengths

1. Problem Formulation: The paper correctly identifies the SpTRSV kernel as a major bottleneck in preconditioned iterative solvers for PDEs and rightly points out the challenges of parallelism and data locality on conventional architectures like GPUs (Section 3, Figure 4).
2. Core Pipelining Concept: The fundamental idea of transforming stencil dependencies into a pipelined dataflow execution across a PE array (Section 4.1) is a sound and promising direction for this problem class.
3. Data Reuse: The architecture is designed to maximize temporal and spatial data reuse, as analyzed in Section 5.3. This is a critical aspect for achieving high efficiency in memory-bound problems like SpTRSV.

Weaknesses

1. Unsupported Generality of the Affine Transformation: The central claim of the dataflow design rests on the affine transformation (Section 4.1.1, Algorithm 2) to eliminate backward dependencies. The paper demonstrates this for the Diamond-13P stencil and asserts it "can be applied to other stencil patterns." This is an unsubstantiated claim. The algorithm appears heuristic, and no formal argument or proof is provided to guarantee its success for any arbitrary stencil pattern arising from PDE discretizations. The work would be much stronger if the authors formally defined the class of stencils for which this transformation is guaranteed to work.
2. Flawed Evaluation of Competing Accelerators: The performance comparison against state-of-the-art accelerators Alrescha, FDMAX, and Spadix is fundamentally unsound. In Section 6.1, the authors state, "None of them has been open-sourced. Therefore, we model their behaviors and scale them..." This self-modeling of competing prior work is a critical methodological flaw. Without extensive validation, these models are unlikely to faithfully represent the performance of the original architectures. Consequently, the claimed speedups of 11x over Alrescha and ~8x over Spadix (Figure 12, Figure 15) are not credible.
3. Overstated Problem Scope: The title and introduction refer broadly to "Partial Differential Equations." However, the entire methodology—from the affine transformation to the PE mapping—is predicated on the extreme regularity of structured Cartesian grids. Many real-world scientific applications rely on unstructured meshes or adaptive mesh refinement (AMR), which generate sparsity patterns that would break the assumptions of Telos. The paper fails to discuss these limitations, implicitly overstating its applicability.
4. Misleading Use of "Systolic": The authors claim their communication aggregation technique enables "systolic-style data transfers" (Abstract, Section 8). However, the communication patterns depicted in Figure 7 are not strictly systolic. Systolic arrays are characterized by simple, regular, nearest-neighbor communication. The paths in Figure 7 (e.g., the aggregated path for x111) are complex, multi-hop, and data-dependent, requiring a more sophisticated routing network than what "systolic" implies. This terminology is misleading and exaggerates the regularity of the dataflow.
5. Insufficient Justification for Architectural Parameters: The choice of 4 vector lanes per PE (Section 6.4, Table 3) is poorly justified. The authors' own analysis in Figure 18c shows that for 3 out of 4 tested stencil patterns, performance saturates at 2 vector lanes. Only the most complex stencil (Box-27P) benefits from more lanes. Choosing 4 lanes for all PEs appears to be an inefficient use of silicon area and power for the majority of workloads presented. A more rigorous analysis of the area/performance trade-off is required.

Questions to Address In Rebuttal

1. Please provide a formal proof or, failing that, a rigorous argument for the correctness and completeness of the Backward Dependency Elimination (Algorithm 2). Specifically, define the exact class of stencil dependency graphs for which the algorithm is guaranteed to find a valid transformation. Are there known stencil types where it would fail?
2. Provide a detailed account of your methodology for modeling the Alrescha, FDMAX, and Spadix accelerators. How were these models validated? Without this, the quantitative comparisons against these key baselines cannot be considered reliable.
3. Please justify the use of the term "systolic-style" communication. Given that the communication paths are multi-hop and stencil-dependent, as shown in Figure 7, how does this align with the established definition of a systolic architecture?
4. How would the Telos architecture handle the irregularities introduced by common PDE solution techniques like unstructured grids or adaptive mesh refinement? If it cannot, please explicitly state this as a primary limitation of the proposed approach.
5. Explain the rationale for implementing 4 vector lanes per PE when your own data (Figure 18c) indicates that performance for most evaluated stencils does not improve beyond 2 lanes. What is the area and power overhead of the two unused lanes in these common cases, and how is this trade-off justified?

Here is a peer review of the paper from the perspective of "The Synthesizer."

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents Telos, a dataflow accelerator for the sparse triangular solve (SpTRSV) kernel, a critical bottleneck in preconditioned iterative solvers for Partial Differential Equations (PDEs). The work's core contribution is a novel methodology that leverages the structured sparsity inherent in stencil-based discretizations on regular grids. Instead of treating the sparse matrix as a generic graph, Telos translates the geometric dependency structure of the underlying stencil into a highly efficient, systolic-like dataflow execution pattern. This is achieved through two key techniques: a "plane-parallel pipelining" method, which uses affine transformations to systematically organize computations into parallel wavefronts, and a "cross-plane communication aggregation" scheme to manage the resulting data transfers between processing elements (PEs) with minimal overhead. The authors demonstrate through extensive experiments that Telos significantly outperforms CPUs, high-end GPUs, and a state-of-the-art general-purpose SpTRSV accelerator.

Strengths

1. Novel and Insightful Problem Framing: The paper carves out a compelling and important niche between two established classes of accelerators. On one hand, there are matrix-free stencil accelerators (like FDMAX), which are efficient but cannot handle the dependencies of SpTRSV. On the other hand, there are general SpTRSV accelerators (like Alrescha), which are flexible but fail to exploit the rich geometric structure of PDE-derived matrices. By focusing specifically on "structured SpTRSV," Telos provides a solution that combines the structural awareness of the former with the algorithmic power of the latter. This is a powerful synthesis of ideas from numerical methods and computer architecture.

2. Systematic and Elegant Dataflow Mapping: The use of affine transformations to resolve backward dependencies (Section 4.1.1, page 5) is the conceptual heart of this paper. It provides a principled and systematic method for converting a complex dependency graph into a regular wavefront computation that can be mapped directly onto a hardware PE array. This elevates the design from an ad-hoc solution for one stencil to a generalizable methodology, which is a significant strength. The resulting systolic-like communication pattern is a classic and highly efficient execution model that this work successfully applies to a notoriously difficult, dependency-laden problem.

3. Demonstrated Real-World Impact: The paper's evaluation is strong not only because the kernel-level speedups are impressive, but because it connects these gains back to the end-to-end application. By evaluating a full Preconditioned Conjugate Gradient (PCG) solver (Section 6.3, page 11), the authors show that accelerating SpTRSV enables the use of more powerful preconditioners. This leads to faster convergence and substantial overall time-to-solution improvements compared to accelerators focused on simpler, matrix-free methods. This clearly demonstrates that Telos is a solution to a real and significant problem in scientific computing.

4. Strong Algorithm-Architecture Co-design: The hardware architecture presented in Section 5 is clearly motivated by the dataflow design. Features like the non-zero value packing, the configurable aggregator primitive, and the Halo Exchange Units (HEUs) are not arbitrary but are direct consequences of the plane-parallel pipelining and communication aggregation schemes. This synergy between algorithm and architecture is a hallmark of excellent DSA design.

Weaknesses

1. Limited Scope (by design): The work's primary strength—its specialization for structured grids—is also its main limitation. Many cutting-edge simulations in fields like fluid dynamics and structural mechanics rely on unstructured grids or Adaptive Mesh Refinement (AMR) to efficiently model complex geometries. The paper would be strengthened by a brief discussion contextualizing its contribution, acknowledging this limitation, and perhaps speculating on the challenges or potential pathways to extend these geometric dataflow principles to more irregular problem domains.

2. Clarity on Generalizability: While the affine transformation is presented as a general method, its application could be further illuminated. For a researcher looking to apply this method to a new or more exotic stencil pattern, it is not immediately clear how the transformation matrix T is derived or whether the process in Algorithm 2 (page 6) is guaranteed to find a valid mapping. A more detailed example or a discussion on the potential for automating this transformation via a compiler would bolster the claim of a truly systematic methodology.

Questions to Address In Rebuttal

1. The affine transformation presented in Algorithm 2 is the cornerstone of your method. Could you please elaborate on its robustness and scope? Does this procedure provably find a valid parallelizable wavefront mapping for any stencil pattern that results in a solvable triangular system, or are there classes of stencils (e.g., those with very long-range or asymmetric dependencies) for which it might fail? Is this process currently automated for the stencils you tested?

2. Your work masterfully exploits the regularity of structured grids. From your perspective, what are the fundamental obstacles to applying the core principles of Telos (i.e., mapping local geometric dependencies to a systolic dataflow) to problems with irregular structures, such as those using unstructured finite element meshes? Is there a conceptual path forward, perhaps by operating on patches of structured sub-grids, or do you view this as a fundamentally structured-grid solution?

3. The Halo Exchange Units (HEUs) appear to handle inter-tile dependencies by writing updated boundary values back to main memory, which are then read in a subsequent execution phase (Section 5.3, page 9). This seems to introduce a memory round-trip that breaks the otherwise pure on-chip dataflow at tile boundaries. Could you quantify the performance impact of this design choice compared to a hypothetical on-chip-only exchange mechanism (e.g., the long FIFOs you mention and dismiss in Section 5.2, page 9)? A more concrete justification would help clarify the trade-offs involved in your inter-tile pipelining strategy.

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

The paper proposes Telos, a dataflow accelerator for the Sparse Triangular Solve (SpTRSV) kernel, specifically targeting structured sparse matrices derived from Partial Differential Equation (PDE) discretizations. The authors identify that standard SpTRSV parallelization methods struggle to balance parallelism and data locality. The core of their proposed solution rests on two main ideas: (1) a "plane-parallel pipelining" technique, which uses an affine coordinate transformation to organize computations into parallel wavefronts, and (2) a "cross-plane communication aggregation" technique, which transforms the resulting data dependencies into a systolic, nearest-neighbor communication pattern. The paper presents a corresponding hardware architecture and demonstrates significant speedups over CPU, GPU, and a state-of-the-art SpTRSV accelerator.

Strengths

The primary strength of this work is the elegant and systematic synthesis of established parallel computing principles into a cohesive, specialized hardware architecture for a very specific and challenging problem domain. The authors have correctly identified that the structure inherent in PDE stencils is an underexploited resource for SpTRSV acceleration. The translation of a stencil's dependency pattern into a hardware-realizable systolic dataflow is well-conceived and thoroughly detailed from algorithm to microarchitecture.

Weaknesses

My evaluation is focused exclusively on the novelty of the core ideas. While the engineering and integration are commendable, the foundational concepts presented as novel in this paper have deep roots in prior art, specifically in the fields of parallelizing compilers and systolic array design.

1. "Plane-Parallel Pipelining" is Wavefront Parallelization via Loop Transformation: The central idea of partitioning the computation domain into hyperplanes (or wavefronts) where all nodes can be processed in parallel is a classic technique for parallelizing algorithms with uniform data dependencies, dating back to the late 1970s and early 1980s. This is the foundational principle behind systolic arrays and various loop parallelization strategies.

2. The Affine Transformation is a Known Polyhedral Compilation Technique: The method used to handle "backward dependencies" (Section 4.1.1, Page 5) is, in essence, a loop skewing transformation. The process of applying an affine transformation to a coordinate system to expose parallelism in a loop nest is the cornerstone of the polyhedral model of compilation. Decades of research in compilers have focused on automatically finding such transformations to enable parallel execution. The paper does not acknowledge this vast body of work, nor does it sufficiently differentiate its proposed transformation algorithm (Algorithm 2, Page 6) from standard polyhedral scheduling algorithms. The claim of novelty for this technique is therefore significantly overstated.

3. "Cross-Plane Communication Aggregation" is Systolic Data Routing: The concept of transforming longer-range data dependencies into a nearest-neighbor, pipelined communication fabric is the very definition of a systolic array, as pioneered by H.T. Kung. The proposed "aggregation" technique (Section 4.2, Page 6) is a specific implementation of this principle, where partial products are accumulated as they flow through the PE array. While Algorithm 3 (Page 7) provides a concrete method for assigning these paths, the underlying concept is not new. It is a direct application of systolic principles to the SpTRSV recurrence.

In summary, the novelty of this paper does not lie in the invention of new parallelization concepts, but rather in the application-specific specialization and hardware co-design of these well-known concepts for structured SpTRSV. The paper's framing, however, presents these foundational techniques as novel contributions in themselves, which is a major weakness. The true "delta" over prior art is the creation of a systematic methodology to map any PDE stencil pattern onto a fixed systolic hardware template, which is a valuable engineering contribution but not a fundamental conceptual breakthrough.

Questions to Address In Rebuttal

The authors must clarify the precise novelty of their work with respect to the extensive prior art in parallel algorithms and compilers.

1. Please clarify the novelty of the "plane-parallel pipelining" technique with respect to the decades of research on wavefront/hyperplane parallelization for algorithms with regular dependencies.
2. The affine transformation presented in Section 4.1.1 and Algorithm 2 appears to be a specialized application of techniques from the polyhedral compilation domain. Could the same result (i.e., a valid parallel schedule) be derived using an existing polyhedral tool like Pluto or ISL? If so, what is the novel contribution of your specific transformation algorithm beyond what is already established in the compiler literature?
3. The goal of creating systolic, nearest-neighbor communication is a well-established design pattern for dataflow accelerators. Is the novelty of the "cross-plane communication aggregation" primarily in the specific path-finding heuristic of Algorithm 3? Please elaborate on why this is a non-trivial contribution beyond a direct mapping of the SpTRSV dependency graph onto a 2D mesh topology.