Quartz: A Reconfigurable, Distributed-Memory Accelerator for Sparse Applications

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors present Quartz, a reconfigurable, distributed-SRAM accelerator architecture for iterative sparse applications. The central thesis is that existing architectures are either too specialized (unprogrammable) or too general (inefficient). Quartz proposes to bridge this gap using a programming model based on Einsum notation to generate short, dataflow tasks that are executed on reconfigurable processing elements (PEs). A significant part of the contribution is a novel set of data partitioning techniques, including a two-phase approach, designed to minimize communication and balance load for computations involving both static and dynamic sparsity patterns. The paper claims a geometric mean speedup of 21.4x over a state-of-the-art baseline, "Dalorex++," and 93x over an H100 GPU.

Strengths

1. Problem Formulation: The paper correctly identifies a critical and persistent challenge in high-performance computing: the memory bandwidth bottleneck for irregular, sparse computations. The motivation is clear and well-established.

2. Systematic Programming Model: The conceptual framework of translating high-level Einsum cascades into partitioned, tile-local tasks (Section 3) is methodical. It provides a structured way to think about decomposing these complex computations for a spatial architecture.

3. Novelty in Partitioning: The work's focus on partitioning for workloads with mixed static-dynamic operand sparsity (Section 5.3) addresses a known limitation of prior techniques. The proposed two-phase clustering and hypergraph partitioning strategy is a non-trivial contribution to the problem space.

Weaknesses

My primary concerns with this manuscript center on the validity of its core performance claims, which appear to rest on a questionable evaluation methodology and an overstatement of the system's practical usability.

1. Unconvincing Baseline Comparison: The central claim of a 21.4x speedup is made against "Dalorex++." However, as described in Section 6.1.4, this is not the original Dalorex system but rather a model constructed by the authors: "We model Dalorex by replacing the Quartz specialized PEs with a model of an in-order RISC core..." within their own simulation framework. This is a critical methodological flaw. The performance of this re-implemented baseline is not validated against the original work's published results or open-source simulator. It is entirely possible that this custom baseline model is unoptimized or fails to capture key performance characteristics of the actual Dalorex architecture, thus artificially inflating the speedup of Quartz. Claims of superiority must be demonstrated against faithful, validated representations of prior art, not potentially biased re-implementations.

2. The "Programmability" Claim is Premature: The paper puts forth a "flexible programming model" as a key contribution. However, the authors explicitly state that the compilation from Einsums to executable tasks is not automated: "...we leave it to future work to encode them as compiler passes" (Section 3, page 4). A programming model without a corresponding compiler or automated toolchain is a conceptual framework, not a programmable system. The claim of high programmability is therefore unsubstantiated, as the actual effort required to map a new application to Quartz remains undefined and potentially prohibitive.

3. Prohibitive and Narrowly Justified Partitioning Cost: The paper reports a geometric mean partitioning time of 18.5 minutes (Section 6.4). The authors justify this extreme offline cost by arguing it can be amortized over millions of runs in domains like navigation or physics simulations. This argument severely limits the applicable domain of Quartz. Any application where the input graph or matrix structure changes with non-trivial frequency would be impractical, as it would require re-running this costly partitioning step. The work fails to adequately characterize the large class of problems for which this static-structure assumption does not hold.

4. Insufficient Architectural Validation: The performance results are derived from a custom cycle-accurate simulator (Section 6.1.1). The paper states the simulator's functional correctness was validated against CPU implementations, but provides no information on how the performance model itself was validated. Without validation against RTL models or hardware prototypes, the cycle-level accuracy of the PE design, network contention model, and memory subsystem remains an open question. Similarly, the area and power estimates (Section 6.5) are derived from standard tools (CACTI, etc.) using a predictive PDK (ASAP7). While a common practice, these are high-level estimates, making the claims of 21x higher performance-per-area over a production chip like the H100 GPU appear highly optimistic and speculative.

Questions to Address In Rebuttal

The authors should address the following points directly:

1. Regarding the Dalorex++ baseline: Can you provide evidence that your model of the Dalorex PE and system is faithful to the original architecture? Specifically, what was the rationale for not using the publicly available Dalorex simulator, and can you provide a comparison of your model's performance against theirs on a common benchmark to establish its validity?

2. Regarding the compiler: Please clarify the current status of the compilation toolchain. How much of the process described in Section 3 is currently automated? What is the extent of manual intervention required to take a new application, express it as an Einsum cascade, and generate the PE configurations and task mappings for Quartz?

3. Regarding partitioning applicability: Can you more precisely define the application domains where the assumption of a static sparsity pattern over millions of runs holds? Conversely, please acknowledge and discuss the application domains for which the 18.5-minute partitioning overhead would make Quartz an impractical solution.

4. Regarding dynamic matrix sparsity: The paper focuses on handling dynamic sparsity in vectors (e.g., the BFS frontier). How would the proposed architecture and partitioning scheme handle problems where the sparsity structure of the primary matrix operand changes over time, as is common in applications like adaptive mesh refinement or dynamic graph analysis? Would this necessitate a full, multi-minute re-partitioning?

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents Quartz, a complete co-designed system for accelerating iterative sparse matrix computations. The core contribution is the synthesis of a reconfigurable, task-based dataflow architecture with a large, distributed on-chip SRAM memory system. This architectural vision is supported by two critical enabling components: a systematic programming model that translates high-level computations expressed in Einsum notation into hardware-friendly tasks, and a novel set of data partitioning techniques designed to simultaneously minimize communication and balance load, even for challenging applications with mixed static and dynamic sparsity. The authors position Quartz as a solution to the well-known tradeoff in this space, where prior architectures have sacrificed either performance for programmability (using general-purpose cores) or programmability for performance (using fixed-function hardware). The work claims significant speedups over both a state-of-the-art academic accelerator (Dalorex) and a commercial GPU (NVIDIA H100).

Strengths

The true strength of this paper lies in its ambitious and coherent system-level vision. The authors are not merely proposing a new hardware unit; they are presenting a cohesive solution that spans the stack from a high-level programming abstraction down to the microarchitecture and the physical data layout.

1. Elegant Synthesis of Architectural Concepts: Quartz effectively bridges several distinct domains of computer architecture research. It combines the high aggregate bandwidth of distributed-SRAM systems (seen in systems like Cerebras, Groq, and Dalorex) with the computational efficiency of Coarse-Grained Reconfigurable Arrays (CGRAs) and the dynamic execution model of dataflow machines. As the authors’ taxonomy in Table 1 (page 3) correctly identifies, this combination occupies a novel and promising point in the design space. By placing reconfigurable compute within a distributed memory fabric, the paper re-frames the core challenges away from managing cache hierarchies and toward managing data distribution and network traffic, which it then proceeds to solve.

2. A Principled Approach to Programmability: The use of an extended Einsum notation as the programming entry point (Section 3, page 4) is a standout feature. This provides a formal, mathematical foundation for describing a wide range of sparse computations. The subsequent "Einsum Cascade" methodology for systematically partitioning the computation across tiles and lowering it to concrete hardware tasks is a powerful idea. This offers a credible path toward a compiler that can target this complex hardware, addressing the programmability challenge that has plagued many specialized accelerators.

3. Sophisticated Solution to a Classic Hard Problem: Data partitioning is the Achilles' heel of many distributed systems. The paper correctly identifies the dual objectives of load balancing and communication minimization. The proposed two-phase partitioning strategy for non-all-active algorithms (Section 5.3, page 9 and Figure 12) is particularly insightful. The idea of first using graph partitioning on the input graph to create behaviorally-related clusters, and then using hypergraph partitioning to distribute each cluster across the tiles, is a novel and well-motivated heuristic for handling the unpredictable nature of dynamic sparsity. It strikes a pragmatic balance between locality and parallelism.

4. Convincing and Well-Structured Evaluation: The evaluation is thorough and compelling. The head-to-head comparison with Dalorex++ provides a clear measure of the benefits of reconfigurable compute over general-purpose cores in this context. The ablation studies (Figure 1, page 2, and Figure 15, page 12) are excellent, clearly attributing performance gains to the specific hardware and partitioning contributions. The paper is also forthright about the high offline cost of its partitioning scheme (Section 6.4, page 12) and provides a reasonable justification for why this is acceptable for the target application domain.

Weaknesses

The weaknesses of the paper are largely related to the scope and boundaries of its ambitious claims, rather than fundamental flaws in the core ideas.

1. The "Programmability" Boundary: The Einsum-based programming model is powerful for computations that fit within the tensor algebra paradigm. However, the true test of general programmability is how the system handles algorithms with more complex, data-dependent control flow that is not easily captured by map/reduce-style operations. While BFS is a good start, it would be valuable to understand the conceptual limits of this model. What kinds of sparse algorithms would be difficult or impossible to express and execute efficiently in Quartz?

2. Compiler and Task Generation Complexity: The paper presents the Einsum-to-task translation as a systematic process, which is a great first step. However, it also notes that the compiler passes are future work. This glosses over what is likely a significant engineering and research challenge. For instance, how does the system handle an application that requires a new task type that maps poorly to the existing functional units in the reconfigurable PE? Does this require a hardware redesign, or is the fabric flexible enough to accommodate a wide diversity of task primitives? The scalability of this compilation process as application complexity grows remains an open question.

Questions to Address In Rebuttal

1. Could the authors elaborate on the limitations of the extended Einsum programming model? Can you provide an example of a sparse algorithm that would be a poor fit for the Quartz programming model and architecture, and explain why? This would help to better define the boundaries of the proposed solution.

2. Regarding the programming model, what happens when a new application is introduced that requires a new set of task types? Is the PE fabric designed to be general enough to construct arbitrary task dataflows, or is it optimized for a certain family of primitives (e.g., scale-and-accumulate)? How would the system handle a task that requires, for example, complex bitwise operations or transcendental functions?

3. The paper makes a strong case for amortizing the high partitioning cost (Section 6.4, page 12). However, in a scenario where the sparsity pattern changes frequently (e.g., dynamic graphs) or where interactive, low-latency execution is needed for a single run, this cost could be a major barrier. Have the authors considered faster, lower-quality partitioning heuristics as a potential fallback, and how might that impact the performance tradeoff?

---

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper proposes Quartz, a distributed-memory, reconfigurable accelerator for iterative sparse applications. The authors identify that existing distributed-SRAM systems are limited by either the poor performance of general-purpose cores (e.g., Dalorex) or the poor programmability of fixed-function units (e.g., Azul).

To address this, the authors' core claims of novelty are threefold:

1. A Novel Architecture: The synthesis of a distributed all-SRAM memory system with task-driven, message-triggered reconfigurable processing elements (PEs).
2. A Novel Programming Model: A systematic method to translate high-level computations expressed as Einsum cascades into short, hardware-friendly tasks, where the Einsum notation is extended to explicitly represent data partitioning and inter-tile communication.
3. A Novel Partitioning Heuristic: A two-phase partitioning technique that claims to be the first to simultaneously optimize for communication minimization and load balance for workloads exhibiting both static (matrix) and dynamic (vector) sparsity.

The paper demonstrates significant performance gains over a state-of-the-art distributed-SRAM system (Dalorex++) and a high-end GPU (NVIDIA H100).

Strengths

The primary novel contribution of this work, and its most significant strength, lies in the partitioning methodology for mixed static-dynamic sparsity workloads (Section 5.3, page 9). To my knowledge, the authors' claim of being the first to explicitly tackle this specific problem by combining graph and hypergraph partitioning is accurate. Prior work has focused on the simpler case of all-static sparsity (as in Azul [30]) or has prioritized one objective over the other (e.g., communication minimization via coordinate-space tiling or load balancing via round-robin). The proposed two-phase heuristic—first clustering via graph partitioning to capture temporal locality, then distributing each cluster via hypergraph partitioning—is an elegant and clever approach to a notoriously difficult problem. The results in Figure 15 (page 12) compellingly demonstrate that this novel technique is essential for achieving good performance on non-all-active algorithms like BFS.

A secondary, but still significant, novel aspect is the specific co-design of the architecture and programming model. While the constituent parts are not new in isolation, their synthesis is. The extension of the Einsum framework (Section 3.2, page 5) to include a partitioning rank and "distribution tensors" (T1, T2) to explicitly model inter-tile communication is a conceptually clean and powerful abstraction. Mapping this abstraction onto an architecture of many simple, fast-reconfiguring PEs that execute short, message-triggered tasks represents a novel design point not fully explored by prior art.

Weaknesses

While the paper presents a compelling system, the novelty of some of its core ideas must be carefully contextualized against a backdrop of extensive prior work.

1. The Architectural Paradigm is an Integration, Not an Invention. The core architectural template is a synthesis of well-established concepts.

   • Distributed All-SRAM Architectures: This model is the foundation for numerous prior works, including Dalorex [59], Azul [30], and commercial systems like the Groq TSP [2] and Cerebras WSE [20]. The novelty is not in the memory system itself.
   • Reconfigurable Compute for Sparsity: Using coarse-grained reconfigurable arrays (CGRAs) to accelerate sparse computations is also a known technique, explored in systems like PolyGraph [24] and Onyx [45]. The key difference is that those systems were coupled with conventional shared memory hierarchies.
   • Task-Based/Message-Driven Execution: The execution model is functionally very similar to classic active messages [28] and more recent triggered-instruction paradigms [61]. The concept of dispatching small compute tasks in response to network messages is not fundamentally new.

   The true architectural contribution is therefore the specific integration of these three concepts to create a scalable fabric of CGRAs, each with high-bandwidth local SRAM. This is a strong engineering contribution, but it should not be mistaken for the invention of a fundamentally new architectural class.

2. The "Systematic" Programming Model May Obscure Manual Effort. The paper claims a "systematic, highly automatable process" (Section 3, page 4) for converting Einsums to tasks. However, the critical step of formulating the initial iterative Einsum cascade for a given application is non-trivial. The derivation of the four distinct task types for BFS (page 6), for instance, requires significant insight into the algorithm's structure. The paper defers the actual implementation of this compilation flow, stating, "we leave it to future work to encode them as compiler passes." This weakens the claim of a fully realized, systematic programming model and suggests the current process may rely on considerable developer effort to fit applications into the required Einsum structure. The novelty is in the proposed flow, but its generality and automation remain unproven.

3. High Cost of Novelty. The novel partitioning heuristic comes at a steep price: a gmean of 18.5 minutes of offline preprocessing time (Section 6.4, page 12). While the authors provide a valid justification for workloads where this cost can be amortized, this fundamentally limits the application domain of Quartz. The novelty of the solution must be weighed against this practical constraint. It is a specialized solution for nearly-static problems, not a general-purpose accelerator for ad-hoc sparse computations.

Questions to Address In Rebuttal

1. Architectural Delta: Could the authors more precisely articulate the novel architectural mechanisms in Quartz compared to a hypothetical system combining a triggered-instruction execution model (e.g., Parashar et al. [61]) with a reconfigurable fabric like that in Onyx [45]? Beyond the memory subsystem, what is fundamentally new in the PE design or execution model that is essential for this problem domain?

2. Generality of the Programming Model: The translation from Einsum to tasks is presented as systematic. Could the authors walk through how a more complex algorithm not evaluated in the paper (e.g., betweenness centrality or a non-linear solver) would be expressed in their extended Einsum notation? How confident are the authors that this process can be fully automated without algorithm-specific templates or transformations?

3. Robustness of the Partitioning Heuristic: The two-phase partitioning is a heuristic. Have the authors identified any graph topologies (e.g., expander graphs, or graphs with no clear community structure) where the initial graph clustering phase might provide a poor partition, leading the second hypergraph phase to produce a suboptimal result for load balancing? How sensitive is the final performance to the quality of the initial clustering?