Implementing Automata Algorithms: Low-Level Parallelism in Modern CPUs

Modern CPUs diverge from the idealized, linear execution of code in two main ways: by having multiple cores that execute concurrently and by offering instructions that can compute component-wise operations on vectors. This talk focuses on the latter and how these instructions can be employed in the context of automata algorithms. These instructions, known as Single Instruction Multiple Data (SIMD), come in a wide variety of shapes and forms, with perks and caveats, and my goal is to provide some guidelines on how to use them. I will give a short introduction on SIMD instructions, then present several examples where SIMD instructions have been used to boost the performances of automata-related algorithms. In particular, this will include Acacia-Bonsai, an LTL-synthesis C++ program that I developed together with Guillermo Pérez, and some exploratory work with several colleagues relying on circuit complexity.

Authors

• Michaël Cadilhac

Keywords

No keywords are indexed for this paper.