FastPrepTwo-bit Branch Predictor
Problems/Two-bit Branch Predictor

Two-bit Branch Predictor

Xilinx logoXilinx● EasyNEW GRADONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks how to implement a branch predictor without specifying its policy or interface. This exercise authors a two-bit saturating-counter table, initial state, PC modulo indexing, aliasing, sequential prediction-before-training and finite bounds. Approximate source match: 65%.

Implement a table of two-bit saturating branch-prediction counters. There are entries counters, all initially1 (weakly not taken). For each [pc,outcome] event, use index pc % entries. Different PCs with the same index share a counter.

First emit a prediction from the current state:0 for states0 or1, and1 for states2 or3. Then train that counter using the actual outcome: increment by1 up to3 for outcome1, or decrement by1 down to0 for outcome0. Process events sequentially and return the predictions in order. Predictions always precede training on that event.

Function

branchPredictions(entries: int, events: int[][]) → int[]

Examples

Example 1

entries = 1events = [[0,1],[0,1],[0,0],[0,0],[0,0]]return = [0,1,1,1,0]

Starting at state1, the states before these predictions are1,2,3,2,1. States2 and3 predict taken.

Example 2

entries = 2events = [[0,1],[2,1],[0,0],[1,1],[3,0]]return = [0,1,1,0,1]

PCs0 and2 share index0; PCs1 and3 share index1. Aliasing shares the learned counter state.

Example 3

entries = 4events = []return = []

No branches produce no predictions.

Constraints

  • 1 <= entries <= 64.
  • 0 <= events.length <= 10000.
  • Every event has exactly 2 integers.
  • Every event value is from 0 to 1000000.
  • Each event is [pc, outcome], where outcome is 0 or 1.

More Xilinx problems

  • Count Ones in a 16-bit WordONSITE INTERVIEW · Seen Feb 2019
  • Delete a Given Linked-list NodeONSITE INTERVIEW · Seen Feb 2019
  • Reservation-station Tag MatchONSITE INTERVIEW · Seen Feb 2019
All Xilinx interview questionsSee Xilinx hiring insights
Saved
public int[] branchPredictions(int entries, int[][] events) {
    return new int[0];
}
Checking account…