On the exploitation of value prediction and producer identification to reduce barrier synchronization time
Khaled Z. Ibrahim, Gregory T. Byrd · 2002
Barrier synchronization is a source of inefficiency in many parallel programs, due to the association of many producer-consumer relations in with one synchronization variable. This inefficiency may consume a significant percentage of total execution time, especially as we increase the degree of parallelism while maintaining the problem size. Barrier synchronization wait time can be hidden by speculatively executing instructions after the barrier. The speculative execution must not violate the dependencies imposed by the program. Dependency violation causes rollback, incurring a penalty that may exceed the benefit of speculation. In this work, we investigate how to reduce the probability of rollback through the use of two different techniques: value prediction and producer identification. The first technique tries to break the dependency between the running processes. The second technique tries to respect only true dependencies by transforming the barrier synchronization into per-variable flags. Simulation results using scientific benchmarks mostly SPLASH-2, indicate that producer identification promises a greater potential reduction in synchronization time, close to actual dependency, and maintains rollback percentage below 10% for most benchmarks.