• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:A Granularity Characterization of Task Scheduling Effectiveness View PDF HTML (experimental)Abstract:Task-based runtime systems provide flexible load balancing and portability for parallel scientific applications, but their strong scaling is highly sensitive to task granularity. • As parallelism increases, scheduling overhead may transition from negligible to dominant, leading to rapid drops in performance for some algorithms, while remaining negligible for others. • Although such effects are widely observed empirically, there is a general lack of understanding how algorithmic structure impacts whether dynamic scheduling is always beneficial. • In this work, we introduce a granularity characterization framework that directly links scheduling overhead growth to task-graph dependency topology. • We show that dependency structure, rather than problem size alone, governs how overhead scales with parallelism. • Based on this observation, we characterize execution behavior using a simple granularity measure that indicates when scheduling overhead can be amortized by parallel computation and when scheduling overhead dominates performance.

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:A Granularity Characterization of Task Scheduling Effectiveness View PDF HTML (experimental)Abstract:Task-based runtime systems provide flexible load balancing and portability for parallel scientific applications, but their strong scaling is highly sensitive to task granularity. As parallelism increases, scheduling overhead may transition from negligible to dominant, leading to rapid drops in performance for some algorithms, while remaining negligible for others. Although such effects are widely ob

Sources: