next up previous
Next: Scheduling and Data Layout Up: Examples Previous: Examples

Excessive synchronization in Water

   figure106
Figure 1: Carnival visualization of Water

Our first example examines Water, a molecular dynamics simulation from the Splash suite [15] that is distributed as part of the Treadmarks release. Water evaluates forces and potentials that occur over time in a system of water molecules. It uses one large, shared array to represent the molecules being simulated.

We executed three iterations of a 512 molecule simulation of Water on four processors and collected the execution traces. The execution took 272 seconds of real time, or 1088 processor seconds. The global execution-time profiles showed that almost 60% of the total processor time was spent waiting for locks and barriers. Waiting time analysis (as shown in the WT Map in Figure 1b) shows three major sources of waiting time, which together account for nearly 90% of all waiting time in the application (and thus over 50% of the execution time):

  1. Nearly half of the total waiting time is associated with the lock acquire operations that control access to individual molecules in the simulation (UPDATE_FORCES_MolLock_comp_acq). The explanations produced by waiting time analysis (shown in the Characterization Map of Figure 1c) show that waiting time at a lock acquire operation is not caused by the actions of another processor (since the left-hand, or negative, side of the explanation is empty); it can be attributed almost entirely to the cost of the lock acquire operation itself (which appears on the right-hand, or positive, side of the explanation).
  2. Roughly one quarter of the total waiting time occurs at a barrier (MDMAIN_barrier). The explanation for this waiting time (not shown in the figure) is the code associated with initialization, which is serialized and therefore produces waiting time on every other processor. Furthermore, the serialized code (which, for simplicity, exploits the same loops used by the parallel code, and therefore includes unnecessary lock operations) is dominated by the cost of lock operations.
  3. About 14% of the waiting time occurs at a barrier at the end of the routine INTERF, where processors wait until all the forces are updated. Although the explanation suggests some load imbalance among the processors in the function UPDATE_FORCES, the majority of the waiting time is again explained by the cost of acquiring and releasing locks.

Our analysis shows that lock acquire operations are the dominant source of overhead for Water on Treadmarks. Each acquire operation is expensive and therefore results in overhead. What is surprising, and is only discovered by waiting time analysis, is the extent to which expensive lock operations on one processor indirectly affect other processors, which must wait at barriers or other synchronization points while waiting for a lock acquire to complete elsewhere.

To reduce both the direct and indirect effects of locks, we examined the execution profiles and the waiting time explanations to identify the source code that is causing the overhead. Most of the overhead is associated with two lock acquire calls, which are used to update molecule accelerations within an iteration. Since the modifications associated with the lock are only used in a subsequent iteration, we can modify the program to accumulate the changes locally within an iteration, and then update the global array of molecules. This modification, which reduces significantly the number of lock acquire operations and was already incorporated into Water in the Splash2 suite [16], improves the execution time by a factor of 17 on four processors.

The original version of Water was written for a shared-memory machine, where lock operations are relatively cheap and excessive synchronization is a small price to pay for simplicity. In DSM systems like Treadmarks the tradeoffs are very different, and locks should be avoided wherever possible. This example shows that Carnival is particularly helpful in analyzing parallel programs that are being ported to a DSM system from another architecture, since it identifies both direct and indirect consequences of tradeoffs made in one environment, and identifies the source code that must be modified to reflect different tradeoffs in the new environment.


next up previous
Next: Scheduling and Data Layout Up: Examples Previous: Examples

Wagner Meira
Mon Dec 16 23:02:14 EST 1996