Algorithmic optimization and parallelization of eppstein's synchronizing heuristic

Karahoda, Sertaç (2018) Algorithmic optimization and parallelization of eppstein's synchronizing heuristic. [Thesis]

[thumbnail of 10209184_SertacKarahoda.pdf] PDF
10209184_SertacKarahoda.pdf

Download (1MB)

Abstract

Testing is the most expensive and time consuming phase in the development of complex systems. Model–based testing is an approach that can be used to automate the generation of high quality test suites, which is the most challenging part of testing. Formal models, such as finite state machines or automata, have been used as specifications from which the test suites can be automatically generated. The tests are applied after the system is synchronized to a particular state, which can be accomplished by using a synchronizing word. Computing a shortest synchronizing word is of interest for practical purposes, e.g. for a shorter testing time. However, computing a shortest synchronizing word is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. GREEDY is one of the fastest synchronizing heuristics currently known. In this thesis, we present approaches to accelerate GREEDY algorithm. Firstly, we focus on parallelization of GREEDY. Second, we propose a lazy execution of the preprocessing phase of the algorithm, by postponing the preparation of the required information until it is to be used in the reset word generation phase. We suggest other algorithmic enhancements as well for the implementation of the heuristics. Our experimental results show that depending on the automata size, GREEDY can be made 500⇥ faster. The suggested improvements become more effective as the size of the automaton increases.
Item Type: Thesis
Uncontrolled Keywords: Finite state automata. -- Synchronizing words. -- Synchronizing heuristics. -- CPU parallelization. -- GPU parallelization. -- Sonlu durum otomatları. -- Sıfırlama kelimeleri. -- Sıfırlama sezgiselleri. -- AİÜ paralelleştirilmesi. -- GİÜ paralelleştirilmesi.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 03 Oct 2018 10:20
Last Modified: 26 Apr 2022 10:25
URI: https://research.sabanciuniv.edu/id/eprint/36594

Actions (login required)

View Item
View Item