Parallel algorithms for reducing derivation time of distinguishing experiments for nondeterministic finite state machines |
| |
Authors: | Khaled El-Fakih Gerassimos Barlas Mustafa Ali Nina Yevtushenko |
| |
Affiliation: | 1. Department of Computer Science and Engineering, American University of Sharjah, Sharjah, UAE;2. Department of Information Technologies, Tomsk State University, Tomsk, Russia |
| |
Abstract: | Many approaches have been proposed for deriving tests from finite state machine (FSM) specifications with respect to some established coverage criteria. A fundamental core problem in FSM-based testing relates to the derivation of input sequences that can distinguish states of an FSM specification, aka distinguishing sequences. A major effort in the construction of these sequences is based on the derivation of a successors search-tree labeled by sets of pairs of states of the given machine. We aim at reducing the time associated with such constructions through the use of state-of-the-art parallel technologies. Namely, we propose a parallel algorithm that we implement and evaluate on multicore CPUs and on many-core GPUs. We evaluate two alternative GPU implementations that use the CUDA and Thrust software platforms and a network of workstations based solution. The latter sports a workload partitioning based on Divisible Load Theory. A rigorous set of experiments highlights the differences of the proposed implementations in terms of execution time and speedup. |
| |
Keywords: | Conformance testing distinguishing experiments nondeterministic finite state machines divisible load theory parallel algorithms CUDA Thrust network of workstations |
|