Visualizing algorithmic progression in task-based parallelism : a visual analytics methodology for evaluating dynamic schedulers

Abstract

The shift towards multicore architectures has increasingly positioned task-based parallelism as a prominent paradigm for high-performance computing (HPC). While runtime systems like StarPU dynamically schedule tasks using directed acyclic graphs (DAGs) to optimize execution, their complex queue management heuristics make performance analysis increasingly difficult. Traditional profiling tools, heavily reliant on timelinebased Gantt charts, often become visually overwhelming at scale and struggle to provide an application-oriented perspective, hindering the diagnosis of performance bottlenecks. This dissertation proposes a two-stage visual analytics methodology to address this diagnostic gap. We first establish an iteration-centric paradigm that reorients performance profiles by mapping task execution metrics to algorithmic iterations, validating its diagnostic expressiveness under diverse scheduling and hardware constraints. Building upon these foundations, we introduce the k-hills visualization, a condensed 2D visualization technique that shifts the analytical focus from individual task lifespans to the aggregated computational volume applied across algorithmic iterations. By mapping the fraction of hardware dedicated to each task type over time, the visualization establishes a geometric column sum rule that instantly exposes hardware utilization and dependency-induced stalls. To validate the proposed methodology, we conduct a case study evaluating a dense tiled QR factorization on a 32-thread architecture. The study contrasts two dynamic scheduling policies: Work Stealing (WS) and Locality Work Stealing (LWS). While macroscopic metrics indicate a significant performance degradation for LWS, they cannot explain its root cause. The k-hills visualization successfully decodes this anomaly, visually proving that LWS falls into a locality trap—anchoring workers to heavy, older matrix updates and stalling the critical path. Conversely, the visualization demonstrates how WS actively unrolls the DAG, maintaining parallel throughput and preventing mid-execution starvation. Additionally, we compare StarPU and OpenMP signatures to show how the methodology exposes distinct scheduling behaviors and localized implementation anomalies. Ultimately, this work provides HPC developers with an intuitive, algorithm-aware diagnostic tool capable of translating abstract scheduler mechanics into actionable visual signatures.