CPC 2006 CPC 2006

Call for Participation
Current List of
Program (List of Talks)
Registration Form
Travel Information

Funded by the Vicerreitoría de Investigación of the University of A Coruña and the Ministry of Education and Science of Spain

Universidade de A Coruña Ministerio de
		      Educación y Ciencia

Optimal Linear-Time Barrier Placement

Alain Darte1 and Rob Schreiber2
1 CNRS, LIP, ENS-Lyon, France
2 Hewlett Packard Laboratories, Palo Alto, USA

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, the best solution so far was given by O'Boyle and Stšhr. 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.

Back to the Workshop Program 

Please contact our webadmin with any comments or changes.