<  Back to the Polytechnique Montréal portal

Efficient methods for trace analysis parallelization

Fabien Reumont-Locke, Naser Ezzati-Jivan and Michel R. Dagenais

Article (2019)

Accepted Version
Terms of Use: All rights reserved.
Download (1MB)
Cite this document: Reumont-Locke, F., Ezzati-Jivan, N. & Dagenais, M. R. (2019). Efficient methods for trace analysis parallelization. International Journal of Parallel Programming, 47(5-6), p. 951-972. doi:10.1007/s10766-019-00631-4
Show abstract Hide abstract


Tracing provides a low-impact, high-resolution way to observe the execution of a system. As the amount of parallelism in traced systems increases, so does the data generated by the trace. Most trace analysis tools work in a single thread, which hinders their performance as the scale of data increases. In this paper, we explore parallelization as an approach to speedup system trace analysis. We propose a solution which uses the inherent aspects of the CTF trace format to create balanced and parallelizable workloads. Our solution takes into account key factors of parallelization, such as good load balancing, low synchronization overhead and an efficient resolution of data dependencies. We also propose an algorithm to detect and resolve data dependencies during trace analysis, with minimal locking and synchronization. Using this approach, we implement three different trace analysis programs: event counting, CPU usage analysis and I/O usage analysis, to assess the scalability in terms of parallel efficiency. The parallel implementations achieve parallel efficiency above 56% with 32 cores, which translates to a speedup of 18 times the serial speed, when running the parallel trace analyses and using trace data stored on consumer-grade solid state storage devices. We also show the scalability and potential of our approach by measuring the effect of future improvements to trace decoding on parallel efficiency.

Uncontrolled Keywords

tracing; trace analysis; parallel computing

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2706 Génie logiciel
2700 Technologie de l'information > 2715 Optimisation
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Grant number: CRDPJ468687-14
Date Deposited: 09 Mar 2020 12:44
Last Modified: 10 Mar 2020 01:20
PolyPublie URL: https://publications.polymtl.ca/4212/
Document issued by the official publisher
Journal Title: International Journal of Parallel Programming (vol. 47, no. 5-6)
Publisher: Springer
Official URL: https://doi.org/10.1007/s10766-019-00631-4


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only