Cyclic dependence based data reference prediction

Abstract

Current work in data prediction and prefetching is mainly focused on one individual predictor per each class of data references. Despite the increasing complexity of these hybrid predictors, their prefetch coverage is still very limited. To reduce the complexity of the predictors and to expand the coverage of data prediction, we propose a novel data predictor, called the Cyclic Dependence based data Predictor (CDP), in this paper. Based on the runtime analysis for value dependence, registers used in the address calculation of a memory access instruction in a loop are classified into cyclic dependent registers and acyclic dependent registers. The complexity and predictability of data references will be determined by the path length of the cycle that contains the index pointer registers. To further illustrate its importance, we generalize our previously proposed Reference Value Prediction Cache with this CDP predictor. Simulation shows that significant reduction in memory latency can be obtained, especially for those using complex data pointer structures.