/**
* 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
{
protected:
/** 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;
/** use counter, used by SPPv2 */
uint8_t counter;
PatternEntry(size_t num_strides) : strideEntries(num_strides),
counter(0)
{}
/** Reset the entries to their initial values */
void reset() override
{
for (auto &entry : strideEntries) {
entry.counter = 0;
entry.stride = 0;
}
counter = 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 last_block last accessed block within the page ppn
* @param delta difference, in number of blocks, from the last_block
* accessed to the block to prefetch. The block to prefetch is
* computed by this formula:
* ppn * pageBytes + (last_block + delta) * blkSize
* This value can be negative.
* @param path_confidence the confidence factor of this prefetch
* @param signature the current path signature
* @param is_secure whether this page is inside the secure memory area
* @param addresses addresses to prefetch will be added to this vector
*/
void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
double path_confidence, signature_t signature,
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
* It also provides the stride of the current block and the initial
* path confidence of the corresponding entry
* @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 if the entry is not found, this will be set to true
* @param stride set to the computed stride
* @param initial_confidence set to the initial confidence value
* @result a reference to the SignatureEntry
*/
SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
bool &miss, stride_t &stride, double &initial_confidence);
/**
* 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);
/**
* Computes the lookahead path confidence of the provided pattern entry
* @param sig the PatternEntry to use
* @param lookahead PatternStrideEntry within the provided PatternEntry
* @return the computed confidence factor
*/
virtual double calculateLookaheadConfidence(PatternEntry const &sig,
PatternStrideEntry const &lookahead) const;
/**
* Computes the prefetch confidence of the provided pattern entry
* @param sig the PatternEntry to use
* @param entry PatternStrideEntry within the provided PatternEntry
* @return the computed confidence factor
*/
virtual double calculatePrefetchConfidence(PatternEntry const &sig,
PatternStrideEntry const &entry) const;
/**
* Increases the counter of a given PatternEntry/PatternStrideEntry
* @param pattern_entry the corresponding PatternEntry
* @param pstride_entry the PatternStrideEntry within the PatternEntry
*/
virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
PatternStrideEntry &pstride_entry);
/**
* Whenever a new SignatureEntry is allocated, it computes the new
* signature to be used with the new entry, the resulting stride and the
* initial path confidence of the new entry.
* @param current_block accessed block within the page of the associated
entry
* @param new_signature new signature of the allocated entry
* @param new_conf the initial path confidence of this entry
* @param new_stride the resulting current stride
*/
virtual void handleSignatureTableMiss(stride_t current_block,
signature_t &new_signature, double &new_conf,
stride_t &new_stride);
/**
* Auxiliar prefetch mechanism used at the end of calculatePrefetch.
* This prefetcher uses this to activate the next line prefetcher if
* no prefetch candidates have been found.
* @param ppn physical page number of the current accessed page
* @param current_block last accessed block within the page ppn
* @param is_secure whether this page is inside the secure memory area
* @param addresses the addresses to be prefetched are added to this vector
* @param updated_filter_entries set of addresses containing these that
* their filter has been updated, if this call updates a new entry
*/
virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
bool is_secure, std::vector<AddrPriority> &addresses);
/**
* Handles the situation when the lookahead process has crossed the
* boundaries of the current page. This is not fully described in the
* paper that was used to implement this code, however, the article
* describing the upgraded version of this prefetcher provides some
* details. For this prefetcher, there are no specific actions to be
* done.
* @param signature the lookahead signature that crossed the page
* @param delta the current stride that caused it
* @param last_offset the last accessed block within the page
* @param path_confidence the path confidence at the moment of crossing
*/
virtual void handlePageCrossingLookahead(signature_t signature,
stride_t last_offset, stride_t delta, double path_confidence) {
}
public:
SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
~SignaturePathPrefetcher() {}
void calculatePrefetch(const PrefetchInfo &pfi,
std::vector<AddrPriority> &addresses) override;
};
#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__