Swift and Trustworthy Large-Scale GPU Simulation with Fine-Grained Error Modeling and Hierarchical Clustering

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors propose STEM+ROOT, a kernel-level sampling methodology for GPU simulation that uses the distribution of kernel execution times as its primary signature. The method employs statistical techniques (the Central Limit Theorem) to determine sample sizes (STEM) and hierarchical clustering to group kernels with similar runtime behaviors (ROOT). The stated goal is to reduce simulation error and profiling overhead compared to prior work that relies on microarchitecture-independent features like instruction counts or Basic Block Vectors (BBVs). While the approach demonstrates impressive speedups and low profiling overhead, its core premise is built on a fundamentally hardware-dependent signature, and it fails to adequately address critical confounding factors such as inter-kernel architectural state, casting significant doubt on the trustworthiness and generality of its results.

Strengths

1. Problem Motivation: The paper effectively uses Figure 1 (Page 2) to illustrate the runtime heterogeneity of identical kernels in modern ML workloads. This observation clearly motivates the need for a more nuanced sampling approach than what is currently practiced.

2. Profiling Scalability: The primary practical contribution of this work is the significant reduction in profiling overhead. As demonstrated in Table 5 (Page 11), the proposed method is orders of magnitude faster to profile than instruction-level or BBV-based techniques (e.g., 1.33-5.53x overhead vs. 293-3704x for PKA/Sieve on CASIO). This is a clear and measurable advantage.

3. Statistical Formulation: The application of the Central Limit Theorem and KKT optimization to determine sample sizes (Section 3.2, 3.3) provides a formal, mathematical basis for the sampling strategy. This is a more rigorous foundation than the heuristic-based or fixed-threshold approaches used in some prior work.

Weaknesses

1. Fundamental Reliance on a Hardware-Dependent Signature: The central thesis—that kernel execution time distribution is a robust signature—is fundamentally flawed. Execution time is an outcome of the interaction between a program and a specific microarchitecture, not an intrinsic property of the workload. The authors' claim that statistical properties like the Coefficient of Variation (CoV) are "relatively hardware-agnostic" (Section 2.3, Page 3) is a strong, unsubstantiated assertion. Their own cross-GPU experiment in Section 5.4 (Page 10, Figure 13) directly contradicts this claim of robustness: using a profile from an H100 to sample for an H200 (a minor architectural evolution) results in an average error of 5.46%. This is a significant error rate that undermines the method's utility for design space exploration (DSE), which is a primary use case for cycle-level simulation.

2. Neglect of Inter-Kernel Architectural State (Warmup): The methodology implicitly assumes that each kernel invocation is an independent event, with no state carried over from previous kernels. In Section 6.2 (Page 12), the authors admit this limitation, stating their method "assumes ideal warmup of cache and hardware states." They attempt to dismiss this concern by asserting that inter-kernel cache reuse is a "negligible fraction" in their benchmarks. This is a dangerous and unproven generalization. For many real-world applications, performance is critically dependent on the state of caches (L1/L2), TLBs, and memory controllers left by preceding kernels. By ignoring this, the "sampled simulation" is not a simulation of a subsampled workload but rather a simulation of a collection of disconnected kernels, which is a different and potentially irrelevant experiment. The "extreme-case experiment" of flushing the L2 cache is insufficient evidence, as it doesn't model the complex, state-dependent patterns of realistic cache reuse.

3. Validity of Statistical Assumptions: The entire statistical model in Section 3.2 (Page 4) rests on the assumption that samples are independent and identically distributed (i.i.d.). The authors claim that "random sampling with replacement satisfies the i.i.d. assumption." While the draws are independent, the underlying distribution they are drawn from may not be identical throughout the workload's execution. Many programs exhibit distinct phases of behavior. Randomly sampling across the entire execution trace may not correctly represent the duration and characteristics of these phases, violating the spirit, if not the letter, of the i.i.d. assumption and potentially leading to biased estimates.

4. Inconsistent and Potentially Overstated Accuracy: The results show a stark contrast between the near-zero error (0.36%) on the CASIO suite (Table 3, Page 8) and the more realistic error on Rodinia (0.93%) and the significant error in the cross-GPU experiment (5.46%). The exceptional performance on CASIO suggests that these workloads may represent a best-case scenario for this methodology—perhaps consisting of many short, independent kernels where statistical averaging works perfectly. This raises concerns that the method has been over-tuned or is being evaluated on workloads that perfectly fit its assumptions, rather than proving its general applicability. The headline claims of accuracy seem to be based on this best-case result.

Questions to Address In Rebuttal

1. Please reconcile the claim that execution time is a "robust signature" for DSE with the 5.46% error observed in the H100-to-H200 experiment (Figure 13). If a simple generational update in memory bandwidth causes such a significant error, why should this method be trusted for exploring more substantial architectural changes (e.g., different cache hierarchies, prefetchers, or memory controllers)?

2. The dismissal of inter-kernel state as "negligible" (Section 6.2) is insufficient. Please provide a quantitative analysis of the error introduced by the ideal warmup assumption on at least one benchmark known to exhibit significant inter-kernel data locality. Without this, the accuracy claims of the paper are suspect.

3. How does the methodology guarantee an unbiased estimate in workloads with distinct, long-running execution phases? Please justify the i.i.d. assumption in this context and explain how random sampling across the entire trace avoids misrepresenting the proportional impact of these different phases.

4. The recursive splitting condition in ROOT (Section 3.4, Page 6) relies on comparing Told and Tnew, which are estimates of simulation time based on sample means. How robust is the clustering outcome to the statistical noise inherent in these estimates? Could an initial sampling error lead to a suboptimal clustering decision, which in turn amplifies the final error?

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper addresses the critical and increasingly challenging problem of slow cycle-level simulation for large-scale GPU workloads, particularly those from the machine learning and large language model domains. The authors propose STEM+ROOT, a novel kernel-level sampling methodology designed to be both swift and trustworthy.

The core contribution is the insight that the statistical distribution of kernel execution times serves as a powerful and highly scalable "signature" for characterizing workload behavior. This represents a departure from prior works that rely on static, microarchitecture-independent features like instruction counts or Basic Block Vectors (BBVs).

The proposed method consists of two main components:

1. STEM: A statistical framework based on the Central Limit Theorem that models sampling error and uses a KKT solver to determine the optimal number of samples required from each kernel cluster to meet a user-defined error bound.
2. ROOT: A fine-grained hierarchical clustering algorithm that recursively partitions invocations of the same kernel based on their execution times. This effectively separates kernels that share the same code but exhibit different runtime behaviors due to varying inputs or system states.

The evaluation demonstrates that this approach significantly reduces sampling error (by 27-81x) and drastically cuts profiling overhead (by 7-600x) compared to state-of-the-art methods, making it practical for the massive workloads that are currently intractable for detailed simulation.

Strengths

This work has several significant strengths, primarily rooted in the elegance and practicality of its central idea.

1. A Powerful and Pragmatic Core Idea: The fundamental contribution—using the execution time distribution as a kernel signature—is excellent. While prior art has focused on creating microarchitecture-agnostic signatures from static code properties, this work makes a compelling case that a dynamic, hardware-dependent signal is actually more useful in practice. It correctly identifies that for modern ML workloads, runtime context (e.g., tensor sparsity, memory locality) often matters more than static code structure. This is a fresh and valuable perspective in the field of workload sampling.

2. Principled Statistical Foundation: The methodology isn't just a collection of heuristics; it is grounded in sound statistical principles. The use of the Central Limit Theorem to model the sampling distribution of the mean execution time and provide theoretical error bounds (Section 3.2, page 4) gives the "Trustworthy" claim in the title real substance. This allows a user to explicitly trade off simulation speed for accuracy via the ε parameter, a crucial feature for flexible design space exploration.

3. Exceptional Scalability and Practicality: The most significant practical advantage of this work is its scalability. By relying on lightweight kernel-level timing information (which can be gathered by profilers like NSYS with low overhead), it sidesteps the crippling profiling costs of methods that require per-warp instruction-level instrumentation (PKA, Sieve) or complex BBV comparisons (Photon). The results in Table 5 (page 11), showing orders of magnitude lower overhead, are dramatic and convincing. This is the key that unlocks the ability to simulate and analyze the gargantuan workloads from suites like Huggingface.

4. Effective Handling of Runtime Heterogeneity: The ROOT clustering mechanism is a clever solution to a well-known problem. Kernels like sgemm can have vastly different performance characteristics depending on the context in which they are called. As shown in Figure 1 (page 2), simply grouping by kernel name is insufficient. ROOT's recursive, goal-oriented approach—to keep splitting clusters as long as it reduces the estimated simulation time—is an elegant way to avoid the need to pre-specify the number of clusters (k) and ensures that the partitioning is done for a practical purpose.

Weaknesses

The paper's weaknesses are less about flaws in the methodology and more about its inherent trade-offs and scope, which could be discussed more explicitly.

1. Hardware-Signature Dependency: The primary conceptual weakness is that the signature (execution time) is intrinsically tied to the hardware on which it was profiled. While the authors acknowledge this limitation in Section 6.1 (page 11) and show promising results in their DSE and cross-GPU experiments (Section 5.4, page 10), it remains a fundamental trade-off. The paper argues this is a feature, not a bug, because it captures sensitivity to the microarchitecture. However, it relies on the assumption that the relative behavior (e.g., the shape of the distribution, the number of peaks) remains largely consistent across different architectures. This assumption may not hold for more radical architectural changes.

2. Neglect of Inter-Kernel Effects: Like most kernel-level sampling techniques, this method treats kernel invocations as largely independent events. It does not explicitly model state that is carried across kernel boundaries, most notably the state of the L2 cache and memory subsystem. The authors provide a reasonable defense in Section 6.2 (page 12), arguing that kernel working sets are often large enough to flush the cache, but this is an assumption about the workload character. This could be a source of error for workloads with tight producer-consumer relationships between kernels operating on the same data.

3. Limited Scope to Single-GPU Workloads: The current work is confined to single-GPU simulation. While this is the foundation upon which multi-GPU simulation is built, the most challenging and interesting systems-level problems in modern ML training involve communication and synchronization across multiple GPUs. The authors correctly identify this as future work, but it is a significant limitation on the immediate applicability of the technique to state-of-the-art distributed training scenarios.

Questions to Address In Rebuttal

I would appreciate it if the authors could use the rebuttal to clarify the following points, which would strengthen the paper and help position its contribution even more clearly.

1. Regarding the hardware-dependency of the signature: Could you elaborate on the potential "failure modes" of your approach? For instance, consider a scenario where a microarchitectural change (e.g., a new cache replacement policy) inverts the performance of two distinct runtime phases of the same kernel. A phase that was fast on Hardware A becomes slow on Hardware B, and vice versa. Would the samples selected based on the Hardware A profile still be representative, or would this lead to significant error?

2. Regarding inter-kernel effects: Your analysis in Section 6.2 is based on flushing the L2 cache. Have you considered workloads where the key interaction is not just cache reuse, but perhaps DRAM row buffer locality or memory controller state that persists across kernels? How sensitive do you believe your methodology is to these more subtle cross-kernel performance dependencies?

3. This is a more philosophical question about the nature of your signature. Do you view the execution time distribution primarily as a direct signal, or as an inexpensive proxy for underlying microarchitectural behaviors (e.g., a wide distribution implies memory-boundness, a narrow peak implies compute-boundness)? Have you considered a hybrid approach where the fast, scalable clustering of ROOT is used to identify behavioral groups, and then a tiny number of kernels from each group are profiled in detail (e.g., with NCU) to "label" the clusters with microarchitectural explanations? This seems like a promising direction for future work that connects your high-level signature back to low-level hardware behavior.

---

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper proposes STEM+ROOT, a kernel-level sampling methodology for accelerating large-scale GPU simulations. The authors identify that existing sampling techniques, which rely on static or microarchitectural signatures (e.g., instruction counts, basic block vectors), fail to capture the runtime heterogeneity of identical kernels in modern workloads.

The claimed novel contributions are:

1. The use of the kernel execution time distribution as the primary signature for identifying and clustering kernels with different runtime behaviors.
2. A statistical framework, STEM, based on the Central Limit Theorem (CLT) and KKT optimization, to derive the optimal number of samples required from each cluster to meet a user-defined error bound.
3. A hierarchical clustering algorithm, ROOT, which recursively partitions kernel clusters and uses the STEM model as a termination condition, thereby avoiding the need to pre-specify the number of clusters (k).

Strengths

The primary strength of this work lies in its core conceptual contribution: the shift from cause-based signatures to an effect-based signature. The vast body of prior art in workload sampling, from SimPoint [9] to Photon [21], has focused on abstracting the cause of a program's behavior—its instruction mix and control flow, represented by Basic Block Vectors (BBVs) or other instruction-level metrics. The fundamental insight of this paper is to instead use the ultimate effect of this behavior—the kernel's execution time—as the signature. This is a genuinely novel perspective in the domain of GPU simulation sampling.

This conceptual shift has several significant and novel consequences:

• Principled Handling of Heterogeneity: It elegantly captures dynamic, input-dependent runtime effects that are invisible to static analysis. The histograms in Figure 1 (page 2) clearly show that execution time is a powerful discriminator where instruction-based signatures would fail.
• A More Rigorous Sampling Framework (STEM): While the use of statistics in simulation sampling is not new (e.g., SMARTS [43]), the direct application of CLT to derive a closed-form solution for the required sample size based on a desired error bound is a more principled approach than the heuristics used in prior GPU work (e.g., "sample the first kernel" in PKA [2] or a fixed similarity threshold in Photon [21]).
• Adaptive Clustering (ROOT): Prior methods like PKA [2] rely on k-means, which requires a priori selection of k. The proposed ROOT framework, which uses the estimated simulation time savings as a stopping criterion for its hierarchical splitting, is a novel and domain-specific adaptation of clustering that is tightly integrated with the end goal.

The combination of these ideas results in a framework that is not only novel in its approach but also demonstrably less complex in its data collection requirements (profiling overhead in Table 5, page 11) than the prior art it seeks to replace.

Weaknesses

My critique is focused exclusively on the boundaries and robustness of the novel claims.

1. Relationship to and Differentiation from Sieve [24]: The closest prior art is Sieve, which the authors cite. Sieve uses the coefficient of variation (CoV, or σ/μ) of execution times to hand-tune its sampling strategy. The authors must be more explicit about the delta. While this paper elevates the execution time distribution from a tuning heuristic to the core principle, one could argue it is a formalization of an existing idea rather than a completely de novo one. The paper's contribution is clearly significant, but its novelty would be better framed by directly contrasting its systematic, automated framework against Sieve's ad-hoc use of the same underlying signal.

2. Hardware-Dependence of the Signature: The most significant weakness of the novel idea is its reliance on a hardware-dependent signature (execution time). The entire field has historically pursued hardware-independent signatures to ensure portability of sampling data across different architectural simulations. This paper makes a conscious, and seemingly successful, trade-off. However, the limits of this approach are not fully explored. The DSE experiments in Section 5.4 (page 10) show robustness to small changes (cache size, SM count), but this may not hold for more fundamental architectural shifts. For example, sampling on a pre-Tensor Core GPU and simulating a post-Tensor Core GPU would likely produce entirely different execution time distributions for GEMM kernels, potentially invalidating the sampling choices. The novelty of the approach is tied to this trade-off, and its limitations define the scope of the contribution.

Questions to Address In Rebuttal

1. Please explicitly articulate the conceptual leap from Sieve's [24] use of the CoV of execution times for tuning to your use of the full execution time distribution for both clustering (ROOT) and sample size determination (STEM). Is this a formalization of a known heuristic, or a fundamentally different approach?

2. The core novel idea is to use a hardware-dependent signal. Consider an architectural design space exploration scenario where a new hardware feature (e.g., a new memory prefetcher, or specialized execution units like Tensor Cores) is being evaluated. This feature could fundamentally alter the execution time distributions of certain kernels, creating new performance peaks or shifting existing ones. How does your methodology, which relies on a profile from a baseline machine without this feature, guarantee representative sampling for a simulation with this feature? The claims of robustness in Section 5.4 seem limited to scaling existing resources rather than introducing new functional capabilities.

3. The ROOT methodology employs hierarchical clustering by recursively applying a k-means-like partitioning (with k=2). Given that the goal is to isolate peaks in a distribution, have you considered density-based clustering algorithms (e.g., DBSCAN) that could identify an arbitrary number of clusters (peaks) in a single pass? Would such an approach be a more direct implementation of your core insight, or does the recursive binary splitting offer a benefit I am overlooking?