Analysis of scratch-pad and data-cache performance using statistical methods

An effectively designed and efficiently used memory hierarchy, composed of scratch-pads or cache, is seen today as the key to obtaining energy and performance gains in data-dominated embedded applications. However, an unsolved problem is - how to make the right choice between the scratch-pad and the data-cache for different class of applications? Recent studies show that applications with regular and manifest data access patterns (e.g. matrix multiplication) perform better on the scratch-pad compared to the cache. In the case of dynamic applications with irregular and non-manifest access patterns, it is however commonly and intuitively believed that the cache would perform better. In this paper, we show by theoretical analysis and empirical results that this intuition can sometimes be misleading. When access-probabilities remain fixed, we prove that the scratch-pad, with an optimal mapping, has always outperform the cache. We also demonstrate how to map dynamic applications efficiently to scratch-pad or cache and additionally, how to accurately predict the performance