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):
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.