PPT Slide

Luk and Mowry (SW)

Recursive Data Structure (RDS)

struct T {

int data;

struct T* next;

}

RDS Traversal

T* l;

...

while(l) {

...

l = l->

}

Greedy Prefetching

T* l;

...

while(l) {

prefetch(l->);

...

l = l->

}

Identify RDSs

Find RDS traversals

Insert Prefetches

Previous slide

Next slide

Back to first slide

View graphic version

First, let us consider another recursive prefetcher proposed by Luk and Mowry. This is a software prefetcher that performs essentially the same task as the hardware scheme we just discussed. However, because it is a compiler optimization, it works very differently.

Their technique first identifies data structures that are candidates for recursive accesses. Shown on the slide is a simple example of a typical linked list, but more complicated structures are also possible. Next, control structures are searched for that traverse the recursive data structure. The compiler uses a template approach. The example in the middle, shows a simple linked list traversal.

The control structure essentially identifies the producer of a base address. The last step is the actual insertion of prefetch instructions as shown in the rightmost box. The run-time behavior of this prefetch is very similar to that generated by the hardware prefetcher. Both are issue shortly after the producer instruction completes.

For tree traversals, the recursive data structure may have multiple next pointers. In the greedy prefetching scheme, Luk and Mowry insert prefetches for all pointers. This is also what the hardware prefetcher does.

I will not discuss the other two prefetching schemes proposed by Luk and Mowry. While they are very effective, they are only applicable to certain types of traversals.