ruby: call setMRU from L1 controllers, not from sequencer

Information
Submitter:	Nilay Vaish
Repository:	gem5
Branch:	default
Bugs:
Depends On:
Reviewers
Groups:	Default
People:

Description

Changeset 11002:86776d8b9a7d
---------------------------
ruby: call setMRU from L1 controllers, not from sequencer
Currently the sequencer calls the function setMRU that updates the replacement
policy structures with the first level caches.  While functionally this is
correct, the problem is that this requires calling findTagInSet() which is an
expensive function.  This patch removes the calls to setMRU from the sequencer.
All controllers should now update the replacement policy on their own.

The set and the way index for a given cache entry can be found within the
AbstractCacheEntry structure. Use these indicies to update the replacement
policy structures.

Testing Done

Issue Summary

Description	From	Last Updated	Status
Can you consistently capitalize 'MRU' in these?	Joel Hestness	Aug. 1, 2015, 11:28 a.m.	Resolved
It would be helpful if these names were a little more verbose. Perhaps sm_setBothCacheMRU, uic_setICacheMRU and udc_setDCacheMRU? Maybe even use ...	Joel Hestness	Aug. 1, 2015, 11:31 a.m.	Resolved
In this file, it appears that sm_setMruCache is only ever called from before x_external_load_hit and xx_external_store_hit. Can we just move ...	Joel Hestness	Aug. 1, 2015, 11:32 a.m.	Resolved
Could you please add a warn_once() here that states "Replacement policy updates recently became the responsibility of SLICC state machines. ...	Joel Hestness	Aug. 14, 2015, 5:52 p.m.	Resolved
Can m_instCache_ptr be removed now? Doesn't look like it's being used elsewhere.	Joel Hestness	Aug. 14, 2015, 5:53 p.m.	Resolved

I'm still pretty ambivalent about this change. There are now 4 potential ways to update MRU: (1) direct call from an action to a cache's setMRU, (2)/(3) calling an action from a transition that updates a specific cache's MRU, and (4) calling an action from a transition that updates the MRU of all caches. This seems quite fragile and could result in all kinds of very difficult-to-debug performance problems.

I feel that we should modify some more with the aim of keeping replacement policy updates within actions that call hit callbacks. This might mean adding actions that are specific to I- vs. D-caches, but it would limit the number of calls to CacheMemory::setMRU() as well as the number of potentially sneaky performance bugs.

Nilay Vaish Aug. 1, 2015, 11:41 a.m. (Aug. 1, 2015, 11:41 a.m.)

Joel, the same problem can happen with split callback functions.
You may make updates to one but not to the other. I think we have
to live with these multiple ways.

Joel Hestness Aug. 1, 2015, 3:46 p.m. (Aug. 1, 2015, 3:46 p.m.)

The difference between this new replacement policy functionality and the callbacks is that the callbacks have been around forever. In fact, the last time that a callback line of code changed was revision 9773 (June 2013). By contrast, given the amount of code that this patch touches, these replacement policy functions are likely to be shifted around and adjusted for a while. For example, if this patch doesn't perfectly match the sequencer replacement policy updates, there may be performance differences that only show up for users when trying to replicate prior tests with one of the gem5 protocols, and fixes may be in order.

Further, everyone that pulls this patch into their repo will have to update their protocol files to properly call cache setMRU before their protocols will produce sensible performance results. You may have been diligent and correctly applied this change to all existing protocols, but other people's protocols may be much trickier to update. We can at least try to provide concise guiding examples in mainline protocols.

Overall, I expect that replacement policy updates can eventually be as stable as the callbacks, but they won't be for a while. A solid start would be to limit the number of places where replacement policy needs to be updated.

Jason Lowe-Power Aug. 3, 2015, 8:29 a.m. (Aug. 3, 2015, 8:29 a.m.)

I agree with Joel that this may cause some difficult to track down performance bugs. For instance, if someone has a protocol outside of the mainline, they may not notice this patch and all of the L1 entries will not have MRU set!

Is the only purpose of this patch to increase the performance of Ruby? Can you quantify the performance difference it makes to not call findTagInSet() in the sequencer?

If the only point is to speed up Ruby IMO, it would be a better option to optimize findTagInSet.

src/mem/protocol/MESI_Three_Level-L0cache.sm (Diff revision 1)

Can you consistently capitalize 'MRU' in these?

Show all issues

src/mem/protocol/MESI_Three_Level-L0cache.sm (Diff revision 1)

It would be helpful if these names were a little more verbose. Perhaps sm_setBothCacheMRU, uic_setICacheMRU and udc_setDCacheMRU? Maybe even use more consistent action ID tags?

This comment applies to all modified protocols.

Show all issues

src/mem/protocol/MOESI_CMP_token-L1cache.sm (Diff revision 1)

In this file, it appears that sm_setMruCache is only ever called from before x_external_load_hit and xx_external_store_hit. Can we just move the MRU updates into those actions instead?

Show all issues

Nilay Vaish Aug. 1, 2015, 11:41 a.m. (Aug. 1, 2015, 11:41 a.m.)
```
We can, but I want to keep those two 'actions' separate.
```

Description:

~		Changeset 10937:8903e39b8b12
	~	Changeset 11001:d9b0c6ae77b1

		ruby: call setMRU from L1 controllers, not from sequencer
		Currently the sequencer calls the function setMRU that updates the replacement
		policy structures with the first level caches. While functionally this is
		correct, the problem is that this requires calling findTagInSet() which is an
		expensive function. This patch removes the calls to setMRU from the sequencer.
		All controllers should now update the replacement policy on their own.

		The set and the way index for a given cache entry can be found within the
		AbstractCacheEntry structure. Use these indicies to update the replacement
		policy structures.

Diff:

Revision 2 (+154 -8)

Show changes

	src/mem/protocol/MESI_Three_Level-L0cache.sm
	src/mem/protocol/MESI_Two_Level-L1cache.sm
	src/mem/protocol/MI_example-cache.sm
	src/mem/protocol/MOESI_CMP_directory-L1cache.sm
	src/mem/protocol/MOESI_CMP_token-L1cache.sm
	src/mem/protocol/MOESI_hammer-cache.sm
	src/mem/protocol/RubySlicc_Types.sm
	src/mem/ruby/structures/CacheMemory.hh
	2 more

Description:

~		Changeset 11001:d9b0c6ae77b1
	~	Changeset 11002:86776d8b9a7d

		ruby: call setMRU from L1 controllers, not from sequencer
		Currently the sequencer calls the function setMRU that updates the replacement
		policy structures with the first level caches. While functionally this is
		correct, the problem is that this requires calling findTagInSet() which is an
		expensive function. This patch removes the calls to setMRU from the sequencer.
		All controllers should now update the replacement policy on their own.

		The set and the way index for a given cache entry can be found within the
		AbstractCacheEntry structure. Use these indicies to update the replacement
		policy structures.

Diff:

Revision 3 (+118 -41)

Show changes

	src/mem/protocol/MESI_Three_Level-L0cache.sm
	src/mem/protocol/MESI_Two_Level-L1cache.sm
	src/mem/protocol/MI_example-cache.sm
	src/mem/protocol/MOESI_CMP_directory-L1cache.sm
	src/mem/protocol/MOESI_CMP_token-L1cache.sm
	src/mem/protocol/MOESI_hammer-cache.sm
	src/mem/protocol/RubySlicc_Types.sm
	src/mem/ruby/structures/CacheMemory.hh
	2 more

Nilay said

It takes about 50ns per call to findTagInSet (on the machine I use). All
those times when the line is found in the first level cache, we would not
those extra calls. Overall, a simulation would be about 2% faster.

I personally don't think that 2% performance is worth the likelyhood that users' protocols will be broken. A change like this one was exactly the kind of thing I talked about in my workshop presentation. This change may cause significant headaches for gem5 users. My personal opinion is that 2% performance isn't worth it.

I think that we should only include this change if most of the community wants to move setMRU into the L1 controllers, instead of being implicit for the L1s, as it is now. If we do decide to move this way, I think we need to broadcast the change loudly. One option is to set the implicit version as deprecated and print warnings if the cache lines are not explicitly setMRU. We could have one version of gem5 stable with the warning, then the next gem5 stable can remove the warning and move to requiring explicit use of setMRU in the L1 controllers.

Also, Nilay, to echo Brad's previous requests, could you please respond to things on reviewboard. Reviewboard is where most people go to see the whole conversation. By responding via email it makes it very difficult for anyone to follow the conversation.

Nilay Vaish Aug. 4, 2015, 7:57 a.m. (Aug. 4, 2015, 7:57 a.m.)

Jason, 2% may seem small, but several such 2%s together lead to a big performance difference.
Which is why ruby loses to classic memory system in terms of simulation speed. Patches on LLSC,
setMRU, shared pointers together give about 5-10% improvement. And then better event handling
gives us about another 15% or more improvement.

As far as broadcasting changes to the community is concerned, I am all for it.
Next time I update the stable branch, I'll patch the sequencer to warn that calls to setMRU would
be dropped when next update takes place.

This is a lot better. Thanks for these changes.

I agree that we need to broadcast this change loudly since it will result in silent performance bugs in non-mainline protocols.

Can you please comment on the testing you did to ensure performance correctness of mainline protocols?

Nilay Vaish Aug. 14, 2015, 5:53 p.m. (Aug. 14, 2015, 5:53 p.m.)
```
Everything has been regression tested.
```

src/mem/ruby/system/Sequencer.cc (Diff revision 3)

Could you please add a warn_once() here that states "Replacement policy updates recently became the responsibility of SLICC state machines. Make sure to setMRU() near callbacks in .sm files!"?

Show all issues

src/mem/ruby/system/Sequencer.cc (Diff revision 3)

Can m_instCache_ptr be removed now? Doesn't look like it's being used elsewhere.

Show all issues

Nilay Vaish Aug. 14, 2015, 5:53 p.m. (Aug. 14, 2015, 5:53 p.m.)
```
Will do so in a separate patch.
```

You have a pending review.

Review Board 2.0.15

This change has been marked as submitted.

Screenshots

Files

Issue Summary

Description:

Changeset 10937:8903e39b8b12

Changeset 11001:d9b0c6ae77b1

Diff:

Description:

Changeset 11001:d9b0c6ae77b1

Changeset 11002:86776d8b9a7d

Diff:

Status: Closed (submitted)