Optimistic Parallel Computation: An Example from Computational Chemistry

Performance penalties due to synchronization are a common concern in parallel programming. This paper describes a technique for avoiding such penalties when they occur in shared data structures. This technique may be used with a segment of code in which two updates are required for any element of a shared array and the values stored in the array are known a priori. Traditional approaches enforce the correct ordering of write operations using locks, but this can be time-consuming and drastically reduce the benefits of using a parallel machine. Instead, we propose using an optimistic approach where the solution is calculated without any locks, during which statistics on memory writes are kept. These statistics can then be used to determine whether the calculation resulted in a correct answer or if the answer should be recalculated due to incorrect ordering of write operations. This scheme is tested on an implementation of the Moller-Plesset perturbation theory energy calculation for closed-shell molecules and significant speedups are shown, as demonstrated on an SGI PowerChallenge