An algebraic approach to vectorial programs

Paperman, Charles; Salvati, Sylvain; Soyez-Martin, Claire

Document type :

Pré-publication ou Document de travail

DOI :

10.4230/LIPIcs.STACS.2023.14

Title :

An algebraic approach to vectorial programs

Author(s) :

Paperman, Charles [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Salvati, Sylvain [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Soyez-Martin, Claire [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]

English keyword(s) :

Vectorisation
Automata theory
Semigroups

HAL domain(s) :

Informatique [cs]

English abstract : [en]

Vectorial programming, the combination of SIMD instructions with usual processor instructions, is known to speed-up many standard algorithms. Simple regular languages have benefited from this technology. This paper is a ...
Show more >Vectorial programming, the combination of SIMD instructions with usual processor instructions, is known to speed-up many standard algorithms. Simple regular languages have benefited from this technology. This paper is a first step towards pushing these benefits further. We take advantage of the inner algebraic structure of regular languages and produce high level representations of efficient vectorial programs that recognize certain classes of regular languages. As a technical ingredient, we establish equivalences between classes of vectorial circuits and logical formalisms, namely unary temporal logic and first order logic. The main result is the construction of compilation procedures that turns syntactic semigroups into vectorial circuits. The circuits we obtain are small in that they improve known upper-bounds on representations of automata within the logical formalisms. The gain is mostly due to a careful sharing of sub-formulas based on algebraic tools.Show less >

Language :

Anglais

Collections :