Hello Giacomo Travaglini, Andreas Sandberg,
I'd like you to do a code review. Please visit
https://gem5-review.googlesource.com/c/public/gem5/+/14737
to review the following change.
Change subject: mem-cache: Signature Path Prefetcher
......................................................................
mem-cache: Signature Path Prefetcher
Related paper:
Lookahead Prefetching with Signature Path
J Kim, PV Gratz, ALN Reddy
The 2nd Data Prefetching Championship (DPC2), 2015
Change-Id: I2319be2fa409f955f65e1bf1e1bb2d6d9a4fea11
---
M src/mem/cache/prefetch/Prefetcher.py
M src/mem/cache/prefetch/SConscript
A src/mem/cache/prefetch/associative_set.hh
A src/mem/cache/prefetch/associative_set_impl.hh
A src/mem/cache/prefetch/signaturepath.cc
A src/mem/cache/prefetch/signaturepath.hh
6 files changed, 821 insertions(+), 1 deletion(-)
diff --git a/src/mem/cache/prefetch/Prefetcher.py
b/src/mem/cache/prefetch/Prefetcher.py
index df547ed..44f99be 100644
--- a/src/mem/cache/prefetch/Prefetcher.py
+++ b/src/mem/cache/prefetch/Prefetcher.py
@@ -40,6 +40,7 @@
# Mitch Hayenga
from ClockedObject import ClockedObject
+from IndexingPolicies import *
from m5.SimObject import *
from m5.params import *
from m5.proxy import *
@@ -139,3 +140,50 @@
cxx_header = "mem/cache/prefetch/tagged.hh"
degree = Param.Int(2, "Number of prefetches to generate")
+
+class SignaturePathPrefetcher(QueuedPrefetcher):
+ type = 'SignaturePathPrefetcher'
+ cxx_class = 'SignaturePathPrefetcher'
+ cxx_header = "mem/cache/prefetch/signaturepath.hh"
+
+ signature_shift = Param.UInt8(3,
+ "Number of bits to shift when calculating a new signature");
+ signature_bits = Param.UInt16(12,
+ "Size of the signature, in bits");
+ signature_table_entries = Param.MemorySize("1024",
+ "Number of entries of the signature table")
+ signature_table_assoc = Param.Unsigned(2,
+ "Associativity of the signature table")
+ signature_table_indexing_policy = Param.BaseIndexingPolicy(
+ SetAssociative(entry_size = 1, assoc =
Parent.signature_table_assoc,
+ size = Parent.signature_table_entries),
+ "Indexing policy of the signature table")
+ signature_table_replacement_policy =
Param.BaseReplacementPolicy(LRURP(),
+ "Replacement policy of the signature table")
+
+ max_counter_value = Param.UInt8(8, "Maximum pattern counter value")
+ pattern_table_entries = Param.MemorySize("16384",
+ "Number of entries of the pattern table")
+ pattern_table_assoc = Param.Unsigned(4,
+ "Associativity of the pattern table")
+ pattern_table_indexing_policy = Param.BaseIndexingPolicy(
+ SetAssociative(entry_size = 1, assoc = Parent.pattern_table_assoc,
+ size = Parent.pattern_table_entries),
+ "Indexing policy of the pattern table")
+ pattern_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
+ "Replacement policy of the pattern table")
+
+ filter_table_entries = Param.MemorySize("512",
+ "Number of entries of the filter table")
+ filter_table_assoc = Param.Unsigned(2,
+ "Associativity of the filter table")
+ filter_table_indexing_policy = Param.BaseIndexingPolicy(
+ SetAssociative(entry_size = 1, assoc = Parent.filter_table_assoc,
+ size = Parent.filter_table_entries),
+ "Indexing policy of the filter table")
+ filter_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
+ "Replacement policy of the filter table")
+ prefetch_confidence_threshold = Param.Float(0.5,
+ "Minimum confidence to issue prefetches")
+ lookahead_confidence_threshold = Param.Float(0.75,
+ "Minimum confidence to continue exploring lookahead entries")
diff --git a/src/mem/cache/prefetch/SConscript
b/src/mem/cache/prefetch/SConscript
index 2665d18..f8a3d83 100644
--- a/src/mem/cache/prefetch/SConscript
+++ b/src/mem/cache/prefetch/SConscript
@@ -36,4 +36,4 @@
Source('queued.cc')
Source('stride.cc')
Source('tagged.cc')
-
+Source('signaturepath.cc')
diff --git a/src/mem/cache/prefetch/associative_set.hh
b/src/mem/cache/prefetch/associative_set.hh
new file mode 100644
index 0000000..cde6401
--- /dev/null
+++ b/src/mem/cache/prefetch/associative_set.hh
@@ -0,0 +1,193 @@
+/**
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Javier Bueno
+ */
+
+#ifndef __CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
+#define __CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
+
+#include "mem/cache/replacement_policies/base.hh"
+#include "mem/cache/replacement_policies/replaceable_entry.hh"
+#include "mem/cache/tags/indexing_policies/base.hh"
+
+/**
+ * Entry used for set-associative tables, usable with replacement policies
+ */
+class TaggedEntry : public ReplaceableEntry {
+ /** Tag for the entry */
+ Addr tag;
+ /** Valid bit */
+ bool valid;
+ /** Whether this entry refers to a memory area in the secure space */
+ bool secure;
+ public:
+ TaggedEntry() : tag(0), valid(false), secure(false) {}
+ virtual ~TaggedEntry() {}
+
+ /**
+ * Consult the valid bit
+ * @return True if the entry is valid
+ */
+ bool isValid() const
+ {
+ return valid;
+ }
+
+ /**
+ * Sets the entry to valid
+ */
+ void setValid()
+ {
+ valid = true;
+ }
+
+ /**
+ * Sets the entry to invalid
+ */
+ void setInvalid() {
+ valid = false;
+ }
+
+ /**
+ * Obtain the entry tag
+ * @return the tag value
+ */
+ Addr getTag() const
+ {
+ return tag;
+ }
+
+ /**
+ * Sets the tag of the entry
+ * @param t the tag value
+ */
+ void setTag(Addr t)
+ {
+ tag = t;
+ }
+
+ /**
+ * Consult if this entry refers to a memory in the secure area
+ * @return True if this entry refers to secure memory area
+ */
+ bool isSecure() const
+ {
+ return secure;
+ }
+
+ /**
+ * Sets the secure value bit
+ * @param s secure bit value
+ */
+ void setSecure(bool s)
+ {
+ secure = s;
+ }
+
+ TaggedEntry(const TaggedEntry &) = delete;
+ TaggedEntry& operator=(const TaggedEntry &) = delete;
+};
+
+/**
+ * Associative container based on the previosuly defined Entry type
+ * Each element is indexed by a key of type Addr, an additional
+ * bool value is used as an additional tag data of the entry.
+ */
+template<class Entry>
+class AssociativeSet {
+ static_assert(std::is_base_of<TaggedEntry, Entry>::value,
+ "Entry must derive from TaggedEntry");
+
+ /** Associativity of the container */
+ const int associativity;
+ /**
+ * Total number of entries, entries are organized in sets of the
provided
+ * associativity. The number of associative sets is obtained by
dividing
+ * numEntries by associativity.
+ */
+ const int numEntries;
+ /** Pointer to the indexing policy */
+ BaseIndexingPolicy* indexingPolicy;
+ /** Pointer to the replacement policy */
+ BaseReplacementPolicy* replacementPolicy;
+ /** Vector containing the entries of the container */
+ std::vector<Entry> entries;
+
+ public:
+ /**
+ * Public constructor
+ * @param assoc number of elements in each associative set
+ * @param num_entries total number of entries of the container, the
number
+ * of sets can be calculated dividing this balue by the 'assoc' value
+ * @param idx_policy indexing policy
+ * @param rpl_policy replacement policy
+ */
+ AssociativeSet(int assoc, int num_entries, BaseIndexingPolicy
*idx_policy,
+ BaseReplacementPolicy *rpl_policy);
+
+ /**
+ * Find an entry within the set
+ * @param addr key element
+ * @param is_secure tag element
+ * @return returns a pointer to the wanted entry or nullptr if it does
not
+ * exist.
+ */
+ Entry* findEntry(Addr addr, bool is_secure) const;
+
+ /**
+ * Do an access to the entry, this is required to
+ * update the replacement information data.
+ * @param entry the accessed entry
+ */
+ void accessEntry(Entry *entry);
+
+ /**
+ * Find a victim to be replaced
+ * @param addr key to select the possible victim
+ * @result entry to be victimized
+ */
+ Entry* findVictim(Addr addr);
+
+ /**
+ * Find the set of entries that could be replaced given
+ * that we want to add a new entry with the provided key
+ * @param addr key to select the set of entries
+ * @result vector of candidates matching with the provided key
+ */
+ std::vector<Entry *> getPossibleEntries(const Addr addr) const;
+
+ /**
+ * Indicate that an entry has just been inserted
+ * @param addr key of the container
+ * @param is_secure tag component of the container
+ * @param entry pointer to the container entry to be inserted
+ */
+ void insertEntry(Addr addr, bool is_secure, Entry* entry);
+};
+
+#endif//__CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
diff --git a/src/mem/cache/prefetch/associative_set_impl.hh
b/src/mem/cache/prefetch/associative_set_impl.hh
new file mode 100644
index 0000000..bb3d78c
--- /dev/null
+++ b/src/mem/cache/prefetch/associative_set_impl.hh
@@ -0,0 +1,111 @@
+/**
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Javier Bueno
+ */
+
+#ifndef __CACHE_PREFETCH_ASSOCIATIVE_SET_IMPL_HH__
+#define __CACHE_PREFETCH_ASSOCIATIVE_SET_IMPL_HH__
+
+#include "mem/cache/prefetch/associative_set.hh"
+
+template<class Entry>
+AssociativeSet<Entry>::AssociativeSet(int assoc, int num_entries,
+ BaseIndexingPolicy *idx_policy, BaseReplacementPolicy *rpl_policy)
+ : associativity(assoc), numEntries(num_entries),
indexingPolicy(idx_policy),
+ replacementPolicy(rpl_policy), entries(numEntries)
+{
+ for (unsigned int entry_idx = 0; entry_idx < numEntries; entry_idx +=
1) {
+ Entry* entry = &entries[entry_idx];
+ indexingPolicy->setEntry(entry, entry_idx);
+ entry->replacementData = replacementPolicy->instantiateEntry();
+ }
+}
+
+template<class Entry>
+Entry*
+AssociativeSet<Entry>::findEntry(Addr addr, bool is_secure) const
+{
+ Addr tag = indexingPolicy->extractTag(addr);
+ const std::vector<ReplaceableEntry*> selected_entries =
+ indexingPolicy->getPossibleEntries(addr);
+
+ for (const auto& location : selected_entries) {
+ Entry* entry = static_cast<Entry *>(location);
+ if ((entry->getTag() == tag) && entry->isValid() &&
+ entry->isSecure() == is_secure) {
+ return entry;
+ }
+ }
+ return nullptr;
+}
+
+template<class Entry>
+void
+AssociativeSet<Entry>::accessEntry(Entry *entry)
+{
+ replacementPolicy->touch(entry->replacementData);
+}
+
+template<class Entry>
+Entry*
+AssociativeSet<Entry>::findVictim(Addr addr)
+{
+ // Get possible entries to be victimized
+ const std::vector<ReplaceableEntry*> selected_entries =
+ indexingPolicy->getPossibleEntries(addr);
+ Entry* victim = static_cast<Entry*>(replacementPolicy->getVictim(
+ selected_entries));
+ // There is only one eviction for this replacement
+ return victim;
+}
+
+
+template<class Entry>
+std::vector<Entry *>
+AssociativeSet<Entry>::getPossibleEntries(const Addr addr) const
+{
+ std::vector<ReplaceableEntry *> selected_entries =
+ indexingPolicy->getPossibleEntries(addr);
+ std::vector<Entry *> entries(selected_entries.size(), nullptr);
+
+ for (unsigned idx = 0; idx < selected_entries.size(); idx += 1) {
+ entries[idx] = static_cast<Entry *>(selected_entries[idx]);
+ }
+ return entries;
+}
+
+template<class Entry>
+void
+AssociativeSet<Entry>::insertEntry(Addr addr, bool is_secure, Entry* entry)
+{
+ entry->setTag(indexingPolicy->extractTag(addr));
+ entry->setSecure(is_secure);
+ replacementPolicy->reset(entry->replacementData);
+}
+
+#endif//__CACHE_PREFETCH_ASSOCIATIVE_SET_IMPL_HH__
diff --git a/src/mem/cache/prefetch/signaturepath.cc
b/src/mem/cache/prefetch/signaturepath.cc
new file mode 100644
index 0000000..8c7a394
--- /dev/null
+++ b/src/mem/cache/prefetch/signaturepath.cc
@@ -0,0 +1,296 @@
+/**
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Javier Bueno
+ */
+
+#include "mem/cache/prefetch/signaturepath.hh"
+
+#include <cassert>
+
+#include "debug/HWPrefetch.hh"
+#include "mem/cache/prefetch/associative_set_impl.hh"
+#include "params/SignaturePathPrefetcher.hh"
+
+SignaturePathPrefetcher::SignaturePathPrefetcher(
+ const SignaturePathPrefetcherParams *p)
+ : QueuedPrefetcher(p),
+ signatureTableEntries(p->signature_table_entries),
+ signatureTableAssoc(p->signature_table_assoc),
+ patternTableEntries(p->pattern_table_entries),
+ patternTableAssoc(p->pattern_table_assoc),
+ filterTableEntries(p->filter_table_entries),
+ filterTableAssoc(p->filter_table_assoc),
+ signatureShift(p->signature_shift),
+ signatureBits(p->signature_bits),
+ maxCounterValue(p->max_counter_value),
+ prefetchConfidenceThreshold(p->prefetch_confidence_threshold),
+ lookaheadConfidenceThreshold(p->lookahead_confidence_threshold),
+ signatureTable(signatureTableAssoc, signatureTableEntries,
+ p->signature_table_indexing_policy,
+ p->signature_table_replacement_policy),
+ patternTable(patternTableAssoc, patternTableEntries,
+ p->pattern_table_indexing_policy,
+ p->pattern_table_replacement_policy),
+ filterTable(filterTableAssoc, filterTableEntries,
+ p->filter_table_indexing_policy,
+ p->filter_table_replacement_policy)
+{
+ assert(isPowerOf2(signatureTableEntries));
+ assert(isPowerOf2(signatureTableAssoc));
+ assert(isPowerOf2(patternTableEntries));
+ assert(isPowerOf2(patternTableAssoc));
+ assert(isPowerOf2(filterTableEntries));
+ assert(isPowerOf2(filterTableAssoc));
+}
+
+void
+SignaturePathPrefetcher::updateFilter(FilterEntry &filter_entry, Addr ppn,
+ bool is_secure)
+{
+ // Check on positions set if the block has been evicted from the cache
+ // cache evictions are supposed to reset entries that were set to 1
+ for (Addr block_id = 0; block_id < (pageBytes/blkSize); block_id += 1)
{
+ if (filter_entry.bitmap[block_id]) {
+ filter_entry.bitmap[block_id] =
+ inCache(ppn + block_id * blkSize, is_secure);
+ }
+ }
+}
+
+SignaturePathPrefetcher::FilterEntry *
+SignaturePathPrefetcher::filterAndAddPrefetch(FilterEntry
*orig_filter_entry,
+ Addr ppn, stride_t block, bool is_secure,
+ std::vector<AddrPriority> &addresses)
+{
+ FilterEntry *filter_entry = orig_filter_entry;
+ /**
+ * block is relative to the provided ppn. Assuming a page size of 4kB
and
+ * a block size of 64B, the range of the stride of this prefetcher is
+ * -63,63 (pageBytes/blkSize) as the last accessed block also ranges
from
+ * 0,63, the block value is expected to be between -63 and 126
+ * Negative block means that we are accessing the lower contiguous
page,
+ * 64 or greater point to the next contiguous.
+ */
+ assert(block > -((stride_t)(pageBytes/blkSize)) &&
+ block < 2*((stride_t)(pageBytes/blkSize)));
+
+ Addr pf_ppn;
+ stride_t pf_block;
+ if (block < 0) {
+ pf_ppn = ppn - 1;
+ pf_block = block + (pageBytes/blkSize);
+ } else if (block >= (pageBytes/blkSize)) {
+ pf_ppn = ppn + 1;
+ pf_block = block - (pageBytes/blkSize);
+ } else {
+ pf_ppn = ppn;
+ pf_block = block;
+ }
+
+ Addr new_addr = pf_ppn * pageBytes;
+ new_addr += pf_block * (Addr)blkSize;
+ Addr hashed_ppn = ppnHash(pf_ppn);
+ //filter entry was not allocated, allocate now
+ if (filter_entry == nullptr) {
+ filter_entry = filterTable.findVictim(hashed_ppn);
+ assert(filter_entry != nullptr);
+ if (!filter_entry->isValid()) {
+ filter_entry->setValid();
+ filter_entry->bitmap.resize(pageBytes/blkSize);
+ }
+
+ for (unsigned block_idx = 0;
+ block_idx < pageBytes/blkSize;
+ block_idx += 1)
+ {
+ filter_entry->bitmap[block_idx] = false;
+ }
+ filterTable.insertEntry(hashed_ppn, is_secure, filter_entry);
+ }
+ if (!filter_entry->bitmap[pf_block]) {
+ DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
+ addresses.push_back(AddrPriority(new_addr, 0));
+ filter_entry->bitmap[pf_block] = true;
+ } else {
+ DPRINTF(HWPrefetch, "Filter out prefetch to %#x.\n", new_addr);
+ }
+ if (pf_ppn == ppn) {
+ return filter_entry;
+ } else {
+ return orig_filter_entry;
+ }
+}
+
+void
+SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
+ std::vector<AddrPriority> &addresses)
+{
+ Addr request_addr = pfi.getAddr();
+ Addr ppn = request_addr / pageBytes;
+ Addr hashed_ppn = ppnHash(ppn);
+ int8_t current_block = (request_addr % pageBytes) / blkSize;
+ int8_t current_stride;
+ bool is_secure = pfi.isSecure();
+
+ FilterEntry* filter_entry = filterTable.findEntry(hashed_ppn,
is_secure);
+ if (filter_entry != nullptr) {
+ // if the entry for this page exists, update the entries that
+ // may have been evicted
+ updateFilter(*filter_entry, ppn, is_secure);
+ }
+
+ SignatureEntry* signature_entry =
+ signatureTable.findEntry(hashed_ppn, is_secure);
+ if (signature_entry != nullptr) {
+ signatureTable.accessEntry(signature_entry);
+ current_stride = current_block - signature_entry->lastBlock;
+ } else {
+ signature_entry = signatureTable.findVictim(hashed_ppn);
+ assert(signature_entry != nullptr);
+
+ signature_entry->setValid();
+ signature_entry->signature =
+ signature_entry->lastBlock = current_block;
+ current_stride = current_block;
+ signatureTable.insertEntry(hashed_ppn, is_secure, signature_entry);
+ }
+
+ // Signature is set index, Stride is tag,
+ // we ignore the secure bit in this table
+ Addr pattern_addr =
+ (current_stride << signatureBits) + signature_entry->signature;
+ PatternEntry* pattern_entry = patternTable.findEntry(pattern_addr,
false);
+ if (pattern_entry == nullptr) {
+ //Specific replacement algorithm for this table,
+ //pick the entry with the lowest counter value,
+ //then decrease the counter of all entries
+ std::vector<PatternEntry *> set_entries =
+ patternTable.getPossibleEntries(pattern_addr);
+ PatternEntry *victim_entry = nullptr;
+ uint8_t current_counter = maxCounterValue;//max value is 8
+ for (auto entry : set_entries) {
+ if (entry->counter < current_counter) {
+ victim_entry = entry;
+ current_counter = entry->counter;
+ }
+ if (entry->counter > 0) {
+ entry->counter -= 1;
+ }
+ }
+ if (victim_entry == nullptr) {
+ //all counters are at max value, fallback to the specified
policy
+ victim_entry = patternTable.findVictim(pattern_addr);
+ assert(victim_entry != nullptr);
+ }
+ pattern_entry = victim_entry;
+ pattern_entry->setValid();
+ pattern_entry->stride = current_stride;
+ pattern_entry->counter = 0;
+ patternTable.insertEntry(pattern_addr, false, pattern_entry);
+ }
+ if (pattern_entry->counter < maxCounterValue) {
+ pattern_entry->counter += 1;
+ patternTable.accessEntry(pattern_entry);
+ }
+
+ signature_entry->signature =
+ updateSignature(signature_entry->signature, current_stride);
+ signature_entry->lastBlock = current_block;
+
+ signature_t current_signature = signature_entry->signature;
+ double current_confidence = 1.0;
+
+ do {
+ //stride 0 as we will inspect all possible entries (strides)
+ Addr prefetch_pattern_address = current_signature;
+ PatternEntry *lookahead = nullptr;
+ std::vector<PatternEntry *> set_entries =
+ patternTable.getPossibleEntries(prefetch_pattern_address);
+ uint8_t max_counter = 0;
+ for (auto entry : set_entries) {
+ //select the entry with the maximum counter value as lookahead
+ if (max_counter < entry->counter) {
+ max_counter = entry->counter;
+ lookahead = entry;
+ }
+ double prefetch_confidence =
+ (double) entry->counter / maxCounterValue;
+
+ if (prefetch_confidence >= prefetchConfidenceThreshold) {
+ //prefetch candidate
+ stride_t block = signature_entry->lastBlock +
entry->stride;
+ filter_entry = filterAndAddPrefetch(filter_entry, ppn,
+ block, is_secure,
+ addresses);
+ }
+ }
+ if (lookahead != nullptr) {
+ double lookahead_confidence;
+ if (lookahead->counter == maxCounterValue) {
+ /**
+ * maximum confidence is 0.95, guaranteeing that
+ * current confidence will eventually fall beyond
+ * the threshold
+ */
+ lookahead_confidence = 0.95;
+ } else {
+ lookahead_confidence =
+ ((double) lookahead->counter / maxCounterValue);
+ }
+ current_confidence *= lookahead_confidence;
+ current_signature =
+ updateSignature(current_signature, lookahead->stride);
+ } else {
+ current_confidence = 0.0;
+ }
+ }
+ while (current_confidence > lookaheadConfidenceThreshold);
+
+ if (addresses.empty()) {
+ //enable the next line prefetcher if no prefetch candidates are
found
+ filter_entry = filterAndAddPrefetch(filter_entry, ppn,
+ current_block + 1, is_secure,
addresses);
+ }
+
+
+}
+
+inline Addr
+SignaturePathPrefetcher::ppnHash(Addr ppn) const
+{
+ int num_signature_sets = signatureTableEntries/signatureTableAssoc;
+ Addr hash1 = ppn >> 1;
+ Addr hash2 = hash1 >> floorLog2(num_signature_sets);
+ return (hash1 ^ hash2) & (Addr)(num_signature_sets - 1);
+}
+
+SignaturePathPrefetcher*
+SignaturePathPrefetcherParams::create()
+{
+ return new SignaturePathPrefetcher(this);
+}
diff --git a/src/mem/cache/prefetch/signaturepath.hh
b/src/mem/cache/prefetch/signaturepath.hh
new file mode 100644
index 0000000..99ac6a2
--- /dev/null
+++ b/src/mem/cache/prefetch/signaturepath.hh
@@ -0,0 +1,172 @@
+/**
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Javier Bueno
+ */
+
+ /**
+ * Implementation of the Signature Path Prefetcher
+ *
+ * References:
+ * Lookahead prefetching with signature path
+ * J Kim, PV Gratz, ALN Reddy
+ * The 2nd Data Prefetching Championship (DPC2)
+ */
+
+#ifndef __MEM_CACHE_PREFETCH_SPP_HH__
+#define __MEM_CACHE_PREFETCH_SPP_HH__
+
+#include "mem/cache/prefetch/associative_set.hh"
+#include "mem/cache/prefetch/queued.hh"
+#include "mem/packet.hh"
+
+struct SignaturePathPrefetcherParams;
+
+class SignaturePathPrefetcher : public QueuedPrefetcher
+{
+ /** Signature type */
+ typedef uint16_t signature_t;
+ /** Stride type */
+ typedef int8_t stride_t;
+
+ /** Total number of entries in the signature table */
+ const uint64_t signatureTableEntries;
+ /** Associativity of the signature table */
+ const unsigned signatureTableAssoc;
+ /** Total number of entries in the pattern table */
+ const uint64_t patternTableEntries;
+ /** Associativity of the signature table */
+ const unsigned patternTableAssoc;
+ /** Total number of entries in the filter table */
+ const uint64_t filterTableEntries;
+ /** Associativity of the filter table */
+ const unsigned filterTableAssoc;
+ /** Number of bits to shift when generating a new signature */
+ const uint8_t signatureShift;
+ /** Size of the signature, in bits */
+ const signature_t signatureBits;
+ /** Maximum pattern entries counter value */
+ const uint8_t maxCounterValue;
+ /** Minimum confidence to issue a prefetch */
+ const double prefetchConfidenceThreshold;
+ /** Minimum confidence to keep navigating lookahead entries */
+ const double lookaheadConfidenceThreshold;
+
+ /** Signature entry data type */
+ struct SignatureEntry : public TaggedEntry
+ {
+ /** Path signature */
+ signature_t signature;
+ /** Last accessed block within a page */
+ stride_t lastBlock;
+ SignatureEntry() : signature(0), lastBlock(0)
+ {}
+ };
+ /** Signature table */
+ AssociativeSet<SignatureEntry> signatureTable;
+
+ /** Pattern entry data type */
+ struct PatternEntry : public TaggedEntry
+ {
+ /** stride in a page in blkSize increments */
+ stride_t stride;
+ /** counter value (max value defined by maxCounterValue) */
+ uint8_t counter;
+ PatternEntry() : stride(0), counter(0)
+ {}
+ };
+ /** Pattern table */
+ AssociativeSet<PatternEntry> patternTable;
+
+ /** Filter entry data type */
+ struct FilterEntry : public TaggedEntry
+ {
+ /** bitmap with the already accessed blocks of a page */
+ std::vector<bool> bitmap;
+ FilterEntry() : bitmap()
+ {}
+ };
+ /** Filter table */
+ AssociativeSet<FilterEntry> filterTable;
+
+ /**
+ * Generates a new signature from an existing one and a new stride
+ * @param sig current signature
+ * @param str stride to add to the new signature
+ * @result the new signature
+ */
+ inline signature_t updateSignature(signature_t sig, stride_t str)
const {
+ sig <<= signatureShift;
+ sig ^= str;
+ sig &= (1<<signatureBits)-1;
+ return sig;
+ }
+
+ /**
+ * Updates the filter entry for the given page entry, it checks
+ * if the blocks marked as prefetched have been evicted from the cache
+ * @param filter_entry entry to update
+ * @param ppn page number of the entry
+ * @param is_secure whether this page is inside the secure memory area
+ */
+ void updateFilter(FilterEntry &filter_entry, Addr ppn, bool is_secure);
+
+ /**
+ * Filters an address and adds it to the address vector if the filter
+ * entry does not indicate that it would be a redundant prefetch.
+ * This function also checks if the block falls within the provided
page
+ * if not, the prefetch is also ignored.
+ * @param filter_entry the filter entry, it can be NULL if there is no
+ * entry allocated in the table, in this case, a victim is
selected
+ * and a new entry is assigned to this page
+ * @param ppn page number to prefetch from
+ * @param block block number within the page, this value can be
negative,
+ * which means that the block refered is actualy in the previous
+ * page (ppn-1), if the value is greater than
(pageBytes/blkSize-1)
+ * then the block refers to a block within the next page (ppn+1)
+ * @param is_secure whether this page is inside the secure memory area
+ * @param addresses if allowed, the address will be added to this
vector
+ * @return a pointer to the filter entry
+ */
+ FilterEntry *filterAndAddPrefetch(FilterEntry *filter_entry, Addr ppn,
+ stride_t block, bool is_secure,
+ std::vector<AddrPriority>
&addresses);
+ /**
+ * Hash function to calculate the signature table key
+ * @param ppn the physical page number
+ * @return the computed hash
+ */
+ Addr ppnHash(Addr ppn) const;
+
+ public:
+ SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
+ ~SignaturePathPrefetcher() {}
+ void calculatePrefetch(const PrefetchInfo &pfi,
+ std::vector<AddrPriority> &addresses) override;
+};
+
+#endif//__MEM_CACHE_PREFETCH_SPP_HH__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/14737
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I2319be2fa409f955f65e1bf1e1bb2d6d9a4fea11
Gerrit-Change-Number: 14737
Gerrit-PatchSet: 1
Gerrit-Owner: Javier Bueno Hedo <[email protected]>
Gerrit-Reviewer: Andreas Sandberg <[email protected]>
Gerrit-Reviewer: Giacomo Travaglini <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
