## 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
 Addr  Data
 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
 ---