Next: Summary Up: Multiprocessor Issues and Previous: An Example

Exclusive-Mode Prefetching

In this subsection, we discuss an issue that arises under invalidation-based coherence schemes (the model we assume for the remainder of this section), which is the use of exclusive-mode prefetching. Under the invalidation-based coherence model, a processor wishing to read a location receives a sharable copy of the line, which allows the line to be replicated in other caches as long as each processor is only reading the line. To write to a line, however, a processor must first acquire an exclusive copy of the line by invalidating the line from other processors' caches. This prevents the replicated copies from becoming stale, thus preserving coherence.

Just as normal memory accesses have two variations (shared accesses for reads, and exclusive accesses for writes), it also makes sense to have two types of prefetches: one that fetches a shared copy of a line, and one that fetches an exclusive copy. If a processor only intends to read a line, it will use the shared-mode prefetch. However, if the processor intends to modify the line-even if the line will be read first and modified shortly thereafter-an exclusive-mode prefetch should be issued to not only fetch a copy of the line, but also to gain ownership.

Proper use of exclusive-mode prefetching can provide two performance benefits. First, it can reduce the latency of the subsequent write since exclusive ownership of the line has already been obtained. This may or may not have a direct impact on execution time, depending on whether writes can be buffered.

The second benefit occurs in the common case where a value is read before it is written. Intuitively, these cases occur frequently because it is more common to update a shared variable (e.g., incrementing a shared counter, updating the position of a particle in a wind tunnel), than to simply overwrite it without reading it first. In such ``read-modify-write'' cases, what normally occurs is that the processor first requests a sharable copy of the line, and then immediately afterward requests an exclusive copy of the same line to perform the write. Rather than issuing two separate requests, a better approach is to issue a single exclusive-mode prefetch, as illustrated in Figure . Therefore exclusive-mode prefetches can potentially eliminate up to half of the total memory traffic, which can improve the performance of all references (both reads and writes) by reducing the amount of contention in the memory subsystem.

We modify our compiler algorithm to exploit exclusive-mode prefetching as follows. After performing locality analysis, the references have been partitioned into equivalence classes (see Section ), which are sets of references that can be treated as a single reference. An equivalence class may contain multiple references if they share group locality. We insert an exclusive-mode prefetch rather than a shared-mode prefetch for a given equivalence class if at least one member of the equivalence class is a write. For example, for the code in Figure (a), locality analysis would determine that both the read and write of A[i] are in the same equivalence class. Therefore, despite the fact that the leading reference to A[i] (i.e. the reference first accessing the data) is a read, our algorithm would schedule a single exclusive-mode prefetch of A[i], thus achieving the desired effect illustrated in Figure (b).

Next: Summary Up: Multiprocessor Issues and Previous: An Example

Sat Jun 25 15:13:04 PDT 1994