The Experts below are selected from a list of 180 Experts worldwide ranked by ideXlab platform
Rakesh Kumar - One of the best experts on this subject based on the ideXlab platform.
-
Branch and Data Herding: Reducing Control and Memory Divergence for Error-Tolerant GPU Applications
IEEE Transactions on Multimedia, 2013Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads within the same execution bundle, or warp, have been shown to cause significant performance bottlenecks for GPU applications. In this paper, we exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications.
-
branch and data herding reducing Control and memory Divergence for error tolerant gpu applications
International Conference on Parallel Architectures and Compilation Techniques, 2012Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads in the same execution bundle, or warp, can significantly throttle the performance of GPU applications. We exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil [7] benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications. For a more detailed exposition of this work, see [6].
-
PACT - Branch and data herding: reducing Control and memory Divergence for error-tolerant GPU applications
Proceedings of the 21st international conference on Parallel architectures and compilation techniques - PACT '12, 2012Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads in the same execution bundle, or warp, can significantly throttle the performance of GPU applications. We exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil [7] benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications. For a more detailed exposition of this work, see [6].
Shaojun Wei - One of the best experts on this subject based on the ideXlab platform.
-
Triggered-Issuance and Triggered-Execution: A Control Paradigm to Minimize Pipeline Stalls in Distributed Controlled Coarse-Grained Reconfigurable Arrays
IEEE Transactions on Parallel and Distributed Systems, 2018Co-Authors: Leibo Liu, Shouyi Yin, Yangdong Deng, Jian Weng, Yiyu Shi, Shaojun WeiAbstract:Distributed Controlled coarse-grained reconfigurable arrays (CGRAs) enable efficient execution of irregular Control flows by reconciling Divergence in the processing elements (PEs). To further improve performance by better exploiting spatial parallelism, the triggered instruction architecture (TIA) eliminates the program counter and branch instructions by converting Control flows into predicate dependencies as triggers. However, pipeline stalls, which occur in pipelines composed of both intra and inter-PEs, remain a major obstacle to the overall performance. In fact, the stalls in distributed Controlled CGRAs pose a unique problem that is difficult to resolve by previous techniques. This work presents a triggered-issuance and triggered-execution (TITE) paradigm in which the issuance and execution of instructions are separately triggered to further relax the predicate dependencies in TIA. In this paradigm, instructions are paired as dual instructions to eliminate stalls caused by Control Divergence. Tags that identify the data transmitted between PEs are forwarded for acceleration. As a result, pipeline stalls of both intra- and inter-PEs can be significantly minimized. Experiments show that TITE improves performance by 21 percent, energy efficiency by 17 percent, and area efficiency by 12 percent compared with a baseline TIA.
-
FPGA - A Novel Composite Method to Accelerate Control Flow on Reconfigurable Architecture (Abstract Only)
Proceedings of the 2015 ACM SIGDA International Symposium on Field-Programmable Gate Arrays, 2015Co-Authors: Junbin Wang, Leibo Liu, Jianfeng Zhu, Shouyi Yin, Shaojun WeiAbstract:Reconfigurable Architecture provides a promising solution for embedded systems for high performance, low power and flexibility. Control dependence and Control Divergence are critical problems that impact the performance. Many methods were proposed to handle Control flows efficiently, such as predicated execution and speculative execution. However, they exhibit different performances for different types of Control flows, so composite methods are required to provide overall optimal performance. In this paper, a novel architecture is proposed which combines Triggered Instruction and parallel condition. It is designed on the basis of triggered instruction architecture (TIA) while each PE incorporates multiple arithmetic logic units with fast mutual Control as in the technique of parallel condition. It can remove branch instructions as well as parallelize Control and compute instructions without reconciliation operation, so it explores parallelism in branch level while avoids over-serialization execution in program-counter-based PE. The experiment was conducted on a model in C language and the result shows that the proposed architecture can achieve 80.0% higher performance on average than TIA.
John Sartori - One of the best experts on this subject based on the ideXlab platform.
-
Branch and Data Herding: Reducing Control and Memory Divergence for Error-Tolerant GPU Applications
IEEE Transactions on Multimedia, 2013Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads within the same execution bundle, or warp, have been shown to cause significant performance bottlenecks for GPU applications. In this paper, we exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications.
-
branch and data herding reducing Control and memory Divergence for error tolerant gpu applications
International Conference on Parallel Architectures and Compilation Techniques, 2012Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads in the same execution bundle, or warp, can significantly throttle the performance of GPU applications. We exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil [7] benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications. For a more detailed exposition of this work, see [6].
-
PACT - Branch and data herding: reducing Control and memory Divergence for error-tolerant GPU applications
Proceedings of the 21st international conference on Parallel architectures and compilation techniques - PACT '12, 2012Co-Authors: John Sartori, Rakesh KumarAbstract:Control and memory Divergence between threads in the same execution bundle, or warp, can significantly throttle the performance of GPU applications. We exploit the observation that many GPU applications exhibit error tolerance to propose branch and data herding. Branch herding eliminates Control Divergence by forcing all threads in a warp to take the same Control path. Data herding eliminates memory Divergence by forcing each thread in a warp to load from the same memory block. To safely and efficiently support branch and data herding, we propose a static analysis and compiler framework to prevent exceptions when Control and data errors are introduced, a profiling framework that aims to maximize performance while maintaining acceptable output quality, and hardware optimizations to improve the performance benefits of exploiting error tolerance through branch and data herding. Our software implementation of branch herding on NVIDIA GeForce GTX 480 improves performance by up to 34% (13%, on average) for a suite of NVIDIA CUDA SDK and Parboil [7] benchmarks. Our hardware implementation of branch herding improves performance by up to 55% (30%, on average). Data herding improves performance by up to 32% (25%, on average). Observed output quality degradation is minimal for several applications that exhibit error tolerance, especially for visual computing applications. For a more detailed exposition of this work, see [6].
Leibo Liu - One of the best experts on this subject based on the ideXlab platform.
-
Triggered-Issuance and Triggered-Execution: A Control Paradigm to Minimize Pipeline Stalls in Distributed Controlled Coarse-Grained Reconfigurable Arrays
IEEE Transactions on Parallel and Distributed Systems, 2018Co-Authors: Leibo Liu, Shouyi Yin, Yangdong Deng, Jian Weng, Yiyu Shi, Shaojun WeiAbstract:Distributed Controlled coarse-grained reconfigurable arrays (CGRAs) enable efficient execution of irregular Control flows by reconciling Divergence in the processing elements (PEs). To further improve performance by better exploiting spatial parallelism, the triggered instruction architecture (TIA) eliminates the program counter and branch instructions by converting Control flows into predicate dependencies as triggers. However, pipeline stalls, which occur in pipelines composed of both intra and inter-PEs, remain a major obstacle to the overall performance. In fact, the stalls in distributed Controlled CGRAs pose a unique problem that is difficult to resolve by previous techniques. This work presents a triggered-issuance and triggered-execution (TITE) paradigm in which the issuance and execution of instructions are separately triggered to further relax the predicate dependencies in TIA. In this paradigm, instructions are paired as dual instructions to eliminate stalls caused by Control Divergence. Tags that identify the data transmitted between PEs are forwarded for acceleration. As a result, pipeline stalls of both intra- and inter-PEs can be significantly minimized. Experiments show that TITE improves performance by 21 percent, energy efficiency by 17 percent, and area efficiency by 12 percent compared with a baseline TIA.
-
FPGA - A Novel Composite Method to Accelerate Control Flow on Reconfigurable Architecture (Abstract Only)
Proceedings of the 2015 ACM SIGDA International Symposium on Field-Programmable Gate Arrays, 2015Co-Authors: Junbin Wang, Leibo Liu, Jianfeng Zhu, Shouyi Yin, Shaojun WeiAbstract:Reconfigurable Architecture provides a promising solution for embedded systems for high performance, low power and flexibility. Control dependence and Control Divergence are critical problems that impact the performance. Many methods were proposed to handle Control flows efficiently, such as predicated execution and speculative execution. However, they exhibit different performances for different types of Control flows, so composite methods are required to provide overall optimal performance. In this paper, a novel architecture is proposed which combines Triggered Instruction and parallel condition. It is designed on the basis of triggered instruction architecture (TIA) while each PE incorporates multiple arithmetic logic units with fast mutual Control as in the technique of parallel condition. It can remove branch instructions as well as parallelize Control and compute instructions without reconciliation operation, so it explores parallelism in branch level while avoids over-serialization execution in program-counter-based PE. The experiment was conducted on a model in C language and the result shows that the proposed architecture can achieve 80.0% higher performance on average than TIA.
Jayvant Anantpur - One of the best experts on this subject based on the ideXlab platform.
-
Enhancing GPGPU Performance through Warp Scheduling, Divergence Taming and Runtime Parallelizing Transformations
2017Co-Authors: Jayvant AnantpurAbstract:There has been a tremendous growth in the use of Graphics Processing Units (GPU) for the acceleration of general purpose applications. The growth is primarily due to the huge computing power offered by the GPUs and the emergence of programming languages such as CUDA and OpenCL. A typical GPU consists of several 100s to a few 1000s of Single Instruction Multiple Data (SIMD) cores, organized as 10s of Streaming Multiprocessors (SMs), each having several SIMD cores which operate in a lock-step manner, o ering a few TeraFLOPS of performance in a single socket. SMs execute instructions from a group of consecutive threads, called warps. At each cycle, an SM schedules a warp from a group of active warps and can context switch among the active warps to hide various stalls. However, various factors, such as global memory latency, Divergence among warps of a thread block (TB), branch Divergence among threads of a warp (Control Divergence), number of active warps, etc., can significantly impact the ability of a warp scheduler to hide stalls. This reduces the speedup of applications running on the GPU. Further, applications containing loops with potential cross iteration dependences, do not utilize the available resources (SIMD cores) effectively and hence su er in terms of performance. In this thesis, we propose several mechanisms which address the above issues and enhance the performance of GPU applications through efficient warp scheduling, taming branch and warp Divergence, and runtime parallelization. First, we propose RLWS, a Reinforcement Learning (RL) based Warp Scheduler which uses unsupervised learning to schedule warps based on the current state of the core and the long-term benefits of scheduling actions. As the design space involving the state variables used by the RL and the RL parameters (such as learning and exploration rates, reward and penalty values, etc.) is large, we use a Genetic Algorithm to identify the useful subset of state variables and RL parameter values. We evaluated the proposed RL based scheduler using the GPGPU-SIM simulator on a large number of applications from the Rodinia, Parboil, CUDA-SDK and GPGPU-SIM benchmark suites. Our RL based implementation achieved an average speedup of 1.06x over the Loose Round Robin (LRR) strategy and 1.07x over the Two-Level (TL) strategy. A salient feature of RLWS is that it is robust, i.e., performs nearly as well as the best performing warp scheduler, consistently across a wide range of applications. Using the insights obtained from RLWS, we designed PRO, a heuristic warp scheduler which in addition to hiding the long latencies of certain operations, reduces the waiting time of warps at synchronization points. Evaluation of the proposed algorithm using the GPGPU-SIM simulator on a diverse set of applications showed an average speedup of 1.07x over the LRR warp scheduler and 1.08x over the TL warp scheduler. In the second part of the thesis, we address problems due to warp and branch Divergences. First, many GPU kernels exhibit warp Divergence due to various…
-
CC - Taming Control Divergence in GPUs through Control Flow Linearization
Lecture Notes in Computer Science, 2014Co-Authors: Jayvant Anantpur, Ramaswamy GovindarajanAbstract:Branch Divergence is a very commonly occurring performance problem in GPGPU in which the execution of diverging branches is serialized to execute only one Control flow path at a time. Existing hardware mechanism to reconverge threads using a stack causes duplicate execution of code for unstructured Control flow graphs. Also the stack mechanism cannot effectively utilize the available parallelism among diverging branches. Further, the amount of nested Divergence allowed is also limited by depth of the branch Divergence stack.