Summary Model‐based development is a popular development approach in which software is implemented and verified based on a model of the required system. Finite state machines (FSMs) are widely used as models for systems in several domains. Validating that a model accurately represents the required behaviour involves the generation and execution of a large number of input sequences, which is often an expensive and time‐consuming process. In this paper, we speed up the execution of input sequences for FSM validation, by leveraging the high degree of parallelism of modern graphics processing units (GPUs) for the automatic execution of FSM input sequences in parallel on the GPU threads. We expand our existing work by providing techniques that improve the performance and scalability of this approach. We conduct extensive empirical evaluation using 15 large FSMs from the networking domain and measure GPU speed‐up over a 16‐core CPU, taking into account total GPU time, which includes both data transfer and kernel execution time. We found that GPUs execute FSM input sequences up to 9.28× faster than a 16‐core CPU, with an average speed‐up of 4.53× across all subjects. Our optimizations achieve an average improvement over existing work of 58.95 % for speed‐up and scalability to large FSMs with over 2K states and 500K transitions. We also found that techniques aimed at reducing the number of required input sequences for large FSMs with high density were ineffective when applied to all‐transition pair coverage, thus emphasizing the need for approaches like ours that speed up input execution.

Model-based development has emerged as a popular approach aiding automation of the software development process, where software is implemented and tested based on a model of the required system. Finite State Machines (FSMs) are a widely used model representation for a variety of systems, including control systems, signal processing and communications protocols. Ensuring that the model accurately represents the required behaviour involves the generation and execution of a large number of tests that is time consuming and expensive. In this paper, we focus on test execution and propose exploiting Graphics Processing Units (GPUs) for accelerating FSM testing by executing the tests in parallel on GPU threads. Our approach includes methods to encode the FSM efficiently and optimise the layout of tests in GPU memory for fast execution. We compare speedup achieved by our approach against parallel test execution on a multi-core CPU with 16 cores. We also assess the improvement in speedup using the proposed FSM encoding and test layouts. We use large FSMs from the networking domain and a large industry FSM from Keysight, who provide electronic measurement solutions, in our evaluation. We accelerate the execution of test suites providing all-transition pair coverage for each of the FSMs. Speedup achieved is subject to characteristics of the FSM and associated tests, and is greatly improved with efficient FSM encoding and test layout in memory. We find our approach on the GPU achieves a maximum test execution speedup of 12× over a 16-core CPU.

Background. The requirements and responsibilities assumed by software has 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 tests. Large test suites result in a corresponding increase in the size of the test code that sets up, exercises and verifies the tests. Time needed to compile and optimise the test code becomes prohibitive for large test code sizes.

Embedded software is found everywhere from our highly visible mobile devices to the confines of our car in the form of smart sensors. Embedded software companies are under huge pressure to produce safe applications that limit risks, and testing is absolutely critical to alleviate concerns regarding safety and user privacy. This requires using large test suites throughout the development process, increasing time-to-market and ultimately hindering competitivity.

With the growing complexity of software, the number of test cases needed for effective validation is extremely large. Executing these large test suites is expensive and time consuming, putting an enormous pressure on the software development cycle. In previous work, we proposed using Graphics Processing Units (GPUs) to accelerate test execution by running test cases in parallel on the GPU threads. However, the complexity of GPU programming poses challenges to the usability and effectiveness of the proposed approach.