<  Back to the Polytechnique Montréal portal

Efficient methods for trace analysis parallelization

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

Article (2019)

Open Access document in PolyPublie
Open Access to the full text of this document
Accepted Version
Terms of Use: All rights reserved
Download (939kB)
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

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2706 Software engineering
2700 Information technology > 2715 Optimization
Department: Department of Computer Engineering and Software Engineering
Grant number: CRDPJ468687-14
PolyPublie URL: https://publications.polymtl.ca/4212/
Journal Title: International Journal of Parallel Programming (vol. 47, no. 5-6)
Publisher: Springer
DOI: 10.1007/s10766-019-00631-4
Official URL: https://doi.org/10.1007/s10766-019-00631-4
Date Deposited: 09 Mar 2020 12:44
Last Modified: 13 May 2023 19:33
Cite in APA 7: Reumont-Locke, F., Ezzati-Jivan, N., & Dagenais, M. (2019). Efficient methods for trace analysis parallelization. International Journal of Parallel Programming, 47(5-6), 951-972. https://doi.org/10.1007/s10766-019-00631-4


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item