Rješavanje velikog punog simetričnog svojstvenog problema na hibridnim arhitekturama

Solving Large Dense Symmetric Eigenproblem on Hybrid Architectures 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 conventional multi-core processors and the general-purpose 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 out-of-core 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 GPU-based architectures. In particular, it aims at developing the eigensolvers that exhibit very high performance even if a problem is out- of-core for the GPU. The developed out-of-core 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, communication-avoiding BLAS routines that overlap the data transfers with the number of computations performed. Next, these routines are applied to speed-up the following eigensolvers: the solver based on the multi-stage reduction to a tridiagonal form, the Krylov subspace-based method, and the spectral divide-and-conquer method. Although the out-of-core BLAS routines significantly improve the performance of these three eigensolvers, a careful re-design is required in order to tackle the solution of the large eigenproblems on the hybrid CPU-GPU systems. In the out-of-core multi-stage 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 BLAS-2 operations, is the fastest method if only a small subset of the eigenpairs is required. Finally, the spectral divide-and- 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 compute-bound BLAS-3 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 out-of-core eigen- solvers, for a set of the specific macromolecular problems, significantly overcome the multi-core variants and attain high flops rate even if data do not fit into the GPU mem- ory. This proves that it is possible to solve large eigenproblems on modest computing systems equipped with a single GPU.Rješavanje velikog punog simetričnog svojstvenog problema na hibridnim arhitekturama Rješavanja gustih simetričnih svojstvenih problema jedan je od najvažnijih problema iz područja numeričke linearne algebre koji se javlja u brojnim granama istraživanja kao što su bioinformatika, računalna kemija i meteorologija. U proteklih nekoliko godina, ubrzani razvoj ovih znanstvenih područja doveo je do sve većih i većih problema za čije efikasno rješavanje je potrebna velika procesorska snaga te velika količina memorijskog prostora. Zbog velike složenosti algoritama za njihovo rješavanje (često kubne složenosti) rješavanje svojstvenog problema postaje jedan od računalno najzahtjevnijih zadataka. Današnji računalni sistemi, koji mogu udovoljiti sve većim računalnim i podatkovnim potrebama današnjih problema, su sistemi koji koriste snagu konvencionalnih višejezgrenih procesora u suradnji s grafičkim procesorima opće namjene (GPGPU) i često se nazivaju hibridnih ili heterogeni računalni sustavi. Ovi sistemi pružaju vrlo visoke performanse za probleme čiji memorijski zahtjevi ne premašuju kapacitet memorije grafičke kartice, međutim, ako količina podataka premašuje kapacitet GPU memorije, tj. ako se radio o problemu vanjske memorije (eng. out-of-core - OOC) s obzirom na GPU memoriju, dolazi do značajnog pada performansi ili je problem nemoguće riješiti koristeći snagu GPU procesora. Glavni cilj doktorskog istraživanja je razviti nove algoritme za rješavanje velikih punih svojstvenih problema na hibridnim arhitekturama temeljenima na GPU procesorima te postići vrlo visoke performanse izvršavanja čak i za probleme čiji memorijski zahtjevi premašuju kapacitet memorije grafičkih kartica. Konkretno, tri su specifična cilja: dizajn i razvoj novih programskih strategija i algoritama linearne algebre za probleme vanjske memorije, redizajn i unaprjeđenje postojećih algoritama za velike pune simetrične probleme svojstvenih vrijednosti na hibridnim arhitekturama, te evaluacija performansi novih algoritama na velikih problemima koji se javljaju u molekularnoj dinamici. U danim makromolekularnim problemima, veličina problema često premašuje kapacitet GPU memorije te je potrebno problem podijeliti na manje dijelove te ih jedan po jedan kopirati u memoriju grafičke kartice. Takva pristup uzrokuje značajan pad performansi uzrokovan skupim memorijskih transferima između glavne memorije i memorije grafičkog procesora. Za učinkovito rješavanje problema kopiranja između dviju memorija predložen je pristup koji se temelji na blokovskoj podjeli i pažljivom redizajnu postojećih algoritama za rješavanje svojstvenih problema, konkretno: algoritma temeljenog na višestupanjskom svođenju na trodijagonalnu formu, Lanczosova metoda temeljena na Krilovljevim potprostorima, te spektralna podijeli-i-vladaj metoda. Cilj blokovskog pristupa je smanjiti volumen podataka koji je potrebno kopirati između glavne i GPU memorije te broj potrebnih memorijskih transfera. Kako bi se postigao traženi cilj, razvijeno je nekoliko metoda i tehnika koje omogućuju izvršavanje osnovnih problema linearne algebre, kao što su npr. matrično množenje ili QR rastav. Pokazano je da se algoritmi, koji se temelje na matričnim operacija, konkretno BLAS-3 operacijama, mogu vrlo efikasno implementirati tako da u potpunosti sakriju negativne posljedice sporog kopiranja između glavne memorije i GPU memorije te tako postignu vrlo visoke performanse. Korištenjem takvih tehnika, uz redizajn postojećih metoda, moguće je dobiti vrlo brze i efikasne algoritme za rješavanje velikih punih simetričnih problema svojstvenih vrijednosti. U višestupanjskoj metodi, odlučujući faktor koji utječe na performanse je širina vrpce tražene vrpčaste matrice. Nadalje, Lanczosova metoda, iako se ne može opisati u pogledu BLAS-3 operacija, pokazala se kao najbrža metoda za dani testni skup problem, ali samo za slučajeve kad se traži samo mali broj svojstvenih vrijednosti. Spektralna podijeli-i-vladaj metoda postiže daleko najbolje performanse u pogledu broj računskih operacija u sekundi (FLOPS) međutim, zbog iznimno velike složenosti samog algoritma, pokazala se kao najsporija. Sve tri razvijene metode pokazale su da se veliki problemi mogu efikasno rješavati na hibridnim arhitekturama temeljenima na GPU procesorima, te da su značajno brže od postojećih višejezgrenih implementacija za dani specifični skup makromolekularnih problema