Rajan, Ajitha

Franke, Bjoern

Stratis, Panagiotis

2020-06-08T12:19:20Z

2020-06-08T12:19:20Z

2020-06-25

The requirements and responsibilities assumed by software have increasingly rendered it to be large and complex. Testing to ensure that software meets all its requirements and is free from failures is a difficult and time-consuming task that necessitates the use of large test suites, containing many test cases. Time needed to compile and execute large test suites has become prohibitive. Current optimization techniques aim to reduce the test suite size by removing redundant test cases. However, as systems become larger, the number of essential test cases is still very large and affects the software life-cycle. In this thesis, we explore techniques for reducing the compilation and the execution time of test suites without removing any test cases or changing computing infrastructure. All of our proposed techniques can be used in conjunction with existing test suite optimisations. 1. For test suite compilation, we propose a data transformation that reduces the number of instructions in the test code, which in turn reduces compilation time. Using two well known compilers, GCC and Clang, we conduct empirical evaluations using subject programs from industry standard benchmarks and an industry provided program. We evaluate compilation speedup, execution time, scalability and correctness of the proposed test code transformation. 2. For test suite execution, we propose a novel approach to improve instruction locality across test case executions. Our approach measures the distance between test case executions (number of different instructions). We then schedule the test cases for execution so that the distance between neighboring test cases is minimised. We empirically evaluate our approach with 20 subject programs and test suites from the SIR repository, EEMBC suite and LLVM Symbolizer to compare execution times and cache misses with test case orderings using our approach versus a traditional ordering maximising coverage and random permutations. We also assess overhead of algorithms in generating orderings that optimise instruction cache locality. 3. In our final contribution, we target execution time of heterogeneous test suites and assess the effect of device-based test case scheduling. We propose a test case scheduling algorithm which improves the load balancing between multiple devices of a heterogeneous system in an attempt to reduce the overall test suite execution time. We conduct empirical evaluation on a large-scaled, industrial test suite targeting implementations of the SYCL standard which has been developed by Codeplay Software. The outcome of our research can be summarized as follows: 1. Our data transformation approach resulted in significant compilation speedups in the range of 1.3×to 69×. Our experiments show that the gains in compilation time allow significantly more test cases to be included in test suites, improving scalability of test code compilation. 2. Our instruction-based test case scheduling algorithms were able to achieve a maximum execution speedup of 29.48%. Performance gains were considerable for programs and test suites where the average number of different instructions executed between test cases was high. 3. Finally, we found that a maximum of 25.42% speed-up is achieved by our device based test scheduling algorithm when compared to parallel test case execution of a heterogeneous test suite without test scheduling. Our proposed techniques are able to significantly reduce the compilation as well as the execution time of test suites without eliminating any test cases or upgrading computing infrastructure. Our data transformation results in faster test code compilation while our test case scheduling algorithms achieve significant speed-ups for programs executing on single-CPU, multi-CPU as well as heterogeneous architectures. As systems get more complex, they require frequent and extensive testing. Our techniques provide safe and efficient means of compiling and executing test suites which, in combination with existing test suite optimisations, can significantly reduce the cost of software testing.

https://hdl.handle.net/1842/37110

http://dx.doi.org/10.7488/era/411

en

The University of Edinburgh

P. Stratis and A. Rajan. Reordering tests for faster test suite execution. In Proceedings of the 40th International Conference on Software Engineering: Companion Proceeedings, pages 442–443, 2018.

P. Stratis and A. Rajan. Speeding up test execution with increased cache locality. Software Testing, Verification and Reliability, 28(5):e1671, 2018.

P. Stratis, V.Yaneva, and A. Rajan. Assessing the effect of data transformations on test suite compilation. In Proceedings of the 12th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement, pages 1–10, 2018

P. Stratis. Improving test execution time with improved cache locality. In 2017 IEEE/ACM 39th International Conference on Software Engineering Companion (ICSE-C), pages 82–84. IEEE, 2017.

P. Stratis and G. Brown. Assessing the effect of device-based test scheduling on heterogeneous test suite execution. In Proceedings of the 22nd International Conference on Evaluation and Assessment in Software Engineering 2018, pages 193–198, 2018

P. Stratis and A. Rajan. Test case permutation to improve execution time. In Automated Software Engineering (ASE), 2016 31st IEEE/ACM International Conference on, pages 45–50. IEEE, 2016

software testing

optimization

compilation speedup

execution time

scalability

instruction locality

load balancing

scheduling algorithms

Software testing: test suite compilation and execution optimizations

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy