Accelerated Finite State Machine Test Execution Using GPUs

Vanya Yaneva, Arnav Kapoor, Ajitha Rajan, Christophe Dubach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 25th Asia Pacific Software Engineering Conference (APSEC 2018)
Place of PublicationNara, Japan
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Electronic)978-1-7281-1970-0
ISBN (Print)978-1-7281-1971-7
Publication statusPublished - 23 May 2019
Event25th Asia-Pacific Software Engineering Conference - Nara, Japan
Duration: 4 Dec 20187 Dec 2018

Publication series

ISSN (Print)1530-1362
ISSN (Electronic)2640-0715


Conference25th Asia-Pacific Software Engineering Conference
Abbreviated titleAPSEC 2018
Internet address

Keywords / Materials (for Non-textual outputs)

  • software testing
  • finite state machines
  • gpus


Dive into the research topics of 'Accelerated Finite State Machine Test Execution Using GPUs'. Together they form a unique fingerprint.

Cite this