On polynomial Code Generation

Paul Feautrier 1 Albert Cohen 1 Alain Darte 2
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : In static analysis, one often has to deal with polynomials in the program control variables, either native to the source code or created by enabling analyses. We have explained elsewhere how to compute dependences in such situations and use them for building polynomial schedules. It remains to explain how to generate polynomial code. The present proposal is to target new parallel programming languages of the async/finish family, like X10 or Habanero, which are "polynomial friendly" and for which efficient compilers exists. Both these languages have barrier-like constructs-clocks for X10 and phasers for Habanero-which may be used to synchronize activities. To understand the behaviour of a clocked program, one has to count the number of clock advance operations since the creation of each activity. Advances with equal counts are synchronized , and these counts may be polynomials. The trick is therefore to insure that before executing an operation, its activity has executed as many advances as the current value of its schedule. This can be obtained by inserting auxilliary loops for executing the necessary advances. This scheme fails if the schedule is not monotone increasing with respect to the execution order in each activity. This problem may be solved by reordering the activities-which is possible since the real execution order is given by the schedule-or in extreme cases by index set splitting.
Type de document :
Communication dans un congrès
IMPACT 2018, Jan 2018, Manchester, United Kingdom. impact.gforge.inria.fr/impact2018, 2018
Liste complète des métadonnées

Contributeur : Paul Feautrier <>
Soumis le : mardi 18 décembre 2018 - 11:59:14
Dernière modification le : jeudi 7 février 2019 - 15:49:28


Copyright (Tous droits réservés)


  • HAL Id : hal-01958096, version 1



Paul Feautrier, Albert Cohen, Alain Darte. On polynomial Code Generation. IMPACT 2018, Jan 2018, Manchester, United Kingdom. impact.gforge.inria.fr/impact2018, 2018. 〈hal-01958096〉



Consultations de la notice


Téléchargements de fichiers