Branch Prediction

[arupc]

Per previous discussion, we would like to develop an API that can support various branch prediction implementations, including possibly any existing open-source implementations.

As an example, the API should be such that it can support:

• a simple oracle predictor
• BOOM's branch predictor, as described here: https://docs.boom-core.org/en/latest/sections/branch-prediction/index.html

Output of the branch predictor is a Fetch Packet. Each Fetch Packet represents a sequence of instructions and is characterized by at least :

• Fetch PC, the pc of the first valid instruction in the Fetch Packet
• Number of instructions in the Fetch Packet

Thus a simple API would like:

class FetchPacket {
    uint64_t FetchPC;
    uint32_t num_insts;
    <implementation-specific-attributes>; // may be added using a template parameter?
};

[danbone]

Sorry we had an internet outage during the SIG meeting, so I missed the last 10 minutes.

Initially I didn't want to change the current Fetch implementation too much. The idea was to have separate units instanced underneath it:

• Branch Target Buffer
• Return Address Stack
• Direction Predictor (gshare/TAGE/Perceptron etc)
• Indirect Target Predictor (ITAGE)

Each of these would have their own parameter set, and the user could configure the topology of fetch to swap different algorithms in and out. An example configuration file:

top.cpu.core0.fetch.params:
  predictor: "TAGE"
  tage.params:
    history_tables: 7
    min_hist_size: 5
    max_hist_size: 130
    table_tag_widths: [0, 9, 9, 10, 10, 11, 11, 12]
    log2_table_sizes: [13, 9, 9, 9, 9, 9, 9, 9]
    bimodel_counter_bits: 4
    tage_table_counter_bits: 3
    tage_table_u_bits: 2
    path_hist_bits: 16
  btb.params:
    num_entries: 4096
    associativity: 8
    block_size: 64
  ras.params:
    num_entries: 16

(I'm not sure how feasible this is yet)

As for the API, maybe it would be better if I placed the sub-components under a separate BranchPred component rather than fetch so we have a single point of interaction under multiple fetch implementations.

Though I'm not sure how practical it would be as the complexity grows. For example if we had a fetch with a small BTB providing fetch PCs in 1 cycle, then a larger BTB which overrides the earlier prediction 2 cycles later (similar to BOOM IIRC). Then it would be heavily coupled with the fetch logic, and the BranchPred API might not be flexible enough for both implementations.

Similarly if the predictor sub-components are hidden under BranchPred then it could make more complex topologies more difficult to implement. i.e. a BTB with a separate prefetch port.

What are you thoughts?

FWIW I started a simple predictor earlier today using an API like:

• Predict an instruction using an address, outputs the direction and some meta data in a implementation structure i.e. index of counter
• Speculative update with a unique ID and the meta data captured from the prediction (prediction might be from a different component i.e. RAS), this would update the history registers and track the meta data using the unique ID provided.
• Flush - restores any state to the what it was previously to the speculative update with the unique ID given
• Update - Clean up, and update state for the unique ID

[egieske]

In a correct-path-only trace-driven model, like Olympia is presently, branch prediction primarily affects the timing of sending packets of instructions from the trace to the Decode unit. Like an ITLB or ICache miss, a branch misprediction stalls the sending of the next (i.e., branch target) correct path instruction packet after the mispredicted branch until execution of that prior branch is completed. Initially in Olympia, rather than flushing on misprediction, a mispredicted branch completion need only wake the next fetch packet, which can be mechanized with a SignalOutPort from the branch execution pipe(s) back to Fetch. In such a model, branch prediction can also affect the size of the fetch packet when the predictor predicts a smaller packet than microarchitecture constraints would otherwise require.

[arupc]

Trying to understand the implications of the comments above on the possible API. Does that mean, a better API would simply be a Fetch API instead of a branch prediction API, i,e, an API that describes the Fetch Packet, instead of the output of the branch prediction?

class FetchPacket {
// vector of Mavis-decoded instructions from STF-trace, subject to parameter-specified max length
// implementation-specific attributes
}

This FetchPacket can be output of the Fetch block and input to Decode unit. This is similar to what Olympia does today. Then, there will be more flexibility in implementing Fetch block, including branch prediction, but less opportunity to potentially reuse branch prediction implementations.

[arupc]

Thinking a little bit more about how branch prediction would work along with STF trace driven fetch. The following is an example uarch, based on BOOM.

• Fetch unit has a parameter num_to_fetch, which denotes number of instructions in a FetchPacket
• At the first cycle:
  • a) the fetch unit reads the PC of the first instruction of the STF trace, uses it look up the BranchPredictor (which will contain BTB and other structures)
  • b) BTB outputs if there is a branch instruction in num_to_fetch instructions, starting with the first instruction and if yes, which one, indicated by `“bidx”, or branch index.
  • c) BTB also outputs the target of that identified branch instruction
  • d) Read a sequence of instructions from STF trace until an actual taken branch is discovered or bidx instructions are read.
  • e) Create FetchPacket
    • if there is actually a branch instruction before bidx instructions, synthesize the tail of FetchPacket
  • f) Using the PC of the first instruction, look up ICache and determine to-be-observed latency
  • g) Create an event to deliver FetchPacket to Decoder Unit after the determined Icache latency
• In the next cycle:
  • Use the predicted target from the prediction in the previous cycle to look up branch predictor and obtain new prediction
  • If the predicted target does not match with PC of next instruction to be read from STF trace, do not read any instructions from STF trace. Synthesize the entire FetchPacket.
  • If the predicted target matches with the PC of the next instruction to be read from STF trace, repeat steps d) and e) from above
  • Repeat steps f) and g) from above

[danbone]

Sorry for the delay I've been on leave since last Thursday.

Trying to understand the implications of the comments above on the possible API. Does that mean, a better API would simply be a Fetch API instead of a branch prediction API, i,e, an API that describes the Fetch Packet, instead of the output of the branch prediction?

Maybe.. The discussion is moving away from branch predictors somewhat, perhaps it's due to branch predictor being an overloaded term referring either to the actual branch prediction algorithm (i.e. gshare/tage), or the component that synchronizes the various predictors to stream addresses into the instruction cache. I've been concentrating more on the branch prediction algorithm part, or branch direction predictor.

[arupc]

Looks like there are 3 items to think about:

• The Fetch API: this that determines the interface from Fetch Unit to Decoder Unit.
• The Branch Prediction API: This is the output of the branch predictor every iteration. The output will be used to a) lookup Icache b) create Fetch Unit output and c) manage STF trace reader.
• Mangement of STF trace reader and creation of FetchPacket per output of the Branch prediction

For both fetch API and branch prediction API, it would be good if we can standardize by specifying what are the minimum required components while accommodating possible extensions for various branch prediction algorithms.

[danbone]

Yes.

For branch prediction I think we need:

1. A BranchPred* (for lack of better word) API, a class containing and gluing the individual components like the BTB, RAS, direction predictor, indirect target predictor, together.
2. Standard APIs for each of those components so they can be swapped in and out.

For the BranchPred API, although it could be done with zero time functions, we probably want to consider moving it into it's own unit and using ports to reflect the pipelining aspects of the predictors and enable someone to model something like BOOM which uses an overriding predictor (essentially flushing itself).

For the individual components, I think they would more likely operate in zero time.

*Separate related point. I thought it might be a good idea just to use Fetch here, and have an ICache component sitting between fetch and decode. Fetch just generates a stream of something like the fetch packet described above (address, size, mask of predictions, some meta data like an ID)

[danbone]

Some points captured in our meeting earlier today

• Branch Prediction API should be independent of trace driven mechanisms (wrong path/random path could be done separately)
• Predictor input could be a block address (fetch group) or individual instruction addresses
• We should revisit the original document put together by @arupc