2021 · International Journal of Parallel Programming
Automated Generation of Model-Based Constraints for Common Multi-core and Real-Time Applications Using Execution Tracing
Evidence basis: metadata-only · Review status: catalog-reviewed; paper-author approval pending
system-tracing multicore-systems trace-analysis performance-analysis lttng
model-based constraints execution tracing multi-core systems real-time applications constraint generation LTTng Trace Compass cyclictest JACK2 wakelock
Core contribution: The paper automatically builds an approximate workflow model and adaptive quantitative constraints from user-space and kernel execution traces, reducing manual model construction for real-time and multicore diagnosis.
Problem and motivation
Manual model and constraint construction for concurrent real-time applications requires substantial system knowledge and effort, even though low-overhead tracing provides the evidence needed for verification.
Method and contribution
The method organizes trace events per thread, groups similar sequences with longest-common-subsequence matching using strict or flexible key-value matching, removes unneeded repetitions, builds a state model, and infers adaptive constraint operators and values from runtime timing distributions. The model is presented for user checking and correction; LTTng is explicitly used in the cyclictest case.
Findings and evidence
The generated model detects the JACK2 xrun, the cyclictest outlier, and the in-kernel wakelock priority inversion. For cyclictest, a manually set 3-ms deadline is inferred as about 2.685 ms. In the reported evaluation, model construction is dominant - about 7 minutes for full cyclictest - while traces range from 321 UST and 419,164 kernel events for JACK2 to 41,677 UST and 208,489 kernel events for cyclictest and 42 UST and 194,997 kernel events for wakelock.
Limitations and future directions
Limitations: Generated models can contain extra constraints and still need user correction. The evaluation emphasizes common real-time cases with relatively simple loops and does not establish performance across more complex modeling requirements.
Future work: Build and detect models on the fly, compatible with LTTng flight-recorder mode.
Sources and identifiers
- Published version published
When to cite this paper
Cite this paper when generating model-based real-time constraints or using user-space and kernel traces for multicore diagnosis.
- Automatic workflow extraction from per-thread traces using sequence matching.
- Adaptive timing constraints inferred from runtime trace values.
- LTTng-backed JACK2, cyclictest, and kernel-wakelock case studies.
Citation
@article{ezzatiJivan2021automatedgeneration,
author = {Raphael Beamonte and Naser Ezzati-Jivan and Michel R. Dagenais},
title = {Automated Generation of Model-Based Constraints for Common Multi-core and Real-Time Applications Using Execution Tracing},
year = {2021},
journal = {International Journal of Parallel Programming},
volume = {49},
number = {1},
pages = {104-134},
publisher = {Springer Science and Business Media LLC},
issn = {0885-7458, 1573-7640},
doi = {10.1007/s10766-020-00689-5},
url = {https://doi.org/10.1007/s10766-020-00689-5}
}Other citation formats for Word and reference managers
Beamonte, R., Ezzati-Jivan, N., & Dagenais, M. R. (2021). Automated Generation of Model-Based Constraints for Common Multi-core and Real-Time Applications Using Execution Tracing. International Journal of Parallel Programming, 49(1), 104-134. https://doi.org/10.1007/s10766-020-00689-5R. Beamonte, N. Ezzati-Jivan, and M. R. Dagenais, "Automated Generation of Model-Based Constraints for Common Multi-core and Real-Time Applications Using Execution Tracing," International Journal of Parallel Programming, vol. 49, no. 1, pp. 104-134, 2021, doi: 10.1007/s10766-020-00689-5