The Experts below are selected from a list of 6372 Experts worldwide ranked by ideXlab platform
Rami Melhem - One of the best experts on this subject based on the ideXlab platform.
-
adaptive page migration for irregular data intensive applications under gpu Memory oversubscription
International Parallel and Distributed Processing Symposium, 2020Co-Authors: Debashis Ganguly, Ziyu Zhang, Jun Yang, Rami MelhemAbstract:Unified Memory in heterogeneous systems serves a wide range of applications. However, limited capacity of the device Memory becomes a first order performance bottleneck for data-intensive general-purpose applications with increasing working sets. The performance overhead under Memory oversubscription depends on the Memory Access Pattern of the corresponding workload. While a regular application with sequential, dense Memory Access suffers from long latency write-backs, performance of a irregular application with sparse, seldom Access to large data-sets degrades due to page thrashing. Although smart spatio-temporal prefetching and large page eviction yield good performance in general, remote zero-copy Access to host-pinned Memory proves to be beneficial for irregular, data-intensive applications. Further, new generation GPUs introduced hardware Access counters to delay page migration and reduce Memory thrashing. However, the responsibility of deciding what strategy is the best fit for a given application relies heavily on the programmer based on thorough understanding of the Memory Access Pattern through intrusive profiling. In this work, we propose a programmer-agnostic runtime that leverages the hardware Access counters to automatically categorize Memory allocations based on the Access Pattern and frequency. The proposed heuristic adaptively navigates between remote zero-copy Access to host-pinned Memory and first-touch page migration based on the trade-off between low latency remote Access and high-bandwidth local Access. We show that although designed to address Memory oversubscription, our scheme has no impact on performance when working sets fit in the device-local Memory. Experimental results show that our scheme provides performance improvement of 22% to 78% for irregular applications under 125% Memory oversubscription compared to the state of the art. At the same time, regular applications are not impacted by the framework.
-
interplay between hardware prefetcher and page eviction policy in cpu gpu unified virtual Memory
International Symposium on Computer Architecture, 2019Co-Authors: Debashis Ganguly, Ziyu Zhang, Jun Yang, Rami MelhemAbstract:Memory capacity in GPGPUs is a major challenge for data-intensive applications with their ever increasing Memory requirement. To fit a workload into the limited GPU Memory space, a programmer needs to manually divide the workload by tiling the working set and perform user-level data migration. To relieve the programmer from this burden, Unified Virtual Memory (UVM) was developed to support on-demand paging and migration, transparent to the user. It further takes care of the Memory over-subscription issue by automatically performing page replacement in an oversubscribed GPU Memory situation. However, we found that naive handling of page faults can cause orders of magnitude slowdown in performance. Moreover, we observed that although prefetching of data from CPU to GPU can hide the page fault latency, the difference among various prefetching mechanisms can lead to drastically different performance results. To this end, we performed extensive experiments on GeForceGTX 1080ti GPUs with PCI-e 3.0 16x to discover that there exists an effective prefetch mechanism to enhance locality in GPU Memory. However, as the GPU Memory is filled to its capacity, such prefetching mechanism quickly proves to be counterproductive due to locality unaware eviction policy. This necessitates the design of new eviction policies that are aware of the hardware prefetcher semantics. We propose two new programmer-agnostic, locality-aware pre-eviction policies which leverage the mechanics of existing hardware prefetcher and thus incur no additional implementation and performance overhead. We demonstrate that combining the proposed tree-based pre-eviction policy with the hardware prefetcher provides an average of 93% and 18.5% performance speed-up compared to LRU based 4KB and 2MB page replacement strategies, respectively. We further examine the Memory Access Pattern of GPU workloads under consideration to analyze the achieved performance speed-up.
Soonhoi Ha - One of the best experts on this subject based on the ideXlab platform.
-
Memory Access Pattern analysis and stream cache design for multimedia applications
Asia and South Pacific Design Automation Conference, 2003Co-Authors: Chanik Park, Soonhoi HaAbstract:The Memory system is a major performance and power bottleneck in embedded systems especially for multimedia applications. Most multimedia applications Access stream type of data structures with regular Access Patterns. It is observed that conventional caches behave poorly for stream-type data structure. Therefore, prediction-based prefetching techniques have been extensively researched to exploit the regular Access Patterns. Prefetching, however, may pollute the cache if the prediction is not accurate and needs extra hardware prediction logic. To overcome these problems, we propose a novel hardware prefetching technique that is assisted by static analysis of data Access Pattern with stream caches. With the proposed stream cache architecture, we could achieve significant performance improvement compared with the conventional cache architecture.
Elaine Shi - One of the best experts on this subject based on the ideXlab platform.
-
lower bounds for external Memory integer sorting via network coding
Communications of The ACM, 2020Co-Authors: Alireza Farhadi, Mohammadtaghi Hajiaghayi, Kasper Green Larsen, Elaine ShiAbstract:Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main Memory; thus, external Memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external Memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In internal Memory, one can sort a set of n integer keys of Θ(lg n) bits each in O(n) time using the classic Radix Sort algorithm; however, in external Memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external Memory algorithms for more than three decades.In this paper, we present a tight conditional lower bound on the complexity of external Memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the Memory Access Pattern is fixed and independent of the input data). Unfortunately, obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an Ω(n lg n) lower bound for internal Memory oblivious sorting when the keys are Θ(lg n) bits. This is in sharp contrast to the classic (nonoblivious) Radix Sort algorithm. Indeed, going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external Memory integer sorting.
-
lower bounds for external Memory integer sorting via network coding
arXiv: Data Structures and Algorithms, 2018Co-Authors: Alireza Farhadi, Mohammadtaghi Hajiaghayi, Kasper Green Larsen, Elaine ShiAbstract:Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main Memory; thus external Memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external Memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal Memory, one can sort a set of $n$ integer keys of $\Theta(\lg n)$ bits each in $O(n)$ time using the classic Radix Sort algorithm, however in external Memory, there are no faster integer sorting algorithms known than the simple comparison based ones. In this paper, we present a tight conditional lower bound on the complexity of external Memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the Memory Access Pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitations, especially for integer sorting: we show that the Li and Li conjecture implies an $\Omega(n \log n)$ lower bound for internal Memory oblivious sorting when the keys are $\Theta(\lg n)$ bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external Memory integer sorting.
Edward G Suh - One of the best experts on this subject based on the ideXlab platform.
-
reverse engineering convolutional neural networks through side channel information leaks
Design Automation Conference, 2018Co-Authors: Weizhe Hua, Zhiru Zhang, Edward G SuhAbstract:A convolutional neural network (CNN) model represents a crucial piece of intellectual property in many applications. Revealing its structure or weights would leak confidential information. In this paper we present novel reverse-engineering attacks on CNNs running on a hardware accelerator, where an adversary can feed inputs to the accelerator and observe the resulting off-chip Memory Accesses. Our study shows that even with data encryption, the adversary can infer the underlying network structure by exploiting the Memory and timing side-channels. We further identify the information leakage on the values of weights when a CNN accelerator performs dynamic zero pruning for off-chip Memory Accesses. Overall, this work reveals the importance of hiding off-chip Memory Access Pattern to truly protect confidential CNN models.
L J A M Somers - One of the best experts on this subject based on the ideXlab platform.
-
loop transformations leveraging hardware prefetching
Symposium on Code Generation and Optimization, 2018Co-Authors: Savvas Sioutas, Sander Stuijk, Henk Corporaal, Twan Basten, L J A M SomersAbstract:Memory-bound applications heavily depend on the bandwidth of the system in order to achieve high performance. Improving temporal and/or spatial locality through loop transformations is a common way of mitigating this dependency. However, choosing the right combination of optimizations is not a trivial task, due to the fact that most of them alter the Memory Access Pattern of the application and as a result interfere with the efficiency of the hardware prefetching mechanisms present in modern architectures. We propose an optimization algorithm that analytically classifies an algorithmic description of a loop nest in order to decide whether it should be optimized stressing its temporal or spatial locality, while also taking hardware prefetching into account. We implement our technique as a tool to be used with the Halide compiler and test it on a variety of benchmarks. We find an average performance improvement of over 40% compared to previous analytical models targeting the Halide language and compiler.