Boosting expensive synchronizing heuristics

Saraç, N. Ege and Altun, Ömer Faruk and Atam, Kamil Tolga and Karahoda, Sertaç and Kaya, Kamer and Yenigün, Hüsnü (2021) Boosting expensive synchronizing heuristics. Expert Systems with Applications, 167 . ISSN 0957-4174 (Print) 1873-6793 (Online)

Full text not available from this repository. (Request a copy)


For automata, synchronization, the problem of bringing an automaton to a particular state regardless of its initial state, is important. It has several applications in practice and is related to a fifty-year-old conjecture on the length of the shortest synchronizing word. Although using shorter words increases the effectiveness in practice, finding a shortest one (which is not necessarily unique) is NP-hard. For this reason, there exist various heuristics in the literature. However, high-quality heuristics such as SYNCHROP producing relatively shorter sequences are very expensive and can take hours when the automaton has tens of thousands of states. The SYNCHROP heuristic has been frequently used as a benchmark to evaluate the performance of the new heuristics. In this work, we first improve the runtime of SYNCHROP and its variants by using algorithmic techniques. We then focus on adapting SYNCHROP for many-core architectures, and overall, we obtain more than 1000× speedup on GPUs compared to naive sequential implementation that has been frequently used as a benchmark to evaluate new heuristics in the literature. We also propose two SYNCHROP variants and evaluate their performance.
Item Type: Article
Uncontrolled Keywords: GPU programming; Parallel algorithms; Synchronizing heuristics
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 19 Aug 2022 12:17
Last Modified: 19 Aug 2022 12:17

Actions (login required)

View Item
View Item