Beyond the DAG: Visualizing Scheduling Bottlenecks in Task-Based Applications

• Alisson dos Passos Fumaco UFRGS
• Lucas Mello Schnorr UFRGS

DOI: https://doi.org/10.5753/eradrs.2026.20569

Resumo

Diagnosing starvation in task-based runtimes like StarPU typically requires tedious manual inspection of complex Directed Acyclic Graphs (DAGs). We propose a visual methodology that abstracts dependencies to evaluate critical path handling at a glance. Combining an enhanced k-iteration chart with StarVZ’s lackready panel reveals scheduling bottlenecks without granular DAG analysis. We validate this approach by comparing Work Stealing (WS) and Locality Work Stealing (LWS) schedulers executing a tiled QR factorization. Visual evidence confirms WS achieves a statistically significant makespan improvement by sacrificing cache locality to unroll critical tasks, effectively preventing starvation and outperforming LWS.

Referências

Augonnet, C., Thibault, S., Namyst, R., and Wacrenier, P.-A. (2009). Starpu: A unified platform for task scheduling on heterogeneous multicore architectures. In Sips, H., Epema, D., and Lin, H.-X., editors, Euro-Par 2009 Parallel Processing, pages 863–874, Berlin, Heidelberg. Springer Berlin Heidelberg.

Brinkmann, S., Gracia, J., and Niethammer, C. (2013). Task debugging with temanejo. In Cheptsov, A., Brinkmann, S., Gracia, J., Resch, M. M., and Nagel, W. E., editors, Tools for High Performance Computing 2012, pages 13–21, Berlin, Heidelberg. Springer Berlin Heidelberg.

Coulomb, K., Degomme, A., Faverge, M., and Trahay, F. (2011). An open source tool chain for performance analysis. In 5th Parallel Tools Workshop, Dresden, Germany.

Leandro Nesi, L., Garcia Pinto, V., Cogo Miletto, M., and Schnorr, L. M. (2020). StarVZ: Performance Analysis of Task-Based Parallel Applications. working paper or preprint.