Branch predictor design for low resource architectures

Abstract

In the landscape of computer architecture research, branch prediction has been an impor- tant item of both academic and industrial research interest since long. Indeed, as widely acknowledged in this community, designing e cient branch predictors has always been one of the top priority research tasks in computer architecture. Over the past few decades, a wide variety of branch prediction strategies have been proposed in literature, with widely varying insights, structures, philosophies and performance considerations. Fostered by phe- nomenal research in branch prediction algorithms, modern commercial processors today embed quite sophisticated predictors inside, with signi cant prediction capabilities and runtime performance on widely varying workloads. This thesis is an attempt to revisit the problem of branch predictor design from a slightly di erent lens. In particular, the speci c focus of our work is in designing predictors that are particularly suited for low storage environments. Dynamic branch predictors which are invoked during program execution typically store outcome histories of program branch instances, learn interesting patterns from these histories and use them for delivering pre- dictions for future branch instances. As is evident from experiments reported in literature, many of the state-of-the-art dynamic branch predictors that show promise when exercised in high end processors, often fail to meet the accuracy and energy expectations when exercised in storage constrained embedded environments. A thorough scrutiny of the performance debacle reveals the fact that these sophisticated prediction strategies are signi cantly sen- sitive to the sizes of the history they learn from, more the size of the history structures these predictors are allowed to operate on, the better is the prediction accuracy, in general. This motivates us to design strategies that can e ciently mitigate these concerns, while maintaining desired prediction accuracies at low storage points. In our journey through the di erent chapters of this thesis, we explore three main directions in branch prediction research. On one side, we examine if static analysis, through which we learn program characteristics beforehand between program versions, can lead to enhanced prediction performance. Our explorations reveal a positive performance bene t, and we propose a novel scheme to do away with a number of dynamic predictor invocations, and thereby improve on latency and energy, without compromising on prediction accuracy. As our second theme of exploration, we explore the problem of multi-component predictor de- sign that can deliver better prediction accuracy by combining several dynamic components to deliver a prediction. Indeed, this is quite useful in general, since branch instances of a given application exhibit widely varying dependencies on the outcome history patterns, and it is usually not possible to learn these and predict their outcomes with a single predictor component. However, the price to be paid for such multi-component predictors is in terms of the storage cost, since these components are typically trained to operate on individual history storage tables, which makes them di cult to exercise at low storage points. This is where our research provides two novel design schemes, with a proposal to unify the stor- age tables of the multiple components, and still deliver the expected prediction accuracy performance. In particular, we look at predictor designs with two or more components, and propose suitable modi cations to make them work with shared predictor tables, while maintaining high prediction accuracy. The nal theme of our research is around branch predictor evaluation. On one side, we develop a framework for branch predictor selection with consideration of multiple metrics of evaluation, namely, accuracy, latency, energy etc. This is an useful aid for prediction strategy selection for a given application domain, wherein multiple performance metrics, not just one, are important elements of concern. Our frame- work provides an useful exploration aid in this direction. On the other side, we examine the di erent components of a branch predictor design with respect to their resilience against faults and attacks. One of our key contributions in this direction is an attack scheme that can de nitively slow down a benign application in a concurrent multi-threaded execution environment. We believe that such studies can lead to positive bene ts for predictor design. In summary, we believe that this thesis makes some important contributions in the space of branch predictor design for low storage processors. On one hand, our strategies for storage consolidation entail predictor component designs that can work on shared predictor tables. On the other hand, inputs from static program analysis help us synthesize better strategies for prediction. This gives us a unique advantage, as we demonstrate through extensive experiments on architecture workloads.