TournamentBP: Fix some bugs with table sizes and counters

Information
Submitter:	Erik Tomusk
Repository:	gem5
Branch:	default
Bugs:
Depends On:
Reviewers
Groups:	Default
People:

Description

Changeset 9394:edeba77c9f2f
---------------------------
TournamentBP: Fix some bugs with table sizes and counters
globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
globalHistoryBits controls how much history is kept, global and choice
predictor sizes control how much of that history is used when accessing
predictor tables. This way, global and choice predictors can actually be
different sizes, and it is no longer possible to walk off the predictor arrays
and cause a seg fault.

There are now individual thresholds for choice, global, and local saturating
counters, so that taken/not taken decisions are correct even when the
predictors' counters' sizes are different.

The interface for localPredictorSize has been removed from TournamentBP because
the value can be calculated from localHistoryBits.

Testing Done

Works with ARM SE quick regression (except for dram target, which fails
with and without this patch).

ARM SE long regressions all pass when version 6 of this patch is
applied onto changeset 9385.

Issue Summary

Description	From	Last Updated	Status
it would be great if you could remove it then	Ali Saidi	Nov. 6, 2012, 8:12 p.m.	Open
should this be the historyRegisterMask? Couldn't this be larger than the globalHistory was specified? This doesn't appear to do what ...	Ali Saidi	Nov. 6, 2012, 8:13 p.m.	Resolved
you created the globalHistoryMask but you're not using it here?	Ali Saidi	Nov. 6, 2012, 8:13 p.m.	Resolved
a temporary variable would be very helpful here	Ali Saidi	Nov. 6, 2012, 7:41 p.m.	Resolved
it would be great to use a temporary variable here and make this much more readble	Ali Saidi	Nov. 6, 2012, 7:41 p.m.	Resolved
could you switch these to use mask() instead af creating the mask yourself? It just makes it a bit clearer ...	Ali Saidi	Nov. 6, 2012, 7:39 p.m.	Resolved
I think something like globalHistory &= (historyRegisterMask & ~ULL(1)) would be clearer that you're clearing the lowest bit. With a ...	Ali Saidi	Nov. 6, 2012, 7:39 p.m.	Resolved
shouldn't need ()	Ali Saidi	Nov. 6, 2012, 7:40 p.m.	Resolved
This definitely changes behavior, but I think it's a correct change to make. The original should have been (1 << ...	Erik Tomusk	Nov. 6, 2012, 7:44 p.m.	Open
Is this clearing the LSB? If so perhaps unify this and others to be & ~ULL(1) instead?	Andreas Hansson	Nov. 9, 2012, 11:18 p.m.	Open
clang static analyzer rightfully points out that this is undefined as the 1 is not typed (according to the standard) ...	Andreas Hansson	Nov. 11, 2012, 9:19 p.m.	Resolved

Description:

~		Changeset 9355:eb19f07b2afc
	~	Changeset 9356:55cf0b4cddc8

~		TournamentBP: Fix some bugs with table sizes and counters
	~	TournamentBP: Fix some bugs with table sizes and counters
-		globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
-		globalHistoryBits controls how much history is kept, global and choice
-		predictor sizes control how much of that history is used when accessing
-		predictor tables. This way, global and choice predictors can actually be
-		different sizes, and it is no longer possible to walk off the predictor arrays
-		and cause a seg fault.
-
-		There are now individual thresholds for choice, global, and local saturating
-		counters, so that taken/not taken decisions are correct even when the
-		predictors' counters' sizes are different.

Diff:

Revision 2 (+71 -24)

Show changes

	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

Thanks for working on this Erik. We very much appreciate your contribution.

I've got some questions below. Additionally, the quick regressions test very little functionality in the branch predictor. I'd be curious to see how the long regeressions turn out with your changes. There are a couple of places that don't quite seem right to me as far as differentiating between taken and not taken branches.

Thanks,
Ali

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)

Am I missing something, or can I not run the long regressions without access to the binaries?

Other comments below.

-Erik

src/cpu/pred/tournament.cc (Diff revision 2)

it would be great if you could remove it then

Show all issues

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)

I can rip one of them out. Is there any preference as to which one?

Erik Tomusk Oct. 30, 2012, 1:37 a.m. (Oct. 30, 2012, 1:37 a.m.)

I removed localPredictorSize because I think a user would be more interested in defining how many bits of history to keep rather than how many entries should be in the counter table. The 2bit_local predictor still uses a localPredictorSize value, so I'm not sure how best to remove it from the configuration when the tournament predictor is used.

src/cpu/pred/tournament.cc (Diff revision 2)

should this be the historyRegisterMask? Couldn't this be larger than the globalHistory was specified? 

This doesn't appear to do what the previous implementation did which was signify that the branch was taken (by oring in a 1 in the lsb). 

Both the taken and not taken versions are the same which doesn't seem correct.

Show all issues

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)

I've changed the meaning of globalHistory slightly from being "history used by the global predictor" to "history stored in the global history register." Both the choice and global predictor use the global history register, so the amount of history in the register shouldn't just be controlled by the global predictor. The historyRegisterMask is based on globalHistoryBits as defined by the user, regardless of how many bits are actually used in the predictors.

The taken/not taken OR is still there (on the previous line).

src/cpu/pred/tournament.cc (Diff revision 2)

you created the globalHistoryMask but you're not using it here?

Show all issues

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)

globalHistoryMask is used in update() and lookup() below where it truncates globalHistory to the number of bits required by the global history table

src/cpu/pred/tournament.cc (Diff revision 2)

a temporary variable would be very helpful here

Show all issues

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)

Good idea. I'll roll that in with removing one of the redundant variables.

src/cpu/pred/tournament.cc (Diff revision 2)

it would be great to use a temporary variable here and make this much more readble

Show all issues

Erik Tomusk Oct. 29, 2012, 3:30 a.m. (Oct. 29, 2012, 3:30 a.m.)
```
Ditto
```

Description:

~		Changeset 9356:55cf0b4cddc8
	~	Changeset 9356:a2d5d47de2bf

~		TournamentBP: Fix some bugs with table sizes and counters
	~	TournamentBP: Fix some bugs with table sizes and counters
	+	globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
	+	globalHistoryBits controls how much history is kept, global and choice
	+	predictor sizes control how much of that history is used when accessing
	+	predictor tables. This way, global and choice predictors can actually be
	+	different sizes, and it is no longer possible to walk off the predictor arrays
	+	and cause a seg fault.
	+
	+	There are now individual thresholds for choice, global, and local saturating
	+	counters, so that taken/not taken decisions are correct even when the
	+	predictors' counters' sizes are different.
	+
	+	The interface for localPredictorSize has been removed from TournamentBP because
	+	the value can be calculated from localHistoryBits.

Diff:

Revision 3 (+69 -40)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

Hi Erik,

Could you rebase this on top of the patch I committed today? 

Thanks,
Ali

Erik Tomusk Nov. 5, 2012, 8:13 p.m. (Nov. 5, 2012, 8:13 p.m.)
```
Done

-Erik
```

Description:

~		Changeset 9356:a2d5d47de2bf
	~	Changeset 9387:38c52462af41

		TournamentBP: Fix some bugs with table sizes and counters
		globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
		globalHistoryBits controls how much history is kept, global and choice
		predictor sizes control how much of that history is used when accessing
		predictor tables. This way, global and choice predictors can actually be
		different sizes, and it is no longer possible to walk off the predictor arrays
		and cause a seg fault.

		There are now individual thresholds for choice, global, and local saturating
		counters, so that taken/not taken decisions are correct even when the
		predictors' counters' sizes are different.

		The interface for localPredictorSize has been removed from TournamentBP because
		the value can be calculated from localHistoryBits.

Diff:

Revision 4 (+69 -40)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

Diff:

Revision 5 (+69 -40)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

I'm curious about the testing statement. No regressions should be failing.

Erik Tomusk Nov. 5, 2012, 8:12 p.m. (Nov. 5, 2012, 8:12 p.m.)

The tgen-simple-dram regression is failing for me even on a clean gem5 and
has been for a while. It goes through all my RAM (4GB), a good bit of swap
space, and then just hangs.

Andreas Hansson Nov. 5, 2012, 8:53 p.m. (Nov. 5, 2012, 8:53 p.m.)

Hmm, how odd. It works fine on zizzer and my local machines (RHE5 and Ubuntu 10.04). What configuration are you running? Any chance you could give it a go with valgrind?

Erik Tomusk Nov. 5, 2012, 9:53 p.m. (Nov. 5, 2012, 9:53 p.m.)

I'm on Scientific Linux 6.3 (so effectively RedHat). Kernel version 2.6.32-279 on x86-64.

Unfortunately I don't think I have time to start digging into the dram test. My valgrind-fu is non-existent and I've got a list of more pressing things that I need to look at.

Andreas Hansson Nov. 7, 2012, 8:33 a.m. (Nov. 7, 2012, 8:33 a.m.)
```
Found the problem. Will have a patch on the board shortly.
```

Change Summary:

Rebase

Testing Done:

		Works with ARM SE quick regression (except for dram target, which fails
		with and without this patch).
	+
	+	ARM SE long regressions all pass when this patch is applied onto
	+	changeset 9354.

Thanks Erik

This seems like a huge improvement. If you could fix up the couple of issue that would be great and we can get it committed.

src/cpu/pred/tournament.cc (Diff revision 5)

could you switch these to use mask() instead af creating the mask yourself? It just makes it a bit clearer about what is going on.

src/base/bitfields.hh

Show all issues

Erik Tomusk Nov. 6, 2012, 3:46 a.m. (Nov. 6, 2012, 3:46 a.m.)

How should bitfields.hh be included in the build process? It's not obvious to me how SCons finds headers.

Ali Saidi Nov. 6, 2012, 8:12 a.m. (Nov. 6, 2012, 8:12 a.m.)

you should be able to include it with:
#include "base/bitfields.hh"

Erik Tomusk Nov. 6, 2012, 7:40 p.m. (Nov. 6, 2012, 7:40 p.m.)
```
It was just a typo.
```

src/cpu/pred/tournament.cc (Diff revision 5)

I think something like
globalHistory &= (historyRegisterMask & ~ULL(1)) would be clearer that you're clearing the lowest bit. With a subtract it's not completely clear to me

Show all issues

src/cpu/pred/tournament.cc (Diff revision 5)

shouldn't need ()

Show all issues

Description:

~		Changeset 9387:38c52462af41
	~	Changeset 9387:942ab8031852

		TournamentBP: Fix some bugs with table sizes and counters
		globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
		globalHistoryBits controls how much history is kept, global and choice
		predictor sizes control how much of that history is used when accessing
		predictor tables. This way, global and choice predictors can actually be
		different sizes, and it is no longer possible to walk off the predictor arrays
		and cause a seg fault.

		There are now individual thresholds for choice, global, and local saturating
		counters, so that taken/not taken decisions are correct even when the
		predictors' counters' sizes are different.

		The interface for localPredictorSize has been removed from TournamentBP because
		the value can be calculated from localHistoryBits.

Diff:

Revision 6 (+76 -46)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

src/cpu/pred/tournament.cc (Diff revision 6)

This definitely changes behavior, but I think it's a correct change to make. The original should have been (1 << floorPow2(localPredictorSize)) - 1.

Show all issues

Testing Done:

		Works with ARM SE quick regression (except for dram target, which fails
		with and without this patch).

~		ARM SE long regressions all pass when this patch is applied onto
~		changeset 9354.
	~	ARM SE long regressions all pass when version 6 of this patch is
	~	applied onto changeset 9385.

Ship It!

src/cpu/pred/tournament.cc (Diff revision 6)

Is this clearing the LSB? If so perhaps unify this and others to be & ~ULL(1) instead?

Show all issues

src/cpu/pred/tournament.cc (Diff revision 6)

clang static analyzer rightfully points out that this is undefined as the 1 is not typed (according to the standard)

ULL(1) instead of 1 will fix the warning

Not sure any compiler would ever not do this...but might as well.

Show all issues

Description:

~		Changeset 9387:942ab8031852
	~	Changeset 9388:1175213b3f61

		TournamentBP: Fix some bugs with table sizes and counters
		globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
		globalHistoryBits controls how much history is kept, global and choice
		predictor sizes control how much of that history is used when accessing
		predictor tables. This way, global and choice predictors can actually be
		different sizes, and it is no longer possible to walk off the predictor arrays
		and cause a seg fault.

		There are now individual thresholds for choice, global, and local saturating
		counters, so that taken/not taken decisions are correct even when the
		predictors' counters' sizes are different.

		The interface for localPredictorSize has been removed from TournamentBP because
		the value can be calculated from localHistoryBits.

Diff:

Revision 7 (+84 -59)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

Ship It!

Description:

~		Changeset 9388:1175213b3f61
	~	Changeset 9394:edeba77c9f2f

		TournamentBP: Fix some bugs with table sizes and counters
		globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
		globalHistoryBits controls how much history is kept, global and choice
		predictor sizes control how much of that history is used when accessing
		predictor tables. This way, global and choice predictors can actually be
		different sizes, and it is no longer possible to walk off the predictor arrays
		and cause a seg fault.

		There are now individual thresholds for choice, global, and local saturating
		counters, so that taken/not taken decisions are correct even when the
		predictors' counters' sizes are different.

		The interface for localPredictorSize has been removed from TournamentBP because
		the value can be calculated from localHistoryBits.

Diff:

Revision 8 (+85 -60)

Show changes

	configs/common/O3_ARM_v7a.py
	src/cpu/inorder/resources/bpred_unit.cc
	src/cpu/o3/bpred_unit_impl.hh
	src/cpu/pred/tournament.hh
	src/cpu/pred/tournament.cc

You have a pending review.

Review Board 2.0.15

This change has been marked as submitted.

Screenshots

Files

Issue Summary

Description:

Changeset 9355:eb19f07b2afc

Changeset 9356:55cf0b4cddc8

Diff:

Description:

Changeset 9356:55cf0b4cddc8

Changeset 9356:a2d5d47de2bf

Diff:

Description:

Changeset 9356:a2d5d47de2bf

Changeset 9387:38c52462af41

Diff:

Diff:

Change Summary:

Testing Done:

Description:

Changeset 9387:38c52462af41

Changeset 9387:942ab8031852

Diff:

Testing Done:

Description:

Changeset 9387:942ab8031852

Changeset 9388:1175213b3f61

Diff:

Description:

Changeset 9388:1175213b3f61

Changeset 9394:edeba77c9f2f

Diff:

Status: Closed (submitted)