@article {1266,
	title = {Accelerating the SVD Bi-Diagonalization of a Batch of Small Matrices using GPUs},
	journal = {Journal of Computational Science},
	volume = {26},
	year = {2018},
	month = {2018-05},
	pages = {237{\textendash}245},
	abstract = {The acceleration of many small-sized linear algebra problems has become extremely challenging for current many-core architectures, and in particular GPUs. Standard interfaces have been proposed for some of these problems, called batched problems, so that they get targeted for optimization and used in a standard way in applications, calling them directly from highly optimized, standard numerical libraries, like (batched) BLAS and LAPACK. While most of the developments have been for one-sided factorizations and solvers, many important applications {\textendash} from big data analytics to information retrieval, low-rank approximations for solvers and preconditioners {\textendash} require two-sided factorizations, and most notably the SVD factorization. To address these needs and the parallelization challenges related to them, we developed a number of new batched computing techniques and designed batched Basic Linear Algebra Subroutines (BLAS) routines, and in particular the Level-2 BLAS GEMV and the Level-3 BLAS GEMM routines, to solve them. We propose a device functions-based methodology and big-tile setting techniques in our batched BLAS design. The different optimization techniques result in many software versions that must be tuned, for which we adopt an auto-tuning strategy to automatically derive the optimized instances of the routines. We illustrate our batched BLAS approach to optimize batched SVD bi-diagonalization progressively on GPUs. The progression is illustrated on an NVIDIA K40c GPU, and also, ported and presented on AMD Fiji Nano GPU, using AMD{\textquoteright}s Heterogeneous{\textendash}Compute Interface for Portability (HIP) C++ runtime API. We demonstrate achieving 80\% of the theoretically achievable peak performance for the overall algorithm, and significant acceleration of the Level-2 BLAS GEMV and Level-3 BLAS GEMM needed compared to vendor-optimized libraries on GPUs and multicore CPUs. The optimization techniques in this paper are applicable to the other two-sided factorizations as well.},
	keywords = {Batched, Eigenvalue and singular value problems, hardware accelerators, numerical linear algebra, Two-sided factorization algorithms},
	doi = {https://doi.org/10.1016/j.jocs.2018.01.007},
	author = {Tingxing Dong and Azzam Haidar and Stanimire Tomov and Jack Dongarra}
}
@conference {1085,
	title = {Optimizing the SVD Bidiagonalization Process for a Batch of Small Matrices},
	booktitle = {International Conference on Computational Science (ICCS 2017)},
	year = {2017},
	month = {2017-06},
	publisher = {Procedia Computer Science},
	organization = {Procedia Computer Science},
	address = {Zurich, Switzerland},
	abstract = {A challenging class of problems arising in many GPU applications, called batched problems, involves linear algebra operations on many small-sized matrices. We designed batched BLAS (Basic Linear Algebra Subroutines) routines, and in particular the Level-2 BLAS GEMV and the Level-3 BLAS GEMM routines, to solve them. We proposed device functions and big-tile settings in our batched BLAS design. We adopted auto-tuning to optimize different instances of GEMV routines. We illustrated our batched BLAS approach to optimize batched bi-diagonalization progressively on a K40c GPU. The optimization techniques in this paper are applicable to the other two-sided factorizations as well.},
	doi = {https://doi.org/10.1016/j.procs.2017.05.237},
	url = {http://www.sciencedirect.com/science/article/pii/S1877050917308645},
	author = {Tingxing Dong and Azzam Haidar and Stanimire Tomov and Jack Dongarra}
}
@techreport {,
	title = {MAGMA Batched: A Batched BLAS Approach for Small Matrix Factorizations and Applications on GPUs},
	journal = {Innovative Computing Laboratory Technical Report},
	number = {ICL-UT-16-02},
	year = {2016},
	month = {2016-08},
	publisher = {University of Tennessee},
	abstract = {A particularly challenging class of problems arising in many applications, called batched problems, involves linear algebra operations on many small-sized matrices. We proposed and designed batched BLAS (Basic Linear Algebra Subroutines), Level-2 GEMV and Level-3 GEMM, to solve them. We illustrate how batched GEMV and GEMM to be able to assist batched advance factorization (e.g. bi-diagonalization) and other BLAS routines (e.g. triangular solve) to achieve optimal performance on GPUs. Our solutions achieved up to 2.8-3{\texttimes} speedups compared to CUBLAS and MKL solutions, wherever possible. We illustrated the batched methodology on a real-world Hydrodynamic application by reformulating the tensor operations into batched BLAS GEMV and GEMM operations. A 2.5{\texttimes} speedup and a 1.4{\texttimes} greenup are obtained by changing 10\% of the code. We accelerated and scaled it on Titan supercomputer to 4096 nodes.},
	author = {Tingxing Dong and Azzam Haidar and Piotr Luszczek and Stanimire Tomov and Ahmad Abdelfattah and Jack Dongarra}
}
@article {858,
	title = {Batched matrix computations on hardware accelerators based on GPUs},
	journal = {International Journal of High Performance Computing Applications},
	year = {2015},
	month = {2015-02},
	abstract = {Scientific applications require solvers that work on many small size problems that are independent from each other. At the same time, the high-end hardware evolves rapidly and becomes ever more throughput-oriented and thus there is an increasing need for an effective approach to develop energy-efficient, high-performance codes for these small matrix problems that we call batched factorizations. The many applications that need this functionality could especially benefit from the use of GPUs, which currently are four to five times more energy efficient than multicore CPUs on important scientific workloads. This paper, consequently, describes the development of the most common, one-sided factorizations, Cholesky, LU, and QR, for a set of small dense matrices. The algorithms we present together with their implementations are, by design, inherently parallel. In particular, our approach is based on representing the process as a sequence of batched BLAS routines that are executed entirely on a GPU. Importantly, this is unlike the LAPACK and the hybrid MAGMA factorization algorithms that work under drastically different assumptions of hardware design and efficiency of execution of the various computational kernels involved in the implementation. Thus, our approach is more efficient than what works for a combination of multicore CPUs and GPUs for the problems sizes of interest of the application use cases. The paradigm where upon a single chip (a GPU or a CPU) factorizes a single problem at a time is not at all efficient in our applications{\textquoteright} context. We illustrate all of these claims through a detailed performance analysis. With the help of profiling and tracing tools, we guide our development of batched factorizations to achieve up to two-fold speedup and three-fold better energy efficiency as compared against our highly optimized batched CPU implementations based on MKL library. The tested system featured two sockets of Intel Sandy Bridge CPUs and we compared with a batched LU factorizations featured in the CUBLAS library for GPUs, we achieve as high as 2.5{\texttimes} speedup on the NVIDIA K40 GPU.},
	keywords = {batched factorization, hardware accelerators, numerical linear algebra, numerical software libraries, one-sided factorization algorithms},
	doi = {10.1177/1094342014567546},
	author = {Azzam Haidar and Tingxing Dong and Piotr Luszczek and Stanimire Tomov and Jack Dongarra}
}
@conference {864,
	title = {Framework for Batched and GPU-resident Factorization Algorithms to Block Householder Transformations},
	booktitle = {ISC High Performance},
	year = {2015},
	month = {2015-07},
	publisher = {Springer},
	organization = {Springer},
	address = {Frankfurt, Germany},
	author = {Azzam Haidar and Tingxing Dong and Stanimire Tomov and Piotr Luszczek and Jack Dongarra}
}
@conference {916,
	title = {Optimization for Performance and Energy for Batched Matrix Computations on GPUs},
	booktitle = {8th Workshop on General Purpose Processing Using GPUs (GPGPU 8)},
	year = {2015},
	month = {2015-02},
	publisher = {ACM},
	organization = {ACM},
	address = {San Francisco, CA},
	abstract = {As modern hardware keeps evolving, an increasingly effective approach to develop energy efficient and high-performance solvers is to design them to work on many small size independent problems. Many applications already need this functionality, especially for GPUs, which are known to be currently about four to five times more energy efficient than multicore CPUs. We describe the development of the main one-sided factorizations that work for a set of small dense matrices in parallel, and we illustrate our techniques on the LU and Cholesky factorizations. We refer to this mode of operation as a batched factorization. Our approach is based on representing the  algorithms as a sequence of batched BLAS routines for GPU-only execution. The goal of avoiding multicore CPU use, e.g., as in the hybrid CPU-GPU algorithms, is to exclusively benefit from the GPU{\textquoteright}s significantly higher energy efficiency, as well as from the removal of the  costly CPU-to-GPU communications. Furthermore, we do not use a single symmetric multiprocessor (on the GPU) to factorize a single problem at a time. We illustrate how our performance analysis and the use of profiling and tracing tools guided the development and optimization of batched factorizations to achieve up to 2-fold speedup and 3-fold better energy efficiency compared to our highly optimized batched CPU implementations based on the MKL library (when using two sockets of Intel Sandy Bridge CPUs). Compared to a batched LU factorization featured in the CUBLAS library for GPUs, we achieved up to 2.5 speedup on the K40 GPU.},
	keywords = {batched factorization, hardware accelerators, numerical linear algebra, numerical software libraries, one-sided factorization algorithms},
	doi = {10.1145/2716282.2716288},
	author = {Azzam Haidar and Tingxing Dong and Piotr Luszczek and Stanimire Tomov and Jack Dongarra}
}
@conference {715,
	title = {A Fast Batched Cholesky Factorization on a GPU},
	booktitle = {International Conference on Parallel Processing (ICPP-2014)},
	year = {2014},
	month = {2014-09},
	address = {Minneapolis, MN},
	abstract = {Currently, state of the art libraries, like MAGMA, focus on very large linear algebra problems, while solving many small independent problems, which is usually referred to as batched problems, is not given adequate attention. In this paper, we proposed a batched Cholesky factorization on a GPU. Three algorithms {\textendash} nonblocked, blocked, and recursive blocked {\textendash} were examined. The left-looking version of the Cholesky factorization is used to factorize the panel, and the right-looking Cholesky version is used to update the trailing matrix in the recursive blocked algorithm. Our batched Cholesky achieves up to 1:8 speedup compared to the optimized parallel implementation in the MKL library on two sockets of Intel Sandy Bridge CPUs. Further, we use the new routines to develop a single Cholesky factorization solver which targets large matrix sizes. Our approach differs from MAGMA by having an entirely GPU implementation where both the panel factorization and the trailing matrix updates are on the GPU. Such an implementation does not depend on the speed of the CPU. Compared to the MAGMA library, our full GPU solution achieves 85\% of the hybrid MAGMA performance which uses 16 Sandy Bridge cores, in addition to a K40 Nvidia GPU. Moreover, we achieve 80\% of the practical dgemm peak of the machine, while MAGMA achieves only 75\%, and finally, in terms of energy consumption, we outperform MAGMA by 1.5 in performance-per-watt for large matrices.},
	author = {Tingxing Dong and Azzam Haidar and Stanimire Tomov and Jack Dongarra}
}
@conference {859,
	title = {LU Factorization of Small Matrices: Accelerating Batched DGETRF on the GPU},
	booktitle = {16th IEEE International Conference on High Performance Computing and Communications (HPCC)},
	year = {2014},
	month = {2014-08},
	publisher = {IEEE},
	organization = {IEEE},
	address = {Paris, France},
	abstract = {Gaussian Elimination is commonly used to solve dense linear systems in scientific models. In a large number of applications, a need arises to solve many small size problems, instead of few large linear systems. The size of each of these small linear systems depends, for example, on the number of the ordinary differential equations (ODEs) used in the model, and can be on the order of hundreds of unknowns. To efficiently exploit the computing power of modern accelerator hardware, these linear systems are processed in batches. To improve the numerical stability of the Gaussian Elimination, at least partial pivoting is required, most often accomplished with row pivoting. However, row pivoting can result in a severe performance penalty on GPUs because it brings in thread divergence and non-coalesced memory accesses. The state-of-the-art libraries for linear algebra that target GPUs, such as MAGMA, focus on large matrix sizes. They change the data layout by transposing the matrix to avoid these divergence and non-coalescing penalties. However, the data movement associated with transposition is very expensive for small matrices. In this paper, we propose a batched LU factorization for GPUs by using a multi-level blocked right looking algorithm that preserves the data layout but minimizes the penalty of partial pivoting. Our batched LU achieves up to 2:5-fold speedup when compared to the alternative CUBLAS solutions on a K40c GPU and 3:6-fold speedup over MKL on a node of the Titan supercomputer at ORNL in a nuclear reaction network simulation.},
	author = {Tingxing Dong and Azzam Haidar and Piotr Luszczek and James Harris and Stanimire Tomov and Jack Dongarra}
}
@conference {713,
	title = {Mixed-precision orthogonalization scheme and adaptive step size for CA-GMRES on GPUs},
	booktitle = {VECPAR 2014 (Best Paper)},
	year = {2014},
	month = {2014-06},
	address = {Eugene, OR},
	abstract = {We propose a mixed-precision orthogonalization scheme that takes the input matrix in a standard 32 or 64-bit floating-point precision, but uses higher-precision arithmetics to accumulate its intermediate results. For the 64-bit precision, our scheme uses software emulation for the higher-precision arithmetics, and requires about 20x more computation but about the same amount of communication as the standard orthogonalization scheme. Since the computation is becoming less expensive compared to the communication on new and emerging architectures, the relative cost of our mixed-precision scheme is decreasing. Our case studies with CA-GMRES on a GPU demonstrate that using mixed-precision for this small but critical segment of CA-GMRES can improve not only its overall numerical stability but also, in some cases, its performance.},
	author = {Ichitaro Yamazaki and Stanimire Tomov and Tingxing Dong and Jack Dongarra}
}
@conference {767,
	title = {A Step towards Energy Efficient Computing: Redesigning A Hydrodynamic Application on CPU-GPU},
	booktitle = {IPDPS 2014},
	year = {2014},
	month = {2014-05},
	publisher = {IEEE},
	organization = {IEEE},
	address = {Phoenix, AZ},
	abstract = {Power and energy consumption are becoming an increasing concern in high performance computing. Compared to multi-core CPUs, GPUs have a much better performance per watt. In this paper we discuss efforts to redesign the most computation intensive parts of BLAST, an application that solves the equations for compressible hydrodynamics with high order finite elements, using GPUs [10, 1]. In order to exploit the hardware parallelism of GPUs and achieve high performance, we implemented custom linear algebra kernels. We intensively optimized our CUDA kernels by exploiting the memory hierarchy, which exceed the vendor{\textquoteright}s library routines substantially in performance. We proposed an autotuning technique to adapt our CUDA kernels to the orders of the finite element method. Compared to a previous base implementation, our redesign and optimization lowered the energy consumption of the GPU in two aspects: 60\% less time to solution and 10\% less power required. Compared to the CPU-only solution, our GPU accelerated BLAST obtained a 2:5x overall speedup and 1:42x energy efficiency (greenup) using 4th order (Q4) finite elements, and a 1:9x speedup and 1:27x greenup using 2nd order (Q2) finite elements.},
	keywords = {Computer science, CUDA, FEM, Finite element method, linear algebra, nVidia, Tesla K20},
	author = {Tingxing Dong and Veselin Dobrev and Tzanio Kolev and Robert Rieben and Stanimire Tomov and Jack Dongarra}
}
@techreport {690,
	title = {Hydrodynamic Computation with Hybrid Programming on CPU-GPU Clusters},
	journal = {University of Tennessee Computer Science Technical Report},
	number = {ut-cs-13-714},
	year = {2013},
	month = {2013-07},
	abstract = {The explosion of parallelism and heterogeneity in today{\textquoteright}s computer architectures has created opportunities as well as challenges for redesigning legacy numerical software to harness the power of new hardware. In this paper we address the main challenges in redesigning BLAST { a numerical library that solves the equations of compressible hydrodynamics using high order nite element methods (FEM) in a moving Lagrangian frame { to support CPU-GPU clusters. We use a hybrid MPI + OpenMP + CUDA programming model that includes two layers: domain decomposed MPI parallelization and OpenMP + CUDA acceleration in a given domain. To optimize the code, we implemented custom linear algebra kernels and introduced an auto-tuning technique to deal with heterogeneity and load balancing at runtime. Our tests show that 12 Intel Xeon cores and two M2050 GPUs deliver a 24x speedup compared to a single core, and a 2.5x speedup compared to 12 MPI tasks in one node. Further, we achieve perfect weak scaling, demonstrated on a cluster with up to 64 GPUs in 32 nodes. Our choice of programming model and proposed solutions, as related to parallelism and load balancing, specifically targets high order FEM discretizations, and can be used equally successfully for applications beyond hydrodynamics. A major accomplishment is that we further establish the appeal of high order FEMs, which despite their better approximation properties, are often avoided due to their high computational cost. GPUs, as we show, have the potential to make them the method of choice, as the increased computational cost is also localized, e.g., cast as Level 3 BLAS, and thus can be done very efficiently (close to \free" relative to the usual overheads inherent in sparse computations).},
	author = {Tingxing Dong and Veselin Dobrev and Tzanio Kolev and Robert Rieben and Stanimire Tomov and Jack Dongarra}
}
@article {701,
	title = {Tridiagonalization of a dense symmetric matrix on multiple GPUs and its application to symmetric eigenvalue problems},
	journal = {Concurrency and Computation: Practice and Experience},
	year = {2013},
	month = {2013-10},
	abstract = {For software to fully exploit the computing power of emerging heterogeneous computers, not only must the required computational kernels be optimized for the specific hardware architectures but also an effective scheduling scheme is needed to utilize the available heterogeneous computational units and to hide the communication between them. As a case study, we develop a static scheduling scheme for the tridiagonalization of a symmetric dense matrix on multicore CPUs with multiple graphics processing units (GPUs) on a single compute node. We then parallelize and optimize the Basic Linear Algebra Subroutines (BLAS)-2 symmetric matrix-vector multiplication, and the BLAS-3 low rank symmetric matrix updates on the GPUs. We demonstrate the good scalability of these multi-GPU BLAS kernels and the effectiveness of our scheduling scheme on twelve Intel Xeon processors and three NVIDIA GPUs. We then integrate our hybrid CPU-GPU kernel into computational kernels at higher-levels of software stacks, that is, a shared-memory dense eigensolver and a distributed-memory sparse eigensolver. Our experimental results show that our kernels greatly improve the performance of these higher-level kernels, not only reducing the solution time but also enabling the solution of larger-scale problems. Because such symmetric eigenvalue problems arise in many scientific and engineering simulations, our kernels could potentially lead to new scientific discoveries. Furthermore, these dense linear algebra algorithms present algorithmic characteristics that can be found in other algorithms. Hence, they are not only important computational kernels on their own but also useful testbeds to study the performance of the emerging computers and the effects of the various optimization techniques.},
	author = {Ichitaro Yamazaki and Tingxing Dong and Raffaele Solc{\`a} and Stanimire Tomov and Jack Dongarra and Thomas C. Schulthess}
}
@conference {1328,
	title = {Tridiagonalization of a Symmetric Dense Matrix on a GPU Cluster},
	booktitle = {The Third International Workshop on Accelerators and Hybrid Exascale Systems (AsHES)},
	year = {2013},
	month = {2013-05},
	author = {Ichitaro Yamazaki and Tingxing Dong and Stanimire Tomov and Jack Dongarra}
}
@article {icl:731,
	title = {Acceleration of the BLAST Hydro Code on GPU},
	journal = {Supercomputing {\textquoteright}12 (poster)},
	year = {2012},
	month = {2012-11},
	publisher = {SC12},
	address = {Salt Lake City, Utah},
	author = {Tingxing Dong and Tzanio Kolev and Robert Rieben and Veselin Dobrev and Stanimire Tomov and Jack Dongarra}
}
@article {1355,
	title = {MAGMA: A Breakthrough in Solvers for Eigenvalue Problems},
	year = {2012},
	month = {2012-05},
	publisher = {GPU Technology Conference (GTC12), Presentation},
	address = {San Jose, CA},
	author = {Stanimire Tomov and Jack Dongarra and Azzam Haidar and Ichitaro Yamazaki and Tingxing Dong and Thomas Schulthess and Raffaele Solc{\`a}}
}
@article {1349,
	title = {MAGMA: A New Generation of Linear Algebra Library for GPU and Multicore Architectures},
	year = {2012},
	month = {2012-11},
	publisher = {The International Conference for High Performance Computing, Networking, Storage, and Analysis (SC12), Presentation},
	address = {Salt Lake City, UT},
	author = {Jack Dongarra and Tingxing Dong and Mark Gates and Azzam Haidar and Stanimire Tomov and Ichitaro Yamazaki}
}
@inproceedings {icl:632,
	title = {Optimizing Symmetric Dense Matrix-Vector Multiplication on GPUs},
	journal = {ACM/IEEE Conference on Supercomputing (SC{\textquoteright}11)},
	year = {2011},
	month = {2011-11},
	address = {Seattle, WA},
	keywords = {magma},
	author = {Rajib Nath and Stanimire Tomov and Tingxing Dong and Jack Dongarra}
}
