Next: An Example Up: Coherence Misses Previous: Coherence Misses

Predicting Coherence Misses

Ideally, we would like to incorporate the notion of coherence misses into our framework of locality analysis, so that a single model could predict all forms of misses. How can this be accomplished? As you may recall from Section , data locality occurs whenever a cache line is reused, provided that the line has not been ejected from the cache since it was last used. In a uniprocessor architecture, a cache line will only be ejected from the cache if it is replaced by another reference that maps into the same cache entry. Our algorithm predicts that such replacements will occur whenever the volume of data accessed between reuses exceeds the effective size of the cache. In a multiprocessor architecture, a cache line can also be ejected from the cache if the line is modified by another processor during the interval between reuses, hence invalidating it from the given processor's cache (we assume an invalidation-based coherence protocol). Under locality analysis, the ejection of data from the cache is modeled through the localized iteration space, which is the set of loops that can carry data locality. Therefore, to predict coherence misses, we extend the concept of the localized iteration space to include not only the volume of data accessed, but also whether lines are being modified by other processors.

Accurately predicting when another processor modifies a given data line is a very difficult problem for the compiler, and requires a complete understanding of the communication and synchronization patterns of an application, as well the data addresses being accessed. In cases where the application has been parallelized by the compiler, this may be feasible since presumably the compiler must understand the communication patterns very well to perform the parallelization. However, even in such cases, factors such as dynamic scheduling may make it difficult to predict exactly when the modifications occur relative to other processors, and which lines are being modified. In addition, while it may be tractable to understand when particular data items are shared among processors (i.e. true sharing), it is more difficult to predict the coherence misses that only occur because separate items fall within the same cache line (i.e. false sharing) [81][19]. Finally, when the compiler is dealing with explicitly-parallelized programs, as is the case in our experiments, it is difficult (if not impossible) for the compiler to extract the communication patterns, since much of this semantic information is contained only in the programmer's head.

Although the compiler cannot precisely understand the communication patterns in the explicitly-parallelized codes used in our experiments, one thing that serves as a useful hint is the explicit synchronization statements inserted by the programmer to ensure that shared data are accessed safely. Assuming that a program is ``properly labeled'' [27] or ``data-race-free'' [2], synchronization statements should exist between the time when one processor modifies data and a second processor reads that data. Therefore, the compiler interprets explicit synchronization as a hint that data communication may be taking place. Ideally, it would be nice to know the data being protected by any given synchronization variable, since such information would allow the compiler to reason more precisely about which particular variables may have been modified. However, since such semantic information is kept only in the programmer's head, our approach is to conservatively assume the worst, which is that all shared objects may have been modified, and therefore no locality is carried across explicit synchronization. We incorporate this notion into our localized iteration space model by saying that a loop is not localized if it either (i) accesses too much data (to model replacement misses, as described earlier in Section ), or (ii) contains explicit synchronization (to model coherence misses).

Next: An Example Up: Coherence Misses Previous: Coherence Misses

Sat Jun 25 15:13:04 PDT 1994