Large-scale software optimization and micro-architectural specialization for accelerated high-performance computing

Abstract

For almost half a century the performance of processors has been improving exponentially, closely following the observations made by Gordon Moore and Robert Dennard. One after the other, both predictions have come to a halt due to the increased complexity in transistor manufacturing, the power and thermal limitations at extremely small-scale technology nodes, and the implications of Amdahl's law to multiprocessing . Nowadays, more than ever, the path to high performance passes through meticulous software optimization, fine tuning, and the design of domain-specific hardware architectures and accelerators. Within the scope of this thesis, we approach High-Performance Computing from two different standpoints. In the first part of the thesis, we bridge the gap between productivity-oriented, high-level programming languages and high-performance computing techniques. The domain of focus is particle accelerator physics, and more specifically beam dynamics. The state-of-art Beam Longitudinal Dynamics simulator BLonD was developed at CERN in 2014, and since then, BLonD has been driving the baseline choices for key-parameters related to the daily operation of the largest circular particle accelerators and their upgrades, as well the research for future machines. We develop a single-node optimized, multi-threaded version of BLonD to accommodate design-space exploration oriented simulation studies. Then, we build a hybrid, MPI-over-OpenMP version to bring the run-time of previously week-long or even month-long simulations down to a few hours. To achieve that, techniques such as intelligent dynamic load-balancing and approximate computing were employed. Finally, to anticipate the demand for ever-growing simulation workloads, we design a distributed, GPU-accelerated version of the code, which delivers more than two orders of magnitude improved latency and throughput compared to the previous state-of-art. All the above technologies and optimizations are developed in a user-friendly way. The dramatic reduction in execution time enables scientists to simulate beam longitudinal dynamics scenarios that combine more complex physics phenomena with finer resolution and larger number of simulated particles. These complex, accurate and fast simulations are essential in the field of beam dynamics to overcome current technological limitations, plan the upcoming upgrades of particle accelerators, and design future machines that will help science advance further. The second part of the thesis is focused on hardware customization to accommodate the needs of modern applications. GPUs, once used for the acceleration of graphic workloads, have now become the dominant platform for general purpose application acceleration. Their processing power and cost-efficiency have led to their adoption in almost every computing domain, including machine learning, scientific computing, and databases. Monitoring the behavior of multiple, GPU-accelerated workloads, the existence of a significant class of kernels was detected, which, due to limited data parallelism fail to support a large degree of Thread-Level Parallelism and hide the latency of memory operations. These kernels seek for more aggressive Instruction-Level Parallelism strategies to improve stall hiding and fill the execution pipeline. This inefficiency is addressed by designing a novel, light-weight Out-Of-Order GPU (LOOG) micro-architecture. LOOG is designed to re-use and re-purpose existing hardware components to minimize the power and area overheads. By exploiting Instruction-Level Parallelism to complement the existing Thread-Level Parallelism execution model, LOOG surpasses both traditional GPU platforms and other prior-art policies. A thorough discussion of LOOG internals and the key design tradeoffs that had to be considered are provided in the thesis. Moreover, an extensive design space exploration is performed to fine tune LOOG and demonstrate its effectiveness when applied on top of a variety of GPU platforms. The LOOG mechanism outperforms conventional platforms by 27.6% and 22.4% in terms of run-time and energy efficiency, respectively. This is a strong indication that LOOG is a promising alternative GPU micro-architecture, which is capable of expanding the applicability of future GPU platforms even further, to new application domains. To summarize, this thesis proposes two approaches to improve the performance in terms of execution time and energy efficiency, anticipating the ever-increasing computing requirements of modern applications. Firstly, we discuss meticulous software customization to take advantage of existing multi-processors and hardware accelerators, while providing an easy-to-use interface to the user-base. Secondly, we explore micro-architectural specializations to adjust to the needs of modern workloads.

ον τελευταίο μισό αιώνα η απόδοση των επεξεργαστών αυξάνεται εκθετικά, ακολουθώντας πιστά τις προβλέψεις των Gordon Moore και Robert Dennard. Η μία μετά την άλλη, αμφότερες οι προβλέψεις έχουν σταματήσει να ισχύουν λόγω της αυξημένης πολυπλοκότητας στην κατασκευή τρανζίστορ, των θερμικών περιορισμών και περιορισμών ισχύος σε εξαιρετικά μικρές κλίμακες, καθώς και του νόμου του Amdahl σχετικά με την πολυεπεξεργασία. Σήμερα, περισσότερο από ποτέ άλλοτε, η πορεία για την υψηλή απόδοση συνοδεύεται από σχολαστική βελτιστοποίηση λογισμικού, ακριβή παραμετροποίηση και σχεδιασμό εξειδικευμένων αρχιτεκτονικών και επιταχυντών. Στα πλαίσια αυτής της διατριβής, εξετάζεται ο Υπολογισμός Υψηλών Επιδόσεων από δύο σκοπιές. Στο πρώτο μέρος της διατριβής, γεφυρώνεται το χάσμα μεταξύ γλωσσών προγραμματισμού υψηλού επιπέδου με κύριο προσανατολισμό την παραγωγικότητα και τεχνικών υψηλής απόδοσης. Ο τομέας εστίασης είναι η φυσική των επιταχυντών σωματιδίων, και πιο συγκεκριμένα της φυσικής που περιγράφει την κίνηση μία δέσμης σωματιδίων μέσα σε κυκλικούς επιταχυντές σωματιδίων. Ο υπερσύγχρονος προσομοιωτής Beam Longitudinal Dynamics BLonD αναπτύχθηκε στον Ευρωπαϊκό Συμβούλιο Πυρηνικής Έρευνας (CERN) το 2014, και έκτοτε καθοδηγεί τον καθορισμό βασικών παραμέτρων σχετικά με την καθημερινή λειτουργία των μεγαλύτερων κυκλικών επιταχυντών, τις αναβαθμίσεις τους, καθώς και την έρευνα για μελλοντικά μηχανήματα. Αρχικά, αναπτύξαμε μία βελτιστοποιημένη για ένα κόμβο πολυνηματική έκδοση του BLonD για να φιλοξενήσει μελέτες προσομοίωσης προσανατολισμένες στην εξερεύνηση του χώρου σχεδιασμού. Στη συνέχεια, κατασκευάσαμε μια υβριδική, MPI-over-OpenMP έκδοση που επέτυχε την μείωση του χρόνο εκτέλεσης προσομοιώσεων που προηγουμένως διαρκούσαν μια εβδομάδα ή ακόμα και έναν μήνα σε μερικές ώρες. Για να επιτευχθεί αυτό, χρησιμοποιήθηκαν τεχνικές όπως η δυναμική εξισορρόπηση φορτίου και οι προσεγγιστικοί υπολογισμοί. Τέλος, λόγω της συνεχούς ζήτησης για συνεχώς αυξανόμενα μεγέθη προσομοίωσης, σχεδιάζουμε μια κατανεμημένη, επιταχυνόμενη με Μονάδες Επεξεργασίας Γραφικών (GPU) έκδοση του κώδικα, η οποία παρέχει περισσότερες από δύο τάξεις μεγέθους βελτιωμένη απόδοση σε σύγκριση με την προηγούμενη έκδοση. Όλες οι παραπάνω τεχνολογίες και βελτιστοποιήσεις αναπτύχθηκαν με φιλικό τρόπο προς τον χρήστη, ώστε να χρειάζονται ελάχιστες επεμβάσεις για την χρήση της κατανεμημένης ή GPU έκδοσης. Η δραματική μείωση του χρόνου εκτέλεσης επιτρέπει στους επιστήμονες να προσομοιώνουν σενάρια που συνδυάζουν πιο πολύπλοκα φυσικά φαινόμενα, με πιο λεπτομερή ανάλυση και μεγαλύτερο αριθμό σωματιδίων. Αυτές οι πολύπλοκες, ακριβείς και γρήγορες προσομοιώσεις είναι απαραίτητες στον τομέα της φυσικής της κίνησης των δεσμών σωματιδίων σε κυκλικούς επιταχυντές για να ξεπεραστούν οι τρέχοντες τεχνολογικοί περιορισμοί, να υλοποιηθούν οι επερχόμενες αναβαθμίσεις των επιταχυντών σωματιδίων και να σχεδιαστούν μελλοντικές μηχανές που θα βοηθήσουν την επιστήμη να προοδεύσει περαιτέρω. Το δεύτερο μέρος της διπλωματικής εργασίας επικεντρώνεται στην προσαρμογή και εξειδίκευση του υλικού με σκοπό να καλύψει τις ανάγκες των σύγχρονων εφαρμογών. Οι GPU, που κάποτε χρησιμοποιούνταν για την επιτάχυνση του εφαρμογών γραφικών, έχουν γίνει πλέον η κυρίαρχη πλατφόρμα για την επιτάχυνση εφαρμογών γενικού σκοπού. Η επεξεργαστική τους ισχύς, σε συνδυασμός με την υψηλή ενεργειακή αποδοτικότητα οδήγησαν στην υιοθέτησή τους σε σχεδόν κάθε υπολογιστικό τομέα, συμπεριλαμβανομένης της μηχανικής μάθησης, του επιστημονικών εφαρμογών και των βάσεων δεδομένων. Παρακολουθώντας την συμπεριφορά πολλαπλών εφαρμογών που χρησιμοποιούν GPU, εντοπίστηκε μια σημαντική συλλογή συναρτήσεων, οι οποίες, λόγω περιορισμένου παραλληλισμού δεδομένων, δεν υποστηρίζουν μεγάλο βαθμό παραλληλισμού νημάτων (Thread-Level Parallelism, TLP) και δεν καταφέρνουν να κρύψουν την καθυστέρηση των λειτουργιών μνήμης. Αυτές οι συναρτήσεις αναζητούν πιο επιθετικές στρατηγικές παραλληλισμού επιπέδου εντολών (Instruction-Level Parallelism, ILP) για τη βελτίωση της χρησιμοποίησης των πόρων κατά την εκτέλεση. Αυτή η προβληματική κατάσταση αντιμετωπίζεται με το σχεδιασμό μιας νέας μικροαρχιτεκτονικής GPU με δυνατότητα εκτέλεσης εντολών εκτός σειράς Out-Of-Order, που ονομάζεται LOOG. Το σύστημα LOOG έχει σχεδιαστεί ώστε να επαναχρησιμοποιεί υπάρχοντα εξαρτήματα υλικού και να ελαχιστοποιεί τα επιπρόσθετα κόστη σε ισχύ και μέγεθος επιφάνειας κυκλώματος. Με την εκμετάλλευση του Παραλληλισμού Επιπέδου Εντολών, το οποίο συμπληρώνει το υπάρχον μοντέλο εκτέλεσης Παραλληλισμού Επιπέδου Νήματος, το LOOG ξεπερνά τόσο τις παραδοσιακές πλατφόρμες GPU όσο και άλλες προγενέστερες υλοποιήσεις υψηλών επιδόσεων. Μια διεξοδική συζήτηση των λεπτομερειών του LOOG και των βασικών σχεδιαστικών αποφάσεων που έπρεπε να ληφθούν υπόψη παρέχονται στη διατριβή. Επιπλέον, εκτελείται μια εκτεταμένη εξερεύνηση του χώρου σχεδίασης για να ρυθμιστεί με ακρίβεια το LOOG και να αποδειχθεί η αποτελεσματικότητά του όταν εφαρμόζεται πάνω από μια ποικιλία από παραδοσιακές πλατφόρμες GPU. Ο μηχανισμός LOOG ξεπερνά τις συμβατικές πλατφόρμες κατά 27.6% και 22.4% όσον αφορά τον χρόνο εκτέλεσης και την ενεργειακή απόδοση, αντίστοιχα. Αυτή είναι μια ισχυρή ένδειξη ότι το LOOG είναι μια πολλά υποσχόμενη εναλλακτική μικροαρχιτεκτονική GPU, η οποία είναι ικανή να επεκτείνει την χρήση μελλοντικών συστημάτων GPU σε νέους τομείς εφαρμογών. Συνοψίζοντας, αυτή η διατριβή προτείνει δύο προσεγγίσεις για τη μείωση του χρόνου εκτέλεσης και της κατανάλωσης ενέργειας, προσαρμοσμένες στις συνεχώς αυξανόμενες υπολογιστικές απαιτήσεις των σύγχρονων εφαρμογών. Πρώτον, εστιάζουμε στην σχολαστική προσαρμογή λογισμικού για να αξιοποιήσουμε τους υπάρχοντες πολυεπεξεργαστές και επιταχυντές υλικού, παρέχοντας παράλληλα μια εύχρηστη διεπαφή στους χρήστες. Δεύτερον, διερευνούμε εξειδικευμένες μικροαρχιτεκτονικές με σκοπό την προσαρμογή στις ανάγκες των σύγχρονων εφαρμογών.