riscv-perf-model
riscv-perf-model copied to clipboard
riscv-software-src
Add a branch predictor
Need a branch predictor to Fetch. Open to considerations on the type. Should be parameterized, but a common API would be beneficial to keep the model generic.
Resolutions of the branches will require feedback from Retire and/or Execute . Typicality this can be done with ports.
There is an example branch prediction uarchitecture described here: https://docs.boom-core.org/en/latest/sections/branch-prediction/index.html . This can serve as an example to implement in Olympia
Unable to get a view of current status of this ticket. @arupc could you please brief about its current status.
We currently have made a timing sheet for the branch predictor based on the BOOM architecture. The plan is to model and implement the branch predictor APIs based on this timing sheet and integrate it with Olympia.
[1] Branch Predictor timing sheet
What is the most efficient way to determine if a Fetched Inst is a branch? Should we add a member to Inst like Inst::isStoreInst() or isLoadStoreInst()? Similarly, how should a branch predictor determine branch instruction type, e.g., call, return, unconditional, etc? Also, how should a branch predictor monitor the execution status of branch instructions? Inst::getStatus()==COMPLETE seems possible, but then the predictor will have to scan a list of in-flight branch Inst's every cycle to determine when it can update predictor internal state which may be inefficient.
What is the most efficient way to determine if a Fetched Inst is a branch?
I have an answer to that question here: https://github.com/riscv-software-src/riscv-perf-model/issues/104#issuecomment-1785229711
Similarly, how should a branch predictor determine branch instruction type, e.g., call, return, unconditional, etc?
Mavis supports multiple instruction type identifiers. You can see them here: https://github.com/sparcians/mavis/blob/4f3fef891f9ddc5c371c27500d02596f21ea6fc8/mavis/InstMetaData.h#L30
So, if you want to know if a branch is JALR, you can add this to Inst.hpp:
bool isJALR() const { return mavis_info_->isInstType(mavis::OpcodeInfo::InstructionTypes::JALR); }
Also, how should a branch predictor monitor the execution status of branch instructions?
The predictor should not monitor anything. Doing so means you're no longer event driven. 😄 How to solve this: add a sparta::DataOutPort<InstPtr> port to the ExecutePipe. When the ExecutePipe complete's the branch, it will write that branch to the port. The predictor will include a sparta::DataInPort<InstPtr> that receives the completed branch and do its magic. WARNING: you might get completed branches out of order. 😉
@klingaard Thanks! I apologize for the redundant questions. I missed your comments on https://github.com/riscv-software-src/riscv-perf-model/issues/104#issuecomment-1785229711 What is the cost of adding sparta::DataOutPort<InstPtr> port to the ExecutePipes that don't execute branches and thus may remain disconnected? What are the tradeoffs between using a sparta::DataOutPort<InstPtr> port and using a sparta::SignalOutPort port to schedule predictor training?
What is the cost of adding sparta::DataOutPort port to the ExecutePipes...
None if you don't use it. The ExecutePipe in the complete inst block can check if the instruction is a branch (in general) and send it on:
if(ex_inst->isBranch()) {
out_branch_complete_->send(ex_inst);
}
The tradeoffs between an Data port and a Signal port (in this case) is use case. Signal port says, "Some branch completed, somewhere." The Data port says, "This specific branch completed."
A SignalOutPort can be tied to multiple SignalInPorts (i.e., broadcast). Can multiple SignalOutPorts be tied to one SignalInPort with a wired-OR effect?
A SignalOutPort can be tied to multiple SignalInPorts (i.e., broadcast). Can multiple SignalOutPorts be tied to one SignalInPort with a wired-OR effect?
Yep. If not, let me know. 😉
Restarting the discussion.
I've done some work towards a branch prediction implementation on #124
I aim to implement a RAS and a simple PHT predictor, as a way of defining the mechanisms for recovery and to serve as a basis for other implementations. The intention I had was to use the fetch factory to instantiate different predictors, BTBs or target predictors.
I'm happy to incorporate branch_pred_api into #124.
I'd probably also propose that we have a flush/squash method for dealing with traps or exceptions.
How can we determine if a branch instruction read from the trace is taken even if the branch is in the compact 'C' ISA form?
Except for the compact encoding case, we can check if the Inst is a branch (as above) && (getTargetVAddr () != (getPC()+4)).
Can we use something like:bool isCompactISA() const { return mavis_info_->isInstType(mavis::OpcodeInfo::ISAExtension::C); } and if TRUE check if (getTargetVAddr() != (getPC()+2)) ?
Defining bool isCompactISA() in Inst.hpp may also facilitate more accurate Fetch to Decode modeling where the hardware isn't limited to a fixed maximum amount of instructions as is currently in Olympia but is instead limited to a fixed maximum amount of bytes. For example, up to 32 bytes may be fetched and sent to Decode per cycle which could contain between 8x 4-byte and 16x 2-byte instructions.
@egieske I think we have a mechanism provided already see isTaken() https://github.com/danbone/riscv-perf-model/blob/0820c37c95068352d2ca7fe9cffb376c2e68fb2a/core/InstGenerator.cpp#L197
I think this comes from the STF reader. If using a different trace format then we'd have to implement it ourselves.
@danbone Thanks! I did a search for isTaken in Olympia and got nothing, then poked around mavis and saw nothing. I only see this in your repo.