6.823: Lab 3 Questions

Nada Amin

                 namin@mit.edu

Due: 7 November 2008

1. When possible, it’s more efficient to move code out of the analysis function and into the instrument function, because the instrument code is executed once, while the analysis code is executed repeatedly. Since we already know whether a branch has been taken or not during the analysis, it is more judicious to have two analysis functions, one for actually taken branches and one for actually not taken branches, so that when we collect the statistics, we can avoid an extra if statement. I haven’t noticed a big speed-up from this change. Perhaps, the overhead of an extra if statement per analysis is rather negligible compared to the overall overhead per analysis.

2. My implementation is based on [1].

I keep a table of N perceptrons. I also keep track of h bits of global history, which tells us whether each of the h most recent branches are taken or not taken. A perceptron learns to compute t(x_{1}, …, x_{h}): given the h bits of global history, it decides whether the target branch is taken or not. The perceptron has h + 1 weights, one for each history bit and one for the branch bias which is independent of the history. If it fails to predict the outcome correctly, the perceptron updates its weights. The perceptron computes the outcome as follows:

w_{0} + ∑_{i=1}^{h} w_{i} · x_{i} > 0

where each x_{i} is 1 or −1 depending on whether the ith most recent history bit indicates taken or not taken. The perceptron updates its weights when it fails to predict the actual outcome. Let t be 1 if the branch is actually taken and −1 if the branch is actually not taken. Then, the weights are updated as follows: w′_{0} ← w_{0} +t and w′_{i} ← w_{i} + tx_{i} for i ∈ {1, …, h}.

3. [2]

4.

References

[1] Daniel A. Jimenez and Calvin Lin. Neural methods for dynamic branch prediction. ACM Transactions on Computer Systems, 20:369–397, 2002.

[2] Scott McFarling. Combining branch predictors. WRL Technical Note TN-36, June 1993.