A Systolic Genetic Search for reducing the execution cost of regression testing

作者：Pedemonte Martin; Luna Francisco; Alba Enrique

来源：Applied Soft Computing, 2016, 49: 1145-1161.

DOI：10.1016/j.asoc.2016.07.018

• Regression testing
• Evolutionary algorithms
• Parallel metaheuristics
• GPU
• CUDA

The Test Suite Minimization Problem (TSMP) is a NP-hard real-world problem that arises in the field of software engineering. It consists in selecting a minimal set of test cases from a large test suite, ensuring that the test cases selected cover a given set of requirements of a piece of software at the same time as it minimizes the amount of resources required for its execution. In this paper, we propose a Systolic Genetic Search (SGS) algorithm for solving the TSMP. SGS is a recently proposed optimization algorithm capable of taking advantage of the high degree of parallelism available in modern GPU architectures. The experimental evaluation conducted on a large number of test suites generated for seven real-world programs and seven large test suites generated for a case study from a real-world program shows that SGS is highly effective for the TSMP. SGS not only outperforms two competitive genetic algorithms, but also outperforms four heuristics specially conceived for this problem. The results also show that the GPU implementation of SGS has achieved a high performance, obtaining a large runtime reduction with respect to the CPU implementation for solutions with similar quality. The GPU implementation of SGS also shows an excellent scalability behavior when solving instances with a large number of test cases. As a consequence, the GPU-based SGS stands as a state of the art alternative for solving the TSMP in real-world software testing environments.

• 出版日期2016-12