Software Prefetching Using Jump Pointers in Linked Data Structures

During linked data structures(LDS) traversals, prefetching improves the performance by reducing memory latency. We will discuss about the jump pointer prefetching which hides additional load latency by using an extra pointer to prefetch objects further than a single link away. Jump pointers can be implemented in Binary tress by adding jump pointers at creation time and in LDS by adding jump pointers at traversal time. Prefetch Arrays are also used to store jump pointers. It has two approaches hardware and software. Both the approaches have highly improved the performance of prefetching with the use of jump pointers. Prefetching in pointer-based codes(java programs) is difficult because separate dynamically allocated objects are disjoint, and the access patterns are thus less regular and predictable. However, according to experimental results, the largest performance improvement is 48% with jump- pointers in java programs, but consistent improvements are difficult to obtain.