Speeding up test execution with increased cache locality. (22nd June 2018)

• Record Type: Journal Article
• Authors: Stratis, Panagiotis; Rajan, Ajitha
• Is Part Of: Software testing, verification & reliability. Volume 28:Number 5(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-06-22
• Subjects: cache misses -- instruction locality -- testing; Computer software -- Testing -- Periodicals; Computer software -- Verification -- Periodicals; Computer software -- Reliability -- Periodicals; 005.14
• DOI: 10.1002/stvr.1671
• Languages: English
• ISSNs: 0960-0833

Abstract

Summary: As the scale and complexity of software increases, the number of tests needed for effective validation becomes extremely large. Executing these large test suites is expensive, both in terms of time and energy. Cache misses are a significant contributing factor to execution time of software. We propose an approach that helps order test executions in a test suite in such a way that instruction cache misses are reduced. We also ensure that the approach scales to large test suite sizes. We conduct an empirical evaluation with 20 subject programs and test suites from the SIR repository, EEMBC suite, and LLVM Symbolizer, comparing execution times and cache misses with test orderings maximising instruction locality versus a traditional ordering maximising coverage and random permutations. We also assess overhead of algorithms in generating the orderings that optimise cache locality. Nature of programs and tests impact the performance gained with our approach. Performance gains were considerable for programs and test suites where the average number of different instructions executed between tests was high. We achieved an average execution speedup of 6.83% and a maximum execution speedup of 17% over subject programs with differing control flow between test executions. Abstract : We propose an approach that helps order test executions in a test suite in such a way that instruction cache misses are reduced. The ordering of tests uses a distance metric based on visited basic blocks in test executions and nearest neighbour analysis. We ensure our approach scales to large test suites. We evaluated our approach with 20 subject programs and test suites. For test suite execution, we achieved an average speedup of 7% and a maximum speedup of 17%.