Idea about the structure of an ideal predictor for architect exploration

[zybzzz]

I am currently working on the design of a value predictor. I have understood the use of arch_db(trace) and have some new ideas. For the value predictor, we use arch_db to record runtime traces. We then adjust our designed value predictor based on these traces, attempting to optimize it—for example, achieving an accuracy rate above 95%. After that, we perform SPEC06 benchmarking to analyze the gains we've obtained.

In this process, the final benefits we get from the value predictor are unknown; that is, we don't know the ideal gains we would achieve if all instructions were predicted successfully. For example, when we optimize branch prediction, we know that better branch prediction can improve the instruction fetch bandwidth, thereby absolutely enhancing processor performance. Similarly, when we optimize cache prefetching, we know that effective prefetching can definitely reduce memory access overhead, thus absolutely improving processor performance. However, with value prediction technology, we cannot be certain that it will yield better performance even when it works well. Simply put, when we predict load instructions, even if the prediction is correct, the correct result might be wasted due to violations of load/store memory access ordering. Similarly, when predicting add instructions, the predicted addition might not be an instruction affected by true dependencies in the out-of-order execution backend; even if the prediction is correct, it may not significantly improve performance and might instead incur the overhead of incorrect predictions. I believe all these reasons boil down to the fact that optimizing backend execution in an out-of-order processor involves too many considerations.

Based on this, I came up with an idea: we can try to first obtain the best-case benefits of value prediction technology. For example, we can use a emulator like NEMU that directly provides absolutely correct results when predicting instructions. This effectively simulates a value predictor with 100% accuracy. We can then perform benchmarking evaluations on such a value predictor to know in advance the maximum gains we can achieve before we start trace tuning, giving us more confidence to proceed with optimization. If the designed interface is sufficiently excellent and general, I believe this approach can help us quickly perform design space exploration and rapidly analyze the benefits that our design can bring.

In comparison, both tuning the value predictor to optimal performance using traces and constructing an ideal predictor with 100% accuracy aim to determine how much benefit our design can achieve under optimal conditions. For trace-based analysis, the difficulty lies in manually analyzing the traces and tuning based on them. For the ideal predictor, the challenge is in designing a NEMU that provides 100% correct values, integrating it into gem5, and ensuring that the instruction streams between the NEMU and gem5 are synchronized.

I wonder if any of you have relevant experience or would be willing to share your thoughts or offer your suggestions. Thanks!

@shinezyy @jensen-yan

[zybzzz]

I find this idea very interesting, and I am now trying to implement it.

[eastonman]

I believe there is a NEMU branch called runahead-xx or something like that, which was used in oracle branch predictor. Maybe that is helpful to you.

[zybzzz]

I believe there is a NEMU branch called runahead-xx or something like that, which was used in oracle branch predictor. Maybe that is helpful to you.

Thank you, I noticed some code related to runahead when reviewing the NEMU source code yesterday. I will switch to the corresponding branch for reference.

[tastynoob]

You can dump trace use NEMU or QEMU, then load it in GEM5 to implement ideal VP

[shinezyy]

You can dump trace use NEMU or QEMU, then load it in GEM5 to implement ideal VP

It is difficult to handle GEM5-specific exception and interrupt with traces.
Ideal BP's solution is more graceful.

[zybzzz]

You can dump trace use NEMU or QEMU, then load it in GEM5 to implement ideal VP

It is difficult to handle GEM5-specific exception and interrupt with traces. Ideal BP's solution is more graceful.

I share the same view. Relying on static traces may present scalability issues and is unable to simulate gem5’s behavior when operating on mispredicted paths, as well as the exceptional behaviors mentioned earlier.

Therefore, it is necessary to dynamically obtain accurate instruction information at runtime from simulators such as NEMU, referred to as the "ideal model." The implementation of the "ideal model" should be entirely guided by gem5, ensuring complete state synchronization with gem5. This means that even when gem5 is operating on a mispredicted instruction path, the ideal model must consistently provide correct runtime information for instruction execution.

This approach involves extensive state maintenance between simulators, and memory allocation and copying may introduce significant overhead. However, setting these challenges aside for the time being, my immediate goal is to develop a simple demo.

[zybzzz]

The design of the “ideal model” has been completed. In my own tests, it has already passed most of them, and testing on the server is currently underway. This ideal model is a five-stage finite-state machine implemented with NEMU. By using NEMU, it can obtain instruction results in advance. When gem5 fetches instructions during its fetch stage, the ideal model can return the correct execution results of those instructions to gem5, along with memory address information, etc. Additionally, the ideal model can adapt to exceptions that occur during gem5’s runtime.

At present, the ideal model supports the following:

• Providing 100% accurate value prediction for simple addition instructions (for exploring a Stride Value Predictor)
• Providing 100% accurate value prediction for scalar load instructions (for exploring a Load Value Predictor)

Currently, the ideal model only supports single-core operation, and only the most basic checkpoints. (Extensions like V/H are not yet supported.)

Because the ideal model’s development is based on a version that’s about 20 commits behind the current upstream, I think the best way to merge into upstream is to adapt the ideal model to the latest commit in upstream and then, at an appropriate time, cherry-pick my commits into upstream. That seems to me to be the best solution.

Any ideas?

[tastynoob]

Thanks for your contribution, you can try to rebase onto xs-dev, then push.