Estimation of Parallel Complexity with Rewriting Techniques

Christophe Alias (1, 2) , Carsten Fuhs (3) , Laure Gonnord (1, 2)

1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 Birkbeck College [University of London]

We show how monotone interpretations – a termination analysis technique for term rewriting systems – can be used to assess the inherent parallelism of recursive programs manipulating inductive data structures. As a side effect, we show how monotone interpretations specify a parallel execution order, and how our approach extends naturally affine scheduling – a powerful analysis used in parallelising compilers – to recursive programs. This work opens new perspectives in automatic parallelisation.

Mots clés: Complexity analysis; parallelism; monotone interpretations; termination; scheduling

Domaines: Informatique et langage [cs.CL]; Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Christophe Alias, Carsten Fuhs, Laure Gonnord. Estimation of Parallel Complexity with Rewriting Techniques. Workshop on Termination, Sep 2016, Obergurgl, Austria. ⟨hal-01345914⟩