Davidović, Davor (2014) Solving Large Dense Symmetric Eigenproblem on Hybrid Architectures. Doctoral thesis, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva.

PDF
 Published Version
Download (2MB)  Preview 
Abstract
Dense symmetric eigenproblem is one of the most significant problems in the numerical linear algebra that arises in numerous research fields such as bioinformatics, computational chemistry, and meteorology. In the past years, the problems arising in these fields become bigger than ever resulting in growing demands in both computational power as well as the storage capacities. In such problems, the eigenproblem becomes the main computational bottleneck for which solution is required an extremely high computational power. Modern computing architectures that can meet these growing demands are those that combine the power of the traditional multicore processors and the generalpurpose GPUs and are called hybrid systems. These systems exhibit very high performance when the data fits into the GPU memory ; however, if the volume of the data exceeds the total GPU memory, i.e. the data is outofcore from the GPU perspective, the performance rapidly decreases. This dissertation is focused on the development of the algorithms that solve dense symmetric eigenproblems on the hybrid GPUbased architectures. In particular, it aims at developing the eigensolvers that exhibit very high performance even if a problem is out ofcore for the GPU. The developed outofcore eigensolvers are evaluated and compared on real problems that arise in the simulation of molecular motions. In such problems the data, usually too large to fit into the GPU memory, are stored in the main memory and copied to the GPU memory in pieces. That approach results in the performance drop due to a slow interconnection and a high memory latency. To overcome this problem an approach that applies blocking strategy and re designs the existing eigensolvers, in order to decrease the volume of data transferred and the number of memory transfers, is presented. This approach designs and implements a set of the block oriented, communicationavoiding BLAS routines that overlap the data transfers with the number of computations performed. Next, these routines are applied to speedup the following eigensolvers: the solver based on the multistage reduction to a tridiagonal form, the Krylov subspacebased method, and the spectral divideandconquer method. Although the outofcore BLAS routines significantly improve the performance of these three eigensolvers, a careful redesign is required in order to tackle the solution of the large eigenproblems on the hybrid CPUGPU systems. In the outofcore multistage reduction approach, the factor that mostly influences the performance is the band size of the obtained band matrix. On the other hand, the Krylov subspace based method, although it is based on the memory bound BLAS2 operations, is the fastest method if only a small subset of the eigenpairs is required. Finally, the spectral divideand conquer algorithm, which exhibits significantly higher arithmetic cost than the other two eigensolvers, achieves extremely high performance since it can be performed completely in terms of the computebound BLAS3 operations. Furthermore, its high arithmetic cost is further reduced by exploiting the special structure of a matrix. Finally, the results presented in the dissertation show that the three outofcore eigen solvers, for a set of the specific macromolecular problems, significantly overcome the multicore variants and attain high flops rate even if data do not fit into the GPU memory. This proves that it is possible to solve large eigenproblems on modest computing systems equipped with a single GPU.
Item Type:  Thesis (Doctoral thesis)  

Uncontrolled Keywords:  numerical linear algebra; eigenproblems; outofcore; GPU; highperformance computing  
Subjects:  NATURAL SCIENCES > Mathematics > Algebra NATURAL SCIENCES > Mathematics > Numerical Mathematics TECHNICAL SCIENCES > Computing 

Divisions:  Center for Informatics and Computing  
Projects: 


Depositing User:  Davor Davidović  
Date Deposited:  11 Dec 2014 10:32  
Last Modified:  11 Dec 2014 10:32  
URI:  http://fulir.irb.hr/id/eprint/1630 
Actions (login required)
View Item 