DepGraph: Localizing Performance Bottlenecks in Multi-Core Applications Using Waiting Dependency Graphs and Software Tracing

Abstract

This paper addresses the challenge of understanding the waiting dependencies between the threads and hardware resources required to complete a task. The objective is to improve software performance by detecting the underlying bottlenecks caused by system-level blocking dependencies. In this paper, we use a system level tracing approach to extract a Waiting Dependency Graph that shows the breakdown of a task execution among all the interleaving threads and resources. The method allows developers and system administrators to quickly discover how the total execution time is divided among its interacting threads and resources. Ultimately, the method helps detecting bottlenecks and highlighting their possible causes. Our experiments show the effectiveness of the proposed approach in several industry-level use cases. Three performance anomalies are analysed and explained using the proposed approach. Evaluating the method efficiency reveals that the imposed overhead never exceeds 10.1%, therefore making it suitable for in-production environments.

Source: arXiv:2103.04933 abstract; public preprint version

Problem and motivation

System-level traces expose waiting and resource interactions, but conventional analysis does not present a compact causal view of why requests are delayed across threads and resources.

Method and contribution

DepGraph collects LTTng kernel events, reconstructs process/resource states in a state database, recursively builds duration-weighted Waiting Dependency Graphs, groups executions with k-means, and compares representative graphs to expose direct and indirect dependencies.

Findings and evidence

The method identified lock contention in a slow Apache/PHP request, CPU/interruption contention in Cyclictest, and disk contention in Apache workloads. Across Sysbench CPU/IO/mixed workloads, dependency tracing stayed within 10.1% relative duration overhead; Babeltrace 3 decoding and graph analysis remained measurable but practical on the test machine.

Limitations and future directions

Limitations: The study uses one Linux machine and selected workloads/use cases. The graph is primarily an off-CPU/resource-waiting abstraction; broad portability, distributed/network causal analysis, and causal validation beyond graph comparison are unknown.

Future work: Extend the graph model and evaluation to broader systems, workloads, and distributed/network settings; reduce state/decoding cost and improve automated interpretation of graph differences.

Sources and identifiers

• Published version published
• Public preprint · PDF public_full_text
• arXiv version arXiv 2103.04933

When to cite this paper

Cite this paper when your work uses or compares waiting Dependency Graphs that unify thread and resource waiting causes.

• For Waiting Dependency Graphs that unify thread and resource waiting causes.
• For distinguishing direct wakeup dependencies from indirect CPU/disk contention dependencies in kernel traces.
• For grouping executions with k-means and comparing representative dependency graphs.
• For the measured worst-case 10.1% dependency-tracing overhead on the stated Sysbench setup.

Citation

@inproceedings{ezzatiJivan2020depgraphlocalizing,
  author = {Naser Ezzati-Jivan and Quentin Fournier and Michel R. Dagenais and Abdelwahab Hamou-Lhadj},
  title = {DepGraph: Localizing Performance Bottlenecks in Multi-Core Applications Using Waiting Dependency Graphs and Software Tracing},
  year = {2020},
  booktitle = {IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM)},
  pages = {149-159},
  publisher = {IEEE},
  doi = {10.1109/SCAM51674.2020.00022},
  url = {https://doi.org/10.1109/SCAM51674.2020.00022}
}

Ezzati-Jivan, N., Fournier, Q., Dagenais, M. R., & Hamou-Lhadj, A. (2020). DepGraph: Localizing Performance Bottlenecks in Multi-Core Applications Using Waiting Dependency Graphs and Software Tracing. In IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM) (pp. 149-159). https://doi.org/10.1109/SCAM51674.2020.00022

N. Ezzati-Jivan, Q. Fournier, M. R. Dagenais, and A. Hamou-Lhadj, "DepGraph: Localizing Performance Bottlenecks in Multi-Core Applications Using Waiting Dependency Graphs and Software Tracing," in IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM), pp. 149-159, 2020, doi: 10.1109/SCAM51674.2020.00022