The code in Figure illustrates the types of locality that our algorithm can discover. We will use this code as a running example throughout the remainder of this chapter. We assume, for this example, that the cache is 8 Kbytes, the prefetch latency is 100 cycles and the cache line size is 4 words (two double-word array elements to each cache line). (Note that for the purpose of illustration, these parameters differ slightly from our previous uniprocessor architecture.) For this example, the set of references that will cause cache misses can be determined by inspection.
For each array reference in our example code, Figure (b) shows which iterations hit and miss in the cache using iteration space plots. In this representation, the horizontal axis corresponds to the j loop, the vertical axis corresponds to the i loop, and each node represents an iteration within the loop nest. Therefore as the loop nest is executed, the nodes in the iteration space would be visited in the following order: first the bottom-most row is visited from left-to-right, then the second-from-bottom row is visited from left-to-right, and so on. To simplify the graphs, we only show the first eight out of 100 j loop iterations.
The three array references in Figure illustrate the three different types of locality: temporal, spatial, and group. Temporal locality can occur when a given reference reuses exactly the same data location. Spatial locality can occur when a given reference accesses different data locations that fall within the same cache line. Group Locality can occur when different references access the same cache line.
The A[i][j] reference in Figure illustrates spatial locality. In this case, given that each cache line contains two array elements, we would expect misses to occur on every other iteration as cache line boundaries are crossed. These misses are shown graphically in Figure (b).
The B[j+1] reference is an example of temporal locality. In contrast with the A[i][j] reference, since the B[j+1] reference traverses the columns rather than the rows of the matrix along the inner loop, there is no cache line reuse and therefore all B[j+1] references suffer misses the first time through the j loop. However, since the same B[j+1] locations are reused on subsequent i loop iterations, and since these 800 bytes of data are likely to remain in the 8 Kbyte cache across i loop iterations, we would expect the B[j+1] references to hit in the cache after the first i loop iteration. This effect is also illustrated in Figure (b).
Finally, the B[j+1] and B[j] references are an example of group locality. Group locality is a relationship that can occur between multiple references whenever one reference brings in much of the data used by the other references. In this example, the data for the B[j] reference is fetched by the B[j+1] reference during the previous j iteration. Consequently the B[j] reference suffers only a single cache miss during the entire loop nest. Whenever group locality occurs, we only worry about prefetching the leading reference within the group, which is the reference that accesses new data first and therefore suffers the bulk of the cache misses. In this example, B[j+1] is the leading reference, and therefore we would not issue prefetches for B[j].
The remainder of this section describes how locality analysis systematically uncovers the types of locality shown in this example.