```## Live Branch / CTI Prediction Material.
#
# 29 April 2020,  9:19:41 CDT
#  4 May 2020, 15:32:28 CDT

bne r1, r2, LOOP  #  T T N  T T N  T T N  T

#  1 May 2020,  9:10:36 CDT

## Branch Predictor Behavior
#
#  Warmup
#
#  Collisions

## Warmup

## Branch Patterns

# 3-iteration Loop.
#
bne r1, r2, WEVR  #  T T N  T T N ...
beq r1, r2, RVEW  #  N N T  N N T ...

# 20-iteration loop
#
bne r1, r1, L     # TTTTTTTTTTTTTTTTTTTN TTTTTTTTTTTTTTTTTTTN ..

## Bimodal performance on n-iteration loops.
#
# After warmup, and assuming no interference:
#
# (n-1) correct predictions, 1 misprediction.
# Accuracy (n-1)/n
#
# Not so good when n is small:
#
# n  Accuracy
# -  --------
# 3  0.667
# 4  0.750
# 5  0.800

#  Material below from 1 May and 4 May 2020
#
## Local Predictor Motivation
#
#  Can you predict the next outcome?:
#
beq r1,r2,Targ   N N T  N N T  N N T  N
#
#  Of course, that's easy!
#  How can hardware do it?
#  How can hardware do it quickly and inexpensively?
#
##  Remember patterns.

# Use a memory device, called a Pattern History Table (PHT)
# Address is the pattern ..
# .. data is a two-bit counter.
#
# Size of address: local history size.
#  Real life: 10 - 16 bits.
#  Classroom examples, smaller so they can be worked by hand.

# Example: local history size of h = 3

beq r1,r2,T   N N T  N N T  N N T  N
#            ------^         ^ ^
#                  |         | |
#                 001        |100   <-- Local histories. h = 3
#                   1        |  0   <-- Local histories. h = 1
#                  01        | 00   <-- Local histories. h = 2
#                            |
#                           10      <-- Local histories. h = 2

# Let local history size be 3 bits.

# PHT: 2^h
000
001   3 -> 2 -> 1 -> 0
010
011
100   0 -> 1 -> 2 -> 3
101
110
111

## Global Predictor

# Motivating Example

A: beq r1, r2    N  T  N N T N  T      # Totally random. p(T) = .5
B: beq r1, r2   T N   T N N T N   T    # Totally random. But correlated with A.
#                 ^         ^ ^
#                 |         | |
#               01        00  |      <- Global
#                           01

# Possible FR values:

A: beq  TTTTTTTTTTTN
B: beq                 T (every time)

C: beq  TTTTTTTTTTTN
D: beq                 N (every time)

## gshare Predictor

# Address of PHT:  GHR xor PC

## 2019 Final Exam Problem 3

# Bimodal on B1.
#
# 0 1 0 0 0 0 1 2   3 2 1 0 0 1 2  <- 2-bit counter values
#  T N N N N T T   T N N N N T T
#  x         x x     x x     x x
#
# Accuracy: 3 (correct) / 7 (outcomes)  = 3/7

# Local on B2

T NT
---

T NNNT T
---

T NNNN NTTT
---

```