Accelerating irregular applications via efficient synchronization and data access techniques

Abstract

Irregular applications comprise an increasingly important workload domain for many fields, including bioinformatics, chemistry, graph analytics, physics, social sciences and machine learning. Therefore, achieving high performance and energy efficiency in the execution of emerging irregular applications is of vital importance. While there is abundant research on accelerating irregular applications, in this thesis, we identify two critical challenges. First, irregular applications are hard to scale to a high number of parallel threads due to high synchronization overheads. Second, irregular applications have complex memory access patterns and exhibit low operational intensity, and thus they are bottlenecked by expensive data access costs. This doctoral thesis studies the root causes of inefficiency of irregular applications in modern computing systems, and aims to fundamentally address such inefficiencies, by 1) proposing low-overhead synchronization techniques among parallel threads in cooperation with 2) well-crafted data access policies. Our approach leads to high system performance and energy efficiency on the execution of irregular applications in modern computing platforms, both processor-centric CPU systems and memory-centric Processing-In-Memory (PIM) systems. We make four major contributions to accelerating irregular applications in different contexts including CPU and Near-Data-Processing (NDP) (or Processing-In-Memory (PIM)) systems. First, we design ColorTM, a novel parallel graph coloring algorithm for CPU systems that trades off using synchronization with lower data access costs. ColorTM proposes an efficient data management technique co-designed with a speculative synchronization scheme implemented on Hardware Transactional Memory, and significantly outperforms prior state-of-the-art graph coloring algorithms across a wide range of real-world graphs. Second, we propose SmartPQ, an adaptive priority queue that achieves high performance under all various contention scenarios in Non-Uniform Memory Access (NUMA) CPU systems. SmartPQ tunes itself by dynamically switching between a NUMA-oblivious and a NUMA-aware algorithmic mode, thus providing low data access costs in high contention scenarios, and high levels of parallelism in low contention scenarios. Our evaluations show that SmartPQ achieves the highest throughput over prior state-of-the-art NUMA-aware and NUMA-oblivious concurrent priority queues under various contention scenarios and even when contention varies during runtime. Third, we introduce SynCron, the first practical and lightweight hardware synchronization mechanism tailored for NDP systems. SynCron minimizes synchronization overheads in NDP systems by (i) adding low-cost hardware support near memory for synchronization acceleration, (ii) directly buffering the synchronization variables in a specialized cache memory structure, (ii) implementing a hierarchical message-passing communication scheme, and (iv) integrating a hardware-only overflow management scheme to avoid performance degradation when hardware resources for synchronization tracking are exceeded. We demonstrate that SynCron outperforms prior state-of-the-art approaches both in performance and energy consumption using a wide range of irregular applications, and has low hardware area and power overheads. Fourth, we design SparseP, the first library for high-performance Sparse Matrix Vector Multiplication (SpMV) on real Processing-In-Memory (PIM) systems. SparseP is publicly-available and includes a wide range of data partitioning, load balancing, compression and synchronization techniques to accelerate this irregular kernel in current and future PIM systems. We also extensively characterize the widely used SpMV kernel on a real PIM architecture, and provide recommendations for software, system and hardware designers of future PIM systems.Overall, we demonstrate that the execution of irregular applications in CPU and NDP/PIM architectures can be significantly accelerated by co-designing lightweight synchronization approaches along with well-crafted data access policies. This dissertation shows that efficient synchronization and data access techniques can provide a high amount of parallelism, low-overhead inter-thread communication and low data access and data movement costs in emerging irregular applications, thus significantly improving system performance and system energy. This doctoral thesis also bridges the gap between processor-centric CPU systems and memory-centric PIM systems in the critically-important area of irregular applications. We hope that this dissertation inspires future work in co-designing software algorithms with cutting-edge computing platforms to significantly accelerate emerging irregular applications.

Οι μη-κανονικές εφαρμογές, όπως οι εφαρμογές επεξεργασίας γράφων, παράλληλων δομών δεδομένων και επίλυσης αραιών γραμμικών συστημάτων, αποτελούν μία από τις πιο σημαντικές οικογένειες υπολογιστικών εφαρμογών στις μέρες μας. Ως αποτέλεσμα, πολλοί ερευνητές έχουν μελετήσει και προτείνει τεχνικές βελτίωσης της επίδοσης και της ενεργειακής κατανάλωσης των μη-κανονικών εφαρμογών σε σύγχρονες πολυπύρηνες αρχιτεκτονικές. Σε αυτήν την διδακτορική διατριβή εντοπίζουμε δύο σημαντικές προκλήσεις σε αυτή την οικογένεια εφαρμογών. Πρώτον, οι παράλληλες μη-κανονικές εφαρμογές είναι δύσκολο να κλιμακώσουν χρησιμοποιώντας ένα μεγάλο αριθμό νημάτων λόγω του υψηλού κόστους συγχρονισμού μεταξύ των νημάτων. Δεύτερον, οι μη-κανονικές εφαρμογές εμφανίζουν πολύπλοκα μοτίβα πρόσβασης των δεδομένων στη μνήμη, και χαμηλή υπολογιστική ικανότητα, με αποτέλεσμα επίδοσή τους περιορίζεται σημαντικά από τις δαπανηρές προσβάσεις δεδομένων στη μνήμη.Αυτή η διδακτορική διατριβή πραγματοποιεί μία εις βάθος ανάλυση της κλιμακωσιμότητας των μη-κανονικών εφαρμογών και αναδεικνύει τα κυριότερα προβλήματα επίδοσής τους. Σε αυτήν την διδακτορική διατριβή υποστηρίζουμε ότι αποδοτικές τεχνικές συγχρονισμού των παράλληλων νημάτων σε συνεργασία με βελτιστοποιημένες τεχνικές διαχείρισης δεδομένων τόσο σε επίπεδο λογισμικού όσο και σε επίπεδο υλικού προσφέρουν υψηλή κλιμακωσιμότητα και σημαντική επίδοση στις μη-κανονικές εφαρμογές. Ως εκ τούτου, προτείνουμε 4 διαφορετικές προσεγγίσεις για την επιτάχυνση μη-κανονικών εφαρμογών σε διαφορετικά περιβάλλοντα, συμπεριλαμβανομένων των κοινών πολυπύρηνων αρχιτεκτονικών και των αρχιτεκτονικών με επεξεργασία κοντά στη μνήμη: (α) Ένας νέος παράλληλος αλγόριθμος χρωματισμού γράφων για πολυπύρηνες αρχιτεκτονικές που προτείνει μία αποδοτική τεχνική διαχείρισης δεδομένων, η οποία συνδυάζεται αρμονικά με το μηχανισμό συγχρονισμού σε επίπεδο υλικού, (β) Μία παράλληλη ουρά προτεραιότητας που εναλλάσσεται δυναμικά μεταξύ δύο αλγοριθμικών σχημάτων, και εκμεταλλεύεται την τοπικότητα δεδομένων με σκοπό να επιτευχθεί υψηλή απόδοση υπό διαφορετικά σενάρια συμφόρησης σε αρχιτεκτονικές με ανομοιόμορφη πρόσβαση στη μνήμη, (γ) Ένας πρακτικός μηχανισμός συγχρονισμού σε επίπεδου υλικού για αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη, και (δ) Μία βιβλιοθήκη αλγορίθμων του υπολογιστικού πυρήνα του πολλαπλασιασμού αραιού πίνακα με διάνυσμα, η οποία περιλαμβάνει μία μεγάλη ποικιλία αποτελεσματικών τεχνικών διαμέρισης δεδομένων και συγχρονισμού για αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη. Συνολικά, στην παρούσα διδακτορική διατριβή αποδεικνύουμε ότι η εκτέλεση μη-κανονικών υπολογιστικών πυρήνων σε πολυπύρηνες αρχιτεκτονικές και αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη μπορεί να επιταχυνθεί με το συν-σχεδιασμό αποδοτικών μηχανισμών συγχρονισμού με βελτιστοποιημένες τεχνικές πρόσβασης και διαχείρισης δεδομένων, παρέχοντας έτσι υψηλά επίπεδα παραλληλισμού, χαμηλό κόστος πρόσβασης στα δεδομένα και χαμηλό κόστος συγχρονισμού για την υψηλή επίδοση και τη χαμηλή ενεργειακή κατανάλωση του συστήματος. Ελπίζουμε ότι η παρούσα διατριβή θα εμπνεύσει μελλοντική έρευνα στο συν-σχεδιασμό μη-κανονικών υπολογιστικών πυρήνων με σύγχρονες υπολογιστικές πλατφόρμες για να επιτευχθεί υψηλή επίδοση και χαμηλή ενεργειακή κατανάλωση σε αναδυόμενες εφαρμογές.