C3ache: Towards Hierarchical Cache-Centric Computing for Sparse Matrix Multiplication on GPGPUs

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors propose C3ache, a hierarchical in-cache computing architecture for Sparse Matrix Multiplications (SPMMs) on GPGPUs. The proposal is a full-stack solution encompassing a novel hybrid dataflow (combining outer-product and Gustavson's), a hardware-level restructuring of the GPGPU L1/L2 cache hierarchy into specialized Processing-In-Memory (PIM) units, and a new "memory-aware" compressed format, C3SR. The stated goal is to mitigate the memory access overhead that dominates SPMM performance, particularly in high-sparsity regimes, where traditional processor-centric optimizations like Sparse Tensor Cores (STCs) are claimed to be suboptimal.

Strengths

1. Problem Identification: The paper correctly identifies that memory access, not computation, is the primary bottleneck for SPMM on GPGPUs, especially as sparsity increases. Figure 1 provides a clear, albeit expected, illustration of this problem.
2. Architectural Scope: The work is comprehensive in its scope, addressing the problem from the data format (C3SR) up through the memory subsystem (modified L1/L2) and the execution model (hybrid dataflow). This end-to-end consideration is commendable.
3. Conceptual Decoupling: The core idea of decoupling the SPMM into a multiplication phase (mapped to L1 PIMs) and a merging phase (mapped to L2 PIMs) is logical. It attempts to map computational characteristics (high data reuse in multiplication, high synchronization in merging) to appropriate levels of the memory hierarchy.

Weaknesses

1. Unsubstantiated Claims Regarding the Hybrid Dataflow: The authors claim the outer-product dataflow achieves "perfect data reuse" (Section 3.2, page 5). This is a significant overstatement. While input reuse is high, this dataflow generates a massive number of partial products, creating a well-known output locality and memory bandwidth problem, which is the very reason it is seldom used in practice. The paper presents its in-cache merging solution as a fix, but it frames the initial dataflow choice with an unjustifiably positive claim.

2. Insufficiently Rigorous Baselines and Evaluation: The experimental evaluation (Section 4, page 9) is not convincing.

   • The "CUDA Cores" baseline is implemented on the authors' own RISC-V GPGPU simulator. The performance of such a baseline is entirely dependent on the quality of its software kernel. It is not clear if this represents a naive implementation or a highly optimized one comparable to state-of-the-art libraries like NVIDIA's cuSPARSE. Without this context, the reported 7.22x speedup is difficult to interpret.
   • The comparison against Sparse Tensor Cores (STC) appears to be a strawman. The authors use a specific pruning strategy (VectorSparse) and data format (BSR) to "maximize the performance of STC" (Section 5, page 10). This may not be the optimal configuration for all workloads. More importantly, the evaluation is against a simulated model of STC from a 2019 paper [61], not against a modern hardware implementation like that in the NVIDIA A100/H100, which has its own highly co-designed software stack.
   • The comparison against the NVIDIA A100 in Figure 12 is fundamentally flawed. Comparing a scaled-down simulator running at a "normalized frequency" against a real, highly optimized commercial product is not a valid methodology for claiming superior performance.

3. The C3SR Format Trades One Problem for Another: The proposed C3SR format (Section 3.4, page 7) aims to reduce memory transactions by packing multiple short rows into a single cache line. While this may reduce the volume of data fetched (as shown in Figure 14), it introduces non-trivial on-the-fly decoding complexity. The hardware must now parse row start flags, offsets, and indices within a cache line before computation can begin. The paper provides no analysis of the latency or area/power overhead of this decoding logic. It is plausible that the saved memory latency is nullified by the increased decoding latency, especially for a hardware implementation.

4. Generality Claims Are Not Supported by Evidence: The claim that C3ache "incurs virtually no performance loss" on other kernels (Figure 13, page 12) is based on a tiny set of benchmarks. A 0.2% average difference is suspiciously low. Partitioning cache ways for PIM functionality (Pways) fundamentally reduces the effective associativity and capacity for all other applications, which should increase conflict misses and degrade performance. A comprehensive evaluation using a standard benchmark suite (e.g., Rodinia) is required to substantiate this claim. The fused SGEMM+SPMM execution example is anecdotal and lacks the detail needed for proper scrutiny.

Questions to Address In Rebuttal

1. Regarding Baselines: Please justify the choice of baselines. How does C3ache compare against a highly optimized library like cuSPARSE running on a contemporary GPU (e.g., NVIDIA A100/H100) for the workloads in Table 4? This comparison to real, state-of-the-art hardware and software is essential for validating your claims.

2. Regarding C3SR Overhead: Please quantify the hardware decoding overhead (latency in cycles, area in µm²) of the C3SR format. How does this added latency compare to the memory access latency it aims to save? Provide a sensitivity analysis showing at what level of sparsity this trade-off becomes beneficial.

3. Regarding Generality: The generality analysis in Figure 13 is insufficient. Please provide a more comprehensive evaluation using a standard GPGPU benchmark suite (e.g., Rodinia, PolyBench) to demonstrate the performance impact of the partitioned cache on non-SPMM kernels that are memory-intensive.

4. Regarding Architectural Cost: The area breakdown in Table 6 focuses on the MSPM macro. What is the total area and power overhead of the entire C3ache modification—including the Stream-aware Request Management Unit (SRMU), the modified cache controllers, and the local adder layer—relative to a standard GPGPU cache hierarchy of equivalent size?

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper proposes C3ache, a novel hierarchical in-cache computing architecture designed to accelerate sparse matrix multiplication (SPMM) on GPGPUs. The core contribution is a profound re-imagining of the GPGPU's cache hierarchy as an active computational resource. The authors astutely identify that SPMM can be decoupled into two distinct computational phases: a massively parallel multiplication phase and a contention-heavy merging (reduction) phase. C3ache elegantly maps these phases onto a restructured hierarchy: the distributed L1 caches across Streaming Multiprocessors (SMs) are transformed into parallel "Multiplication PIM" units, while the shared L2 cache is converted into an "In-situ Merging PIM" unit.

This central hardware concept is supported by a holistic co-design, including: (1) a hybrid outer-product/Gustavson dataflow that maximizes data reuse while managing intermediate data, (2) a novel C3SR sparse format that aligns data granularity with cache lines to reduce memory transactions, and (3) a custom multi-precision PIM macro (MSPM). The experimental results are compelling, demonstrating significant speedups (avg. 7.22x over CUDA cores) and dramatic reductions in energy-delay product (EDP) and memory traffic, particularly for the highly sparse matrices where conventional GPGPUs falter.

Strengths

1. Elegant Problem-Architecture Mapping: The paper's most significant strength is its insightful mapping of the SPMM algorithm's structure directly onto the GPGPU's physical memory hierarchy. Recognizing that the distributed L1 caches are ideal for the "embarrassingly parallel" multiplication step and the shared L2 is the natural locus for the global merging step is a powerful conceptual leap. This moves beyond simply adding another accelerator and instead leverages the billions of transistors already dedicated to on-chip memory, directly addressing the data movement bottleneck that plagues this class of problem.

2. A Holistic, Systems-Level Approach: The authors present a commendably complete vision. The work is not just a hardware proposal; it is a co-designed system. The creation of the hybrid dataflow (Section 3.2, page 5), the memory-aware C3SR format (Section 3.4, page 7), and the corresponding ISA extensions and programming model (Figure 5f, page 6) shows a deep understanding of the problem. This holistic approach makes the proposal far more credible and practical than a point solution focused on only one aspect of the system.

3. Addressing a Key GPGPU Weakness: GPGPUs excel at dense, regular computation but often see their efficiency plummet for memory-bound, irregular workloads like high-sparsity SPMM. Processor-centric solutions like Sparse Tensor Cores (STCs) are an improvement but, as the authors correctly identify, they are still fundamentally limited by the von Neumann bottleneck. C3ache directly targets this fundamental weakness by turning the memory system into the solution. This work provides a compelling architectural direction for making GPGPUs more effective for a broader range of scientific computing and graph analytics workloads, which are often characterized by high sparsity.

4. Strong Contextualization and Motivation: The paper does an excellent job of positioning itself within the broader landscape. The analysis of different dataflows (Section 2.3, page 4) and the clear motivation provided in the introduction (Figure 1, page 2) effectively establish the "why" behind their work. This places C3ache as a logical and innovative next step in the evolution of GPGPU architecture, moving from processor-centric to memory-centric acceleration.

Weaknesses

While the core idea is powerful, the paper could be strengthened by addressing the following points in more detail:

1. Generality and System-Wide Overheads: The paper briefly touches upon generality in Figure 13 (page 12), showing minimal performance impact on other kernels. However, this analysis feels somewhat superficial. Modifying cache way logic, adding a Stream-aware Request Management Unit (SRMU), and implementing PIM functionality in SRAM arrays inevitably introduces area, power, and potentially timing complexity. A more thorough analysis of the potential impact on the GPGPU's critical path frequency and static power consumption for workloads that do not use C3ache would make the proposal more robust. Is the 0.2% performance difference truly representative of the system-wide cost?

2. Scalability of the L2 Merge Network: The paper describes the L2 merging PIM as leveraging a "peripheral local adder layer" (page 7). As the number of SMs in future GPGPUs continues to scale (e.g., beyond 108 in the A100), this shared merging resource could become a significant point of contention. The paper would benefit from a more detailed architectural description and scalability analysis of this merge network. At what scale of SM count would this L2 adder layer become the new system bottleneck, replacing the previous DRAM access bottleneck?

3. Practicality of the C3SR Format: The proposed C3SR format is cleverly designed to align with cache lines. However, its multi-level indirect indexing (Cache Line Offset, Row Offset, Row Indices) introduces a degree of software complexity. More importantly, sparse formats often involve a trade-off between compression efficiency and decoding overhead during execution. A discussion of the preprocessing time required to convert standard formats (like COO or CSR) to C3SR, and how C3SR performs on matrices with more structured sparsity patterns (where formats like BSR excel), would provide a more complete picture of its practical utility.

Questions to Address In Rebuttal

1. Regarding the system's generality, could the authors provide a more detailed breakdown of the area and static power overhead of the C3ache modifications? Furthermore, could you elaborate on why these changes are believed to have a negligible impact on the GPGPU's maximum clock frequency when running conventional, non-PIM workloads?

2. Could you provide more architectural detail on the L2 "in-situ merging PIM"? Specifically, what is the structure and bandwidth of the "local adder layer," and how is contention managed as dozens of SMs attempt to write and accumulate partial products concurrently? How does this mechanism scale compared to the L2 crossbar's native bandwidth?

3. The C3SR format is presented as a key enabler. Could you discuss the preprocessing overhead required to generate this format? Additionally, could you comment on its performance characteristics on matrices with structured or block-sparsity, where its row-packing strategy might be less advantageous compared to formats like BSR?

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper, "C3ache," proposes a hierarchical, cache-centric computing architecture to accelerate Sparse Matrix Multiplications (SpMMs) on GPGPUs. The authors identify memory access as the primary bottleneck for SpMMs, especially at high sparsity, and argue that processor-centric solutions like Sparse Tensor Cores (STCs) provide diminishing returns.

The core novel claim of this work is the co-design of a new GPGPU memory hierarchy, a hybrid computational dataflow, and a supporting sparse data format. Specifically, the contribution is a synthesis of three main ideas:

1. A Hierarchical In-Cache Computing Architecture: The L1 and L2 caches of a GPGPU are fundamentally restructured. The L1 cache is transformed into a large-scale parallel "Multiplication PIM" unit, while the L2 cache is converted into an "In-situ Merging PIM" unit.
2. A Hybrid Dataflow: The SpMM computation is decoupled into a multiplication phase (based on outer-product) and a merging phase (based on Gustavson's dataflow). These phases are then architecturally mapped onto the L1 and L2 PIM units, respectively.
3. A Memory-Aware Compressed Format (C3SR): A new sparse format is proposed to coalesce multiple short sparse rows into a single cache line, aligning data fetching with the memory subsystem's granularity and the proposed hardware.

While the constituent technologies (in-cache computing, hybrid dataflows, custom sparse formats) are not new in isolation, their specific synthesis into a functionally partitioned, hierarchical PIM system for GPGPUs appears to be the central claim to novelty.

Strengths

1. Novelty in Architectural Synthesis: The primary strength of this paper lies in its novel system-level vision. While prior art has extensively explored in-cache computing (e.g., [16, 17]), these works typically focus on transforming a single level of cache (often L1 or LLC) into a monolithic compute fabric. The C3ache proposal to create a functionally specialized hierarchy—where L1 PIMs perform parallel multiplication and L2 PIMs perform atomic merging/reduction—is a conceptually new architecture for GPGPUs. This tight coupling of algorithmic phases to distinct hierarchical hardware levels is the paper's most significant novel contribution.

2. Novelty of the C3SR Format: The proposed C3SR format, detailed in Section 3.4 (page 8), presents a non-trivial advancement over standard formats like CSR. The core idea of dynamically compressing multiple logical rows into a single physical cache line to maximize memory transaction efficiency is a clever software/hardware co-design. While related to blocked formats (e.g., BSR), its explicit goal of aligning with the cache-line quantum and enabling the proposed dataflow is a distinct and novel approach.

3. Boldness of the Proposal: The authors propose a fundamental redesign of the GPGPU's cache and memory subsystem. This represents a significant departure from more incremental approaches (e.g., adding specialized functional units alongside the existing hierarchy). Such a holistic architectural transformation, while complex, is precisely the kind of high-risk, high-reward idea that pushes the field forward.

Weaknesses

1. Insufficient Differentiation from Prior Art on Hierarchical PIM: The paper claims to be the "first hierarchical in-cache computing architecture" (page 2) for this purpose. However, the concept of multi-level or hierarchical processing-in-memory is not entirely unexplored. The authors need to more rigorously defend this claim by positioning their L1-multiply/L2-merge functional split against other systems that may use PIM at different levels of the memory hierarchy (e.g., logic in DRAM controllers vs. logic in LLC). The novelty is in the specifics of the functional partitioning, which should be emphasized more clearly.

2. Incremental Novelty of the Hybrid Dataflow: The paper's description of its hybrid dataflow (Section 3.2, page 5) as a combination of outer-product and Gustavson's is accurate. However, the core idea of decoupling SpMM into a partial-product generation phase and a reduction/accumulation phase is a well-established pattern in hardware accelerators. For instance, OuterSPACE [37] is built on the outer-product, which inherently separates these two phases. The true novelty here is not the decoupling itself, but rather the mapping of these phases onto their proposed hierarchical PIM architecture. The paper's narrative could be sharpened to make this distinction clear.

3. Overstated Novelty of the PIM Macro (MSPM): The design of the MSPM macro (Section 3.5, page 8), while a necessary and detailed engineering effort, is built upon established techniques. The use of exponent-mantissa pipelining for floating-point PIM and in-memory Booth encoding are known concepts in the PIM/in-cache computing literature. The novelty is in the specific implementation and integration, but it does not represent a fundamental conceptual breakthrough in PIM circuit design.

Questions to Address In Rebuttal

1. The claim of proposing the "first hierarchical in-cache computing architecture" is a strong one. Can the authors provide a more detailed comparison to any prior work that has proposed distinct computational functionalities in different levels of the cache/memory hierarchy and articulate why C3ache's specific L1-multiply/L2-merge split is fundamentally different and novel?

2. Regarding the hybrid dataflow, please clarify the novelty beyond the architectural mapping. Is the claim that the combination of outer-product for multiplication and Gustavson's for merging is itself a new algorithmic formulation for SpMM, or is the novelty exclusively in how this known computational pattern is mapped to the new cache hierarchy?

3. The C3SR format's novelty hinges on coalescing rows to the granularity of a cache line. Are there conceptually analogous data packing schemes from other domains (e.g., network packet payload optimization, file systems) that achieve a similar goal? Please elaborate on what makes C3SR's approach uniquely suited for SpMM on PIM architectures.

4. The proposed architecture is a highly specialized solution for SpMM. From a novelty perspective, how generalizable is the core architectural idea? Could the proposed L1-multiply/L2-merge hierarchy be a novel template for other algorithms with similar computation patterns (e.g., certain graph algorithms, database join operations), or is its novelty strictly confined to the SpMM domain?