SAFARI Live Sem. - Accelerating Irregular Applications via Efficient Synch. & Data Access Techniques

Title: Accelerating Irregular Applications via Efficient Synchronization and Data Access Techniques Speaker: Christina Giannoula, Ph.D. candidate in the School of Electrical and Computer Engineering at the National Technical University of Athens (NTUA) SAFARI Live Seminar Talk https://safari.ethz.ch/safari-live-seminar-christina-giannoula-nov-2022/ Slides (pdf): https://safari.ethz.ch/safari_public_wp/wp-content/uploads/final-PhD-cgiannoula_safari_live_seminar_clean.pdf Slides (pptx): https://safari.ethz.ch/safari_public_wp/wp-content/uploads/final-PhD-cgiannoula_safari_live_seminar_clean.pptx Papers (PDF): [1] "SparseP: Towards Efficient Sparse Matrix Vector Multiplication on Real Processing-In-Memory Architecture": https://people.inf.ethz.ch/omutlu/pub/SparseP-SpMV-in-Real-Processing-in-Memory-Systems_pomacs22-arxiv22.pdf [2] "SynCron: Efficient Synchronization Support for Near-Data-Processing Architectures": https://people.inf.ethz.ch/omutlu/pub/SynCron-synchronization-for-near-data-processing-systems_hpca21.pdf [3] "An Adaptive Concurrent Priority Queue for NUMA Architectures": https://dl.acm.org/doi/abs/10.1145/3310273.3323164 [4] "Combining HTM with RCU to Speed up Graph Coloring on Multicore Platforms": https://link.springer.com/chapter/10.1007/978-3-319-92040-5_18 Abstract: Irregular applications comprise an increasingly important workload domain for many fields, including bioinformatics, chemistry, web graph analysis, physics, social sciences and machine learning. Therefore, achieving high performance and energy efficiency in the execution of emerging irregular applications is of vital importance nowadays. While there is abundant research on accelerating irregular applications, we identify two critical performance challenges. First, irregular applications are hard to scale to a high number of parallel threads due to high synchronization overheads. Second, irregular applications incur complex memory access patterns and exhibit low operational intensity, thus they are bottlenecked by expensive data access costs. In this seminar, we will discuss the root causes of inefficiency of irregular applications in modern computing systems, and we will present low-overhead synchronization techniques and well-crafted data access policies to fundamentally address such inefficiencies in CPU and Near-Data-Processing (NDP/PIM) systems. We make four contributions. First, we will describe ColorTM, a novel parallel graph coloring algorithm for CPU systems that proposes an efficient data management technique co-designed with a speculative synchronization scheme implemented on Hardware Transactional Memory. Second, we will introduce SmartPQ, an adaptive concurrent priority queue that tunes itself by dynamically switching between a NUMA-oblivious and a NUMA-aware algorithmic mode to achieve high performance under all various contention scenarios in NUMA CPU systems. Third, we present SynCron, a practical and lightweight hardware synchronization mechanism tailored for NDP/PIM systems. Finally, we will discuss SparseP, the first open-source library for high-performance Sparse Matrix Vector Multiplication (SpMV) on real NDP/PIM systems. Overall, we will 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 techniques, thus providing a high amount of parallelism, low-overhead inter-thread communication, and low data access and data movement costs. We hope that this seminar inspires future work in co-designing software algorithms with modern computing platforms to significantly accelerate emerging irregular applications. Speaker Bio: Christina Giannoula is a Ph.D. candidate in the School of Electrical and Computer Engineering at the National Technical University of Athens (NTUA) advised by Prof. Georgios Goumas, Prof. Nectarios Koziris and Prof. Onur Mutlu. She is working in the Computing Systems Laboratory, and the SAFARI research group at ETH Zürich, which is led by Prof. Onur Mutlu. Her research interests lie in the intersection of computer architecture and high-performance computing. Specifically, her research focuses on the hardware/software co-design of emerging applications, including graph processing, pointer-chasing data structures, machine learning workloads, and sparse linear algebra, with modern computing paradigms, such as large-scale multicore systems and near-data processing architectures. Christina Giannoula will be joining the University of Toronto as a PostDoctoral Researcher in Winter 2023. Past SAFARI Live Seminars: https://safari.ethz.ch/safari-seminar-series/ RECOMMENDED: =============== Interview with Onur Mutlu: https://www.youtube.com/watch?v=8ffSEKZhmvo&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=9 Public Lectures by Onur Mutlu: https://www.youtube.com/watch?v=kgiZlSOcGFM&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl