Search

Graphics processing units (GPUs) are powerful in performing data-parallel applications. Such applications most often rely on the GPU’s memory hierarchy to deliver high performance. Designing efficient memory hierarchy for GPUs is a challenging task because of its wide architectural space. To moderate this challenge, this paper proposes a framework, called stack distance-analytic modeling (SDAM), to estimate memory performance of the GPU in terms of memory cycle counts. Providing the input data to the model is crucial in terms of the accuracy of the input data, and the time spent to obtain them. SDAM employs the stack distance analysis method and analytical modeling to obtain the required input accurately and swiftly. Further, it employs a detailed analytical model to estimate memory cycles. SDAM is validated against real GPU executions. Further, it is compared with a cycle accurate simulator. The experimental evaluations, performed on a set of memory-intensive benchmarks, prove that SDAM is faster and more accurate than cycle-accurate simulation, thus it can facilitate the GPU cache design-space exploration. For a selection of data-intensive benchmarks, SDAM showed a 32% average error in estimating memory data transfer cycles in a modern GPU, which outperforms cycle-accurate simulation, while it is an order of magnitude faster than the cycle-accurate simulation. Finally, the applicability of SDAM in exploring cache design-space in GPUs is demonstrated through experimenting with various cache designs.

Stack distance characterizes temporal locality of workloads and plays a vital role in cache analysis since the 1970s. However, exact stack distance calculation is too costly, and impractical for online use. Hence, much work was done to optimize the exact computation, or approximate it through sampling or modeling. This paper introduces a new approximation technique PG2S that is based on reference popularity and gap distance. This approximation is exact under the Independent Reference Model (IRM). The technique is further extended, using machine learning, to PG2S+ for non-IRM reference patterns. Extensive experiments show that PG2S+ is much more accurate and robust than other state-of-the-art algorithms for determining stack distance. PG2S+ is the first technique to exploit the strong correlation among reference popularity, gap distance and stack distance.

Mutation testing is a means to assess the effectiveness of a test suite and its outcome is considered more meaningful than code coverage metrics. However, despite several optimizations, mutation testing requires a significant computational effort and has not been widely adopted in industry. Therefore, we study in this paper whether test effectiveness can be approximated using a more light-weight approach. We hypothesize that a test case is more likely to detect faults in methods that are close to the test case on the call stack than in methods that the test case accesses indirectly through many other methods. Based on this hypothesis, we propose the minimal stack distance between test case and method as a new test measure, which expresses how close any test case comes to a given method, and study its correlation with test effectiveness. We conducted an empirical study with 21 open-source projects, which comprise in total 1.8 million LOC, and show that a correlation exists between stack distance and test effectiveness. The correlation reaches a strength up to 0.58. We further show that a classifier using the minimal stack distance along with additional easily computable measures can predict the mutation testing result of a method with 92.9% precision and 93.4% recall. Hence, such a classifier can be taken into consideration as a light-weight alternative to mutation testing or as a preceding, less costly step to that., EASE 2019

The replacement policies known as MIN and OPT are optimal for a two-level memory hierarchy. The computation of the cache content for these policies requires the off-line knowledge of the entire address trace. However, the stack distance of a given access, that is, the smallest capacity of a cache for which that access results in a hit, is independent of future accesses and can be computed on-line. Off-line and on-line algorithms to compute the stack distance in time O(V) per access have been known for several decades, where V denotes the number of distinct addresses within the trace. The off-line time bound was recently improved to O(√V log V). This paper introduces the Critical Stack Algorithm for the online computation of the stack distance of MIN and OPT, in time O(log V) per access. The result exploits a novel analysis of properties of OPT and data structures based on balanced binary trees. A corresponding Ω(log V) lower bound is derived by a reduction from element distinctness; this bound holds in a variety of models of computation and applies even to the off-line simulation of just one cache capacity.

Power is arguably the critical resource in computer system design today. In this work, we focus on maximizing performance of a chip multiprocessor (CMP) system, for a given power budget, by developing techniques to budget power between processor cores and caches. Dynamic cache configuration can reduce cache capacity and associativity, thereby freeing up chip power, but may increase the miss rate (and potentially memory power). Dynamic voltage and frequency scaling (DVFS) can exploit the saved power to increase core performance, potentially increasing system performance. Detailed simulation models show that carefully budgeting power between cores and caches can improve system performance 2-16% for 11 of 17 workloads. To intelligently budget power between cores and caches, we investigate using hardware support to drive analytical models of system power and performance. Online estimation enables real-time feedback and adaptation to dynamic changes such as operating system interactions or changing workload mixes. We demonstrate an integrated online framework that combines a cache reuse model, performance model, power model and DVFS model to identify optimal power-budgeted configurations.

Memory caches significantly improve the performance of workloads that have temporal and spatial locality by providing faster access to data. Current processor designs have multiple cores sharing a cache. To accurately model a workload performance and to improve system throughput by intelligently scheduling workloads on cores, we need to understand how sharing caches between workloads affects their data accesses.Past research has developed analytical models that estimate the cache behavior for combined workloads given the stack distance profiles describing these workloads. We extend this research by presenting an analytical model with contributions to accuracy and composability - our model makes fewer simplifying assumptions than earlier models, and its output is in the same format as its input, which is an important property for hierarchical composition during software performance modeling.To compare the accuracy of our analytical model with earlier models, we attempted to reproduce the reported accuracy of those models. This proved to be difficult. We provide additional insight into the major factors that influence analytical model accuracy.

We develop a reuse distance/stack distance based analytical modeling framework for efficient, online prediction of cache performance for a range of cache configurations and replacement policies LRU, PLRU, RANDOM, NMRU. Such a predictive framework can be extremely useful in selecting the optimal parameters in a dynamic reconfiguration environment that performs power-shifting or resource reallocation through cache partitioning. Our framework unifies existing cache miss-rate prediction techniques such as Smith?s associativity model, Poisson variants, and hardware way-counter based schemes. We also show how to adapt way-counters to work when the number of sets in the cache changes. We propose a novel low-overhead hardware mechanism to estimate reuse distance/stack distance distributions using a combination of set-sampling and time-sampling. This can be used even in cases where using way-counters is not possible, e.g. RANDOM/NMRU replacement policies.

In Chip Multi-Processors (CMPs) with private L2 caches, to combine the strengths of private and shared caches, private caches can share capacity through spilling replaced blocks to other private caches. However, indiscriminate spilling can make the capacity problem worse and influence performance negatively. This paper proposes throttling capacity sharing (TCS) for effective capacity sharing. TCS determines whether to spill a replaced block by predicting its reuse possibility based on stack distance. We evaluate the performance improvement of TCS in a 4 core system. TCS improves weighted speedup on average by 54.64%, 5.34% and 7.21% compared to no spilling, Cooperative Caching (CC) with best spill probability and Dynamic Spill-Receive (DSR), respectively.

The worst-case execution time (WCET) analysis is critical to ensure the schedulability and correctness of hard real-time systems. Modern microprocessors, however, make the WCET analysis complicated, mainly because of their performance acceleration features like caches, pipelines, out-of-order execution, etc. This paper focuses on studying an accurate static timing analysis approach for instruction caches with the LRU-based strategy by computing the worst-case stack distance. The experimental results indicate that our approach can accurately predict worst-case instruction cache performance. Also, the stack distance based timing analysis approach can efficiently categorize worst-case instruction cache misses into cold, conflict and capacity misses, which can provide useful insights to improve the worst-case instruction cache performance.

Reducing the cost of program memory access can improve program performance. In this paper, a scheduling approach based on coherency and thread affinity has been introduced which is able to estimate scheduling cost according to the number of common data blocks and their coherency cost. The estimated results are used to find the appropriate thread mapping to cores so that the number of common data blocks between cores and their coherence cost are reduced. In the proposed model, the effect of shared cache size on affinity and coherency is considered. Since the shared cache behavior on different architectures is not the same and changes according to the cache size, stack distance analysis is used to estimate the behavior of shared cache on different architectures. Finally, the model is evaluated by a synthetic application and SPLASH-2 benchmark.

Efficient execution on modern architectures requires good data locality, which can be measured by the powerful stack distance abstraction. Based on this abstraction, the miss rate for LRU caches of any size can be predicted. However, measuring stack distance requires the number of unique memory objects to be counted between successive accesses to the same data object, which requires complex and inefficient data collection.