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

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101848
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:59 AM
Last modification on : Sunday, May 19, 2019 - 1:20:46 AM

File

RR2004-57.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101848, version 1

Collections

Citation

Alain Darte, Robert Schreiber. Nested Circular Intervals: A Model for Barrier Placement in Single-Program, Multiple-Data Codes with Nested Loops.. [Research Report] LIP RR-2004-57, Laboratoire de l'informatique du parallélisme. 2004, 2+27p. ⟨hal-02101848⟩

Share

Metrics

Record views

3

Files downloads

7