Add unit tests for all BP modes

[pavelkryukov]

BP unit tests cover only few BP modes, according to the CodeCov report.

Using Wiki manual about branch prediction model, TDD manual, and existing tests, you may easily add tests to cover all the BP types.

[pavelkryukov]

Do you have any progress? There are new students and it may be better for them to use that task as a kick-off, while you may proceed with something more advanced.

[YanLogovskiy]

Hi, I'm trying to make progress, but still I spent a lot of of time to deeply understand how simulator implementation works. (It is my mistake, next time I will assign myself only if I approximately know what to do). I'm going to add some test cases in unit_test.cpp to cover all lines in bpentry.h and now I'm anylizing how red lines can be tested. So, I'm trying to finish this issue, but if you consider that it will be better if newcomers fix it, I will do what you suggest. Thanks.

[YanLogovskiy]

How does codecov works? I want to comment some lines in unit_tests.cpp to undertand what tests cover these exact lines. How can I do it?

[YanLogovskiy]

Maybe, I can find a tutorial somewhere. I will look for it now by myself

[pavelkryukov]

CodeCov is a remote tool, it takes data from pull requests. You may open one to make your experiments.

[pavelkryukov]

Alternatively, you may put dummy couts to BPEntry code:

   std::cout << "Running " << __LINE__ << std:;endl;

and check it locally

[YanLogovskiy]

How should I run unit_tests to see how they cover bpentry.h lines? When I run unit-tests in simulator folder I see a lot of dump info and if I am not mistaken, it is all about cache. I run yan@yan-X555LJ:~/mipt-mips/simulator$ ./unit-tests

[pavelkryukov]

Unfortunately, I do not know any good way to do that other than submitting a pull request.

[YanLogovskiy]

I did only an experiment to check if my changes make any difference considering coverage. But codecov showed that there is no difference. My changes are not harmful of course but they are useless as codecov says. So, why did you merge my pull request?

[YanLogovskiy]

An obvious idea is to test the predictor in the situation where target is a smaller value that current PC. As I did in my changes. But maybe I did something wrong in following lines.

    bp->update( BPInterface( PC, true, target));
    CHECK( bp->is_taken(PC) );
    CHECK( bp->get_target(PC) == target);

[pavelkryukov]

Your test looks more what unit test should look like (comparing to the previous ones), as it tests simple functionality. The only thing I would change is to move it closer to the beginning of the fie.

[pavelkryukov]

    bp->update( BPInterface( PC, true, target));
    CHECK( bp->is_taken(PC) );
    CHECK( bp->get_target(PC) == target);

Looks reasonable. "If we see a taken branch, predict it is a taken and predict its target next time"

[pavelkryukov]

Obviously, for static mode, the branch will be predicted as not taken - and that should be asserted in your test case.

[YanLogovskiy]

Do you mean "always taken"?

[pavelkryukov]

Nope, always taken is always taken

[pavelkryukov]

Oh, we do not have "always not taken" mode....

[pavelkryukov]

Yan, I think you'd better to catch @olegladin. His duty is to help students with their assignments, and he lives in Dolgoprudny, so you can spent some time to understand what happens.

[YanLogovskiy]

Ok.

[YanLogovskiy]

I added always not taken to static predictor

[pavelkryukov]

https://codecov.io/gh/MIPT-ILab/mipt-mips/src/cc7398da9f6a66d8f9a0655fc9fab4876cd4f51e/simulator/modules/fetch/bpu/bpentry.h

Now we can analyze report to see what is not covered yet:

1. Backward-only branch prediction
2. One bit branch prediction in case of target change (was predicted to one target, now goes to another)
3. Adaptive prediction mode

[YanLogovskiy]

I think that we can test this case in a such simple way.

1. after first checks we change the target.
2. update prediction one more time.
3. check if predicted target is right.

TEST_CASE( "One bit predictor")
 58 {
 59     auto bp = BaseBP::create_bp( "saturating_one_bit", 128, 16);
 60 
 61     Addr PC = 28;
 62     Addr target = 12;
 63 
 64     bp->update( BPInterface( PC, true, target));
 65     CHECK( bp->is_taken(PC) );
 66     CHECK( bp->get_target(PC) == target);
 67  
 68     target = 16;
 69     bp->update( BPInterface( PC, true, target));
 70     CHECK( bp->get_target(PC) == target);
 71 }   

but unfortunately last check fails with 32 == 16 So, it means that branch wasn't taken, why?

[pavelkryukov]

That's how that prediction mode is implemented: if branch target changes, it resets the prediction completely:

https://github.com/MIPT-ILab/mipt-mips/blob/93aa34a8413e871e12d4f3e8babfcd0321516175/simulator/modules/fetch/bpu/bpentry.h#L80

For me, it looks like a bug — we should reset target, but not the bit prediction.

[pavelkryukov]

By the way, the 2-bit prediction has no similar bug.

[pavelkryukov]

https://codecov.io/gh/MIPT-ILab/mipt-mips/src/96818454e60832628b41f21c510e37e333028a3d/simulator/modules/fetch/bpu/bpentry.h

Now we have only adaptive predictor left. I advise to start with copy-pasting the 'advanced' tests for saturating two-bit prediction.

[YanLogovskiy]

Unfortunately, it doesn't work. Even one simple test fails

TEST_CASE( "Adaptive two bit prediction")
161 {
162     auto bp = BaseBP::create_bp( "adaptive_two_levels", 128, 16);
163 
164     Addr PC = 12;
165     Addr target = 28;
166 
167     // Learn
168     bp->update( BPInterface( PC, true, target));
169     CHECK( bp->is_taken(PC) );
170     CHECK( bp->get_target(PC) == target);
171 }

Error dump

/home/yan/mipt-mips/simulator/modules/fetch/bpu/t/unit_test.cpp:169: FAILED:
CHECK( bp->is_taken(PC) )
with expansion:
  false

/home/yan/mipt-mips/simulator/modules/fetch/bpu/t/unit_test.cpp:170: FAILED:
  CHECK( bp->get_target(PC) == target )
with expansion:
  16 == 28

I don't really understand why it happens, maybe we should look deeply into the specific of adaptive predictor. But it seems to me that more advanced predictors must cope with the simplest test cases.

[pavelkryukov]

But it seems to me that more advanced predictors must cope with the simplest test cases.

No, it's not true. More complicated predictors (and adaptive prediction is complicated) use more knowledge about history. The fact that a single branch was taken once is not enough for that predictor to assume it will be taken next time.

I advise you to think about our implementation as a 'black box' and investigate its behavior outside. The description describes an example of the behavior. You formalize it to unit test, for instance.

[pavelkryukov]

https://codecov.io/gh/MIPT-ILab/mipt-mips/src/a0b1f8db6c1d9a4710a7f5750216ba1e5c106708/simulator/modules/fetch/bpu/bpentry.h

So now we do not cover only the corner case of target mismatch. Please create a test case to cover it and finish your great job!

[YanLogovskiy]

I added test case.

TEST_CASE( "Adaptive two bit prediction in case of changed target")
203 {
204     auto bp = BaseBP::create_bp( "adaptive_two_levels", 128, 16);
205 
206     Addr PC = 28;
207     Addr target = 12;
208 
209     // Learn in sequence 001001001
210     bp->update( BPInterface( PC, false, target));
211     bp->update( BPInterface( PC, false, target));
212     bp->update( BPInterface( PC, true, target));
213 
214     bp->update( BPInterface( PC, false, target));
215     bp->update( BPInterface( PC, false, target));
216     bp->update( BPInterface( PC, true, target));
217     
218     bp->update( BPInterface( PC, false, target));
219     bp->update( BPInterface( PC, false, target));
220     bp->update( BPInterface( PC, true, target));
221 
222     //change the target
223     target = 16;
224     bp->update( BPInterface( PC, false, target));
225     bp->update( BPInterface( PC, false, target));
226     CHECK( bp->is_taken(PC) );
227     CHECK( bp->get_target(PC) == target);
228 }   

CHECK( bp->istaken(PC)) is not essential here, but I put it to make sure that branch is taken. But at the same time target is not updated, so I have the last check failed.

I don't know why this happens.

[pavelkryukov]

What does bp->get_target(PC) return?

[YanLogovskiy]

12, So, it wasn't updated. I solved it. I added all sequence 001001001 to update the target. I don't completely understand, why 00 was't enough to do it, but now all tests pass.

[pavelkryukov]

224     bp->update( BPInterface( PC, false, target));
225     bp->update( BPInterface( PC, false, target));

If branch is not taken, then we do not care about its target (the next instruction is PC+4)

[YanLogovskiy]

But after such a sequence predictor must assume, that next time the branch will be taken

[YanLogovskiy]

So, the first check CHECK( bp->istaken(PC)) passes

[YanLogovskiy]

I added all this lines

        bp->update( BPInterface( PC, false, target));
211     bp->update( BPInterface( PC, false, target));
212     bp->update( BPInterface( PC, true, target));
213 
214     bp->update( BPInterface( PC, false, target));
215     bp->update( BPInterface( PC, false, target));
216     bp->update( BPInterface( PC, true, target));
217     
218     bp->update( BPInterface( PC, false, target));
219     bp->update( BPInterface( PC, false, target));
220     bp->update( BPInterface( PC, true, target));

And all tests pass. I will do a pull request in 5 minutes.

[YanLogovskiy]

224     bp->update( BPInterface( PC, false, target));
225     bp->update( BPInterface( PC, false, target));

If branch is not taken, then we do not care about its target (the next instruction is PC+4)

I understand, so, predictor sees that branch is not taken and doesn't care about target and, therefore, does not update it. Thank you

[pavelkryukov]

Thank you for your contribution! You may use your expertise in branch prediction for one of these issues

The most straightforward are #613 and #91, the most challenging are #36 (totally creative stuff, I do not even sure I understand what to do) and #614 (I barely understand)