7.2.Related publications

7.2. RELATED PUBLICATIONS

Finally, the improvement techniques introduced as the main contribution of Chapter 3 were first introduced in [83].

The following is a detailed list of the main publications related to this topic:

IGUAL, F. D., MAYO, R., AND QUINTANA-ORT´ı, E. S. Attaining high performance in generalpurpose computations on current graphics processors. High Performance Computing for Computational Science - VECPAR 2008: 8th International Conference, Toulouse, France, June 24-27, 2008. Revised Selected Papers (2008), 406–419.

The increase in performance of the last generations of graphics processors (GPUs) has made this class of hardware a co-processing platform of remarkable success in certain types of operations. In this paper we evaluate the performance of linear algebra and image processing routines, both on classical and unified GPU architectures and traditional processors (CPUs). From this study, we gain insights on the properties that make an algorithm more likely to deliver high performance on a GPU.

CONFERENCE

PROCEEDINGS

The increase in performance of the last generations of graphics processors (GPUs) has made this class of platform a co-processing tool with remarkable success in certain types of operations. In this paper we evaluate the performance of the Level 3 operations in NVIDIA CUBLAS, the implementation of BLAS for NVIDIA GPUs with unified architecture. From this study, we gain insights on the quality of the kernels in the library and we propose several alternative implementations that are competitive with those in NVIDIA CUBLAS. Experimental results on a GeForce 8800 Ultra compare the performance of NVIDIA CUBLAS and the new variants.

ZAFONT, M. J., MARTIN, A., IGUAL, F., AND QUINTANA-ORTI, E. S. Fast development of

dense linear algebra codes on graphics processors. In Proceedings of the 2009 IEEE International

Symposium on Parallel&Distributed Processing. Workshop on High-Level Parallel Programming Models & Supportive Environments, IEEE Computer Society, pp. 1–8.

We present an application programming interface (API) for the C programming language that facilitates the development of dense linear algebra algorithms on graphics processors applying the FLAME methodology. The interface, built on top of the NVIDIA CUBLAS library, implements all the computational functionality of the FLAME/C interface. In addition, the API includes data transference routines to explicitly handle communication between the CPU and GPU memory spaces. The flexibility and simplicity-of-use of this tool are illustrated using a complex operation of dense linear algebra: the Cholesky factorization. For this operation, we implement and evaluate all existing variants on an NVIDIA G80 processor, attaining speedups 7x compared with the CPU implementations.

BARRACHINA, S., CASTILLO, M., IGUAL, F. D., MAYO, R., AND QUINTANA-ORT´ı, E. S.

FLAG@lab: An M-script API for linear algebra operations on graphics processors. In 9th International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA 2008). (To appear as Lecture Notes in Computer Science).

CONFERENCE

PROCEEDINGS

CONFERENCE

PROCEEDINGS

CONFERENCE

PROCEEDINGS

CONFERENCE

PROCEEDINGS

We propose two high-level application programming interfaces (APIs) to use a graphics processing unit (GPU) as a co-processor for dense linear algebra operations. Combined with an extension of the FLAME API and an implementation on top of NVIDIA CUBLAS, the result is an e cient and user-friendly tool to design, implement, and execute dense linear algebra operations on the current generation of NVIDIA graphics processors, of wide-appeal to scientists and engineers. As an application of the developed APIs, we implement and evaluate the performance of three di erent variants of the Cholesky factorization.

IGUAL, F. D., QUINTANA-ORT´ı, G., AND VAN DE GEIJN, R. Level-3 BLAS on a GPU: Picking the low hanging fruit. In ICCMSE 2010: Proceedings of the Eighth International Conference of Computational Methods in Sciences and Engineering (2011), AIP Conference Proceedings. (To appear. Also published as FLAME Working Note 37).

The arrival of hardware accelerators has created a new gold rush to be the first to deliver their promise of high performance for numerical applications. Since they are relatively hard to program, with limited language and compiler support, it is generally accepted that one needs to roll up one’s sleeves and tough it out, not unlike the early days of distributed memory parallel computing (or any other period after the introduction of a drastically di erent architecture). In this paper we remind the community that while this is a noble endeavor, there is a lot of low hanging fruit that can be harvested easily. Picking this low hanging fruit benefits the scientific computing community immediately and prototypes the approach that the further optimizations may wish to follow. We demonstrate this by focusing on a widely used set of operations, the level-3 BLAS, targeting the NVIDIA family of GPUs.

Chapter 4. LAPACK-level routines on single-GPU systems

In [22], we introduced the first results to date using NVIDIA CUBLAS as the underlying building block to develop LAPACK-level routines. In addition, we evaluated several algorithmic routines for the Cholesky and LU factorization with partial pivoting. For the first time, we applied the mixedprecision iterative refinement approach to the graphics processors, exploiting their high performance in single-precision arithmetic. In [23], we extended this evaluation to double-precision arithmetic. In [30] we proposed a method to accelerate the reduction to condensed forms using the GPU as the underlying platform.

The following is a detailed list of the main publications related to this topic:

BARRACHINA, S., CASTILLO, M., IGUAL, F. D., MAYO, R., AND QUINTANA-ORT´ı, E. S.

Solving dense linear systems on graphics processors. In Proceedings of the 14th International EuroPar Conference (2008), E. Luque, T. Margalef, and D. Ben´ıtez, Eds., Lecture Notes in Computer Science, 5168, Springer, pp. 739–748.

We present several algorithms to compute the solution of a linear system of equations on a GPU, as well as general techniques to improve their performance, such as padding and hybrid GPU-CPU computation. We also show how iterative refinement with mixed-precision can be used to regain full accuracy in the solution of linear systems. Experimental results on a G80 using NVIDIA CUBLAS 1.0, the implementation of BLAS for NVIDIA GPUs with unified architecture, illustrate the performance of the di erent algorithms and techniques proposed.

7.2. RELATED PUBLICATIONS

BARRACHINA, S., CASTILLO, M., IGUAL, F. D., MAYO, R., QUINTANA-ORT´ı, E. S., AND

QUINTANA-ORT´ı, G. Exploiting the capabilities of modern GPUs for dense matrix computations.

Concurrency and Computation: Practice and Experience 21, 18 (2009), 2457–2477.

We present several algorithms to compute the solution of a linear system of equations on a graphics processor (GPU), as well as general techniques to improve their performance, such as padding and hybrid GPU-CPU computation. We compare single and double precision performance of a modern GPU with unified architecture, and show how iterative refinement with mixed precision can be used to regain full accuracy in the solution of linear systems, exploiting the potential of the processor for single precision arithmetic. Experimental results on a GTX280 using NVIDIA CUBLAS 2.0, the implementation of BLAS for NVIDIA GPUs with unified architecture, illustrate the performance of the di erent algorithms and techniques proposed.

BIENTINESI, P., IGUAL, F. D., KRESSNER, D., AND QUINTANA-ORT´ı, E. S. Reduction to

condensed forms for symmetric eigenvalue problems on multi-core architectures. In PPAM (1) (2009), pp. 387–395.

We investigate the performance of the routines in LAPACK and the Successive Band Reduction (SBR) toolbox for the reduction of a dense matrix to tridiagonal form, a crucial preprocessing stage in the solution of the symmetric eigenvalue problem, on general-purpose multi-core processors. In response to the advances of hardware accelerators, we also modify the code in SBR to accelerate the computation by o -loading a significant part of the operations to a graphics processor (GPU). Performance results illustrate the parallelism and scalability of these algorithms on current high-performance multi-core architectures.

BIENTINESI, P., IGUAL, F. D., KRESSNER, D., PETSCHOW, M., AND QUINTANA-ORT´ı, E. S.

Condensed forms for the symmetric eigenvalue problem on multi-threaded architectures. Concurrency and Computation: Practice and Experience 23, 7 (2011), 694–707.

We investigate the performance of the routines in LAPACK and the Successive Band Reduction (SBR) toolbox for the reduction of a dense matrix to tridiagonal form, a crucial preprocessing stage in the solution of the symmetric eigenvalue problem, on general-purpose multi-core processors. In response to the advances of hardware accelerators, we also modify the code in the SBR toolbox to accelerate the computation by o -loading a significant part of the operations to a graphics processor (GPU). The performance results illustrate the parallelism and scalability of these algorithms on current high-performance multi-core and many-core architectures.

Chapter 5. Matrix computations on multi-GPU systems

The work in [114] was in fact the first contribution, as far as we know, that utilized a run-time system to exploit task parallellism on dense linear algebra operations using multiple GPUs. A similar approach was taken to implement GPUSs, as detailed in [16]. Facing the programmability problem, the work on the extension of the StarSs programming model and its adaptation to future heterogeneous multi-core and many-core architectures derived in the extension proposals of the OpenMP standard presented in [15] and [14].

The following is a detailed list of the main publications related to that topic:

JOURNAL

CONFERENCE

PROCEEDINGS

JOURNAL

CONFERENCE

PROCEEDINGS

CONFERENCE

PROCEEDINGS

CONFERENCE

PROCEEDINGS

QUINTANA-ORT´ı, G., IGUAL, F. D., QUINTANA-ORT´ı, E. S., AND VAN DE GEIJN, R. A.

Solving dense linear systems on platforms with multiple hardware accelerators. In PPoPP ’09:

Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming (New York, NY, USA, 2009), ACM, pp. 121–130.

The FLAME methodology, combined with the SuperMatrix runtime system, yields a simple yet powerful solution for programming dense linear algebra operations on multicore platforms. In this paper we provide evidence that this approach solves the programmability problem for this domain by targeting a more complex architecture, composed of a multicore processor and multiple hardware accelerators (GPUs, Cell B.E., etc.), each with its own local memory, resulting in a platform more reminiscent of a heterogeneous distributed-memory system. In particular, we show that the FLAME programming model accommodates this new situation e ortlessly so that no significant change needs to be made to the codebase. All complexity is hidden inside the SuperMatrix runtime scheduling mechanism, which incorporates software implementations of standard cache/memory coherence techniques in computer architecture to improve the performance. Our experimental evaluation on a Intel Xeon 8-core host linked to an NVIDIA Tesla S870 platform with four GPUs delivers peak performances around 550 and 450 (single-precision) GFLOPS for the matrix-matrix product and the Cholesky factorization, respectively, which we believe to be the best performance numbers posted on this new architecture for such operations.

AYGUAD´E, E., BADIA, R. M., IGUAL, F. D., LABARTA, J., MAYO, R., AND QUINTANA-

ORT´ı, E. S. An extension of the StarSs programming model for platforms with multiple GPUs. In Euro-Par (2009), pp. 851–862.

While general-purpose homogeneous multi-core architectures are becoming ubiquitous, there are clear indications that, for a number of important applications, a better performance/power ratio can be attained using specialized hardware accelerators. These accelerators require specific SDK or programming languages which are not always easy to program. Thus, the impact of the new programming paradigms on the programmer’s productivity will determine their success in the high-performance computing arena. In this paper we present GPU Superscalar (GPUSs), an extension of the Star Superscalar programming model that targets the parallelization of applications on platforms consisting of a general-purpose processor connected with multiple graphics processors. GPUSs deals with architecture heterogeneity and separate memory address spaces, while preserving simplicity and portability. Preliminary experimental results for a well-known operation in numerical linear algebra illustrate the correct adaptation of the runtime to a multi-GPU system, attaining notable performance results.

AYGUADE, E., BADIA, R. M., CABRERA, D., DURAN, A., GONZALEZ, M., IGUAL, F.,

JIMENEZ, D., LABARTA, J., MARTORELL, X., MAYO, R., PEREZ, J. M., AND QUINTANA-

ORT´ı, E. S. A proposal to extend the OpenMP tasking model for heterogeneous architectures. In IWOMP ’09: Proceedings of the 5th International Workshop on OpenMP (Berlin, Heidelberg, 2009), Springer-Verlag, pp. 154–167.

OpenMP has recently evolved towards expressing unstructured parallelism, targeting the parallelization of a broader range of applications in the current multicore era. Homogeneous multicore architectures from major vendors have become mainstream, but