BPU research

[ArsenyBochkarev]

List below all your findings on CPU's branch prediction unit: inner structure, algorithms, code snippets for testing, projects, etc.

[ArsenyBochkarev]

BPU structure

High-level overview

Advanced Branch Prediction presentation

Example for the simplest idea: always guess NextPC = PC + 4. To support it, compiler needs maximize the chances that the next sequential instruction is the next instruction to be executed:

1. Lay out the control flow graph such that the “likely next instruction” is on the not-taken path of a branch
2. Get rid of unnecessary control flow instructions by combining predicates (predicate combining)
3. Convert control dependences into data dependences (predicated execution)

A Branch Target Buffer (BTB) -- Branch Target Address Cache can be implemented.

Two state machines for BPU are presented: Last-time prediction and 2-bit counter (change prediction after 2 consecutive mistakes)

Other approaches are

• Global Branch Correlation: keep track of global True/False for all branches (Global History Register or GHR), use it to guess the next branch (if it contains some of the patterns seen before -- patterns are in Pattern History Table or PHT). The 2-bit counters can be used. The further improvement is to detect biased branches (i.e. 99% of which are taken) and predict them with a simplier predictor
• Local branch correlation: works mostly for small loops. It keeps a per-branch history register

A combined predictor can be implemented.

State-of-the-art tendencies in branch-prediction:

• Branch Prediction with perceptrones (in short: AI-powered BP)
• Multiple history lengths for branches (different branches require different history lengths for better prediction accuracy)
• Branch confidence estimation (used to decide which BP to use)

Issues in fast and/or wide instruction fetch engines

• Fast fetch: Complex branch prediction can take too long
• Wide fetch (multiple instructions per cycle): direction in branches present in the fetch block is not known but the instructions need to be fetched

Wikipedia

A lot of approaches are described

Projects

None for now (as we're just testing out the flow)

Code snippets

List of found BPU benchmarks

• Take a look at code used in this article (more precisely here)
• C++ sorted/unsorted array example
• BPU benchmark for multiple small hot runs (the code is here)
• Take a look at this discourse

Additional performance tuning

See some guidelines here. I'll list some below.

Utilize the compilers flags and attributes:

• -align-all-blocks=<uint> Force the alignment of all blocks in the function.
• -align-all-functions=<uint> Force the alignment of all functions.
• -align-all-nofallthru-blocks=<uint> Force the alignment of all blocks that have no fall-through predecessors (i.e. don't add nops that are executed).

Use the compiler/language features for tuning:

• C++'s likely/unlikely attribute specifiers
• Clang's noinline/always_inline attributes
• Clang supports hot/cold attributes
• Clang's #pragma unroll <N> directive

N.B.The inline function specifier does not guarantee that the function will actually be inlined (see here).

LLVM

See the investigation pipeline for relocation relaxation elimination (aka short jumps elimination): Stackoverflow question AND this presentation -> fixupNeedsRelaxationAdvanced from LLVM backend -> RISCVAsmBackend::getRelaxedOpcode takes the PseudoLongBxx -> RISCVMCCodeEmitter::expandLongCondBr expands the PseudoLongBxx to an inverted conditional branch and an unconditional jump

• We can play with it using the option -riscv-asm-relax-branches or force disabling it any other way
• Possibly take a look at this discourse :man_shrugging:

See:

• MBB Placement pass
• HotCold Splitting pass
• RISCV asm backend utilities
• Pass for noop insertion in X86 target (which was then reverted). It may be pretty cheap to adapt it for our needs.