Multilevel Algorithms in Lattice QCD for Exascale Machines

Abstract

Η παρούσα διατριβή πραγματεύεται την εφαρμογή και ανάπτυξη μεθόδων πολλαπλών επιπέδων, για την επίλυση γραμμικών συστημάτων εξισώσεων και υπολογισμού ιχνών συναρτήσεων πινάκων, στη ρύθμιση δικτυωτού Κβαντική Χρωμοδυναμική (ΚΧΔ). ́Οταν τα εξαιρετικά μεγάλα και κακώς διαμορφωμένος γραμμικά συστήματα επιλύονται μέσω μεθόδων πολλαπλών δικτύων, η επεκτασιμότητα της υλοποίησης συνήθως διακυβεύεται καθώς μετακινούμαστε σε μεγάλο αριθμό κόμβων υπολογιστών. Η πρώτη συμβολή αυτής της διατριβής είναι στη μείωση αυτών των ζητημάτων επεκτασιμότητας στο ΔΔ-αΑΜΓ (μια βιβλιοθήκη για την επίλυση γραμμικών συστημάτων σε δικτυωτά ΚΧΔ). Αυτό το κάνουμε ενσωματώνοντας τέσσερις μεθόδους στο πιο χονδροειδές επίπεδο: ανακύκλωση, πολυωνυμική προετοιμασία, προετοιμασία με διαγώνιο μπλοκ και διοχέτευση. Με αυτόν τον τρόπο, έχουμε αξιοσημείωτα αλγοριθμικά και υπολογιστικά κέρδη στην περίπτωση Ωιλσον και είμαστε επίσης σε θέση να απαλλαγούμε από μια κάπως τεχνητή παράμετρο στο πιο χονδροειδές επίπεδο στην περίπτωση συνεστραμμένης μάζας. Στη συνέχεια, στρεφόμαστε σε περισσότερες υπολογιστικές πτυχές και, ως δεύτερη συνεισφορά από την εργασία μας, επεκτείνουμε τη βιβλιοθήκη ΔΔ-αΑΜΓ για να γίνει μια υβριδική δι- αλύτης ΓΠΥ+ΞΠΥ, μεταφέροντας ορισμένα μέρη του κώδικα μέσω ΞΥΔΑ Ξ . ́Ετσι, αντιλαμβανόμαστε τη σημασία της ομαλότερης αποσύνθεσης με βάση τον τομέα κατά την εκτέλεση σε ΓΠΥ, καθώς και της χρήσης μιας (πιο) επιθετικής χονδροειδοποίησης στην ιεραρχία πολλαπλών δικτύων, κατά την εκτέλεση με τον υβριδικό μας επιλύτη. Τέλος, συζητάμε την ανάπτυξη και τη δοκιμή μιας νέας μεθόδου για τον υπολογισμό των ιχνών των συναρτήσεων των πινάκων, tr(f (A)). Αυτή η νέα μέθοδος βασίζεται στο πολυεπίπεδο Μοντε Ξαρλο, σε συνδυασμό με μια ιεραρχία πολλαπλών δικτύων. Δοκιμάσαμε τη μέθοδο στην αντίστροφη συνάρτηση (δηλαδή f (A) = A −1 ), για τρεις πίνακες: Σξηωινγερ, Ωιλ- σον και στριμμένη μάζα. Βλέπουμε αξιοσημείωτα αποτελέσματα στο Σξηωινγερ, και πολύ καλά και πολλά υποσχόμενα αποτελέσματα για τον Ωιλσον και τη στριφτή μάζα. Αυτά τα αποτελέσματα ανοίγουν νέους δρόμους έρευνας, όπου η πολυεπίπεδη μέθοδος Μοντε Ξαρλο πολλαπλών δικτύων μπορεί να χρησιμοποιηθεί σε συνδυασμό με άλλες μεθόδους όπως ο αποπληθωρισμός και η ιεραρχική ανίχνευση.

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. The first contribution of this thesis is on diminishing these scalability issues in DD-αAMG (a library for solving linear systems in lattice QCD). We do this by in- tegrating four methods into the coarsest level: recycling, polynomial preconditioning, block-diagonal preconditioning and pipelining. In doing so, we get remarkable algo- rithmic and computational gains in the Wilson case, and we are also able to get rid of a somewhat artificial parameter at the coarsest level in the twisted mass case. 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 domain decomposition when running on GPUs, as well as of us- ing an (more) aggressive coarsening in the multigrid hierarchy, when running with our hybrid solver. 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. We have tested the method on the inverse (i.e. f (A) = A −1 ), for three matrices: Schwinger, Wilson and twisted mass. We see remarkable results in Schwinger, and very good and promising results for Wilson and twisted mass. These results open new paths of research, where the multigrid multilevel Monte Carlo method can be used in combination with other methods such as deflation and hierarchical probing.