Allegro: GPU Simulation Acceleration for Machine Learning Workloads

Authors: euijun  chung
seonjin  na
hyesoon  kim
Venue: iscaconf_org_ISCA_2024_Workshop_MLArchSys
Published: 2024-05-03 21:55:35

Abstract: Current GPU simulators face challenges in handling large machine learning workloads like LLMs due to their slow execution. To address this issue, we leverage our observations on the massive number of GPU kernel calls inside these workloads. Given the homogeneous nature and cache-unfriendly behavior of these kernels, we demonstrate that they exhibit identically and independently distributed (i.i.d.) execution times, thus allowing us to apply statistical sampling approaches for accurate GPU kernel sampling.

We introduce Allegro, a practical methodology for GPU simulators that significantly reduces workload size while maintaining low error. Employing a statistical measure with a recursive algorithm, we design an accurate kernel sampling scheme, supported by a proof of theoretical error bounds. 

By integrating Allegro into Macsim, we achieve simulation speedup of 983.96x on 7 of the latest ML workloads with an error rate of 0.057%. Compared to other simulation acceleration techniques, Allegro achieves an average error which is 9.22x smaller than the random sampling method with the speedup value fixed. Additionally, we demonstrate that adjusting the error bound enables the simulator to achieve larger speedups with only a slight increase in error. This flexibility provided by Allegro allows researchers to easily balance desired performance and accuracy.

Main paper: 
 i. introduction: 
 Given the widespread adoption of large-scale Machine Learning (ML) models and their applications, such as Large Language Models (LLMs), their significant computational demands have become a crucial problem [29] . Many researchers are actively seeking methodologies to optimize the hardware architecture of accelerators tailored for machine learning workloads [21] , or to resolve the hidden performance bottlenecks in software perspective [8] . GPU's extensive thread-level parallelism has made them become the predominant accelerator for the ML workloads [24] . Consequently, researchers are actively exploring faster and more energy-efficient GPU architectures to meet the evolving demands of ML tasks.The need for a precise and fast architectural simulator for GPUs is also rising along with their demands. Architectural simulators play an important role in both validating new architectural designs and finding the hidden performance bottlenecks in the processing pipeline. Macsim [23] , AccelSim [22] , and MGPUSim [37] are the most widely used GPU simulators. However, without any optimization techniques applied to the simulators, they suffer from significant slowdowns on running ML workloads, especially on the workloads using the latest Deep Neural Network (DNN) models [2] . Table I shows the relative slowdowns on these simulators compared to the real GPU. Running the latest ML workloads on a simulator is an important issue, as reducing the discrepancy between the simulated and actual GPU usage is critical for accurately validating new architecture designs.A few previous works have been made to speed up architectural simulations. However, methodologies designed for CPU simulations [5] , [13] , [33] do not apply to GPU simulations due to the incomparable amount of thread parallelism inherent in GPUs. Studies on GPU simulations [2] , [25] , [28] have indeed achieved speedups in GPU workloads. However, they do not provide theoretical bounds for sampling error nor they do not leverage the characteristics of GPU kernels utilized in ML workloads to achieve a greater degree of speedup.In this paper, we begin by analyzing the newest ML workloads, specifically focusing on state-of-the-art large language models (LLMs), to identify key insights that can be leveraged to enhance simulation acceleration. Subsequently, we introduce Allegro, a statistic-based sampling approach designed to accurately reduce the GPU simulation time of ML workloads. In summary, our work makes the following contributions:• This paper presents novel insights into the characteristics of the latest ML workloads on GPUs, highlighting that GPU kernels for ML exhibit high homogeneity and identically and independently distributed (i.i.d.) execution times, enabling the adoption of statistical approaches such as the Central Limit Theorem (CLT) and other sampling methods.• We present methodologies demonstrating how statistical theories can be applied to design a simple and accurate measure, which we then utilize to propose Allegro's sampling algorithm. Additionally, we provide mathematical proofs concerning the bounds of error in our approach. Table I presents the simulation rate and the relative slowdown of various GPU simulators, along with the results from a real GPU. The setup environment for experiments is shown in Section V-A. The GPU simulator statistics are sourced from papers (GPGPU-Sim and MGPUSim) [22] , [37] or measured directly (Macsim). Even though generating a single 100-token length sentence with a GPT-2 model takes less than 1 second on a real GPU, the same workload on a GPU simulator takes around a few days, as shown in Table I . It is infeasible to run GPU simulators with the latest ML workloads due to these long simulation times. Therefore, performance optimization techniques for GPU simulators are necessary.There have been numerous efforts to address this performance slowdown. Works such as Simpoint [13] , Barrierpoint [5] , and similar methods [33] propose techniques to accelerate CPU simulations. However, existing CPU solutions are not applicable in the GPU domain due to the massive level of thread parallelism of GPUs [2] .Similar approaches optimized for GPUs have also been proposed, including TBPoint [19] , PKA [2] , Photon [25] , and Sieve [28] . We categorized these solutions as well as other GPU performance modeling techniques as follows. Analytical models ( [15] , [16] , [18] , [27] , [42] ): Building and employing an analytical model for evaluating GPU architectures offers a fast and efficient approach. However, such models may lack accuracy compared to cycle-level simulations, as ensuring the accuracy of analytical models requires regular updates to follow up on the design changes in new GPU architectures. Additionally, such analytical models are not capable of reflecting the impact of certain architectural design changes, such as different cache replacement policies or workload scheduling policies (e.g., warp and block scheduling in GPUs). Early stopping ([2], [28] ): Early stopping simulations after stabilization of IPC is another approach that can yield speedup in simulations. However, in many GPU workloads, it is known that IPCs do not remain stable during the entire workload execution [25] , and this may lead to significant errors in the simulation results. Workload Sampling ([2], [19] , [25] , [28] ): Workload sampling in GPU simulation has been a popular solution due to its effectiveness and acceptable accuracy. TBPoint [19] is the first paper to utilize clustering and sampling for GPU kernels to achieve efficient and accurate sampling. However, this method requires per-application tuning and does not provide sufficient speedup for running modern ML workloads.PKA [2] is a follow-up work that also employs clusterthen-sample and early-stopping techniques on GPU kernels. Although this work demonstrates that GPU kernel sampling can yield simulation speedup for various GPU workloads, it lacks sufficient speedup to run ML workloads and lacks any theoretical explanations of the sampling errors.Photon [25] and Sieve [28] are subsequent works after PKA [2] , and they demonstrate notable speedup on certain workloads. However, these works still rely on empirical kernel classification and sampling techniques.To address these issues, we propose Allegro, an efficient and accurate kernel sampling methodology for ML workloads. We first focus on ML workloads and present several observations indicating that statistical approaches can be applied to model the sampling process. In Section III, we demonstrate that the GPU kernels used in ML workloads are homogeneous and have identically and independently distributed (i.i.d.) execution times. Subsequently, we design an algorithm and a sampling scheme that can accurately and effectively sample the GPU kernels by leveraging these observations. We also prove that the sampling error is theoretically bounded by the given error bound.In this paper, we define ML workloads on GPUs as workloads that utilize ML models, encompassing both inference and training processes. Given the widespread adoption of Python libraries in the ML field, we particularly focus on ML workloads that utilize widely-used libraries such as Tensor-Flow [11] and PyTorch [32] , which leverage NVIDIA GPU libraries such as cuDNN, cuBLAS, etc., under the abstraction layer. While there are some pure C++/CUDA implementations of ML models [3] , [30] , as they are not as commonly used compared to other Python implementations, we focus on the Python-front-end and NVIDIA library-based back-end ML workloads.Modern ML models often employ a repeated block structure across multiple layers. For example, ResNet50 [14] comprises 48 identical convolutional layers, while transformerbased LLMs consist of multiple repetitions of the transformer blocks that consist of a self-attention layer followed by fully connected layers. Moreover, ML workloads typically involve running the same model multiple times for batch iterations. Consequently, we can expect ML workloads to exhibit homogeneity at the GPU kernel level as well.By employing a GPU hardware profiler such as Nsight Systems [31] , we can unveil the kernel calls of ML workloads inside NVIDIA's CUDA libraries. Table II presents an example of a list of kernels alongside the number of calls made throughout the entire ResNet50 workload (refer to Table III for more details). We observe that in ML workloads, the kernels exhibit high repetition, as evidenced by the large number of kernel calls. Moreover, it is well known that the kernel names suggest they are highly optimized-some hand-coded, architecturespecific, and compiler-optimized-for particular GPU architectures, such as the Volta architecture GPU from NVIDIA, as indicated by the presence of "volta" in the kernel names [9] . This indicates that we should focus on the statistics that we can collect at runtime, unlike previous works [2] , [19] , [28] where they only collected statistics that are independent of architecture, such as the number of dynamically executed instructions or the number of memory requests.We also observe that ML workloads do not benefit much from the GPU cache system between the kernel exit and the kernel call. This means that since the memory footprint of GPU kernels in ML workloads is very big, GPU kernels make no use of the cache when they are launched because for the following memory accesses the kernel will only experience cache misses.To investigate this behavior, we conducted an experiment to compare the effect of the cache system in a GPU, with the ResNet50, GPT-2, and Bert workloads (refer to Table III ). We measured the L1 and L2 cache hit rates under two conditions: 1) when the GPU cache is flushed between every kernel call, and 2) when the GPU cache remains intact (baseline).Figure 1 depicts the L1 and L2 cache hit rates of each kernel called within the Bert and ResNet50 workloads. Each kernel's cache hit rate is sorted in ascending order for better visualization.We observe that the L1 cache hit rate shows a very small difference between the two cache scenarios, where the cache flush between the kernel calls is On/Off. In the case of ResNet50, even the L2 hit rates show a similar trend, suggesting that the L2 cache does not significantly contribute to running the workload.These results suggest that the majority of cache hits occur due to memory access locality within the kernel itself, rather than due to the locality between kernels. Consequently, the GPU cache does not substantially benefit consecutive kernels by leveraging data stored in the cache to reduce execution times.Although some workloads show a difference in L2 cache statistics, we empirically discovered that such a difference in L2 cache hit rate does not greatly affect the execution time distribution of kernels, due to the long latency of L2 memory in GPUs. We will discuss about this issue more in the section III-C. Hence, we can infer that the execution times of kernels are independent, as the kernels' execution order does not significantly affect subsequent kernel execution times. Additionally, even if the same kernel is launched multiple times, the cache's impact on kernel execution is minimal, resulting in uniform execution times irrespective of launch location or preceding kernels. In summary, this implies that kernels launched multiple times exhibit identically and independently distributed (i.i.d.) execution time.We utilize Nsight-Systems to visualize the distribution of kernel execution times. We first partition the profiled kernels into kernel groups based on their name, blockSize, and grid-Size, so that we can plot a histogram of execution time. We observed that the histograms exhibit 1) a single narrow peak with a very small standard deviation divided by the mean (σ/µ), or 2) multiple discrete peaks of narrow distributions. The example histograms are shown in Figure 2 .Since most of the GPU kernels' execution time distribution in the histogram has discrete and spread-out peaks, we can employ 1-D k-means clustering to separate them into subgroups, ensuring that each group contains only one narrow peak in the histogram. Then, since each kernel subgroup comprises a high number of kernels with very narrow distributions, we can apply the sampling methodology to significantly shorten simulation times while maintaining high accuracy.In Section IV, we will demonstrate how we can exploit the fact that the execution times of kernels in a subgroup are identically and independently distributed (i.i.d.) by leveraging the Central Limit Theorem (CLT). We will introduce a measure named m min , representing the minimum number of samples required to ensure the error bound. Furthermore, we will outline an algorithm with a scheme for sampling the kernels to accurately predict the total execution time.Although we observed the effects of the L2 cache in some workloads like GPT-2 and BERT (Figure 1 ), we could not observe the impact of L2 caches in the execution time histogram (Figure 2 ), as the histogram of GPT-2 and Bert were not very different from the ones of ResNet50. As shown in the histograms of all three workloads, kernel execution time distributions were very discrete and narrow. Therefore, we assumed that such L2 cache hit rate discrepancy in Figure 1 is negligible for our method of using execution time statistics in sampling.Although we observed the effects of the L2 cache in some workloads like GPT-2 and BERT (Figure 1 ), these effects were not evident in the execution time histograms. The histograms for GPT-2 and BERT were not significantly different from those of ResNet50. As shown in the histograms for all three workloads, kernel execution time distributions were very discrete and narrow. Therefore, we assumed that the L2 cache hit rate discrepancy in Figure 2 is negligible for our method of using execution time statistics in sampling.Figure 3 is an overall diagram of how Allegro performs kernel sampling to accelerate the GPU simulation. We first cluster the GPU kernels into groups based on their name, grid size, and block size. Then, we further subdivide each group with 1-D k-means clustering so that every kernel within a group exhibits a homogeneous execution time.We sample m min kernels from each group, where the value of m min varies for each group. This m min value is a number that is obtained from the error bound calculation, such that the total estimated execution time falls within a specified error bound. The exact equation and the theory behind it are shown in Theorem 2. Following the sampling process, we generate simulation traces only for the sampled kernels and execute the simulation accordingly. In this way, we can drastically reduce the number of GPU kernels in a GPU simulation, achieving a high degree of speedup.We adopt a statistical approach to propose the method for clustering, aiming to ensure that the sampled simulation result closely approximates the outcome of the full simulation within a small error bound.First, we profile the provided ML workload using a GPU hardware profiler, extracting various statistics including execution time, kernel name, block size, and grid size for each kernel. We then partition the kernels into groups based on their kernel name, block size, and grid size. Subsequently, we calculate the mean and variance of execution times for each kernel group.From our observation, we noticed that some kernel groups have multiple peaks in the execution time histogram, which means that even if the kernel has the same name and gridblock size, each kernel may have been used in a different context of the workload. Therefore, we need to split the kernel group into subgroups with homogeneous distribution.To provide a metric for whether a group of kernels needs to be split or not, we exploit the Central Limit Theorem (CLT). The number of samples that we should take depends on the variance of execution time relative to the mean. The following section describes how we designed this metric, so we can recursively apply 1-D K-Means clustering with k = 2 to split the kernels afterwards.Let K be an arbitrary set of N GPU kernels with the same name and grid/block size, and let µ and σ 2 be the mean and variance of the execution time of kernels in K. Assume we are sampling m kernels from K. For any given i ∈ {1, ..., m}, we define a random variable X i to be the execution time of i-th sampled kernel.We can assume that the sequence of random variables {X 1 , X 2 , ..., X m } are independent and identically distributed (i.i.d.) because we observed that the impact of GPU caches are negligible in ML workloads and thus the execution time of a GPU kernel is uniform throughout the full run. We predict the sum of the execution time of every kernel in K as N X where E[X i ] = X. To calculate the error between µ and N X, we use the CLT.Theorem 1 (Central Limit Theorem). Let {X 1 , X 2 , ..., X m } be a sequence of m i.i.d. random variables having a distribution with mean µ and variance σ 2 . Then, the sampled mean X = end for 27: end function a normal distribution with mean µ and variance σ 2 /m as m → ∞.By using CLT and Lemma 4 in the Appendix (Sec. VIII-A), we can approximate that N X follows a normal distribution N (N µ, N 2 σ 2 /m) := N (μ, σ2 ). Then, we can use Theorem 2 below to obtain m min , the minimum number of samples to ensure the error of N X is within the error bound ϵ under 95% confidence.Theorem 2. For a random variable N X, which follows a normal distribution of N (N µ, N 2 σ 2 /m) := N (μ, σ2 ), the minimum number of samples to ensure the error between N X and μ is smaller than the error bound ϵ for 95% confidence is as follows:m min := max 1.96 ϵ σ µ 2 , 30 .Proof. Proof in the Appendix (Section VIII-A).We utilize m min as a metric for each kernel group to assess whether the kernels within the group exhibit homogeneous execution times. The overall algorithm for both the partitioning and clustering process is depicted in Algorithm 1.To predict the total execution time of the whole workload, we apply Algorithm 1 to every kernel group in the workload. Assume we split kernels into k groups {K 1 , K 2 , ..., K k }, and we sample m 1 , m 2 , ..., m k kernels from each group, using the error bound ϵ for all groups. Each m i is derived from the m min of Theorem 2.Let Y * be the ground-truth total execution time, Xi be the average execution time of the sampled kernels from K i , and N i be the number of kernels in K i . Note that Xi 's are normal and mutually independent, i.e., Xi ∼ N (µ i , σ 2 i ) for ∀i ∈ {1, ..., k}. Then, we predict the total execution time as Y = i=1 k N i Xi , and according to Lemma 4, the random variable Y also follows a normal distribution, i.e., Y ∼ N (k i=1 N i µ i , k i=1 N 2 i σ 2 i mi ).In Theorem 3, we ensure that the error of our prediction also falls within the same error bound ϵ with 95% certainty. Theorem 3. If the error between N i Xi and N i µ i is bounded by ϵ with 95% confidence, the error between Y , the prediction for total execution time, and its ground-truthY * = k i=1 N i µ i , is also bounded by ϵ.In other words, the error e between Y and Y * is constrained by the following inequality:e = Y -Y * Y * = 1.96 k i=1 N 2 i σ 2 i mi k i=1 N i µ i ≤ ϵ.Proof. Proof in the Appendix (Section VIII-A).We implemented Algorithm 1 in conjunction with Macsim's trace generation tool [7] to produce traces for the sampled GPU simulation. Macsim is capable of executing NVIDIA GPU simulations with SASS-Assembly in trace-driven mode. By utilizing the sampled trace alongside the sampling information, we generated simulation statistics to predict the outcome of the original workload. All seven latest ML workloads listed in Table III were successfully executed on Macsim. Detailed performance results and error analysis will be discussed in the evaluation section.We used NVIDIA RTX 2080 GPU to evaluate our sampling methodology along with Nsight-systems [31] as GPU hardware profiler. Table III shows the list of ML workloads that are used in this paper. For more information about the workloads, check the Appendix (Section VIII-B).The performance overhead introduced by Allegro is negligible and operates as a one-time cost. While hardware profiling and sampling indeed add performance overhead, they are only incurred during trace generation for GPU simulation and are not incurred during actual simulation execution.In comparison to the time required for trace generation, the time taken for GPU hardware profiling is negligible, being over x1000 less than the trace generation. Additionally, the sampling process itself is also very efficient-we conducted tests on workloads consisting of several million to 50 million kernel calls, and the splitting, clustering, and sampling procedure only took a few minutes to complete. As the sampling information file is generated alongside the simulation traces, there is no additional performance overhead during GPU simulation execution.First, we evaluated how the error bound ϵ affects the speedup of the GPU simulation. We varied the value of ϵ to 1%, 3%, 5%, 10%, and 25% and measured the speedup for each ML workload.Figure 4 illustrates how the speedup value changes as the error bound is increased. We observe that when ϵ = 5%, Allegro can achieve a geometric mean speedup of 983.96x in the given workload simulations, or even more when a larger error bound is used. It is also important to note that the speedup does not scale linearly due to the requirement of sampling at least 30 kernels to satisfy the CLT (Theorem 1).Figure 5 shows the measured error for each given error bound ϵ. When ϵ = 5%, Allegro achieves a geometric mean error of 0.057% in predicting the total execution time of the workloads.Note that the actual error of the total execution time is considerably smaller than the specified error bound ϵ. Also, since the actual error is much smaller than the error bound, increasing the error bound does not significantly affect the actual error. This is because the randomness involved in the clustering stage accounts for most of the actual error. This suggests that there still exists more room to reduce the number of samples, thereby providing more opportunity to enhance the amount of speedup achieved.We also compared the accuracy of Allegro against other sampling methods. For the baseline, we employed random kernel sampling, where we randomly sampled kernels from the entire workload until we achieved the same degree of speedup as Allegro. For instance, if Allegro achieved a 100x speedup on a certain workload, the baseline will randomly sample kernels until the sum of the execution times of the sampled kernels is 1% of the total execution time of the whole workload. Since the baseline method does not utilize information from the profiler as Allegro does, we expect the random sampling to have a larger error than Allegro.We compare the error of the two sampling methods while constraining the amount of speedup. For Allegro, we set ϵ = 5%, and the random sampling method also aimed for the same speedup achieved by Allegro with this error bound.We can observe from Figure 6 that Allegro achieves the highest accuracy on a constrained amount of speedup. In this experiment, Allegro achieved a geomean error of 0.088%, whereas the random sampling achieved a geomean error of 0.81%, which is 9.22 times bigger than our method.We examined scenarios in which the sampling method of Allegro may not achieve notable speedup or where its error could surpass the theoretical prediction. In this section, we provide three categories of workload scenarios where Allegro may encounter its limitations. Cases of Insufficient Speedup: In certain scenarios, Allegro, or the GPU kernel sampling methodology in general, may not achieve a satisfactory level of simulation speedup. If the number of samples is relatively too large compared to the number of kernels in the entire workload, or if the workload itself contains a very small number of kernels, Allegro may not be able to achieve the high degree of speedup observed in ML workloads.For example, in non-ML GPU workloads like the Rodinia benchmark suite [6] , benchmarks such as backprop or lavaMD comprise fewer than 10 GPU kernels. In such cases, Allegro cannot generate a significant level of speedup in GPU simulations. This is because as shown in Theorem 2, Allegro requires more than 30 samples of kernels from each kernel cluster. Thus, kernel clusters containing fewer than 30 kernels would not benefit from Allegro's sampling approach.However, as Allegro operates orthogonal of other simulation-speedup techniques, such as early stopping in PKA [2] or the use of analytical models in GPUMech [18] , there remains further potential to accelerate GPU simulation even after the adoption of Allegro in the simulators. Cases of Non-i.i.d. Kernels: Allegro's sampling methodology runs under the assumption that the execution time of kernels is independent and identically distributed (i.i.d.). In certain GPU workloads, this assumption may not hold, as the performance of GPU kernels may be influenced by other factors such as GPU cache.We've identified two scenarios where we cannot guarantee the independent and identically distributed (i.i.d.) nature of kernel execution times. First, the independence assumption of kernel execution times may be compromised when the execution time of each kernel is influenced by preceding kernels due to GPU caches, leading to inter-dependencies in execution times between kernels. Second, contention on interconnections between other components such as DRAM, CPU, or other GPUs in multi-GPU systems may result in varying execution times depending on the workload phase. Although these scenarios didn't manifest in our tested ML workloads due to their homogeneity and single-GPU environment, it's essential to further investigate how we can quantify workload homogeneity to ensure the i.i.d. nature of kernels. Reduced number of memory requests: In scenarios where GPU simulations require full memory traces, kernel sampling methods may not be a suitable way to expect precise simulation results. For instance, when employing ML workloads to analyze how the workload populates architectural components such as memory, cache, TLB, etc., sampling the small number of kernels and only running them may not let the simulator adequately capture the memory access patterns. This limitation arises due to the significantly reduced number of memory requests compared to running the full workload, potentially leading to incomplete or inaccurate insights into the architectural behavior. Therefore, excessively speeding up simulations using Allegro may compromise the fidelity of the detailed behaviors expected in the simulation.Leveraging Analytical Models for Further Speedup: Designing an analytical model to reduce the workload size after sampling may be a good follow-up work after Allegro. We can further exploit homogeneity and the statistics obtained from hardware profiling to design such an analytical model. Since there exist similar previous works [2] , [19] that utilize methods to accelerate simulation after applying sampling, Allegro can also benefit from analogous approaches. Power estimation on RTL simulations: Workload sampling can offer significant benefits for tasks such as power estimation, particularly in the context of RTL design and simulations. For instance, collecting statistics related to power usage often doesn't necessitate a full workload simulation. By deploying a methodology similar to Allegro on RTL simulators, power measurements can be conducted more efficiently on RTL design and optimization processes.We present Allegro as a novel GPU kernel sampling approach for accelerating GPU simulations on ML workloads characterized by homogeneity and repetition. By utilizing statistical methods to design a sampling scheme, Allegro achieved an average speedup of 983.96x on 7 of the latest ML workloads with an error rate of 0.057%, and achieved 9.22x smaller error in the comparison with the random sampling method. Despite Allegro's limitations with non-uniform or non-ML workloads, its robust mathematical foundation, compatibility with other acceleration methods, and substantial performance improvement set the stage for Allegro for broader adoption and application.Theorem 2. For a random variable N X which follows a normal distribution of N (N µ, N 2 σ 2 /m) := N (μ, σ2 ), the minimum number of samples to ensure the error between N X and μ is smaller than the error bound ϵ for 95% confidence is as follows:EQUATION.Proof. If we assume normal distribution for N X, error bound of N X for 95% confidence is calculated as P (μ -1.96σ ≤ N X ≤ μ + 1.96σ) = 0.95.If we aim for a 5% bound on the error e := (N X-μ) μ with the same level of certainty, we can derive the following inequality: (1)Inequality (1) suggests that if the number of samples m is large enough such that the inequality holds, the error between μ and N X is less than 5% for 95% chance.It is empirically well-known that the Central Limit Theorem (CLT) becomes useful when the sample size m is equal to or greater than 30 [38] . Hence, we define m min , the minimum number of samples required to ensure the error bound, as Equation ( 2) with an arbitrary error bound ϵ > 0.EQUATIONWe also apply a ceiling function to ensure m min is a natural number.Theorem 3. If the error between N i Xi and N i µ i is bounded by ϵ with 95% confidence, the error between Y , the prediction for total execution time, and its ground-truth Proof. For ∀i ∈ {1, ..., k}, m i ≥ ( 1.96 ϵ σi µi ) 2 from Inequality 1. Then, by reordering each side we can get µ 2 i ≥ ( 1.96 ϵ ) 2 σ 2 i mi . By summing up the both side for all i's from 1 to k, we obtainY * = k i=1 N i µ ii N 2 i µ 2 i ≥ ( 1.96 ϵ ) 2 i N 2 i σ 2 i mi . Since N i ≥ 0 and µ i ≥ 0, ( i N i µ i ) 2 ≥ i N 2 i µ 2 i holds. Thus, ( i N i µ i ) 2 ≥ ( 1.96 ϵ ) 2 i N 2 i σ 2 i ni .Taking the square root on each side preserves the inequality direction because both sides are non-negative.i N i µ i ≥ 1.96 ϵ i N 2 i σ 2 i n iGiven that ϵ > 0, we can obtain the original inequality, which infers that the error e is bounded by the error bound ϵ. e = 1.96k i=1 N 2 i σ 2 i mi k i=1 N i µ i ≤ ϵ.Lemma 4. Let {X 1 , X 2 , ..., X m } be mutually independent normal random variables, i.e., X 1 ∼ N (µ 1 , σ 2 1 ), X 2 ∼ N (µ 2 , σ 2 2 ), and so on. Then, for any a 1 , a 2 , ..., a m ∈ R, the linear combination Y = a 1 X 1 + a 2 X 2 + ... + a m X m also follows a normal distribution of Y ∼ N (Σ m i=1 a i µ i , Σ m i=1 a 2 i σ 2 i ).Proof. A set of n independent normal random variables is equivalent to an n × 1 vector having a multivariate normal distribution with a diagonal covariance matrix. We define a random vector x as follows: x = [X 1 X 2 ... X n ] T ∼ N (µ, Σ) where µ = [µ 1 µ 2 ... µ n ] T and Σ = diag(σ 2 1 , σ 2 2 , ..., σ 2 n ). Let a constant matrix A = [a 1 a 2 ... a n ] and a vector b = 0. Then, by applying the linear transformation theorem for the multivariate normal distribution [1] , [36] = N (Σ n i=1 a i µ i , Σ n i=1 a 2 i σ 2 i ).We downloaded every ML model in Table III from Huggingface [20] . Below are the URLs to Huggingface repositories of the models and datasets that we used for the ML workloads. 
 
 Appendix:  


Decision: Congratulations! We are pleased to inform you that your paper has been accepted for presentation at MLArchSys 2024. We look forward to your participation at the workshop. Further details regarding the schedule and format will be provided soon. See you at the workshop!

Reviews: review: title: title: Accelerating GPU simulation for ML workloads with statistical analysis
strength_weakness: strength_weakness: -- The paper attempts to bring up some of the limitations of Allegro, however, the paper does not discuss scenarios where kernels that are not truly i.i.d. or where the full memory traces are needed.

-- The experimental results show significant speedup, but the evaluation seems still limited. For example, it was not clear how training/inference would impact the results. Also, it could help to show comparison with some of the previous techniques that the authors mentioned in the paper. 

-- (nit) The paper exceeds the page limit for the workshop.
questions: questions: The paper clearly motivates the issue of slow GPU simulation for ML workloads and highlights the need for efficient acceleration techniques (with high accuracy). The proposed method, Allegro, uses statistical method, based on the homogeneity and i.i.d. nature of ML kernels which is a good contribution for the workshop. The method is supported by a strong theoretical foundation, including error bounds and analysis of kernel execution time distribution. Finally the results show promising results, high speedup with low error. Here are some questions/feedback:

(1) Could you elaborate on the limitations of Allegro in scenarios where the assumption of i.i.d. kernel execution times is not met? How does that impact the accuracy of your method? Is it possible to extend Allegro to handle these cases, perhaps by incorporating techniques for detecting and addressing non-i.i.d. behavior?

(2) I did not see comparison against other methods (speedup/error) in simulating ML workloads on GPUs.

(3) Do we need to do the entire sampling procedure for each GPU hardware + Compiler? How do you plan to handle differences in the GPU compilation workflow?

(4) It would be great if the authors consider releasing the code and scripts of Allegro.
title: title: Good theoretical proofs for error bounds, but evaluation does not fully validate its usefulness/accuracy
strength_weakness: strength_weakness: 1. Problem is not well motivated.  Why should I go for simulation of LLMs on GPUs? Isn't analytical model enough? Even in the results the error is shown for the execution time prediction and not for other useful metrics. 

2. Not sure of the pattern in Fugure 5, hence I doubt the accuracy/usefulness of the theoretical proof

3. Evaluation needs to be stronger
questions: questions: 1. How is faster simulation for LLMs helping? Isn't analytical modeling more convenient? Motivate your problem better
2. The cited analytical models are quite old and for generic applications. What about the newer analytical models such as "Performance Modeling and Scalability Optimization of Distributed Deep Learning Systems" or "AMPeD: An Analytical Model for Performance in Distributed Training of Transformers" that are specific for CNNs and transformers, respectively? 
3. Is Allegro open-source?
4. I am not very sure when you say that the name of GPU architecture in the kernel names suggests that they are optimized for that GPU.  Is it a well-established fact from some source or just a guess?
5. In section III.B, the L2 hit rate for BERT is different for flush on and off. So that means Allegro is not valid for Bert, is that so?
6. Could you show the histogram for Bert kernels too in Figure 2 for more confidence?
7. Explain the pattern for Figure 5. Is there any pattern or correlation? When the error bound is lower, the measured error is higher for some workloads while opposite for other workloads. The trends are not the same for the workloads while it is not the case in Figure 4. Does this mean that the theoretical bounds are not accurate enough?
8. Figure 6 shows the error only in execution times of the workloads. Shouldn't the error be validated for other metrics too such as cache misses, hits, IPCs, memory accesses? The purpose of going for detailed simulation is to be able to predict these metrics otherwise one can go for analytical models, which are quite accurate in predicting the execution times. 
9. On page 7, you say "Although these scenarios didn't manifest our tested ML workloads"  while it clearly appeared in BERT in figure 1. There was a dependence on GPU caches and hence IID can't be claimed. Is that right?
title: title: Interesting paper on static sampling method to optimize GPU simulation
strength_weakness: strength_weakness: 1) As was mentioned by the paper itself, sampling is limited for homogenous and cache-unfriendly workloads only, hence project's impact is limited and might not be useful for more complicated, practical and exciting projects.  
2) Accordingly, its potential for more discussions might be rather limited as per workshop goals. 
3) Concerned about the idea of directly sourcing the latency numbers from other papers as a direct comparison, given setup, application and environment variables might be totally different.
questions: questions: This paper presents very useful sampling optimization for GP-GPU simulation. This way, researchers and developers can cut/sample the number of to-be-simulated traces before simulation actually starts, and can gain a huge speedup for certain set of applications. Particularly, this method is based on observations that many ML workloads are pretty homogenous and cache-unfriendly, which includes well-known apps like Resnet and Gemma. Despite the fact, this solution might not be useful for more complex ML apps that employ elaborate optimization tricks, or for fetching more fine grain architectural performance counters, high-level observations can be very handy for early stage research and proof of hypothesis which are also very important.
title: title: Simple approach with theoretical guarantee and great results. Evaluation can be improved.
strength_weakness: strength_weakness: * Applicability of the approach to workloads with generated fused kernels
* Evaluation on only single-device workloads (no evaluation on communication kernels)
* Missing some technical details
questions: questions: The paper shows excellent results compared to existing works in terms of both accuracy and speedup. The simulation errors are extremely small: less than 1% in most cases. The simulation time speedup over existing systems is impressive. The paper also builds on a nice insight that most GPU kernels in ML workloads are independent of other kernels. Therefore, we can measure the runtime of each kernel independently (no need to set up a context). The proposed approach is simple, sampling based on the Central Limit Theorem, which also provides a theoretical guarantee on an error bound. 

One concern with this approach is that although it doesn’t require hardware during the simulation execution, it still requires hardware to sample the kernels’ runtime in advance. If most workloads share the same common sets of GPU kernels, then we can pre-sample all common kernels. However, if a workload includes kernels that are not pre-sampled, then this approach wouldn’t work. While in the past, most frameworks (PyTorch and TensorFlow) depends on CuDNN/CuBLAS kernels, they now move to a code generation strategy (e.g. PyTorch 2.0 generates Triton kernels). In this paradigm, there is a high chance that generated kernels (arbitrary fusions of multiple ops) won’t be part of the pre-sampled set.

 
The major weakness of the paper is that only workloads on a single device are evaluated. This means that the majority of the kernels are compute kernels, and there is no communication operation. We know that communication and compute kernels utilize dramatically different sets of resources and exhibit very different characteristics. Communication is also required in the most capable models like LLMs. Therefore, for the simulation to be useful, it also has good accuracy on communication kernels.

While the paper is mostly well written, it misses some important technical details. The simulation execution is extremely short, and it doesn’t explain at all how the simulation execution utilizes the pre-sampled data. I assume that all kernels must be profiled offline in advance, but the paper doesn’t explicitly mention that. Next, during the simulation, does the simulator then sample a runtime of the kernel from the modeled Gaussian distribution. In the case where a single kernel has multiple clusters (e.g. volta_sgemm_128x64_nn), how does the simulator decide which cluster to use during the simulation?

The random kernel sampling experiment requires more explanation. I don’t understand the setup and how it is different from the proposed method. I also don’t understand the discussion around the case of insufficient speedup, perhaps because I don’t understand how the simulation execution actually utilizes the samples. If sampling is done offline (before simulation), then there should be any slowdown using this method.