In distributed shared memory environments like Treadmarks[2], communication occurs as a consequence of coherence protocol activity. There are two possible causes for a communication event: (1) the processor has never accessed the data before (i.e., a cold start), and (2) the processor had a copy of the data, but the copy was invalidated as a consequence of other coherency actions. Although cold starts tend to be infrequent, invalidations can be a significant source of protocol overhead. In systems that employ release consistency, the cause of a communication event is an earlier invalidation, which itself is caused by write operations on another processor. We can explain each communication operation (i.e., request for a page) in terms of the coherence operations involving the data since it was last available locally.
Protocol analysis focuses on those events in an execution trace that are the result of coherence actions, including read and write page faults, invalidations, and synchronization operations. From the trace, 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.
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.
In our visualization (see figure 3) each graph is represented as an incidence matrix, where the column header identifies the access pattern (using a color code), the source code location of the faults (R for request, I for invalidation, and W for preceding writes), and the percentage of total page fault cost in the graph associated with that node. The entries quantify the relative frequency of transitions between nodes in the graph.
Figure: Transaction analysis for data mining - This figure describes
the data access and contention conflicts that cause 65% of the
transaction aborts for the transactions
issued in the application Par_DM at line 25
on file DM_Phase_1. All of the conflicts are with processes
in the same application (see Appl column), but not all conflicts are within
the same file (see File column). The table indicates which servers
completed the transaction (light color),
which aborted due to a data access conflict (darker color) and
which aborted due to a timeout (darkest color).