More Like this

1. Towards Fine-Grained Parallelism in Contemporary HPC Applications

   Kerney, J; Raicu, I (May 2024, IIT)

   In recent years we have witnessed large changes in how HPC users express their applications. While many applications still use traditional languages(e.g. C, Fortran) and frameworks(e.g. OpenMP, MPI), new applications are trending towards orchestration. Frameworks such as Parsl [2] and Dask [3] have marked this new era of high-performance computing. Scientists glue these frameworks together with high- performant simulation and data analysis applications written in low-level languages. With this shift towards orchestration, we see serverless computing, a new model of computation taking hold. Using the serverless model, scientists register a compute task with a serverless platform and specify the set of resources that the task can be deployed on. In recent years, orchestration and serverless have trended towards decomposing applications into smaller tasks. This trend is rooted in the fact that decomposing coarse-grained jobs into fine–grained tasks enables clusters to make more precise scheduling decisions. Current HPC orchestration and serverless frameworks efficiently launch and manage coarse-grained jobs, however, they struggle to do the same for fine–grained tasks. In this work we investigate the mechanisms that compose orchestration systems and improve those mechanisms for fine–grained parallelism. We also examine how serverless frameworks are used in the context of HPC systems. For HPC serverless frameworks we propose changes to their software stack to improve their performance. We conclude this work by discussing future directions for fine– grained parallelism in HPC. 

   more » « less
2. Exploring Fine-Grained Parallelism in Data-flow Runtime Systems on Many-Core Systems

   Wang, W; Gonthier, M; Lai, H; Nookala, P; Pan, H; Foster, I; Raicu, I; Chard, K (November 2025, IEEE/ACM)

   High synchronization overhead in frameworks like GNU OpenMP impedes fine-grained task parallelism on many-core architectures. We introduce three advances to GNU OpenMP: a lock-less concur- rent queue (XQueue), a scalable distributed tree barrier, and two NUMA-aware, lock-less load balancing strategies. Evaluated with Barcelona OpenMP Task Suite (BOTS) bench- marks, our XQueue and tree barrier improve performance by up to 1522.8×over the original GNU OpenMP. The load balancing strate- gies provide an additional performance improvement of up to 4×. We further apply these techniques to the TaskFlow runtime, demon- strating performance and scalability gains in selected applications while also analyzing the inherent limitations of the lock-less ap- proach on x86 architectures. 

   more » « less
3. Reasoning about recursive tree traversals

   https://doi.org/10.1145/3437801.3441617  

   Wang, Yanjun; Liu, Jinwei; Zhang, Dalin; Qiu, Xiaokang (February 2021, Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming)

   null (Ed.)

   Traversals are commonly seen in tree data structures, and performance-enhancing transformations between tree traversals are critical for many applications. Existing approaches to reasoning about tree traversals and their transformations are ad hoc, with various limitations on the classes of traversals they can handle, the granularity of dependence analysis, and the types of possible transformations. We propose Retreet, a framework in which one can describe general recursive tree traversals, precisely represent iterations, schedules and dependences, and automatically check data-race-freeness and transformation correctness. The crux of the framework is a stack-based representation for iterations and an encoding to Monadic Second-Order (MSO) logic over trees. Experiments show that Retreet can automatically verify optimizations for complex traversals on real-world data structures, such as CSS and cycletrees, which are not possible before. Our framework is also integrated with other MSO-based analysis techniques to verify even more challenging program transformations. 

   more » « less
4. A Decidable Logic for Tree Data-Structures with Measurements

   https://doi.org/10.1007/978-3-030-11245-5_15  

   Qiu, Xiaokang; Wang, Yanjun (January 2019, 20th International Conference on Verification, Model Checking, and Abstract Interpretation)

   We present DRYADdec, a decidable logic that allows reasoning about tree data-structures with measurements. This logic supports user-defined recursive measure functions based on Max or Sum, and recursive predicates based on these measure functions, such as AVL trees or red-black trees. We prove that the logic’s satisfiability is decidable. The crux of the decidability proof is a small model property which allows us to reduce the satisfiability of DRYADdec to quantifier-free linear arithmetic theory which can be solved efficiently using SMT solvers. We also show that DRYADdec can encode a variety of verification and synthesis problems, including natural proof verification conditions for functional correctness of recursive tree-manipulating programs, legality conditions for fusing tree traversals, synthesis conditions for conditional linear-integer arithmetic functions. We developed the decision procedure and successfully solved 220+ DRYADdec formulae raised from these application scenarios, including verifying functional correctness of programs manipulating AVL trees, red-black trees and treaps, checking the fusibility of height-based mutually recursive tree traversals, and counterexample-guided synthesis from linear integer arithmetic specifications. To our knowledge, DRYADdec is the first decidable logic that can solve such a wide variety of problems requiring flexible combination of measure-related, data-related and shape-related properties for trees. 

   more » « less
5. Towards Fine-Grained Parallelism in Parallel and Distributed Python Libraries

   https://doi.org/10.1109/IPDPSW63119.2024.00133  

   Kerney, Jamison; Raicu, Ioan; Raicu, John; Chard, Kyle (May 2024, IEEE)

   There is a growing need, for example in machine learning and analytics, to decompose applications into smaller schedulable units. Such decomposition can improve perfor- mance, reduce energy consumption, and increase resource utilization. Unfortunately, enabling fine-grained parallelism comes with significant overheads and requires improvements at all layers of the programming stack. We consider the challenges of supporting fine-grained parallelism in the increasingly popu- lar Python-based programming libraries. Specifically, we focus on Parsl, a Python library that is widely used to parallelize the execution of fine-grained Python functions. Parsl’s Python- based runtime supports a maximum throughput of around 1200 tasks per second—insufficient to meet modern application needs. We perform a comprehensive analysis of Parsl and iden- tify areas that prohibit it from achieving higher throughput. We first profile Parsl components and identify that, with fine- grained tasks workers are often not saturated. We find that tasks spend a majority of their time in the components between the scheduler and worker, however, we also learned that the scheduler is capable of submitting thousands of tasks per second. We then focused on developing new optimizations and implementing crucial components in C to improve throughput. Our new implementation increases Parsl’s throughput 6 fold. 

   more » « less