Questa tesi si occupa dell'implementazione e dello sviluppo di metodi multilivello, per la risoluzione di sistemi di equazioni lineari e il calcolo di tracce di funzioni di matrici, nell'ambito della Cromodinamica Quantistica (QCD) su reticolo. Quando si risolvono sistemi lineari estremamente grandi e mal condizionati con metodi multigrid, la scalabilità dell'implementazione è tipicamente compromessa quando si passa a un numero elevato di nodi di calcolo. Quando si utilizzano (scalabili) smoothers di decomposizione del dominio (DD), come nella nostra libreria DD-αAMG, questa scarsa scalabilità è causata dalle (tipicamente) cattive proprietà di scalabilità del livello più grossolano della gerarchia multigrid. Il primo contributo di questa tesi riguarda la riduzione di questi problemi di scalabilità in DD-αAMG. Lo facciamo integrando i metodi di riciclo con un precondizionatore polinomiale; scopriamo che questa combinazione ha un'ottima performance algoritmica per i problemi in questione. Inoltre, sfruttiamo la località includendo anche un precondizionatore a blocchi diagonali, basato sull'idea del blocco di Jacobi. Infine, esploriamo l'occultamento della comunicazione attraverso il pipelining. Tutti questi metodi combinati sfruttano un risolutore complesso e potente a livello grossolano, che nel caso dei fermioni di Wilson ci permette di ottenere notevoli vantaggi algoritmici e computazionali. Quando vengono applicati ai fermioni a twisted mass, questi metodi basati su Krylov (più il precondizionatore a blocchi diagonali) ci permettono di sbarazzarci di un parametro "artificialmente" introdotto a livello coarsest. Ampliamo ulteriormente le possibilità algoritmiche all'ultimo livello in DD-αAMG, utilizzando un risolutore approssimato basato su LU come precondizionatore di GMRES riavviato. Queste soluzioni dirette approssimate, eseguite tramite la libreria MUMPS, ci permettono, nel caso della twisted mass, non solo di sbarazzarci dello stesso parametro "artificiale" al livello più grossolano, ma ci danno anche migliori prestazioni algoritmiche e computazionali, su un singolo nodo, rispetto a tutti gli altri metodi qui esplorati. Passiamo quindi ad aspetti più computazionali e, come secondo contributo del nostro lavoro, estendiamo la libreria DD-αAMG in modo che diventi un solutore ibrido GPU+CPU, effettuando il porting di alcune parti del codice tramite CUDA C. In questo modo, ci rendiamo conto dell'importanza di avere uno smoother basato sulla DD e inoltre esploriamo il comportamento computazionale dello smoother quando si hanno diverse dimensioni per i blocchi di DD. Concludiamo che i blocchi più piccoli sono migliori in termini di prestazioni computazionali. Notiamo anche l'importanza di utilizzare un coarsening (più) aggressivo nella gerarchia multigrid, quando si opera con il nostro solutore ibrido. L'implementazione risultante ha attualmente un tempo di esecuzione simile a quello della vecchia versione per CPU, ma con il grande vantaggio che ulteriori miglioramenti della GPU al livello più fine possono rendere il solutore ibrido largamente superiore alla versione per CPU. Infine, discutiamo lo sviluppo e la sperimentazione di un nuovo metodo per il calcolo delle tracce di funzioni di matrici, tr(f(A)). Questo nuovo metodo si basa su multilevel Monte Carlo, in combinazione con una gerarchia multigrid. Sebbene sia del tutto generale in termini di funzione f e matrice A, il metodo viene qui testato sull'inversa (i.e. f(A)=A-1), per tre matrici: Schwinger, Wilson e twisted mass. Dimostriamo che il metodo funziona in tutti e tre i casi, con vantaggi sia algoritmici che computazionali, con risultati notevoli per Schwinger e risultati molto buoni e promettenti per Wilson e twisted mass. Questi risultati aprono nuovi percorsi di ricerca, in cui il nostro metodo multigrid multilevel Monte Carlo può essere utilizzato in combinazione con altri metodi come la deflation e il probing.

This thesis deals with the implementation and development of multilevel methods, for solving linear systems of equations and computing traces of functions of matrices, in the lattice Quantum Chromodynamics (QCD) setting. When extremely large and ill-conditioned linear systems are being solved via multigrid methods, the scalability of the implementation is typically compromised as we move to a large number of compute nodes. When using (scalable) domain decomposition (DD) smoothers, as in our DD-αAMG library, this poor scalability is then caused by the (typically) bad scaling properties of the coarsest level in the multigrid hierarchy. The first contribution of this thesis is on diminishing these scalability issues in DD-αAMG. We do this by integrating recycling methods with a polynomial preconditioner; we find that this combination has a great algorithmic performance for the problems at hand. Furthermore, we exploit locality by including a block-diagonal preconditioner as well, based on the idea of block Jacobi. Finally, we explore communication hiding via pipelining. All these methods combined leverage a complex and powerful coarsest-level solver, which in the case of Wilson fermions gives us remarkable algorithmic and computational gains. When applied to twisted mass fermions, these Krylov-based methods (plus the block-diagonal preconditioner) allow us to get rid of an “artificially”-introduced coarsest-level parameter. We further broaden the algorithmic possibilities at the last level in DD-αAMG, by using an LU-based approximate solver as a preconditioner to restarted GMRES. Those approximate direct solves, done via the MUMPS library, allow us to, in the twisted mass case, not only get rid of the same “artificial” parameter at the coarsest level, but they also give us improved algorithmic and computational performances, on a single node, with respect to all the other methods explored here. We then turn to more computational aspects and, as a second contribution from our work, we extend the DD-αAMG library to become a hybrid GPU+CPU solver, by porting some parts of the code via CUDA C. In doing so, we realize the importance of having a smoother based on DD, and furthermore we explore the computational behaviour of the smoother when having different sizes for the DD blocks. We conclude that smaller blocks are better in terms of computational performance. We also notice the importance of using (more) aggressive coarsening in the multigrid hierarchy, when running with our hybrid solver. The resulting implementation currently performs with an execution time similar to the old CPU version, but with the great advantage that further GPU improvements at the finest level can render a hybrid solver largely outperforming the CPU version. Finally, we discuss the development and testing of a new method for the computation of traces of functions of matrices, tr(f(A)). This new method is based on multilevel Monte Carlo, in combination with a multigrid hierarchy. Although completely general in terms of the function f and the matrix A, the method is tested here on the inverse (i.e. f(A)=A-1), for three matrices: Schwinger, Wilson and twisted mass. We show that the method works in all three cases, with both algorithmic and computational gains in all, with remarkable results in Schwinger, and very good and promising results for Wilson and twisted mass. These results open new paths of research, where our multigrid multilevel Monte Carlo method can be used in combination with other methods such as deflation and hierarchical probing.

Multilevel Algorithms in Lattice QCD for Exascale Machines

-
2022

Abstract

Questa tesi si occupa dell'implementazione e dello sviluppo di metodi multilivello, per la risoluzione di sistemi di equazioni lineari e il calcolo di tracce di funzioni di matrici, nell'ambito della Cromodinamica Quantistica (QCD) su reticolo. Quando si risolvono sistemi lineari estremamente grandi e mal condizionati con metodi multigrid, la scalabilità dell'implementazione è tipicamente compromessa quando si passa a un numero elevato di nodi di calcolo. Quando si utilizzano (scalabili) smoothers di decomposizione del dominio (DD), come nella nostra libreria DD-αAMG, questa scarsa scalabilità è causata dalle (tipicamente) cattive proprietà di scalabilità del livello più grossolano della gerarchia multigrid. Il primo contributo di questa tesi riguarda la riduzione di questi problemi di scalabilità in DD-αAMG. Lo facciamo integrando i metodi di riciclo con un precondizionatore polinomiale; scopriamo che questa combinazione ha un'ottima performance algoritmica per i problemi in questione. Inoltre, sfruttiamo la località includendo anche un precondizionatore a blocchi diagonali, basato sull'idea del blocco di Jacobi. Infine, esploriamo l'occultamento della comunicazione attraverso il pipelining. Tutti questi metodi combinati sfruttano un risolutore complesso e potente a livello grossolano, che nel caso dei fermioni di Wilson ci permette di ottenere notevoli vantaggi algoritmici e computazionali. Quando vengono applicati ai fermioni a twisted mass, questi metodi basati su Krylov (più il precondizionatore a blocchi diagonali) ci permettono di sbarazzarci di un parametro "artificialmente" introdotto a livello coarsest. Ampliamo ulteriormente le possibilità algoritmiche all'ultimo livello in DD-αAMG, utilizzando un risolutore approssimato basato su LU come precondizionatore di GMRES riavviato. Queste soluzioni dirette approssimate, eseguite tramite la libreria MUMPS, ci permettono, nel caso della twisted mass, non solo di sbarazzarci dello stesso parametro "artificiale" al livello più grossolano, ma ci danno anche migliori prestazioni algoritmiche e computazionali, su un singolo nodo, rispetto a tutti gli altri metodi qui esplorati. Passiamo quindi ad aspetti più computazionali e, come secondo contributo del nostro lavoro, estendiamo la libreria DD-αAMG in modo che diventi un solutore ibrido GPU+CPU, effettuando il porting di alcune parti del codice tramite CUDA C. In questo modo, ci rendiamo conto dell'importanza di avere uno smoother basato sulla DD e inoltre esploriamo il comportamento computazionale dello smoother quando si hanno diverse dimensioni per i blocchi di DD. Concludiamo che i blocchi più piccoli sono migliori in termini di prestazioni computazionali. Notiamo anche l'importanza di utilizzare un coarsening (più) aggressivo nella gerarchia multigrid, quando si opera con il nostro solutore ibrido. L'implementazione risultante ha attualmente un tempo di esecuzione simile a quello della vecchia versione per CPU, ma con il grande vantaggio che ulteriori miglioramenti della GPU al livello più fine possono rendere il solutore ibrido largamente superiore alla versione per CPU. Infine, discutiamo lo sviluppo e la sperimentazione di un nuovo metodo per il calcolo delle tracce di funzioni di matrici, tr(f(A)). Questo nuovo metodo si basa su multilevel Monte Carlo, in combinazione con una gerarchia multigrid. Sebbene sia del tutto generale in termini di funzione f e matrice A, il metodo viene qui testato sull'inversa (i.e. f(A)=A-1), per tre matrici: Schwinger, Wilson e twisted mass. Dimostriamo che il metodo funziona in tutti e tre i casi, con vantaggi sia algoritmici che computazionali, con risultati notevoli per Schwinger e risultati molto buoni e promettenti per Wilson e twisted mass. Questi risultati aprono nuovi percorsi di ricerca, in cui il nostro metodo multigrid multilevel Monte Carlo può essere utilizzato in combinazione con altri metodi come la deflation e il probing.
RAMIREZ HIDALGO, GUSTAVO ALONSO
SCHIFANO, Sebastiano Fabio
TRIPICCIONE, Raffaele
File in questo prodotto:
File Dimensione Formato  
007_thesis.pdf

accesso aperto

Descrizione: thesisGARH
Tipologia: Tesi di dottorato
Dimensione 1.98 MB
Formato Adobe PDF
1.98 MB Adobe PDF Visualizza/Apri

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2496718
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact