A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> Recent advances in computing have led to an explosion in the amount of data being generated. Processing the ever-growing data in a timely manner has made throughput computing an important aspect for emerging applications. Our analysis of a set of important throughput computing kernels shows that there is an ample amount of parallelism in these kernels which makes them suitable for today's multi-core CPUs and GPUs. In the past few years there have been many studies claiming GPUs deliver substantial speedups (between 10X and 1000X) over multi-core CPUs on these kernels. To understand where such large performance difference comes from, we perform a rigorous performance analysis and find that after applying optimizations appropriate for both CPUs and GPUs the performance gap between an Nvidia GTX280 processor and the Intel Core i7-960 processor narrows to only 2.5x on average. In this paper, we discuss optimization techniques for both CPU and GPU, analyze what architecture features contributed to performance differences between the two architectures, and recommend a set of architectural features which provide significant improvement in architectural efficiency for throughput kernels. <s> BIB001 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> While the correctness of an NVIDIA CUDA program is easy to achieve, exploiting the GPU capabilities to obtain the best performance possible is a task for CUDA experienced programmers. Typical code tuning strategies, like choosing an appropriate size and shape for the thread-blocks, programming a good coalescing, or maximize occupancy, are inter-dependent. Moreover, the choices are also dependent on the underlying architecture details, and the global-memory access pattern of the designed solution. For example, the size and shapes of threadblocks are usually chosen to facilitate encoding (e.g. square shapes), while maximizing the multiprocessors' occupancy. However, this simple choice does not usually provide the best performance results. In this paper we discuss important relations between the size and shapes of threadblocks, occupancy, global memory access patterns, and other Fermi architecture features, such as the configuration of the new transparent cache. We present an insight based approach to tuning techniques, providing lines to understand the complex relations, and to easily avoid bad tuning settings. <s> BIB002 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> Manycore accelerators such as graphics processor units (GPUs) organize processing units into single-instruction, multiple data “cores” to improve throughput per unit hardware cost. Programming models for these accelerators encourage applications to run kernels with large groups of parallel scalar threads. The hardware groups these threads into warps/wavefronts and executes them in lockstep-dubbed single-instruction, multiple-thread (SIMT) by NVIDIA. While current GPUs employ a per-warp (or per-wavefront) stack to manage divergent control flow, it incurs decreased efficiency for applications with nested, data-dependent control flow. In this paper, we propose and evaluate the benefits of extending the sharing of resources in a block of warps, already used for scratchpad memory, to exploit control flow locality among threads (where such sharing may at first seem detrimental). In our proposal, warps within a thread block share a common block-wide stack for divergence handling. At a divergent branch, threads are compacted into new warps in hardware. Our simulation results show that this compaction mechanism provides an average speedup of 22% over a baseline per-warp, stack-based reconvergence mechanism, and 17% versus dynamic warp formation on a set of CUDA applications that suffer significantly from control flow divergence. <s> BIB003 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> The "Basic Local Alignment Search Tool'' (BLAST) is arguably the most widely used computational tool in bioinformatics. However, the computational power required for routine BLAST analysis has been outstripping Moore's Law due to the exponential growth in the size of the genomic sequence databases that BLAST searches on. To address the above issue, we propose the design and optimization of the BLAST algorithm for searching protein sequences (i.e., BLASTP) in a heterogeneous computing system. The end result is a BLASTP implementation that delivers a seven-fold speedup over the sequential BLASTP for the most computationally intensive phase (i.e., hit detection and ungapped extension) on a NVIDIA Fermi C2050 GPU. In addition, when pipelining the processing on a dual-core CPU and the NVIDIA Fermi GPU, our implementation can achieve a six-fold speedup for the overall program execution. <s> BIB004 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> Graphs are a fundamental data representation that has been used extensively in various domains. In graph-based applications, a systematic exploration of the graph such as a breadth-first search (BFS) often serves as a key component in the processing of their massive data sets. In this paper, we present a new method for implementing the parallel BFS algorithm on multi-core CPUs which exploits a fundamental property of randomly shaped real-world graph instances. By utilizing memory bandwidth more efficiently, our method shows improved performance over the current state-of-the-art implementation and increases its advantage as the size of the graph increases. We then propose a hybrid method which, for each level of the BFS algorithm, dynamically chooses the best implementation from: a sequential execution, two different methods of multicore execution, and a GPU execution. Such a hybrid approach provides the best performance for each graph size while avoiding poor worst-case performance on high-diameter graphs. Finally, we study the effects of the underlying architecture on BFS performance by comparing multiple CPU and GPU systems, a high-end GPU system performed as well as a quad-socket high-end CPU system. <s> BIB005 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> This paper describes the 32nm Sandy Bridge processor that integrates up to 4 high performance Intel Architecture (IA) cores, a power/performance optimized graphic processing unit (GPU) and memory and PCIe controllers in the same die. The Sandy Bridge architecture block diagram is shown in Fig. 15.1.1 and the floorplan of a four IA-core version is shown in Fig. 15.1.2. The Sandy Bridge IA core implements an improved branch prediction algorithm, a micro-operation (Uop) cache, a floating point Advanced Vector Extension (AVX), a second load port in the L1 cache and bigger register files in the out-of-order part of the machine; all these architecture improvements boost the IA core performance without increasing the thermal power dissipation envelope or the average power consumption (to preserve battery life in mobile systems). The CPUs and GPU share the same 8MB level-3 cache memory. The data flow is optimized by a high performance on die interconnect fabric (called “ring”) that connects between the CPUs, the GPU, the L3 cache and the system agent (SA) unit that houses a 1600MT/s, dual channel DDR3 memory controller, a 20-lane PCIe gen2 controller, a two parallel pipe display engine, the power management control unit and the testability logic. An on die EPROM is used for configurability and yield optimization. <s> BIB006 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> General Purpose Graphics Processing Units (GPGPUs) operate many threads concurrently, however they demand large DRAM access because of small internal memory size assigned to each thread. As a result, the power consumption in DRAM components becomes increasingly significant. We have examined a few techniques that can reduce DRAM power consumption in GPGPUs. A GPGPU simulator supporting L2 cache is used for this study. The effects of changing the memory channel organization, DRAM clock frequency, row buffer management policy, open or closed, and the L2 cache memory system are studied. Not only the total DRAM energy consumption but also that due to each DRAM operation, such as active-precharge, burst, and background, are estimated. The examined DRAM power reduction techniques bring negligible execution time changes for solving compute-bound problems, but they result in 12–27% savings of DRAM power consumption. <s> BIB007 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> Sparse matrix-vector multiplication is an integral part of many scientific algorithms. Several studies have shown that it is a bandwidth-limited operation on current hardware. On cache-based architectures the main factors that influence performance are spatial locality in accessing the matrix, and temporal locality in re-using the elements of the vector. <s> BIB008 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> SUMMARY Graphical Processing Units (GPUs) are good data-parallel performance accelerators for solving regular mesh partial differential equations (PDEs) whereby low-latency communications and high compute to communications ratios can yield very high levels of computational efficiency. Finite-difference time-domain methods still play an important role for many PDE applications. Iterative multi-grid and multilevel algorithms can converge faster than ordinary finite difference methods but can be much more difficult to parallelise with GPU memory constraints. We report on some practical algorithmic and data layout approaches and on performance data on a range of GPUs with CUDA. We focus on the use of multiple GPU devices with a single CPU host and the asynchronous CPU/GPU communications issues involved. We obtain more than two orders of magnitude of speedup over a comparable CPU core. <s> BIB009 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> We address in this paper the problem of mapping three-dimensional Fast Fourier Transforms (FFTs) onto the recent, highly multithreaded CUDA Graphics Processing Units (GPUs) and present some of the fastest known algorithms for a wide range of 3-D FFTs on the NVIDIA Tesla and Fermi architectures. We exploit the high-degree of multi-threading offered by the CUDA environment while carefully managing the multiple levels of the memory hierarchy in such a way that: (i) all global memory accesses are coalesced into 128-byte device memory transactions issued in such a way as to optimize effects related to partition camping [19], locality [22], and associativity. and (ii) all computations are carried out on the registers with effective data movement involved in shared memory transposition. In particular, the number of global memory accesses to the entire 3-D dataset is minimized and the FFT computations along the X dimension are almost completely overlapped with global memory data transfers needed to compute the FFTs along the Y or Z dimensions. We were able to achieve performance between 135 GFlops and 172 GFlops on the Tesla architecture (Tesla C1060 and GTX280) and between 192 GFlops and 290 GFlops on the Fermi architecture (Tesla C2050 and GTX480). The bandwidths achieved by our algorithms reach over 90 GB/s for the GTX280 and around 140 GB/s for the GTX480. <s> BIB010 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> In this paper we revisit the design of concurrent data structures --- specifically queues --- and examine their performance portability with regard to the move from conventional CPUs to graphics processors. We have looked at both lock-based and lock-free algorithms and have, for comparison, implemented and optimized the same algorithms on both graphics processors and multi-core CPUs. Particular interest has been paid to study the difference between the old Tesla and the new Fermi and Kepler architectures in this context. We provide a comprehensive evaluation and analysis of our implementations on all examined platforms. Our results indicate that the queues are in general performance portable, but that platform specific optimizations are possible to increase performance. The Fermi and Kepler GPUs, with optimized atomic operations, are observed to provide excellent scalability for both lock-based and lock-free queues. <s> BIB011 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> This work presents an efficient CUDA implementation of the Canny edge detection Filter for the Insight Segmentation and Registration Toolkit (ITK). The algorithm is tested on three generations of NVidia GPGPUs, showing performance gains of 3.6 to 50 times when compared to the standard ITK Canny running on two CPU models. The CUDA-enabled Canny is also compared to a more efficient Canny implementation from the OpenCV library. Examples of coding strategies to avoid warp serialization in CUDA are shown on a smart implementation of the Sobel filter, as well as on other algorithms. <s> BIB012 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> This paper uses hardware thread scheduling to improve the performance and energy efficiency of divergent applications on GPUs. We propose Divergence-Aware Warp Scheduling (DAWS), which introduces a divergence-based cache footprint predictor to estimate how much L1 data cache capacity is needed to capture intra-warp locality in loops. Predictor estimates are created from an online characterization of memory divergence and runtime information about the level of control flow divergence in warps. Unlike prior work on Cache-Conscious Wave front Scheduling, which makes re­active scheduling decisions based on detected cache thrashing, DAWS makes proactive scheduling decisions based on cache us­age predictions. DAWS uses these predictions to schedule warps such that data reused by active scalar threads is unlikely to exceed the capacity of the L1 data cache. DAWS attempts to shift the burden of locality management from software to hardware, in­creasing the performance of simpler and more portable code on the GPU. We compare the execution time of two Sparse Matrix Vector Multiply implementations and show that DAWS is able to run a simple, divergent version within 4% of a performance op­timized version that has been rewritten to make use of the on-chip scratchpad and have less memory divergence. We show that DAWS achieves a harmonic mean 26% performance improvement over Cache-Conscious Wavefront Scheduling on a diverse selection of highly cache-sensitive applications, with minimal additional hardware. <s> BIB013 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> General-purpose graphics processing units (GPGPUs) are at their best in accelerating computation by exploiting abundant thread-level parallelism (TLP) offered by many classes of HPC applications. To facilitate such high TLP, emerging programming models like CUDA and OpenCL allow programmers to create work abstractions in terms of smaller work units, called cooperative thread arrays (CTAs). CTAs are groups of threads and can be executed in any order, thereby providing ample opportunities for TLP. The state-of-the-art GPGPU schedulers allocate maximum possible CTAs per-core (limited by available on-chip resources) to enhance performance by exploiting TLP. However, we demonstrate in this paper that executing the maximum possible number of CTAs on a core is not always the optimal choice from the performance perspective. High number of concurrently executing threads might cause more memory requests to be issued, and create contention in the caches, network and memory, leading to long stalls at the cores. To reduce resource contention, we propose a dynamic CTA scheduling mechanism, called DYNCTA, which modulates the TLP by allocating optimal number of CTAs, based on application characteristics. To minimize resource contention, DYNCTA allocates fewer CTAs for applications suffering from high contention in the memory sub-system, compared to applications demonstrating high throughput. Simulation results on a 30-core GPGPU platform with 31 applications show that the proposed CTA scheduler provides 28% average improvement in performance compared to the existing CTA scheduler. <s> BIB014 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> While scalable coherence has been extensively studied in the context of general purpose chip multiprocessors (CMPs), GPU architectures present a new set of challenges. Introducing conventional directory protocols adds unnecessary coherence traffic overhead to existing GPU applications. Moreover, these protocols increase the verification complexity of the GPU memory system. Recent research, Library Cache Coherence (LCC) [34, 54], explored the use of time-based approaches in CMP coherence protocols. This paper describes a time-based coherence framework for GPUs, called Temporal Coherence (TC), that exploits globally synchronized counters in single-chip systems to develop a streamlined GPU coherence protocol. Synchronized counters enable all coherence transitions, such as invalidation of cache blocks, to happen synchronously, eliminating all coherence traffic and protocol races. We present an implementation of TC, called TC-Weak, which eliminates LCC's trade-off between stalling stores and increasing L1 miss rates to improve performance and reduce interconnect traffic. By providing coherent L1 caches, TC-Weak improves the performance of GPU applications with inter-workgroup communication by 85% over disabling the non-coherent L1 caches in the baseline GPU. We also find that write-through protocols outperform a writeback protocol on a GPU as the latter suffers from increased traffic due to unnecessary refills of write-once data. <s> BIB015 </s> A Survey of Techniques for Managing and Leveraging Caches in GPUs <s> Motivations and challenges for designing novel cache management techniques <s> General purpose computing on GPUs (GPGPU) has experienced rapid growth over the last several years as new application realms are explored and traditional highly parallel algorithms are adapted to this computational substrate. However, a large portion of the parallel workload space, both in emerging and traditional domains, remains ill-suited for GPGPU deployment due to high reliance on atomic operations, particularly as global synchronization mechanisms. Unlike the sophisticated synchronization primitives available on supercomputers, GPGPU applications must rely on slow atomic operations on shared data. Further, unlike general purpose processors which take advantage of coherent L1 caches to speed up atomic operations, the cost and complexity of coherency on the GPU, coupled with the fact that a GPU's primary revenue stream - graphics rendering - does not benefit, means that new approaches are needed to improve atomics on the GPU. In this paper, we present a mechanism for implementing low-cost coherence and speculative acquisition of atomic data on the GPU that allows applications that utilize atomics to greater extents than is generally accepted practice today, to perform much better than they do on current hardware. As our results show, these unconventional applications can realize non-trivial performance improvements approaching 20% with our proposed system. With this mechanism, the scope of applications that can be accelerated by these commodity, highly-parallel pieces of hardware can be greatly expanded. <s> BIB016
Achieving a balance between multithreading and cache usage efficiency: GPUs employ deep multithreading by which the control switches among numerous active threads to hide the memory latency. This helps in achieving maximum level of execution parallelism. However, due to deep multithreading, different thread groups may replace the useful blocks of other threads (called interference), which may lead to poor performance BIB002 BIB013 . Use of smaller number of threads alleviates this issue, however, this comes at the cost of reduced execution parallelism BIB014 . Thus, due to availability of multithreading in GPUs, an improvement in cache performance does not directly translate into improved program performance  and hence, intelligent cache management techniques are required for achieving a balance between the two factors. Avoiding off-chip accesses and increasing bandwidth: To provide high performance, GPUs demand very high memory bandwidth. Due to the power-wall problem and the physical limitations of chip-packaging, achieving high bandwidth by increasing clock-frequency or pin-count is extremely challenging. Intelligent cache management policies can be highly useful in such scenarios since they can help in reducing the off-chip accesses by capturing data locality BIB007 BIB001 BIB003 BIB015 BIB008 . This also increases the effective memory bandwidth, which translates into improved performance and energy-efficiency. Several researchers have compared the performance of Tesla and Fermi GPUs and have observed that hardware-managed caches play an important role in offering Fermi GPUs a performance advantage over previous generation GPUs BIB004 BIB009 BIB005 BIB010 BIB011 BIB012 . L2 caches in Fermi also improve the performance of atomic operations BIB016 . Managing shared cache in CPU-GPU heterogeneous computing processors: Since CPUs and GPUs are more suitable for different classes of applications, chip-designers have recently focused on CPU-GPU heterogeneous computing to achieve the best of two worlds. Such chips may feature a last level cache which is shared by both CPU and GPU, for example, on Intel's Sandy Bridge processor, CPU and GPU are on the same chip with a shared on-chip 8MB L3 cache BIB006 . It is well known that CPU and GPU applications have different characteristics and cache requirements, for example, GPUs have very large number of threads and hence, they may access the cache much more frequently, which would lead to starvation of CPU application. Hence, intelligent techniques are extremely important for managing caches in such heterogeneous computing systems. Table 1 presents a classification of the techniques proposed for GPU caches. In the remainder of the section, we summarize the key ideas of several of these techniques.