Shared memory is an attractive programming model because it is easier to use than a distributed-memory model. Software DSM (distributed shared memory) systems offer the simplicity of the shared-memory programming model on cost-effective distributed-memory architectures (including networks of workstations). Although early DSM systems could only provide good performance for a limited class of applications, recent advances at both the protocol level [8, 7, 9] and the architecture level [5, 2, 3] have made DSM a practical and cost effective approach to parallel computing. Nonetheless, synchronization and communication are still major sources of performance degradation in DSM systems.
Reducing or eliminating synchronization and communication in DSM systems is complicated by several factors. First, communication in a DSM system is dictated by the details of the coherence protocol, and therefore is not under the direct control of the user. As a result, the relationship between shared-memory references in the source code and the resulting frequency of invalidations, page requests, and diffs may not be understood by the programmer. Second, DSM systems support the shared-memory model on a range of architectures, where the costs associated with synchronization and communication vary widely. Implicit tradeoffs between the costs of various operations are embedded in the source code (including the data layout scheme, the scheduling strategy, and the degree of parallelism to be exploited), and thus are difficult to discover and change when porting code from one architecture to another. Third, the dynamic nature of synchronization and communication makes it difficult to associate runtime overhead with specific code segments or data structures. Often the cost of an operation is distributed in time (a write operation by one processor causes a subsequent invalidation on another, but only at a later synchronization point) and space (a request by one processor must be satisfied by another), making it difficult to understand the cause of excessive overhead observed during runtime.
There are many tools that help the programmer in understanding and tuning the performance of parallel applications. Many tools identify the location of performance problems. For example, Paradyn [12] measures performance bottlenecks, and presents the resulting performance information in an abstraction hierarchy. MTool [6] measures the time spent by processors waiting for memory requests to be satisfied, and relates memory behavior to code segments. MemSpy [10] identifies the data structures that cause remote memory references, and classifies the misses into various categories, such as invalidation misses and replacement misses. All of these tools measure performance effects and assist the programmer in finding the causes of performance degradation; however, the programmer is responsible for most of the inference process that links an observed effect to a specific cause.
There are two tools that focus on cause-and-effect relationships. Rajamony and Cox [14] implemented a performance debugger that automatically detects unnecessary and excessive synchronization by verifying data accesses between synchronization intervals. StormWatch [4] is a visualization tool for memory system protocols that presents multiple views of memory access operations, including performance slices that capture relationships between individual memory events, exposing causality in memory operations.
In this paper we present two techniques that help to automate the inference process between observed performance phenomena and underlying causes in DSM systems. Waiting time analysis is used to understand the causes of synchronization overhead; communication analysis is used to understand page reference and invalidation behavior. These techniques, which have been implemented as part of the Carnival performance visualization tool, can be used to understand an application's performance and tune the implementation.
In the next section we present two automated techniques that relate observed performance phenomena (synchronization and communication overhead) to underlying causes. Section 3 describes how these techniques are implemented within Treadmarks (a DSM system) and Carnival (a performance visualization tool). Section 4 shows how to use these techniques to understand and tune the performance of two Splash applications running under Treadmarks on a cluster of DEC Alpha stations connected by a DEC memory channel. Section 5 presents our conclusions and the directions of our future work.