A Survey of Deep Learning Techniques for Dynamic Branch Prediction

It is software based prediction strategy. This approach assumes either the branch is always take on branch is always not taken. This is a very simple and cost effective prediction technique. Since this approach does not maintains a history table of previous branch decisions it takes only less energy for instruction execution when compared to other branch prediction techniques [13]. Following are the schemes of static (software-based) branch prediction.

This hardware-based prediction strategy is based on the history of branch executions. Dynamic branch predictions are complex compared to static prediction approach but has high accuracy rate. The performance is based on the prediction accuracy and penalty rate. Different dynamic (hardware-based) branch prediction strategies are:

In 1957 Frank Rosenblatt introduced perceptrons which was inspired by learning abilities of a biological neuron [15]. Perceptron is a single layer neural network which consists of a processor that takes multiple inputs with weights and biases to generate single output. As illustrated in Figure 1 Perceptrons work by multiplying inputs with weights and weighted sum of all multiplied values are taken and applied to an activation function.

Jimenez et al. [16] proposed a perceptron based branch prediction method which can be used as an alternative to traditional two-bit branch prediction buffers. The proposed perceptron predictor is the first dynamic predictor to use neural networks for branch prediction.The predictor make use of long branch history which is made possible by the hardware resources which can scale the history length linearly to improve the accuracy of prediction method. Basically the design space of two-level branch predictor (correlation-based branch predictor) is explored and instead of pattern history table, table with perceptrons are used.

In this study the branch behaviour is classified as linearly separable or linearly inseparable. Perceptron predictor’s performance was better with linearly separable branches. Decisions made by perceptrons are easy to understand when compared to complex neural networks. Another factor is choosing perceptron as predictor is because of efficient hardware implementation. Other popular neural architectures like ADALINE and Hebb were used in this study but performance was low due to low hardware efficiency and low accuracy.

Figure 2 is the block diagram for proposed perceptron predictor. The system processor maintains a table of perceptrons in SRAM like two-bit counters. Based on number of weights the and budget for hardware the number of perceptrons in the table is fixed. When a branch instruction is fetched an index is produced in the perceptrons table by hashing the branch address and the perceptron at this index is moved to a vector register of weights (In this experiment signed weights are used).The dot product of weight and global history register is computed to produce output. If the output value is negative then the branch is predicted to be not taken or if the value is positive then branch is taken. When actual outcome is known, the weights are updated based on the actual result and predicted value by the training algorithm.

To achieve best performance three parameters are considered and tuned, 1) History Length, 2) Weight Representations, 3) Threshold. The increase in history length yielded more accuracy in predictions. history lengths from 12 to 62 reported best outcome for this training algorithms. As mentioned earlier the weights are signed integers and they simplify the architecture design.

In [16] two dynamic predictors gshare and bi-mode were chosen to compare with perceptron predictor. As seen in the figure 3, when longer histories are considered gshare shows poor performance and perceptron predictor improves the performance. This paper is concluded by stating that although perceptrons are not capable of learning linearly inseparable behaviour of branches (Figure 4) and they are complex when compared to two-bit counters, perceptrons can use long history tables without any exponential resources and also achieve a low misprediction rates and higher accuracy when compared to existing dynamic predictors.

Akkary et al. in [17] proposed a perceptron based branch confidence estimator to reduce the misprediction of branch instructions. One of the factor that contribute to high performance of a system is execution of unresolved branches based on some speculations made by branch prediction techniques. Mispredicted executions negatively impact the system by taking up the resources, creating stalls in execution and also affect the power of the system because more instructions are executed when there is mis-speculation occurs. In deeper pipeline processors, pipelining gating plays a vital role in reducing wasted executions based on wrong speculative decisions made by predictors. With perceptron-based branch confidence estimator predictions provide multi-valued outputs. i.e the classify the branch instructions into “strongly low confident” and “weakly low confident”.

With confidence estimation, instruction fetching can be stalled when low confidence unresolved branch instructions are encountered. Estimation is correct when low confident branch is actually mispredicted. This correct estimation can reduce the execution wastage. When estimation is wrong (i.e low confident branch is correctly predicted) there will be a pipeline stall which can lead to performance loss.

As seen in the figure 5, index of array of perceptrons are based on conditional branch memory address. In this method global history register which contains taken branch represented as 1 and not-taken branch represented as -1 is passed as a input vector tho the perceptron. Dot product of weight vector in perceptron and this input vector is used to generate the output. As mentioned earlier the output of this approach is multi-valued. i.e, branches can be further classified as low or high confidence. The generated output is then compared against a specific threshold $\lambda$ . When output is larger then prediction can be wrong or if the output is smaller than the threshold then the prediction is more likely to be correct.

Specificity and Predictive value of a negative test (PVN) are the primary metrics used for perceptron based branch confidence estimator. Specificity is the percentage of mispredicted branches which were classified as low confidence by branch confidence estimator. PVN is the probability of correctly mispredicted low confidence branches (as a measure of accuracy).

Tarsa et al. in [18] says that although branch prediction attained 99% accuracy in prediction static branches, Hard-to -predict(H2P) branches are still a major bottleneck in the system performance. Authors suggested machine learning approach to that could work along with standard branch predictors to predict H2P. They developed helper predictors mainly convolutional neural network based helpers to improve the process of pattern matching in global history data. Unlike the TAGE and preceptron based BPs, CNN based helper predictors are deployed offline.

This paper illustrated two examples of program in which the data dependency of iteration counts creates H2Ps. Variations available in data can confuse the state-of-the-art predictors but are handled by convolutional filters. The global history (instruction pointer and direction of previous branches) are converted to vector representations. The input to CNN is generated by concatenating the vectors to from a matrix for global history. CNN calculates the dot product of data vector, weight vector,filter and bias to perform the pattern matching. Score computer by each filter against the each history matrix column are passed to filter in the linear layer (similar to perceptron layer) to match the output of layer 1 in two-layer CNN. If the output of layer 2 is ¿ 0 then the branch is taken or it is not-taken. the first layer (layer 1) in CNN identifies which instruction pointer and direction in history table correlates with the h2P’s direction and layer 2 identifies which position in history contribute to branch prediction process.

This paper concluded by stating the how two-layer CNN along with the branch predictors can reduce the positional variants in global history data which can lead to branch mispredictions. They also provided some insights like passing more data like register values to network to improve the accuracy for future development of ML-based branch predictors.

Based on the work [18] by Tarsa et al, Zangeneh et al. developed a convolutional neural network called as BranchNet [19] for hard-to-predict branches in 2020. As mentioned in [18] traditional branch predictors are updated in run-time which makes it difficult to find the correlations in branch history. Exisiting predictors cannot find correlations from a noisy history while CNN can identify those correlations correctly. This capability of CNN improves the prediction rates but requires high computational cost and large dataset for training. BranchNet can be trained offline and this models are attached to the program so that the predictors can use this model in runtime. Authors [19] popose CNN architecture in two-ways. 1)Using geometric history length as input to the model, 2)Sum-pooling for the compression of global history information. The designed CNN architecture is storage efficient and same latency as TAGE-SC-L.

In this paper two-variants of BranchNet are proposed. Big-BranchNet, consists of two fully-connected layers and five feature extraction layers (slice) (see 6). Slice consists of embedding layer, sum-pooling layer and convolutional layer for feature extraction from branch history. Each slice works on different history length to form a geometric series. Concatenated output from all slices are passed to FC layer for prediction output. Authors do not recommend the practical use of this variant as a branch predictor as this is a software model. Another variant of BranchNet is mini-BranchNet is co-designed with an inference engine. The architecture of min-BranchNet is similar to big-BranchNet except that it has knobs that can be tuned to reduce the latency and storage. Mini-BranchNet can work as a branch predictor.

The key achievement described in this paper is that with BranchNet deep learning network architectures can be trained in offline mode and this approach is very useful in eliminating the issues of state-of-the-art branch predictors when executed in runtime.

Deep Belief Networks (DBN) are stack of Restricted Boltzmann Machine(RBM) or Autoencoders which can be used as a solution to mitigate the vanishing gradient problem caused by backpropagation process. DBNs can be defined as a combination of probability and statistics with neural network architectures. The two layers (top) in this generative hybrid model are undirected and the layers are connected to next following layers [20]. Figure 8 is commonly used DBN architecture. It has four RBM layers and an output layer. Layer 1 and layer 3 has same size. Size of input layer and layer 4 are also same. The last layer in the network architecture is a perceptron (single layer neural network). Deep Belief Networks uses unsupervised leaning techinque, where it trains the network layers to reconstruct the input data in last RBM layer. The inner layer extract the features from input to regenerate it with minimum error.

In 2017 Mao et al. proposed the idea of using neural networks with deep belief networks for branch prediction [22] which could outperform perceptron based BPs in terms of reducing misprediction rate. Later in 2017 [21] Mao et al. discuss about the possibility of using advanced deep neural networks like convolutional neural network along with deep belief network for branch prediction. Branch prediction problem is considered as a classification problem to implement different deep learning network architectures and impact of global history register (GHR), branch global address, length of program counter of the classifier on the rate of mis-speculated branch is studied . 90% of data is used for training set and remaining 10% is used for testing and validation purpose. For branch prediction two CNN and one DBN models were created.

Figure 9 is the DBN architecture. Neurons in the fully connected layers (FC) 1 and 3 are same (630). Layer 4 is same as the input layer. Figure 10 shows the 2 differnt CNN architectures used for this experiment. First CNN architecture is based on LeNet and second one is based on AlexNet. The results of these network architectures are compared against state-of-the-art branch predictors.

This paper is concluded by stating that performance of deep neural network architecture based branch predictors are better than perceptron based BPs. Deeper CNN architectures can outperform state-of-the-art branch predictors like Multi-poTAGE+SC and MTAGE+SC. When the performance of DBN and CNN are compared, CNN architecture outperformed DBN based branch predictors.

Reinforcement Learning is a machine learning methodology in which the training algorithm estimates the error based on the penalty or reward in particular situation. The penalty is high and reward is low when the error is high. Reward is high when the calculated error is low.

In [23] Zouzias et al. proposed the idea of using machine learning technique Reinforcement Learning (RL) formulation in improving branch predictor designs. Today branch predictors in high-end processors are perceptron based or variants of TAGE. But there are not significant improvements in recent years to the prediction mechanism of these two variants. [23] suggests that branch prediction can be viewed as reinforcement learning problem because they have similar theoretical principles.We can consider branch predictor as an agent which can closely observe the control flow of the code (i.e the history of branch results) and learns a policy to improve the accuracy in future predictions. Execution environment of processor is considered as environment for branch predictor agent. Branch prediction with RL enables to explore design of branch predictor in the aspects of predictor’s decision making policy, state representation and misprediction minimization strategy.

The environment communicates with the agent (branch predictor) so that agent can choose and action from state space. Later, based on the correctness of the action selected by agent environment responds back with a reward. This reward helps to update the predictor. Normally the state space from where agent selects action contains PC address of branch, local/global history of branch instructions.

Based on the RL methods, the branch predictors are classified into two class categories 1) tabular, 2) functional. TAGE based predicors, gshare and bimodal predictors are categorized as tabular and perceptron based predictors are categorized as functional (O-GHEL, hased perceptron and multiperspective predictors). From figure 11 tabular predictors can be formulated with Q-learning and functional predictors with policy-gradient methods.

This paper provide information on how to use reinforcement learning in designing future branch predictors. Key aspects to be considered for the development are: