Accurate prediction of future events in high-performance computers is an important means to enable aggressive speculation technique. These speculation techniques enable a processor to e.g. execute beyond unresolved branch conditions (branch speculation), to avoid stalling on data dependences (value speculation), to avoid costly cache misses (prefetching), or to avoid costly coherence events in multiprocessors (coherence speculation).



Typically, dynamic prediction techniques use the sequence of past events to predict future events. As a concrete example, the well-known two-level branch predictor uses the recent past sequence of branch outcomes of a branch to predict the outcome of the next execution of the same branch. The sequence of past branch outcomes is stored in a history register associated with the branch. While the prediction accuracy is expected to increase when the length of the history register increases, increasing the size introduces several problems. First, as we increase the history register size, the time to train the predictor increases. Hence, it takes longer to get useful predictions out of the predictor. Second, the amount of memory devoted to the predictor increases more than linearly; while the register size increases linearly, the number of predictor entries increases by 2N, given N history bits. Finally, it may be that only a few branches may benefit from long history sequences; i.e., there is a need to adapt the length of the history registers based on the prediction accuracy for that branch.



The aim of this collaboration is to explore the design space of a new class of predictors that adapt the history length of predictors based on the prediction accuracy. The baseline approach we will start from is a first cut on such a predictor which was proposed in the context of coherence prediction in [Nilsson 2004]. In this predictor, the prediction accuracy was constantly monitored while producing new predictions. As long as the prediction accuracy is below a certain threshold, the number of entries in the history register was increased. It was found that the prediction accuracy could be increased and at the same time keeping training time at a manageable level. Subsequently, we aim to apply variable history-length prediction on a class of Tag-Correlating Prefetchers introduced in ISCA-29, 2002 and HPCA-9, 2003 by Hu, Kaxiras and Martonosi. Furthermore, we will examine the applicability of our approach to branch prediction. Our aim is also to get a deeper understanding into performance and design tradeoffs for this new family of prediction techniques.



Our aim is to get a deeper understanding into performance and design tradeoffs for this new family of prediction techniques.

The collaboration is between Chalmers University of Technology (Per Stenstrom) and University of Patras (Stefanos Kaxiras). Initially, we are seeking funds for the first six months to support shorter research visits to develop the above concept and perform some pre-studies. While most of the interaction will be done using email, phone, and netmeeting facilities, we ask for support corresponding to two 1-week trips during the spring semester:



Two round-trip flights between Sweden and Greece. Estimated cost: 1200 EU

14 days of hotel plus allowances: Estimated cost : 14 x 120 EU plus 14 x 50 EU plus 200 EU for local transportation. Total : ~ 2800 EU