It is known that effects of memory access latencies in a data processing system may be mitigated by moving elements of vector data into a local, high-speed memory known as a cache. The elements are moved, or prefetched, into the cache before they are needed so that they are readily available when requested. If the elements are in a predictable order, there is no theoretical limit to how far in advance the elements may be fetched. However, since the cache has a limited size, if elements are fetched too far in advance, prior elements may be displaced from the cache before they have been used. This can lead to the phenomenon of “thrashing”, where an element is prefetched and displaced multiple times before they are used. As a consequence, the performance of the data processing system may be worse than if no cache is used.
One approach to prevent thrashing is to prefetch elements directly from memory or indirectly via a cache into a sequentially ordered storage memory or queue. Once queued, elements remain in the queue until used, thus reducing thrashing. A disadvantage of this approach is that repeated accesses to an element either within or between vectors will result in the element being duplicated in the queue as well as in the cache. Additionally, if the element is evicted from the cache before subsequent prefetches, then the element must be fetched from memory again. In the worse case, this would result in a performance similar to having no cache.
Another approach is to provide prefetch instructions and place the burden on the programmer to use them in a manner that avoids thrashing. A disadvantage of this approach is that changes in the sparseness of the vector elements, the number of vectors, the memory access latency and even cache line replacement policy can require changes in the placement of the prefetch instructions.