next up previous
Next: Instrumentation and Visualization Up: Overview of Analysis Techniques Previous: Waiting Time Analysis

Communication Analysis

In DSM systems, communication occurs when a page (the granularity supported by the coherence protocol) is accessed by a processor and that page is not available locally. The page may not be available because (1) this is the first reference to the page (e.g., a cold start) or (2) the page was invalidated as a consequence of write operations by another processor and a subsequent synchronization point. In order to understand why a page reference results in a remote request, we must know the operations that preceded the request (e.g., reads, writes, invalidations); the ordering and type of operations on a page that precede a remote request are the cause for that remote request. Analyzing the causes of remote requests is particularly important in DSM systems employing release consistency, since the cause of a remote request can involve multiple processors executing different portions of source code asynchronously.

Communication analysis examines the causes for remote requests (either from the point of view of an individual page or set of pages, or from the point of view of an individual source code line) and from that information infers the access pattern exhibited by a page or source code line. The access patterns are: (1) single-producer-single-consumer, (2) single-producer-multiple-consumer, (3) multiple-producer-single-consumer, (4) multiple-producer-multiple-consumer, (5) migratory, and (6) cold start.

To infer these access patterns, communication analysis uses traces of program executions that contain a record of every page fault and synchronization operation, with a global timestamp for each. Each page fault records the source code line that generated the fault, the nature of the fault (read or write), and the page number. Each synchronization operation records the list of pages that were invalidated as part of the operation. From these traces, the immediate cause of each remote request is determined automatically, where an immediate cause is the invalidation that preceded the page fault, and the write faults that generated the write notices at the synchronization point.

Requests to a particular page are usually chained (i.e., one page fault is the cause of another that happens later in time), corresponding to the migration of the page across processors. We represent causality between requests to a page as a directed graph, called the communication graph. We build this graph for each page while traversing the trace file and determining immediate causes for page faults. The nodes in the graph represent page faults (and their immediate cause), and edges in the graph represent causality relationships. There is an edge between two nodes if the write fault explained by one node generates a write notice that is an immediate cause for the fault in the other node. We assign weights to the edges according to the cumulative cost of the communication operations that the edge represents.

Since we are interested in learning why a processor faulted on a page that it owned in the past, we trace back through the edges in the graph until we arrive at a node representing the previous fault on the same page on the same processor. The explanation for the page fault is the set of paths leading back to the immediately previous page fault on the same processor.

We can merge explanations to understand reference behavior across pages. Similar explanations for different pages are combined, allowing us to generalize the reference behavior at a single source code location. The criteria for similarity takes into account the relative importance of each edge's weight in the graph.

The output of this process is, for each data structure, a list of sets of graphs that provide explanations for the page faults on that data structure. As described above, each set of graphs represents one or more pages that behave similarly. These explanations are augmented with communication profiles, which describe how the communication costs during execution are distributed among data structures, source code lines, and causes. With this information, the programmer can identify the source code, data structures, and access patterns that result in page requests, and thereby discover optimizations in data layout or scheduling to improve performance.

It is important to note that communication is a common source of waiting time, and therefore contributes to overhead both on the processor that performs the communication, and on any other processor that must wait for the communication to complete. Therefore, reducing the amount of communication can have the added benefit of reducing waiting time, so that the total savings during execution are much larger than the measured communication time. Waiting time analysis identifies the communication operations that contribute to waiting time; communication analysis identifies the access patterns (and associated pages and source code lines) that cause communication, so that both communication and waiting time can be reduced.


next up previous
Next: Instrumentation and Visualization Up: Overview of Analysis Techniques Previous: Waiting Time Analysis

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