Parallel algorithms for reducing derivation time of distinguishing experiments for nondeterministic finite state machines. Issue 2 (4th March 2018)

• Record Type: Journal Article
• Authors: El-Fakih, Khaled; Barlas, Gerassimos; Ali, Mustafa; Yevtushenko, Nina
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 33:Issue 2(2018)
• Page Start: 197
• Page End: 210
• Publication Date: 2018-03-04
• Subjects: Conformance testing -- distinguishing experiments -- nondeterministic finite state machines -- divisible load theory -- parallel algorithms -- CUDA -- Thrust -- network of workstations; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2017.1300801
• Languages: English
• ISSNs: 1744-5760

Abstract

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. Abstract : We aim at reducing the time associated with the construction of the successors of all state pairs of a given non-deterministic finite state machine. 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. Additionally, we propose and evaluate a Network of Workstations solution based on Divisible Load Theory. A rigorous set of experiments highlights the differences of the proposed implementations in terms of execution time and speedup.