diff options
| -rw-r--r-- | src/mem/cache/prefetch/Prefetcher.py | 40 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/SConscript | 2 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/associative_set.hh | 200 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/associative_set_impl.hh | 119 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/signature_path.cc | 275 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/signature_path.hh | 204 |
6 files changed, 839 insertions, 1 deletions
diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py index df547ed42..a868a2583 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,42 @@ class TaggedPrefetcher(QueuedPrefetcher): 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/signature_path.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(7, "Maximum pattern counter value") + pattern_table_entries = Param.MemorySize("4096", + "Number of entries of the pattern table") + pattern_table_assoc = Param.Unsigned(1, + "Associativity of the pattern table") + strides_per_pattern_entry = Param.Unsigned(4, + "Number of strides stored in each pattern entry") + 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") + + 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 2665d1890..ccbc2e3b8 100644 --- a/src/mem/cache/prefetch/SConscript +++ b/src/mem/cache/prefetch/SConscript @@ -34,6 +34,6 @@ SimObject('Prefetcher.py') Source('base.cc') Source('queued.cc') +Source('signature_path.cc') Source('stride.cc') Source('tagged.cc') - diff --git a/src/mem/cache/prefetch/associative_set.hh b/src/mem/cache/prefetch/associative_set.hh new file mode 100644 index 000000000..99b6a6d07 --- /dev/null +++ b/src/mem/cache/prefetch/associative_set.hh @@ -0,0 +1,200 @@ +/** + * 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; + } + + /** + * Resets the entry, this is called when an entry is evicted to allocate + * a new one. Types inheriting this class should provide its own + * implementation + */ + virtual void reset () { + } +}; + +/** + * 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* const indexingPolicy; + /** Pointer to the replacement policy */ + BaseReplacementPolicy* const 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 + * @param initial value of the elements of the set + */ + AssociativeSet(int assoc, int num_entries, BaseIndexingPolicy *idx_policy, + BaseReplacementPolicy *rpl_policy, Entry const &init_value = + Entry()); + + /** + * 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 000000000..5e6e7c585 --- /dev/null +++ b/src/mem/cache/prefetch/associative_set_impl.hh @@ -0,0 +1,119 @@ +/** + * 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, + Entry const &init_value) + : associativity(assoc), numEntries(num_entries), indexingPolicy(idx_policy), + replacementPolicy(rpl_policy), entries(numEntries, init_value) +{ + fatal_if(!isPowerOf2(num_entries), "The number of entries of an " + "AssociativeSet<> must be a power of 2"); + fatal_if(!isPowerOf2(assoc), "The associativity of an AssociativeSet<> " + "must be a power of 2"); + 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 + victim->reset(); + 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); + + unsigned int idx = 0; + for (auto &entry : selected_entries) { + entries[idx++] = static_cast<Entry *>(entry); + } + return entries; +} + +template<class Entry> +void +AssociativeSet<Entry>::insertEntry(Addr addr, bool is_secure, Entry* entry) +{ + entry->setValid(); + 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/signature_path.cc b/src/mem/cache/prefetch/signature_path.cc new file mode 100644 index 000000000..a0356b1d1 --- /dev/null +++ b/src/mem/cache/prefetch/signature_path.cc @@ -0,0 +1,275 @@ +/** + * 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/signature_path.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), + stridesPerPatternEntry(p->strides_per_pattern_entry), + signatureShift(p->signature_shift), + signatureBits(p->signature_bits), + maxCounterValue(p->max_counter_value), + prefetchConfidenceThreshold(p->prefetch_confidence_threshold), + lookaheadConfidenceThreshold(p->lookahead_confidence_threshold), + signatureTable(p->signature_table_assoc, p->signature_table_entries, + p->signature_table_indexing_policy, + p->signature_table_replacement_policy), + patternTable(p->pattern_table_assoc, p->pattern_table_entries, + p->pattern_table_indexing_policy, + p->pattern_table_replacement_policy, + PatternEntry(stridesPerPatternEntry)) +{ +} + +SignaturePathPrefetcher::PatternStrideEntry & +SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride, + uint8_t max_counter_value) +{ + PatternStrideEntry *pstride_entry = findStride(stride); + if (pstride_entry == nullptr) { + // Specific replacement algorithm for this table, + // pick the entry with the lowest counter value, + // then decrease the counter of all entries + + // If all counters have the max value, this will be the pick + PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]); + + uint8_t current_counter = max_counter_value; + for (auto &entry : strideEntries) { + if (entry.counter < current_counter) { + victim_pstride_entry = &entry; + current_counter = entry.counter; + } + if (entry.counter > 0) { + entry.counter -= 1; + } + } + pstride_entry = victim_pstride_entry; + pstride_entry->counter = 0; + pstride_entry->stride = stride; + } + return *pstride_entry; +} + +void +SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t block, + bool is_secure, std::vector<AddrPriority> &addresses) +{ + /** + * 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))); + assert(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; + + DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); + addresses.push_back(AddrPriority(new_addr, 0)); +} + +void +SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride) +{ + assert(stride != 0); + // The pattern table is indexed by signatures + PatternEntry &p_entry = getPatternEntry(signature); + PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride, + maxCounterValue); + if (ps_entry.counter < maxCounterValue) { + ps_entry.counter += 1; + } +} + +SignaturePathPrefetcher::SignatureEntry & +SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure, + stride_t block, bool &miss) +{ + SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure); + if (signature_entry != nullptr) { + signatureTable.accessEntry(signature_entry); + miss = false; + } else { + signature_entry = signatureTable.findVictim(ppn); + assert(signature_entry != nullptr); + + signatureTable.insertEntry(ppn, is_secure, signature_entry); + signature_entry->signature = block; + signature_entry->lastBlock = block; + miss = true; + } + return *signature_entry; +} + +SignaturePathPrefetcher::PatternEntry & +SignaturePathPrefetcher::getPatternEntry(Addr signature) +{ + PatternEntry* pattern_entry = patternTable.findEntry(signature, false); + if (pattern_entry != nullptr) { + // Signature found + patternTable.accessEntry(pattern_entry); + } else { + // Signature not found + pattern_entry = patternTable.findVictim(signature); + assert(pattern_entry != nullptr); + + patternTable.insertEntry(signature, false, pattern_entry); + } + return *pattern_entry; +} + +void +SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) +{ + Addr request_addr = pfi.getAddr(); + Addr ppn = request_addr / pageBytes; + stride_t current_block = (request_addr % pageBytes) / blkSize; + stride_t stride; + bool is_secure = pfi.isSecure(); + + // Get the SignatureEntry of this page to: + // - compute the current stride + // - obtain the current signature of accesses + bool miss; + SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure, + current_block, miss); + if (miss) { + // No history for this page, can't continue + return; + } + + stride = current_block - signature_entry.lastBlock; + if (stride == 0) { + // Can't continue with a stride 0 + return; + } + + // Update the confidence of the current signature + updatePatternTable(signature_entry.signature, stride); + + // Update the current SignatureEntry signature and lastBlock + signature_entry.signature = + updateSignature(signature_entry.signature, stride); + signature_entry.lastBlock = current_block; + + signature_t current_signature = signature_entry.signature; + double current_confidence = 1.0; + stride_t current_stride = signature_entry.lastBlock; + + do { + // With the updated signature, attempt to generate prefetches + // - search the PatternTable and select all entries with enough + // confidence, these are prefetch candidates + // - select the entry with the highest counter as the "lookahead" + PatternEntry *current_pattern_entry = + patternTable.findEntry(current_signature, false); + PatternStrideEntry const *lookahead = nullptr; + if (current_pattern_entry != nullptr) { + uint8_t max_counter = 0; + for (auto const &entry : current_pattern_entry->strideEntries) { + //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) { + assert(entry.stride != 0); + //prefetch candidate + addPrefetch(ppn, current_stride + entry.stride, + is_secure, addresses); + } + } + } + if (lookahead != nullptr) { + // If a lookahead was selected, compute its confidence using + // the counter of its entry and the accumulated confidence + // if the confidence is high enough, generate a new signature + 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); + current_stride += lookahead->stride; + } else { + current_confidence = 0.0; + } + // If the accumulated confidence is high enough, keep repeating + // this process with the updated signature + } + while (current_confidence > lookaheadConfidenceThreshold); + + if (addresses.empty()) { + // Enable the next line prefetcher if no prefetch candidates are found + addPrefetch(ppn, current_block + 1, is_secure, addresses); + } +} + +SignaturePathPrefetcher* +SignaturePathPrefetcherParams::create() +{ + return new SignaturePathPrefetcher(this); +} diff --git a/src/mem/cache/prefetch/signature_path.hh b/src/mem/cache/prefetch/signature_path.hh new file mode 100644 index 000000000..0371b56e3 --- /dev/null +++ b/src/mem/cache/prefetch/signature_path.hh @@ -0,0 +1,204 @@ +/** + * 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) + * The filter feature described in the paper is not implemented, as it + * redundant prefetches are dropped by the cache. + */ + +#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ +#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_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 int16_t stride_t; + + /** Number of strides stored in each pattern entry */ + const unsigned stridesPerPatternEntry; + /** 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; + + /** A stride entry with its counter */ + struct PatternStrideEntry + { + /** stride in a page in blkSize increments */ + stride_t stride; + /** counter value (max value defined by maxCounterValue) */ + uint8_t counter; + PatternStrideEntry() : stride(0), counter(0) + {} + }; + /** Pattern entry data type, a set of stride and counter entries */ + struct PatternEntry : public TaggedEntry + { + /** group of stides */ + std::vector<PatternStrideEntry> strideEntries; + PatternEntry(size_t num_strides) : strideEntries(num_strides) + {} + + /** Reset the entries to their initial values */ + void reset() override + { + for (auto &entry : strideEntries) { + entry.counter = 0; + entry.stride = 0; + } + } + + /** + * Returns the entry with the desired stride + * @param stride the stride to find + * @result a pointer to the entry, if the stride was found, or nullptr, + * if the stride was not found + */ + PatternStrideEntry *findStride(stride_t stride) + { + PatternStrideEntry *found_entry = nullptr; + for (auto &entry : strideEntries) { + if (entry.stride == stride) { + found_entry = &entry; + break; + } + } + return found_entry; + } + + /** + * Gets the entry with the provided stride, if there is no entry with + * the associated stride, it replaces one of them. + * @param stride the stride to find + * @param max_counter_value maximum value of the confidence counters, + * it is used when no strides are found and an entry needs to be + * replaced + * @result reference to the selected entry + */ + PatternStrideEntry &getStrideEntry(stride_t stride, + uint8_t max_counter_value); + }; + /** Pattern table */ + AssociativeSet<PatternEntry> patternTable; + + /** + * 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 &= mask(signatureBits); + return sig; + } + + /** + * Generates an address to be prefetched. + * @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 + */ + void addPrefetch(Addr ppn, stride_t block, bool is_secure, + std::vector<AddrPriority> &addresses); + + /** + * Obtains the SignatureEntry of the given page, if the page is not found, + * it allocates a new one, replacing an existing entry if needed + * @param ppn physical page number of the page + * @param is_secure whether this page is inside the secure memory area + * @param block accessed block within the page + * @param miss output, if the entry is not found, this will be set to true + * @result a reference to the SignatureEntry + */ + SignatureEntry & getSignatureEntry(Addr ppn, bool is_secure, + stride_t block, bool &miss); + /** + * Obtains the PatternEntry of the given signature, if the signature is + * not found, it allocates a new one, replacing an existing entry if needed + * @param signature the signature of the desired entry + * @result a reference to the PatternEntry + */ + PatternEntry & getPatternEntry(Addr signature); + + /** + * Updates the pattern table with the provided signature and stride + * @param signature the signature to use to index the pattern table + * @param stride the stride to use to index the set of strides of the + * pattern table entry + */ + void updatePatternTable(Addr signature, stride_t stride); + + public: + SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p); + ~SignaturePathPrefetcher() {} + void calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) override; +}; + +#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ |