From 28482880974510a267acfd3f16d793e8c2ab324d Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Sun, 29 Dec 2019 10:14:26 +0100 Subject: [PATCH] mem-cache: Use AssociativeSet in Stride prefetcher Avoid replicating associative set functionality in Stride prefetcher's pc tables. The indexing policy used previously had some peculiarities, so both the extractTag and extractSet have been made virtual so that previous behavior could be kept. Change-Id: I19a86cb3c4b40031fef427d5f7eed9d5c5673a44 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/24603 Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris Tested-by: kokoro --- src/mem/cache/prefetch/Prefetcher.py | 18 ++- src/mem/cache/prefetch/stride.cc | 98 ++++----------- src/mem/cache/prefetch/stride.hh | 116 ++++++++---------- src/mem/cache/tags/indexing_policies/base.hh | 2 +- .../tags/indexing_policies/set_associative.hh | 4 +- 5 files changed, 86 insertions(+), 152 deletions(-) diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py index 51132f9a3..f131ccf77 100644 --- a/src/mem/cache/prefetch/Prefetcher.py +++ b/src/mem/cache/prefetch/Prefetcher.py @@ -139,6 +139,11 @@ class QueuedPrefetcher(BasePrefetcher): throttle_control_percentage = Param.Percent(0, "Percentage of requests \ that can be throttled depending on the accuracy of the prefetcher.") +class StridePrefetcherHashedSetAssociative(SetAssociative): + type = 'StridePrefetcherHashedSetAssociative' + cxx_class = 'Prefetcher::StridePrefetcherHashedSetAssociative' + cxx_header = "mem/cache/prefetch/stride.hh" + class StridePrefetcher(QueuedPrefetcher): type = 'StridePrefetcher' cxx_class = 'Prefetcher::Stride' @@ -154,15 +159,18 @@ class StridePrefetcher(QueuedPrefetcher): confidence_threshold = Param.Percent(50, "Prefetch generation confidence threshold") - table_sets = Param.Int(16, "Number of sets in PC lookup table") - table_assoc = Param.Int(4, "Associativity of PC lookup table") use_master_id = Param.Bool(True, "Use master id based history") degree = Param.Int(4, "Number of prefetches to generate") - # Get replacement policy - replacement_policy = Param.BaseReplacementPolicy(RandomRP(), - "Replacement policy") + table_assoc = Param.Int(4, "Associativity of the PC table") + table_entries = Param.MemorySize("64", "Number of entries of the PC table") + table_indexing_policy = Param.BaseIndexingPolicy( + StridePrefetcherHashedSetAssociative(entry_size = 1, + assoc = Parent.table_assoc, size = Parent.table_entries), + "Indexing policy of the PC table") + table_replacement_policy = Param.BaseReplacementPolicy(RandomRP(), + "Replacement policy of the PC table") class TaggedPrefetcher(QueuedPrefetcher): type = 'TaggedPrefetcher' diff --git a/src/mem/cache/prefetch/stride.cc b/src/mem/cache/prefetch/stride.cc index 101adf2d0..36773c6aa 100644 --- a/src/mem/cache/prefetch/stride.cc +++ b/src/mem/cache/prefetch/stride.cc @@ -53,13 +53,14 @@ #include "base/random.hh" #include "base/trace.hh" #include "debug/HWPrefetch.hh" +#include "mem/cache/prefetch/associative_set_impl.hh" #include "mem/cache/replacement_policies/base.hh" #include "params/StridePrefetcher.hh" namespace Prefetcher { Stride::StrideEntry::StrideEntry(const SatCounter& init_confidence) - : ReplaceableEntry(), confidence(init_confidence) + : TaggedEntry(), confidence(init_confidence) { invalidate(); } @@ -67,9 +68,7 @@ Stride::StrideEntry::StrideEntry(const SatCounter& init_confidence) void Stride::StrideEntry::invalidate() { - instAddr = 0; lastAddr = 0; - isSecure = false; stride = 0; confidence.reset(); } @@ -78,13 +77,11 @@ Stride::Stride(const StridePrefetcherParams *p) : Queued(p), initConfidence(p->confidence_counter_bits, p->initial_confidence), threshConf(p->confidence_threshold/100.0), - pcTableAssoc(p->table_assoc), - pcTableSets(p->table_sets), useMasterId(p->use_master_id), degree(p->degree), - replacementPolicy(p->replacement_policy) + pcTableInfo(p->table_assoc, p->table_entries, p->table_indexing_policy, + p->table_replacement_policy) { - assert(isPowerOf2(pcTableSets)); } Stride::PCTable* @@ -104,7 +101,8 @@ Stride::allocateNewContext(int context) { // Create new table auto insertion_result = pcTables.insert(std::make_pair(context, - PCTable(pcTableAssoc, pcTableSets, name(), replacementPolicy, + PCTable(pcTableInfo.assoc, pcTableInfo.numEntries, + pcTableInfo.indexingPolicy, pcTableInfo.replacementPolicy, StrideEntry(initConfidence)))); DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context); @@ -113,28 +111,6 @@ Stride::allocateNewContext(int context) return &(insertion_result.first->second); } -Stride::PCTable::PCTable(int assoc, int sets, const std::string name, - BaseReplacementPolicy* replacementPolicy, StrideEntry init_confidence) - : pcTableSets(sets), _name(name), entries(pcTableSets), - replacementPolicy(replacementPolicy) -{ - for (int set = 0; set < sets; set++) { - entries[set].resize(assoc, init_confidence); - for (int way = 0; way < assoc; way++) { - // Inform the entry its position - entries[set][way].setPosition(set, way); - - // Initialize replacement policy data - entries[set][way].replacementData = - replacementPolicy->instantiateEntry(); - } - } -} - -Stride::PCTable::~PCTable() -{ -} - void Stride::calculatePrefetch(const PrefetchInfo &pfi, std::vector &addresses) @@ -157,6 +133,8 @@ Stride::calculatePrefetch(const PrefetchInfo &pfi, StrideEntry *entry = pcTable->findEntry(pc, is_secure); if (entry != nullptr) { + pcTable->accessEntry(entry); + // Hit in table int new_stride = pf_addr - entry->lastAddr; bool stride_match = (new_stride == entry->stride); @@ -202,66 +180,34 @@ Stride::calculatePrefetch(const PrefetchInfo &pfi, StrideEntry* entry = pcTable->findVictim(pc); - // Invalidate victim - entry->invalidate(); - replacementPolicy->invalidate(entry->replacementData); - // Insert new entry's data - entry->instAddr = pc; entry->lastAddr = pf_addr; - entry->isSecure = is_secure; - replacementPolicy->reset(entry->replacementData); + pcTable->insertEntry(pc, is_secure, entry); } } -inline Addr -Stride::PCTable::pcHash(Addr pc) const +inline uint32_t +StridePrefetcherHashedSetAssociative::extractSet(const Addr pc) const { - Addr hash1 = pc >> 1; - Addr hash2 = hash1 >> floorLog2(pcTableSets); - return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); + const Addr hash1 = pc >> 1; + const Addr hash2 = hash1 >> tagShift; + return (hash1 ^ hash2) & setMask; } -inline Stride::StrideEntry* -Stride::PCTable::findVictim(Addr pc) +Addr +StridePrefetcherHashedSetAssociative::extractTag(const Addr addr) const { - // Rand replacement for now - int set = pcHash(pc); - - // Get possible entries to be victimized - std::vector possible_entries; - for (auto& entry : entries[set]) { - possible_entries.push_back(&entry); - } - - // Choose victim based on replacement policy - StrideEntry* victim = static_cast( - replacementPolicy->getVictim(possible_entries)); - - DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", - victim->getSet(), victim->getWay()); - - return victim; + return addr; } -inline Stride::StrideEntry* -Stride::PCTable::findEntry(Addr pc, bool is_secure) +} // namespace Prefetcher + +Prefetcher::StridePrefetcherHashedSetAssociative* +StridePrefetcherHashedSetAssociativeParams::create() { - int set = pcHash(pc); - for (auto& entry : entries[set]) { - // Search ways for match - if ((entry.instAddr == pc) && (entry.isSecure == is_secure)) { - DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", entry.getSet(), - entry.getWay()); - replacementPolicy->touch(entry.replacementData); - return &entry; - } - } - return nullptr; + return new Prefetcher::StridePrefetcherHashedSetAssociative(this); } -} // namespace Prefetcher - Prefetcher::Stride* StridePrefetcherParams::create() { diff --git a/src/mem/cache/prefetch/stride.hh b/src/mem/cache/prefetch/stride.hh index 090c13ac3..72e335b2d 100644 --- a/src/mem/cache/prefetch/stride.hh +++ b/src/mem/cache/prefetch/stride.hh @@ -53,15 +53,38 @@ #include "base/sat_counter.hh" #include "base/types.hh" +#include "mem/cache/prefetch/associative_set.hh" #include "mem/cache/prefetch/queued.hh" #include "mem/cache/replacement_policies/replaceable_entry.hh" +#include "mem/cache/tags/indexing_policies/set_associative.hh" #include "mem/packet.hh" +#include "params/StridePrefetcherHashedSetAssociative.hh" +class BaseIndexingPolicy; class BaseReplacementPolicy; struct StridePrefetcherParams; namespace Prefetcher { +/** + * Override the default set associative to apply a specific hash function + * when extracting a set. + */ +class StridePrefetcherHashedSetAssociative : public SetAssociative +{ + protected: + uint32_t extractSet(const Addr addr) const override; + Addr extractTag(const Addr addr) const override; + + public: + StridePrefetcherHashedSetAssociative( + const StridePrefetcherHashedSetAssociativeParams *p) + : SetAssociative(p) + { + } + ~StridePrefetcherHashedSetAssociative() = default; +}; + class Stride : public Queued { protected: @@ -71,86 +94,43 @@ class Stride : public Queued /** Confidence threshold for prefetch generation. */ const double threshConf; - const int pcTableAssoc; - const int pcTableSets; - const bool useMasterId; const int degree; - /** Replacement policy used in the PC tables. */ - BaseReplacementPolicy* replacementPolicy; - - struct StrideEntry : public ReplaceableEntry + /** + * Information used to create a new PC table. All of them behave equally. + */ + const struct PCTableInfo + { + const int assoc; + const int numEntries; + + BaseIndexingPolicy* const indexingPolicy; + BaseReplacementPolicy* const replacementPolicy; + + PCTableInfo(int assoc, int num_entries, + BaseIndexingPolicy* indexing_policy, + BaseReplacementPolicy* replacement_policy) + : assoc(assoc), numEntries(num_entries), + indexingPolicy(indexing_policy), + replacementPolicy(replacement_policy) + { + } + } pcTableInfo; + + /** Tagged by hashed PCs. */ + struct StrideEntry : public TaggedEntry { StrideEntry(const SatCounter& init_confidence); - /** Invalidate the entry */ - void invalidate(); + void invalidate() override; - Addr instAddr; Addr lastAddr; - bool isSecure; int stride; SatCounter confidence; }; - - class PCTable - { - public: - /** - * Default constructor. Create a table with given parameters. - * - * @param assoc Associativity of the table. - * @param sets Number of sets in the table. - * @param name Name of the prefetcher. - * @param replacementPolicy Replacement policy used by the table. - */ - PCTable(int assoc, int sets, const std::string name, - BaseReplacementPolicy* replacementPolicy, - StrideEntry init_confidence); - - /** - * Default destructor. - */ - ~PCTable(); - - /** - * Search for an entry in the pc table. - * - * @param pc The PC to look for. - * @param is_secure True if the target memory space is secure. - * @return Pointer to the entry. - */ - StrideEntry* findEntry(Addr pc, bool is_secure); - - /** - * Find a replacement victim to make room for given PC. - * - * @param pc The PC value. - * @return The victimized entry. - */ - StrideEntry* findVictim(Addr pc); - - private: - const std::string name() {return _name; } - const int pcTableSets; - const std::string _name; - std::vector> entries; - - /** - * Replacement policy used by StridePrefetcher. - */ - BaseReplacementPolicy* replacementPolicy; - - /** - * PC hashing function to index sets in the table. - * - * @param pc The PC value. - * @return The set to which this PC maps. - */ - Addr pcHash(Addr pc) const; - }; + typedef AssociativeSet PCTable; std::unordered_map pcTables; /** diff --git a/src/mem/cache/tags/indexing_policies/base.hh b/src/mem/cache/tags/indexing_policies/base.hh index 435a078ae..9a56b54f6 100644 --- a/src/mem/cache/tags/indexing_policies/base.hh +++ b/src/mem/cache/tags/indexing_policies/base.hh @@ -133,7 +133,7 @@ class BaseIndexingPolicy : public SimObject * @param addr The address to get the tag from. * @return The tag of the address. */ - Addr extractTag(const Addr addr) const; + virtual Addr extractTag(const Addr addr) const; /** * Find all possible entries for insertion and replacement of an address. diff --git a/src/mem/cache/tags/indexing_policies/set_associative.hh b/src/mem/cache/tags/indexing_policies/set_associative.hh index 7bfa65401..e7126c39c 100644 --- a/src/mem/cache/tags/indexing_policies/set_associative.hh +++ b/src/mem/cache/tags/indexing_policies/set_associative.hh @@ -78,14 +78,14 @@ class ReplaceableEntry; */ class SetAssociative : public BaseIndexingPolicy { - private: + protected: /** * Apply a hash function to calculate address set. * * @param addr The address to calculate the set for. * @return The set index for given combination of address and way. */ - uint32_t extractSet(const Addr addr) const; + virtual uint32_t extractSet(const Addr addr) const; public: /** -- 2.30.2