mem: refactor LRU cache tags and add random replacment tags

Information
Submitter:	Tony Gutierrez
Repository:	gem5
Branch:	default
Bugs:
Depends On:
Reviewers
Groups:	Default
People:

Description

this patch implements a new tags class that uses a random replacement policy.
these tags prefer to evict invalid blocks first, if none are available a
replacement candidate is chosen at random.

this patch factors out the common code in the LRU class and creates a new
abstract class: the BaseSetAssoc class. any set associative tag class must
implement the functionality related to the actual replacement policy in the
following methods:

accessBlock()
findVictim()
insertBlock()
invalidate()

Testing Done

Regressions pass

Issue Summary

Description	From	Last Updated	Status
should this be const?	Andreas Hansson	June 24, 2014, 4:24 p.m.	Resolved
should this not be using the mersenne twister rather? random_mt.random<int>(...)	Andreas Hansson	June 24, 2014, 4:22 p.m.	Resolved
2003-2005,2014?	Ali Saidi	July 22, 2014, 7:34 a.m.	Resolved
why not unsigned?	Ali Saidi	July 22, 2014, 7:24 a.m.	Open
It seems sensible to make it an unsigned param and only check for 0.	Andreas Hansson	July 22, 2014, 9:26 a.m.	Open
Same here, instead of an Int param it should probably be Unsigned.	Andreas Hansson	July 22, 2014, 9:26 a.m.	Open
Is Cycles, so it can never be < 0	Andreas Hansson	July 22, 2014, 9:26 a.m.	Open
A bit pedantic perhaps, but (slightly stupid) static code analysers get unhappy with the member variables not being initialised in ...	Andreas Hansson	July 22, 2014, 9:26 a.m.	Open

Description:

		Changeset 10084:209fc6fadbe5

		mem: add random replacement cache tags

		this patch implements a new tags class that uses a random replacement policy.
		these tags prefer to evict invalid blocks first, if none are available a
		replacement candidate is chosen at random.
	+
	+	this patch reuses the LRU tag code and simply modifies the following methods:
	+
	+	accessBlock()
	+	findVictim()
	+	insertBlock()
	+	invalidate()

src/mem/cache/tags/random_repl.cc (Diff revision 1)

should this be const?

Show all issues

src/mem/cache/tags/random_repl.cc (Diff revision 1)

should this not be using the mersenne twister rather? random_mt.random<int>(...)

Show all issues

Summary:

-	mem: add random replacement cache tags
+	mem: re-factor LRU code and add random replacement cache tags

Description:

~		Changeset 10084:209fc6fadbe5
	~	Changeset 10244:7f45ea64d8e6

~		mem: add random replacement cache tags
	~	mem: re-factor LRU code and add random replacement cache tags

		this patch implements a new tags class that uses a random replacement policy.
		these tags prefer to evict invalid blocks first, if none are available a
		replacement candidate is chosen at random.

~		this patch reuses the LRU tag code and simply modifies the following methods:
	~	this patch factors out the common code in the LRU class and creates a new
	+	abstract class: the BaseLRU class. any LRU tag or derivative of LRU must
	+	implement the methods related to the actual replacement policy. these are the
	+	following methods, which are pure virtual methods in BaseLRU:

		accessBlock()
		findVictim()
		insertBlock()
		invalidate()

Diff:

Revision 2 (+781 -379)

Show changes

	src/mem/cache/base.cc
	src/mem/cache/cache.cc
	src/mem/cache/tags/SConscript
	src/mem/cache/tags/Tags.py
	src/mem/cache/tags/base_lru.hh
	src/mem/cache/tags/base_lru.cc
	src/mem/cache/tags/lru.hh
	src/mem/cache/tags/lru.cc
	2 more

Description:

~		Changeset 10244:7f45ea64d8e6
	~	Changeset 10244:18b48ce610af

		mem: re-factor LRU code and add random replacement cache tags

		this patch implements a new tags class that uses a random replacement policy.
		these tags prefer to evict invalid blocks first, if none are available a
		replacement candidate is chosen at random.

		this patch factors out the common code in the LRU class and creates a new
		abstract class: the BaseLRU class. any LRU tag or derivative of LRU must
		implement the methods related to the actual replacement policy. these are the
		following methods, which are pure virtual methods in BaseLRU:

		accessBlock()
		findVictim()
		insertBlock()
		invalidate()

Diff:

Revision 3 (+782 -381)

Show changes

	src/mem/cache/base.cc
	src/mem/cache/cache.cc
	src/mem/cache/tags/SConscript
	src/mem/cache/tags/Tags.py
	src/mem/cache/tags/base_lru.hh
	src/mem/cache/tags/base_lru.cc
	src/mem/cache/tags/lru.hh
	src/mem/cache/tags/lru.cc
	2 more

Description:

~		Changeset 10244:18b48ce610af
	~	Changeset 10243:8f4099f6b9a2

		mem: re-factor LRU code and add random replacement cache tags

		this patch implements a new tags class that uses a random replacement policy.
		these tags prefer to evict invalid blocks first, if none are available a
		replacement candidate is chosen at random.

		this patch factors out the common code in the LRU class and creates a new
		abstract class: the BaseLRU class. any LRU tag or derivative of LRU must
		implement the methods related to the actual replacement policy. these are the
		following methods, which are pure virtual methods in BaseLRU:

		accessBlock()
		findVictim()
		insertBlock()
		invalidate()

Diff:

Revision 4 (+782 -381)

Show changes

	src/mem/cache/base.cc
	src/mem/cache/cache.cc
	src/mem/cache/tags/SConscript
	src/mem/cache/tags/Tags.py
	src/mem/cache/tags/base_lru.hh
	src/mem/cache/tags/base_lru.cc
	src/mem/cache/tags/lru.hh
	src/mem/cache/tags/lru.cc
	2 more

Testing Done:

Regressions pass

Overall, I think this patch looks good and the refactoring is a well-needed change to the way we implement replacement policies.

At a high level, I'd really appreciate it if you could split this patch into two patches so the refactoring becomes its own commit. That makes things like bisection much cleaner in the future.

I also found the naming of the different classes a bit confusing. I would suggest that you rename BaseLRU -> BaseSetAssoc or something similar. After all, the common stuff that goes into this base class isn't really LRU specific. I also get a bit confused by the PseudoLRU class. When I think of pseudo-LRU, I generally think of things like tree-based LRU or the algorithm used in Nehalem. I'd suggest that you rename it to something with random in the name instead.

Ali Saidi July 15, 2014, 11:44 a.m. (July 15, 2014, 11:44 a.m.)

I think the benefit of splitting it vs the effort to do so is too great. However the naming change would be useful. Thanks a lot for the patch Tony.

Hi Tony,

Sorry for taking so long to get around to this.  I think your patch is definitely a step in the right direction.  My main concern is that it doesn't go far enough, in the sense that there's still a lot of duplication between the LRU and PseudoLRU classes that could be factored out into the common base class.  I'm just eyeballing the diff here, so I might be missing something, but the two versions of insertBlock() and invalidate() look the same to me, and accessBlock() looks the same except for the added moveToHead() line in LRU (and the associated DPRINTF).

Also, is there a need for all these functions to be virtual?  The way we have the Cache class templated on the tag class, I would think not.  (The whole intent of that templating is to avoid those virtual function calls.)

If you don't want to add an additional virtual function dispatch, you can continue to have the most derived classes implement the interface, but then have them call non-virtual, potentially inlined common methods in the base class that provide the common code; or you can use CRTP to include code from the derived classes in what are syntactically base class methods.  If you don't like those solutions, I'd be willing to consider trading a virtual function dispatch for less code redundancy.  (Others can chime in on where they stand on these tradeoffs.)

Also, it seems like preferentially replacing invalid blocks is orthogonal to the LRU vs. PseudoLRU replacement policy, and it would be nice to make it so.  I'd be OK with breaking backward compatibility by making it universal and putting it in the base class too.

Tony Gutierrez July 21, 2014, 11:46 a.m. (July 21, 2014, 11:46 a.m.)

I got rid of the virtual functions and have consolidated more of the code into the base class. I also changed the names of the base and random classes.

Summary:

-	mem: re-factor LRU code and add random replacement cache tags
+	# Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c

Description:

~		Changeset 10243:8f4099f6b9a2
	~	Changeset 10259:8837fb57db79

~		mem: re-factor LRU code and add random replacement cache tags
	~	Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c

~		this patch implements a new tags class that uses a random replacement policy.
	~	Parent 4fda06352148a39d7c41bd75b19e485ca7102c77
-		these tags prefer to evict invalid blocks first, if none are available a
-		replacement candidate is chosen at random.
-
-		this patch factors out the common code in the LRU class and creates a new
-		abstract class: the BaseLRU class. any LRU tag or derivative of LRU must
-		implement the methods related to the actual replacement policy. these are the
-		following methods, which are pure virtual methods in BaseLRU:
-
-		accessBlock()
-		findVictim()
-		insertBlock()
-		invalidate()

Diff:

Revision 5 (+807 -461)

Show changes

	src/mem/cache/base.cc
	src/mem/cache/cache.cc
	src/mem/cache/tags/SConscript
	src/mem/cache/tags/Tags.py
	src/mem/cache/tags/base_set_assoc.hh
	src/mem/cache/tags/base_set_assoc.cc
	src/mem/cache/tags/lru.hh
	src/mem/cache/tags/lru.cc
	2 more

Summary:

-	# Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c
+	mem: refactor cache tags and add random replacment tags

Summary:

-	mem: refactor cache tags and add random replacment tags
+	mem: refactor LRU cache tags and add random replacment tags

Description:

~		Changeset 10259:8837fb57db79
	~	this patch implements a new tags class that uses a random replacement policy.
	+	these tags prefer to evict invalid blocks first, if none are available a
	+	replacement candidate is chosen at random.

~		Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c
	~	this patch factors out the common code in the LRU class and creates a new
	+	abstract class: the BaseSetAssoc class. any set associative tag class must
	+	implement the functionality related to the actual replacement policy in the
	+	following methods:

~		Parent 4fda06352148a39d7c41bd75b19e485ca7102c77
	~	accessBlock()
	+	findVictim()
	+	insertBlock()
	+	invalidate()

src/mem/cache/tags/lru.hh (Diff revision 5)

2003-2005,2014?

Show all issues

src/mem/cache/tags/lru.cc (Diff revision 5)

why not unsigned?

Show all issues

Tony Gutierrez July 22, 2014, 9:41 a.m. (July 22, 2014, 9:41 a.m.)

I made it unsigned because CacheBlk's set field is an int, as well as the fact that extractSet() returns an int, and I prefer int unless there is a really good reason to use unsigned. I can keep it unsigned if you'd prefer though.

Ali Saidi July 22, 2014, 1:37 p.m. (July 22, 2014, 1:37 p.m.)

Sorry, I should have checked. I assumed that extractSet returned an unsigned as well. I guess i'd prefer that everything return unsigned since i can't think of a good reason that a cache block index would be negative, however this is extremely minor, so feel free to ignore and just keep them ints.

looks good to me.. two minor issues, I think the copyrights you've updated should be 2003-2005, 2014 and i'm not sure why you changed from unsigned to int for extract set?

otherwise ship it

src/mem/cache/tags/base_set_assoc.cc (Diff revision 5)

It seems sensible to make it an unsigned param and only check for 0.

Show all issues

src/mem/cache/tags/base_set_assoc.cc (Diff revision 5)

Same here, instead of an Int param it should probably be Unsigned.

Show all issues

src/mem/cache/tags/base_set_assoc.cc (Diff revision 5)

Is Cycles, so it can never be < 0

Show all issues

src/mem/cache/tags/base_set_assoc.cc (Diff revision 5)

A bit pedantic perhaps, but (slightly stupid) static code analysers get unhappy with the member variables not being initialised in the initialisation list. Could we add a default value, or move the assignment up to the initialisation list?

Show all issues

Some style-related suggestions, for the rest it looks great. Feel free to punt this to a later patch.

Tony Gutierrez July 22, 2014, 9:39 a.m. (July 22, 2014, 9:39 a.m.)

I'd prefer to put it in a later patch, this is all pre-existing code.

Looks good!  Thanks for the changes.

You have a pending review.

Review Board 2.0.15

This change has been marked as submitted.

Screenshots

Files

Issue Summary

Description:

Changeset 10084:209fc6fadbe5

Summary:

Description:

Changeset 10084:209fc6fadbe5

Changeset 10244:7f45ea64d8e6

Diff:

Description:

Changeset 10244:7f45ea64d8e6

Changeset 10244:18b48ce610af

Diff:

Description:

Changeset 10244:18b48ce610af

Changeset 10243:8f4099f6b9a2

Diff:

Testing Done:

Summary:

Description:

Changeset 10243:8f4099f6b9a2

Changeset 10259:8837fb57db79

Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c

Parent 4fda06352148a39d7c41bd75b19e485ca7102c77

Diff:

Summary:

Summary:

Description:

Changeset 10259:8837fb57db79

Node ID 8f4099f6b9a204495c2ce540340276eb5d1fbf3c

Parent 4fda06352148a39d7c41bd75b19e485ca7102c77

Status: Closed (submitted)