Boosting expensive synchronizing heuristics

N. Ege Saraç

doi:10.1016/j.eswa.2020.114203

Boosting expensive synchronizing heuristics

2021-04-01

2

PRE

AI

DOI：10.1016/j.eswa.2020.114203

原文链接

原文求助

摘要

En 中文

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 1000x 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.

Keyword:

Synchronizing heuristics

Parallel algorithms

GPU programming

Boosting expensive synchronizing heuristics

摘要

AI总结

期刊

机构