(An) adaptive sequential prefetching scheme in shared-memory multiprocessors

Abstract

The performance of processor has increased dramatically over the past decade and has outperformed that of main memory. As a result, the main memory access latency becomes an obstacle to achieve high performance computing. In large-scale multiprocessors with a general interconnection network, the program execution time significantly depends on the shared-memory access latency which consists of the memory access latency and the network latency. The shared-memory access latency reaches to tens to hundreds of processor cycles with the advent of very fast uniprocessors and massively parallel systems. The most part of this latency comes from the large network latency associated with the traversal of the processor-memory interconnect. Caches are quite effective to reduce and hide the main memory access latency in uniprocessor systems and the shared-memory access latency in shared-memory multiprocessors. However, the remained cache miss penalty is still a serious bottleneck to achieve high performance computing. Prefetching is an attractive scheme to reduce the cache miss penalty by exploiting the overlap of processor computations with data accesses. Especially for multiprocessors, cache miss penalty can be decreased significantly by overlapping the network latency of fetched block with those of prefetched blocks. Many prefetching schemes based on software or hardware have been proposed. Software prefetching schemes perform static program analysis and insert explicitly prefetch instructions into the program code, which increases the program size. In contrast, hardware prefetching schemes control the prefetch activities according to the program execution by only hardware. Several hardware prefetching schemes prefetch blocks if a regular access pattern is detected. These schemes require complex hardware to detect a regular access pattern. Prefetch on misses [29] is a simple hardware scheme, but needs a miss to prefetch one block. Thus this scheme reduces the miss rate ...