Synchronizing billion-scale automata

Mustafa Kemal Taş, Kamer Kaya, Hüsnü Yenigün

Information Sciences
Volume 574, October 2021, Pages 162-175

  • Existing synchronization heuristics do not scale due to quadratic space complexity.
  • We propose a simple approach to avoid memory usage thanks to massive parallelism.
  • We use different parallelization approaches on CPUs and GPUs, in a hybrid way.
  • A different treatment of parallelism is useful at different phases of the algorithm.
  • Our algorithms can synchronize a billion-state automaton in around 4 mins.

Read the full article at: