Details

Autor(en) / Beteiligte

• DINIZ, P. C
• RINARD, M. C

Titel

Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

Ist Teil von

• ACM transactions on computer systems, 1999-05, Vol.17 (2), p.89-132

Ort / Verlag

New York, NY: Association for Computing Machinery

Erscheinungsjahr

1999

Link zum Volltext

Quelle

ACM Digital Library

Beschreibungen/Notizen

• This article presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.