Nested Circular Intervals: A Model for Barrier Placement in Single-Program, Multiple-Data Codes with Nested Loops.

We want to perform compile-time analysis of an SPMD program and place barriers in it to synchronize it correctly, minimizing the runtime cost of the synchronization. This is the barrier minimization problem. No full solution to the problem has been given previously. Here we model the problem with a new combinatorial structure, a nested family of sets of circular intervals. We show that barrier minimization is equivalent to finding a hierarchy of minimum cardinality point sets that cut all intervals. For a single loop, modeled as a simple family of circular intervals, a linear-time algorithm is known. We extend this result, finding a linear-time solution for nested circular intervals families. This result solves the barrier minimization problem for general nested loops.Le but de ce rapport est de montrer comment, après une analyse statique de code, on peut synchroniser, `a l’aide de barrières, un programme de type SPMD tout en minimisant le temps de synchronisation à l’exécution. C’est le problème de minimisation des barrières. Aucune solution complète n’a été donnée à ce jour.Nous modélisons le problème par une nouvelle structure qui généralise la notion de graphe d’arcs circulaires, une famille d’intervalles circulaires imbriqués. Nous montrons que le problème de minimisation de barrières revient à trouver une hiérarchie d’ensembles, de tailles minimales, de points du code (où placer les barrières) qui coupent Ż tous les intervalles. Pour une boucle simple, modélisée par un graphe d’arcs circulaires traditionnel, un algorithme linéaire est connu. Nous l’ étendons en un algorithme linéaire pour une famille d’intervalles circulaires imbriqués. Ce résultat résout le problème de minimisation des barrières pour des boucles imbriquées