n (m,n) correlating branch predictor uses the behavior of the most recent m executed branches to choose from 2m predictors, each of which is an n- bit predictor. A two-level local predictor works in a similar fashion, but only keeps track of the past behavior of each individual branch to predict future behavior.There is a design trade-off involved with such predictors: correlating predictors require little memory for history, which allows them to maintain 2-bit predictors for a large number of individual branches (reducing the probability of branch instructions reusing the same predictor), while local predictors require substan- tially more memory to keep history and are thus limited to tracking a relatively small number of branch instructions. For this exercise, consider a (1,2) correlating predictor that can track four branches (requiring 16 bits) versus a (1,2) local pre- dictor that can track two branches using the same amount of memory. For the fol- lowing branch outcomes, provide each prediction, the table entry used to make the prediction, any updates to the table as a result of the prediction, and the final mis- prediction rate of each predictor. Assume that all branches up to this point have been taken. Initialize each predictor to the following:
