Dynamic feedback: an effective technique for adaptive computing

This paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environ-ments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a dif-ferent optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase mea-sures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the pre-vious sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a par-allelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchro-nization 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 stat-ically 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.