The Experts below are selected from a list of 29142 Experts worldwide ranked by ideXlab platform
John A. Stratton - One of the best experts on this subject based on the ideXlab platform.
-
Data Layout Transformation Exploiting Memory-Level Parallelism in Structured Grid Many-Core Applications
International Journal of Parallel Programming, 2012Co-Authors: I-jui Sung, Nasser Anssari, John A. StrattonAbstract:We present automatic data layout transformation as an effective compiler performance optimization for Memory-Bound structured grid applications. Structured grid applications include stencil codes and other code structures using a dense, regular grid as the primary data structure. Fluid dynamics and heat distribution, which both solve partial differential equations on a discretized representation of space, are representative of many important structured grid applications. Using the information available through variable-length array syntax, standardized in C99 and other modern languages, we enable automatic data layout transformations for structured grid codes with dynamically allocated arrays. We also present how a tool can guide these transformations to statically choose a good layout given a model of the Memory system, using a modern GPU as an example. A transformed layout that distributes concurrent Memory requests among parallel Memory system components provides substantial speedup for structured grid applications by improving their achieved Memory-level parallelism. Even with the overhead of more complex address calculations, we observe up to 10.94X speedup over the original layout, and a 1.16X performance gain in the worst case.
-
data layout transformation exploiting Memory level parallelism in structured grid many core applications
International Conference on Parallel Architectures and Compilation Techniques, 2010Co-Authors: I-jui Sung, John A. StrattonAbstract:We present automatic data layout transformation as an effective compiler performance optimization for Memory-Bound structured grid applications. Structured grid applications include stencil codes and other code structures using a dense, regular grid as the primary data structure. Fluid dynamics and heat distribution, which both solve partial differential equations on a discretized representation of space, are representative of many important structured grid applications. Using the information available through variable-length array syntax, standardized in C99 and other modern languages, we have enabled automatic data layout transformations for structured grid codes with dynamically allocated arrays. We also present how a tool can guide these transformations to statically choose a good layout given a model of the Memory system, using a modern GPU as an example. A transformed layout that distributes concurrent Memory requests among parallel Memory system components provides substantial speedup for structured grid applications by improving their achieved Memory-level parallelism. Even with the overhead of more complex address calculations, we observe up to 560% performance increases over the language-defined layout, and a 7% performance gain in the worst case, in which the language-defined layout and access pattern is already well-vectorizable by the underlying hardware.
I-jui Sung - One of the best experts on this subject based on the ideXlab platform.
-
Data Layout Transformation Exploiting Memory-Level Parallelism in Structured Grid Many-Core Applications
International Journal of Parallel Programming, 2012Co-Authors: I-jui Sung, Nasser Anssari, John A. StrattonAbstract:We present automatic data layout transformation as an effective compiler performance optimization for Memory-Bound structured grid applications. Structured grid applications include stencil codes and other code structures using a dense, regular grid as the primary data structure. Fluid dynamics and heat distribution, which both solve partial differential equations on a discretized representation of space, are representative of many important structured grid applications. Using the information available through variable-length array syntax, standardized in C99 and other modern languages, we enable automatic data layout transformations for structured grid codes with dynamically allocated arrays. We also present how a tool can guide these transformations to statically choose a good layout given a model of the Memory system, using a modern GPU as an example. A transformed layout that distributes concurrent Memory requests among parallel Memory system components provides substantial speedup for structured grid applications by improving their achieved Memory-level parallelism. Even with the overhead of more complex address calculations, we observe up to 10.94X speedup over the original layout, and a 1.16X performance gain in the worst case.
-
data layout transformation exploiting Memory level parallelism in structured grid many core applications
International Conference on Parallel Architectures and Compilation Techniques, 2010Co-Authors: I-jui Sung, John A. StrattonAbstract:We present automatic data layout transformation as an effective compiler performance optimization for Memory-Bound structured grid applications. Structured grid applications include stencil codes and other code structures using a dense, regular grid as the primary data structure. Fluid dynamics and heat distribution, which both solve partial differential equations on a discretized representation of space, are representative of many important structured grid applications. Using the information available through variable-length array syntax, standardized in C99 and other modern languages, we have enabled automatic data layout transformations for structured grid codes with dynamically allocated arrays. We also present how a tool can guide these transformations to statically choose a good layout given a model of the Memory system, using a modern GPU as an example. A transformed layout that distributes concurrent Memory requests among parallel Memory system components provides substantial speedup for structured grid applications by improving their achieved Memory-level parallelism. Even with the overhead of more complex address calculations, we observe up to 560% performance increases over the language-defined layout, and a 7% performance gain in the worst case, in which the language-defined layout and access pattern is already well-vectorizable by the underlying hardware.
Jack Dongarra - One of the best experts on this subject based on the ideXlab platform.
-
lu factorization with partial pivoting for a multicore system with accelerators
IEEE Transactions on Parallel and Distributed Systems, 2013Co-Authors: Jakub Kurzak, Piotr Luszczek, Mathieu Faverge, Jack DongarraAbstract:LU factorization with partial pivoting is a canonical numerical procedure and the main component of the high performance LINPACK benchmark. This paper presents an implementation of the algorithm for a hybrid, shared Memory, system with standard CPU cores and GPU accelerators. The difficulty of implementing the algorithm for such a system lies in the disproportion between the computational power of the CPUs, compared to the GPUs, and in the meager bandwidth of the communication link between their Memory systems. An additional challenge comes from the complexity of the Memory-Bound and synchronization-rich nature of the panel factorization component of the block LU algorithm, imposed by the use of partial pivoting. The challenges are tackled with the use of a data layout geared toward complex Memory hierarchies, autotuning of GPU kernels, fine-grain parallelization of Memory-Bound CPU operations and dynamic scheduling of tasks to different devices. Performance in excess of one TeraFLOPS is achieved using four AMD Magny Cours CPUs and four NVIDIA Fermi GPUs.
-
LU Factorization with Partial Pivoting for a Multi-CPU, Multi-GPU Shared Memory System
2012Co-Authors: Jakub Kurzak, Piotr Luszczek, Mathieu Faverge, Jack DongarraAbstract:LU factorization with partial pivoting is a canonical numerical procedure and the main component of the High Performance Linpack benchmark. This article presents an implementation of the algorithm for a hybrid, shared Memory, system with standard CPU cores and GPU accelerators. The optimizations include lookahead, dynamic task scheduling, fine grain parallelism for Memory-Bound operations, autotuning, and data layout geared towards complex Memory hierarchies. Performance in excess of one Tera flop/s is achieved using four AMD Magny Cours CPUs and four NVIDIA Fermi GPUs.
Umit V Catalyurek - One of the best experts on this subject based on the ideXlab platform.
-
performance evaluation of sparse matrix multiplication kernels on intel xeon phi
International Conference on Parallel Processing, 2013Co-Authors: Erik Saule, Kamer Kaya, Umit V CatalyurekAbstract:Intel Xeon Phi is a recently released high-performance coprocessor which features 61 cores each supporting 4 hardware threads with 512-bit wide SIMD registers achieving a peak theoretical performance of 1Tflop/s in double precision. Its design differs from classical modern processors; it comes with a large number of cores, the 4-way hyperthreading capability allows many applications to saturate the massive Memory bandwidth, and its large SIMD capabilities allow to reach high computation throughput. The core of many scientific applications involves the multiplication of a large, sparse matrix with a single or multiple dense vectors which are not compute-Bound but Memory-Bound. In this paper, we investigate the performance of the Xeon Phi coprocessor for these sparse linear algebra kernels. We highlight the important hardware details and show that Xeon Phi’s sparse kernel performance is very promising and even better than that of cutting-edge CPUs and GPUs.
Jack Dongarra - One of the best experts on this subject based on the ideXlab platform.
-
progressive optimization of batched lu factorization on gpus
IEEE High Performance Extreme Computing Conference, 2019Co-Authors: Ahmad Abdelfattah, Stanimire Tomov, Jack DongarraAbstract:This paper presents a progressive approach for optimizing the batched LU factorization on graphics processing units (GPUs). The paper shows that the reliance on level-3 BLAS routines for performance does not really pay off, and that it is indeed important to pay attention to the Memory-Bound part of the algorithm, especially when the problem size is very small. In this context, we develop a size-aware multi-level blocking technique that utilizes different granularities for kernel fusion according to the problem size. Our experiments, which are conducted on a Tesla V100 GPU, show that the multi-level blocking technique achieves speedups for single/double precisions that are up to 3.28×/2.69× against the generic LAPACK-style implementation. It is also up to 8.72×/7.2× faster than the cuBLAS library for single and double precisions, respectively. The developed solution is integrated into the open-source MAGMA library.
-
a jaccard weights kernel leveraging independent thread scheduling on gpus
Symposium on Computer Architecture and High Performance Computing, 2018Co-Authors: Hartwig Anzt, Jack DongarraAbstract:Jaccard weights are a popular metric for identifying communities in social network analytics. In this paper we present a kernel for efficiently computing the Jaccard weight matrix on G PU s. The kernel design is guided by fine-grained parallelism and the independent thread scheduling supported by NVIDIA's Volta architecture. This technology makes it possible to interleave the execution of divergent branches for enhanced data reuse and a higher instruction per cycle rate for Memory-Bound algorithms. In a performance evaluation using a set of publicly available social networks, we report the kernel execution time and analyze the built-in hardware counters on different GPU architectures. The findings have implications beyond the specific algorithm and suggest a reformulation of other data-sparse algorithms.
-
performance optimization of sparse matrix vector multiplication for multi component pde based applications using gpus
Concurrency and Computation: Practice and Experience, 2016Co-Authors: Ahmad Abdelfattah, Hatem Ltaief, David E Keyes, Jack DongarraAbstract:Simulations of many multi-component PDE-based applications, such as petroleum reservoirs or reacting flows, are dominated by the solution, on each time step and within each Newton step, of large sparse linear systems. The standard solver is a preconditioned Krylov method. Along with application of the preconditioner, Memory-Bound Sparse Matrix-Vector Multiplication SpMV is the most time-consuming operation in such solvers. Multi-species models produce Jacobians with a dense block structure, where the block size can be as large as a few dozen. Failing to exploit this dense block structure vastly underutilizes hardware capable of delivering high performance on dense BLAS operations. This paper presents a GPU-accelerated SpMV kernel for block-sparse matrices. Dense matrix-vector multiplications within the sparse-block structure leverage optimization techniques from the KBLAS library, a high performance library for dense BLAS kernels. The design ideas of KBLAS can be applied to block-sparse matrices. Furthermore, a technique is proposed to balance the workload among thread blocks when there are large variations in the lengths of nonzero rows. Multi-GPU performance is highlighted. The proposed SpMV kernel outperforms existing state-of-the-art implementations using matrices with real structures from different applications. Copyright © 2016 John Wiley & Sons, Ltd.
-
performance analysis and design of a hessenberg reduction using stabilized blocked elementary transformations for new architectures
IEEE International Conference on High Performance Computing Data and Analytics, 2015Co-Authors: Khairul Kabir, Azzam Haidar, Stanimire Tomov, Jack DongarraAbstract:The solution of nonsymmetric eigenvalue problems, Ax = λx, can be accelerated substantially by first reducing A to an upper Hessenberg matrix H that has the same eigenvalues as A. This can be done using Householder orthogonal transformations, which is a well established standard, or stabilized elementary transformations. The latter approach, although having half the flops of the former, has been used less in practice, e.g., on computer architectures with well developed hierarchical memories, because of its Memory-Bound operations and the complexity in stabilizing it. In this paper we revisit the stabilized elementary transformations approach in the context of new architectures -- both multicore CPUs and Xeon Phi coprocessors. We derive for a first time a blocking version of the algorithm. The blocked version reduces the Memory-Bound operations and we analyze its performance. A performance model is developed that shows the limitations of both approaches. The competitiveness of using stabilized elementary transformations has been quantified, highlighting that it can be 20 to 30% faster on current high-end multicore CPUs and Xeon Phi coprocessors.