[libre-riscv-dev] [Bug 206] Implement branch prediction

[bugzilla-daemon at libre-riscv.org]

http://bugs.libre-riscv.org/show_bug.cgi?id=206

--- Comment #8 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #7)

> (second time writing this all, my text editor crashed on my phone)

bleh. pain when that hapoens

> What's reverted is the branch predictor's logical internal state (as well as
> the fetch PC and branch target buffer), not all the registers and memory
> locations that are written to.

ok got the terminology. with you.

> Oversimplified Diagram:
> 
> Branch Predictor/BTB  <----+
>    |                       |
>    v                       |
> Fetch <--------------------+
>    |                       |
>    v                       |
> Decode <-------------------+
>    |                       |
>    v                       |
> Issue Queue <--------------+
>    |    ^                  |
>    v    |                  |
> 6600 Scheduler <-----------+
>    |     ^   ^             |
>    |     |   |             |
>    +--> ALU  |             |
>    |         |             |
>    +--> Load/Store         |
>    |                       |
>    +--> Branch Execution --+
> 
> The branch predictor is logically separate from the branch execution unit --
> the branch predictor is part of the fetch pipeline, while the branch
> execution unit is after the 6600 OoO engine has a chance to schedule and
> manage the instructions, which can only happen after the fetch pipeline
> gives the OoO engine the required instructions.
> 
> Basically, the 6600 OoO engine can only manage speculative execution of the
> instructions it's in charge of, where the fetch pipeline is in charge of
> instructions that haven't yet reached the OoO engine, so the fetch pipeline
> has to be able to cancel instructions that were erroneously fetched. Part of
> canceling instructions is reverting the state of the branch predictor such
> that those erroneously fetched instructions don't show up in the branch
> predictor's logical state and the correct result of branch execution shows
> up instead.
> 
> Hopefully this all makes more sense.

it reminds me of the vehicle simulator i did in 1994. SpecManager. it's sold on
ebay still! i was amazed to find it there :)

there i created a series of "states" representing the vehicle: position, gear,
speed, and from that computed acceleration fuel economy etc as a separate
struct.

chains of these were calculated, giving a "forward look" into the future.  it
was  obviously, possible to run that multiple times, say by saying "downshift"
in one chain, and "stay in gear" on another.

after several chains were done (for short distances) the "best" was selected
and the rest discarded.

this is the fundamental basis apparently of "game theory" although i only found
that out after 18 months work on it.

i suspect we need something similar: a set of tables which are separate from
each other: one that is for KNOWN program pathing (path-ing) and one (or more,
if we have multiple Branch Units) for currently-unknown (speculative) paths.

on correct selection of a path the statistics collected from that path are
merged into the "KNOWN" table(s).

if that path information is actually needed during fetch (even if it is
speculative) then a "merge" function can take the data from both tables and
make decisions.

hm i am going to reach out to comp.arch see what people think, there.  there is
likely a real simple elegant "thing"
which decades of collective experience knows of immediately.

-- 
You are receiving this mail because:
You are on the CC list for the bug.