Title:
Optimistic Parallel Computation: An Example from Computational Chemistry
Optimistic Parallel Computation: An Example from Computational Chemistry
Author(s)
Crawford, Emily Angerer
Schwan, Karsten
Yalamanchili, Sudhakar
Schwan, Karsten
Yalamanchili, Sudhakar
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
Abstract
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.
Sponsor
Date Issued
1996
Extent
219277 bytes
Resource Type
Text
Resource Subtype
Technical Report