Give that man some soup

For many memory prefetching algorithms, it is necessary to predict the re-reference interval of a memory access, so that the memory can be moved to the cache before the memory is called for, vastly decreasing memory access time.

Consider the following address stream:

ACDACBBD

In this example, the re-reference interval of D would typically be 4, because there are 4 memory accesses between consecutive accesses of D(I'll get to the reason that I say "typically" in a second). This means that, given the following access stream

ACDACBBDACAC

it would be natural to prefetch D, because, based on the idea that D is accesses every 4 accesses, it would likely be the next address. However, in practice, it has been shown that the next memory access is more likely to be something like BBD. Why is that? Well, we're not quite sure, but studies have shown that prefetching based on the unique re-reference interval, i.e. the number of unique memory accesses between consecutive addresses, produces significantly better results. Under this model, the unique re-reference interval of the first example would be 3, since there are 3 unique memory addresses: A, B, and C. The problem is that keeping track of the data required to find the unique re-reference interval is extremely difficult to do efficiently, so, for the past 2 weeks, I have been researching methods to do this efficiently.