Analyzing Multiprocessor Cache Behavior Through Data Reference Modeling

Abstract

This paper develops a data reference modeling technique to estimate with high accuracy the cache miss ratio in cache-coherent multiprocessors. The technique involves analyzing the dynamic data referencing behavior of parallel algorithms. Data reference modeling first identifies of different types of shared data blocks accessed during the execution of a parallel algorithm, then captures in a few parameters the cache behavior of each shared block as a function of the problem size, number of processors, and cache size, and finally constructs an analytical expression for each algorithm to estimate the cache miss ratio.