research-article

Comprehending performance from real-world execution traces: a device-driver case

Authors:

Xiao Yu,

Shi Han,

Dongmei Zhang,

Tao XieAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 4

Pages 193 - 206

https://doi.org/10.1145/2644865.2541968

Published: 24 February 2014 Publication History

Get Access

Abstract

Real-world execution traces record performance problems that are likely perceived at deployment sites. However, those problems can be rooted subtly and deeply into system layers or other components far from the place where delays are initially observed. To tackle challenges of identifying deeply rooted problems, we propose a new trace-based approach consisting of two steps: impact analysis and causality analysis. The impact analysis measures performance impacts on a component basis, and the causality analysis discovers patterns of runtime behaviors that are likely to cause the measured impacts. The discovered patterns can help performance analysts quickly identify root causes of perceived performance problems. We instantiate our approach to study the performance of device drivers on over 19,500 real-world execution traces. The impact analysis shows that device drivers constitute a non-trivial part (≈ 38) in the overall system performance, and a big part (≈ 26) is due to interactions between drivers. The causality analysis effectively discovers highly suspicious and high-impact behavioral patterns in device drivers, examined and confirmed by our automated evaluation, developers, and performance analysts.

References

[1]

http://msdn.microsoft.com/en-us/library/windows/desktop/bb968803(v=vs.85).aspx.

Google Scholar

[2]

http://en.wikipedia.org/wiki/DTrace.

Google Scholar

[3]

M. K. Aguilera, J. C. Mogul, J. L. Wiener, P. Reynolds, and A. Muthitacharoen. Performance Debugging for Distributed Systems of Black Boxes. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP '03, pages 74--89, New York, NY, USA, 2003. ACM.

Digital Library

Google Scholar

[4]

E. Altman, M. Arnold, S. Fink, and N. Mitchell. Performance Analysis of Idle Programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA'10, pages 739--753, New York, NY, USA, 2010. ACM.

Digital Library

Google Scholar

[5]

G. Ammons, J.-D. Choi, M. Gupta, and N. Swamy. Finding and Removing Performance Bottlenecks in Large Systems. In Proceedings of ECOOP 2004 - Object-Oriented Programming, volume 3086 of Lecture Notes in Computer Science, pages 172--196. Springer Berlin Heidelberg, 2004.

Crossref

Google Scholar

[6]

M. Attariyan, M. Chow, and J. Flinn. X-ray: Automating Root-Cause Diagnosis of Performance Anomalies in Production Software. In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation, OSDI'12, pages 307--320, Berkeley, CA, USA, 2012. USENIX Association.

Digital Library

Google Scholar

[7]

J. Bailey and N. V. Laboratory. Contrast Data Mining: Methods and Applications. Tutorial at ICDM, 2007.

Google Scholar

[8]

G. Balakrishnan and T. Reps. Analyzing Stripped Device-Driver Executables. In Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS'08, pages 124--140, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

Google Scholar

[9]

T. Ball, E. Bounimova, B. Cook, V. Levin, J. Lichtenberg, C. McGarvey, B. Ondrusek, S. K. Rajamani, and A. Ustuner. Thorough Static Analysis of Device Drivers. SIGOPS Oper. Syst. Rev., 40(4):73--85, Apr. 2006.

Digital Library

Google Scholar

[10]

P. Barham, A. Donnelly, R. Isaacs, and R. Mortier. Using Magpie for Request Extraction and Workload Modelling. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation - Volume 6, OSDI'04, pages 18--18, Berkeley, CA, USA, 2004. USENIX Association.

Digital Library

Google Scholar

[11]

S. Boyd-Wickizer and N. Zeldovich. Tolerating Malicious Device Drivers in Linux. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC'10, pages 9--9, Berkeley, CA, USA, 2010. USENIX Association.

Digital Library

Google Scholar

[12]

V. Ganapathy, A. Balakrishnan, M. M. Swift, and S. Jha. Microdrivers: A New Architecture for Device Drivers. In Proceedings of the 11th USENIX Workshop on Hot Topics in Operating Systems, HOTOS'07, pages 15:1--15:6, Berkeley, CA, USA, 2007. USENIX Association.

Digital Library

Google Scholar

[13]

V. Ganapathy, M. J. Renzelmann, A. Balakrishnan, M. M. Swift, and S. Jha. The Design and Implementation of Microdrivers. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XIII, pages 168--178, New York, NY, USA, 2008. ACM.

Digital Library

Google Scholar

[14]

S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A Call Graph Execution Profiler. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, CC'82, pages 120--126, New York, NY, USA, 1982. ACM.

Digital Library

Google Scholar

[15]

M. Grechanik, C. Fu, and Q. Xie. Automatically Finding Performance Problems with Feedback-Directed Learning Software Testing. In Proceedings of the 2012 International Conference on Software Engineering, ICSE'12, pages 156--166, Piscataway, NJ, USA, 2012. IEEE Press.

Digital Library

Google Scholar

[16]

S. Han, Y. Dang, S. Ge, D. Zhang, and T. Xie. Performance Debugging in the Large via Mining Millions of Stack Traces. In Proceedings of the 2012 International Conference on Software Engineering, ICSE'12, pages 145--155, Piscataway, NJ, USA, 2012. IEEE Press.

Digital Library

Google Scholar

[17]

J. H. Huang and C.-W. Chen. On Performance Measurements of TCP/IP and Its Device Driver. In Proc. 17th Conference on Local Computer Networks, pages 568--575, Sept. 1992.

Google Scholar

[18]

G. Jin, L. Song, X. Shi, J. Scherpelz, and S. Lu. Understanding and Detecting Real-World Performance Bugs. In Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation, PLDI'12, pages 77--88, New York, NY, USA, 2012. ACM.

Digital Library

Google Scholar

[19]

M. Jovic, A. Adamoli, and M. Hauswirth. Catch Me If You Can: Performance Bug Detection in the Wild. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA'11, pages 155--170, New York, NY, USA, 2011. ACM.

Digital Library

Google Scholar

[20]

A. Kadav, M. J. Renzelmann, and M. M. Swift. Tolerating Hardware Device Failures in Software. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, SOSP'09, pages 59--72, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[21]

A. Kadav and M. M. Swift. Understanding Modern Device Drivers. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pages 87--98, New York, NY, USA, 2012. ACM.

Digital Library

Google Scholar

[22]

V. Kuznetsov, V. Chipounov, and G. Candea. Testing Closed-Source Binary Device Drivers with DDT. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, USENIXATC'10, pages 12--12, Berkeley, CA, USA, 2010. USENIX Association.

Digital Library

Google Scholar

[23]

B. Leslie, P. Chubb, N. Fitzroy-Dale, S. Gtz, C. Gray, L. Macpherson, D. Potts, Y.-T. Shen, K. Elphinstone, and G. Heiser. User-Level Device Drivers: Achieved Performance. Journal of Computer Science and Technology, 20(5):654--664, 2005.

Crossref

Google Scholar

[24]

J. Li, F. Xie, T. Ball, V. Levin, and C. McGarvey. An Automata-Theoretic Approach to Hardware/Software Co- Verification. In Proceedings of the 13th International Conference on Fundamental Approaches to Software Engineering, FASE'10, pages 248--262, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

Google Scholar

[25]

A. Menon, S. Schubert, and W. Zwaenepoel. TwinDrivers: Semi-Automatic Derivation of Fast and Safe Hypervisor Network Drivers from Guest OS Drivers. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XIV, pages 301--312, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[26]

L. Ryzhyk, P. Chubb, I. Kuz, and G. Heiser. Dingo: Taming Device Drivers. In Proceedings of the 4th ACM European Conference on Computer Systems, EuroSys'09, pages 275--288, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[27]

L. Ryzhyk, P. Chubb, I. Kuz, E. Le Sueur, and G. Heiser. Automatic Device Driver Synthesis with Termite. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, SOSP'09, pages 73--86, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[28]

L. Ryzhyk, J. Keys, B. Mirla, A. Raghunath, M. Vij, and G. Heiser. Improved Device Driver Reliability through Hardware Verification Reuse. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVI, pages 133--144, New York, NY, USA, 2011. ACM.

Digital Library

Google Scholar

[29]

L. Ryzhyk, Y. Zhu, and G. Heiser. The Case for Active Device Drivers. In Proceedings of the 1st ACM Asia-PacificWorkshop on Systems, APSys'10, pages 25--30, New York, NY, USA, 2010. ACM.

Digital Library

Google Scholar

[30]

K. Shen, C. Stewart, C. Li, and X. Li. Reference-Driven Performance Anomaly Identification. In Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'09, pages 85--96, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[31]

M. F. Spear, T. Roeder, O. Hodson, G. C. Hunt, and S. Levi. Solving the Starting Problem: Device Drivers as Self- Describing Artifacts. SIGOPS Oper. Syst. Rev., 40(4):45--57, Apr. 2006.

Digital Library

Google Scholar

[32]

K. Srinivas and H. Srinivasan. Summarizing Application Performance from a Components Perspective. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE'13, pages 136--145, New York, NY, USA, 2005. ACM.

Digital Library

Google Scholar

[33]

M. M. Swift, M. Annamalai, B. N. Bershad, and H. M. Levy. Recovering Device Drivers. ACM Trans. Comput. Syst., 24(4):333--360, Nov. 2006.

Digital Library

Google Scholar

[34]

M. M. Swift, B. N. Bershad, and H. M. Levy. Improving the Reliability of Commodity Operating Systems. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, SOSP'03, pages 207--222, New York, NY, USA, 2003. ACM.

Digital Library

Google Scholar

[35]

N. R. Tallent and J. M. Mellor-Crummey. Effective Performance Measurement and Analysis of Multithreaded Applications. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'09, pages 229--240, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[36]

N. R. Tallent, J. M. Mellor-Crummey, and A. Porterfield. Analyzing Lock Contention in Multithreaded Applications. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'10, pages 269--280, New York, NY, USA, 2010. ACM.

Digital Library

Google Scholar

[37]

L. Wang, H. Zhao, G. Dong, and J. Li. On the Complexity of Finding Emerging Patterns. Theor. Comput. Sci., 335(1):15--27, May 2005.

Digital Library

Google Scholar

[38]

A. Wert, J. Happe, and L. Happe. Supporting Swift Reaction: Automatically Uncovering Performance Problems by Systematic Experiments. In Proceedings of the 2013 International Conference on Software Engineering, ICSE'13, pages 552--561, Piscataway, NJ, USA, 2013. IEEE Press.

Digital Library

Google Scholar

Cited By

View all

Zheng WHua B(2024)WASMDYPA: Effectively Detecting WebAssembly Bugs via Dynamic Program Analysis2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00037(296-307)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00037
Li JZhang YLu SGunawi HGu XHuang FLi D(2023)Performance Bug Analysis and Detection for Distributed Storage and Computing SystemsACM Transactions on Storage10.1145/358028119:3(1-33)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3580281
Li LZhang XHe SKang YZhang HMa MDang YXu ZRajmohan SLin QZhang D(2023)CONAN: Diagnosing Batch Failures for Cloud Systems2023 IEEE/ACM 45th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)10.1109/ICSE-SEIP58684.2023.00018(138-149)Online publication date: May-2023
https://doi.org/10.1109/ICSE-SEIP58684.2023.00018
Show More Cited By

Index Terms

Comprehending performance from real-world execution traces: a device-driver case
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
  2. Software organization and properties
    1. Extra-functional properties
      1. Software performance

Recommendations

Comprehending performance from real-world execution traces: a device-driver case
ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems

Real-world execution traces record performance problems that are likely perceived at deployment sites. However, those problems can be rooted subtly and deeply into system layers or other components far from the place where delays are initially observed. ...
Comprehending performance from real-world execution traces: a device-driver case
ASPLOS '14

Real-world execution traces record performance problems that are likely perceived at deployment sites. However, those problems can be rooted subtly and deeply into system layers or other components far from the place where delays are initially observed. ...
Visualization, transformation, and analysis of execution traces with the eclipse TRACE4CPS trace tool
Abstract
An execution trace is a model of a single system behavior. Execution traces occur everywhere in the system’s lifecycle as they can typically be produced by executable models, by prototypes of (sub)systems, and by the system itself during its ...

Reviews

Reviewer: Amos O Olagunju

How should the impact of individual components and the runtime behaviors of device drivers be probed to inform optimal systems design__?__ Yu and colleagues present algorithms for measuring the performance impact and execution time behaviors of the components of device drivers. The impact investigation uses a wait graph configuration to assess the execution and wait times of device driver components. The wait graph model couples each delayed event with its allied nonstop event to reestablish delay chains between threads, then uses reinstated delay chains to create edge events as graph nodes, and finally applies the timestamps on delay and nonstop events to restore the extent of delay events. The impact analysis uses cases of event trace streams and components of device drivers to compute the respective percentages due to execution, delay, and other costs. Causality analysis uncovers the runtime behaviors of high-impact components of device drivers. The authors correlated the delay, nonstop, and execution traces of components of device drivers with events. They designed an algorithm for syndicating the wait graphs of the high-impact device driver events and for computing the average execution cost for each device driver component. A dataset with massive trace streams and usage settings for Windows and applications was used to gauge the effectiveness of the algorithms. The results reveal that: device drivers significantly affect the performance of operating and application systems; there is a substantial amount of time due to propagation; device drivers consume a slight amount of central processing unit time; and causality analysis accurately uncovered and prioritized patterns of high-impact device driver behavior. Although causality analysis is sporadically unsuccessful in distinguishing between problematic and embedded-design behaviors, the authors provide great insights for identifying the core origins of the performance glitches in device drivers. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 49, Issue 4

ASPLOS '14

April 2014

729 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2644865

Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Sarita Adve
University of Illinois at Urbana-Champ

Issue’s Table of Contents

ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems
February 2014
780 pages
ISBN:9781450323055
DOI:10.1145/2541940
General Chairs:
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Program Chair:
Sarita Adve
University of Illinois at Urbana-Champ

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2014

Published in SIGPLAN Volume 49, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
588
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zheng WHua B(2024)WASMDYPA: Effectively Detecting WebAssembly Bugs via Dynamic Program Analysis2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00037(296-307)Online publication date: 12-Mar-2024
Li JZhang YLu SGunawi HGu XHuang FLi D(2023)Performance Bug Analysis and Detection for Distributed Storage and Computing SystemsACM Transactions on Storage10.1145/358028119:3(1-33)Online publication date: 19-Jun-2023
Li LZhang XHe SKang YZhang HMa MDang YXu ZRajmohan SLin QZhang D(2023)CONAN: Diagnosing Batch Failures for Cloud Systems2023 IEEE/ACM 45th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)10.1109/ICSE-SEIP58684.2023.00018(138-149)Online publication date: May-2023
Calinescu RCortellessa VStefanakos ITrubiani C(2020)Analysis and Refactoring of Software Systems Using Performance Antipattern ProfilesFundamental Approaches to Software Engineering10.1007/978-3-030-45234-6_18(357-377)Online publication date: 17-Apr-2020
He HRen JZhao GZhang YHao X(2019)Mining of Probabilistic Controlling Behavior Model From Dynamic Software Execution TraceIEEE Access10.1109/ACCESS.2019.29229987(79602-79616)Online publication date: 2019
Bernardi SDomínguez JGómez AJoubert CMerseguer JPerez-Palacin DRequeno JRomeu A(2018)A systematic approach for performance assessment using process miningEmpirical Software Engineering10.1007/s10664-018-9606-923:6(3394-3441)Online publication date: 1-Dec-2018
Kang YZhou YXu HLyu MZimmermann TCleland-Huang JSu Z(2016)DiagDroid: Android performance diagnosis via anatomizing asynchronous executionsProceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2950290.2950316(410-421)Online publication date: 1-Nov-2016
Zimmermann TCleland-Huang JSu Z(2016)Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software EngineeringundefinedOnline publication date: 1-Nov-2016
Gao ZXue ZHu XShang WXia Xd'Amorim M(2024)Easy over Hard: A Simple Baseline for Test Failures Causes PredictionCompanion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering10.1145/3663529.3663850(306-317)Online publication date: 10-Jul-2024
Li JZhang YLu SGunawi HGu XHuang FLi D(2023)Performance Bug Analysis and Detection for Distributed Storage and Computing SystemsACM Transactions on Storage10.1145/358028119:3(1-33)Online publication date: 19-Jun-2023
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations