From b496d4abcede94b0042c584cdedaee12cf541b7a Mon Sep 17 00:00:00 2001 From: Javier Bueno Date: Thu, 7 Mar 2019 15:42:10 +0100 Subject: [PATCH] mem-cache: Added the Indirect Memory Prefetcher Reference: Xiangyao Yu, Christopher J. Hughes, Nadathur Satish, and Srinivas Devadas. 2015. IMP: indirect memory prefetcher. In Proceedings of the 48th International Symposium on Microarchitecture (MICRO-48). ACM, New York, NY, USA, 178-190. DOI: https://doi.org/10.1145/2830772.2830807 Change-Id: I52790f69c13ec55b8c1c8b9396ef9a1fb1be9797 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/16223 Reviewed-by: Daniel Carvalho Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris --- src/mem/cache/prefetch/Prefetcher.py | 35 +++ src/mem/cache/prefetch/SConscript | 1 + src/mem/cache/prefetch/indirect_memory.cc | 269 ++++++++++++++++++++++ src/mem/cache/prefetch/indirect_memory.hh | 194 ++++++++++++++++ 4 files changed, 499 insertions(+) create mode 100644 src/mem/cache/prefetch/indirect_memory.cc create mode 100644 src/mem/cache/prefetch/indirect_memory.hh diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py index e29f121ca..eacdf78f7 100644 --- a/src/mem/cache/prefetch/Prefetcher.py +++ b/src/mem/cache/prefetch/Prefetcher.py @@ -142,6 +142,41 @@ class TaggedPrefetcher(QueuedPrefetcher): degree = Param.Int(2, "Number of prefetches to generate") +class IndirectMemoryPrefetcher(QueuedPrefetcher): + type = 'IndirectMemoryPrefetcher' + cxx_class = 'IndirectMemoryPrefetcher' + cxx_header = "mem/cache/prefetch/indirect_memory.hh" + pt_table_entries = Param.MemorySize("16", + "Number of entries of the Prefetch Table") + pt_table_assoc = Param.Unsigned(16, "Associativity of the Prefetch Table") + pt_table_indexing_policy = Param.BaseIndexingPolicy( + SetAssociative(entry_size = 1, assoc = Parent.pt_table_assoc, + size = Parent.pt_table_entries), + "Indexing policy of the pattern table") + pt_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(), + "Replacement policy of the pattern table") + max_prefetch_distance = Param.Unsigned(16, "Maximum prefetch distance") + max_indirect_counter_value = Param.Unsigned(8, + "Maximum value of the indirect counter") + ipd_table_entries = Param.MemorySize("4", + "Number of entries of the Indirect Pattern Detector") + ipd_table_assoc = Param.Unsigned(4, + "Associativity of the Indirect Pattern Detector") + ipd_table_indexing_policy = Param.BaseIndexingPolicy( + SetAssociative(entry_size = 1, assoc = Parent.ipd_table_assoc, + size = Parent.ipd_table_entries), + "Indexing policy of the Indirect Pattern Detector") + ipd_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(), + "Replacement policy of the Indirect Pattern Detector") + shift_values = VectorParam.Int([2, 3, 4, -3], "Shift values to evaluate") + addr_array_len = Param.Unsigned(4, "Number of misses tracked") + prefetch_threshold = Param.Unsigned(2, + "Counter threshold to start the indirect prefetching") + stream_counter_threshold = Param.Unsigned(4, + "Counter threshold to enable the stream prefetcher") + streaming_distance = Param.Unsigned(4, + "Number of prefetches to generate when using the stream prefetcher") + class SignaturePathPrefetcher(QueuedPrefetcher): type = 'SignaturePathPrefetcher' cxx_class = 'SignaturePathPrefetcher' diff --git a/src/mem/cache/prefetch/SConscript b/src/mem/cache/prefetch/SConscript index c96ec4e34..f533b3c52 100644 --- a/src/mem/cache/prefetch/SConscript +++ b/src/mem/cache/prefetch/SConscript @@ -37,6 +37,7 @@ Source('base.cc') Source('bop.cc') Source('delta_correlating_prediction_tables.cc') Source('irregular_stream_buffer.cc') +Source('indirect_memory.cc') Source('queued.cc') Source('sbooe.cc') Source('signature_path.cc') diff --git a/src/mem/cache/prefetch/indirect_memory.cc b/src/mem/cache/prefetch/indirect_memory.cc new file mode 100644 index 000000000..41edfe0ab --- /dev/null +++ b/src/mem/cache/prefetch/indirect_memory.cc @@ -0,0 +1,269 @@ +/** + * 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/indirect_memory.hh" + + #include "mem/cache/base.hh" + #include "mem/cache/prefetch/associative_set_impl.hh" + #include "params/IndirectMemoryPrefetcher.hh" + +IndirectMemoryPrefetcher::IndirectMemoryPrefetcher( + const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), + maxPrefetchDistance(p->max_prefetch_distance), + shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), + maxIndirectCounterValue(p->max_indirect_counter_value), + streamCounterThreshold(p->stream_counter_threshold), + streamingDistance(p->streaming_distance), + prefetchTable(p->pt_table_assoc, p->pt_table_entries, + p->pt_table_indexing_policy, p->pt_table_replacement_policy), + ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, + p->ipd_table_replacement_policy, + IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), + ipdEntryTrackingMisses(nullptr), +#if THE_ISA != NULL_ISA + byteOrder(TheISA::GuestByteOrder) +#else + byteOrder((ByteOrder) -1) +#endif +{ + fatal_if(byteOrder == -1, "This prefetcher requires a defined ISA\n"); +} + +void +IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, + std::vector &addresses) +{ + // This prefetcher requires a PC + if (!pfi.hasPC()) { + return; + } + + bool is_secure = pfi.isSecure(); + Addr pc = pfi.getPC(); + Addr addr = pfi.getAddr(); + bool miss = pfi.isCacheMiss(); + + checkAccessMatchOnActiveEntries(addr); + + // First check if this is a miss, if the prefetcher is tracking misses + if (ipdEntryTrackingMisses != nullptr && miss) { + // Check if the entry tracking misses has already set its second index + if (!ipdEntryTrackingMisses->secondIndexSet) { + trackMissIndex1(addr); + } else { + trackMissIndex2(addr); + } + } else { + // if misses are not being tracked, attempt to detect stream accesses + PrefetchTableEntry *pt_entry = + prefetchTable.findEntry(pc, false /* unused */); + if (pt_entry != nullptr) { + prefetchTable.accessEntry(pt_entry); + + if (pt_entry->address != addr) { + // Streaming access found + pt_entry->streamCounter += 1; + if (pt_entry->streamCounter >= streamCounterThreshold) { + int64_t delta = addr - pt_entry->address; + for (unsigned int i = 1; i <= streamingDistance; i += 1) { + addresses.push_back(AddrPriority(addr + delta * i, 0)); + } + } + pt_entry->address = addr; + pt_entry->secure = is_secure; + + + // if this is a read, read the data from the cache and assume + // it is an index (this is only possible if the data is already + // in the cache), also, only indexes up to 8 bytes are + // considered + + if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { + int64_t index = 0; + switch(pfi.getSize()) { + case sizeof(uint8_t): + index = pfi.get(byteOrder); + break; + case sizeof(uint16_t): + index = pfi.get(byteOrder); + break; + case sizeof(uint32_t): + index = pfi.get(byteOrder); + break; + case sizeof(uint64_t): + index = pfi.get(byteOrder); + break; + default: + panic("Invalid access size\n"); + } + if (!pt_entry->enabled) { + // Not enabled (no pattern detected in this stream), + // add or update an entry in the pattern detector and + // start tracking misses + allocateOrUpdateIPDEntry(pt_entry, index); + } else { + // Enabled entry, update the index + pt_entry->index = index; + if (!pt_entry->increasedIndirectCounter) { + if (pt_entry->indirectCounter > 0) { + pt_entry->indirectCounter -= 1; + } + } else { + // Set this to false, to see if the new index + // has any match + pt_entry->increasedIndirectCounter = false; + } + + // If the counter is high enough, start prefetching + if (pt_entry->indirectCounter > prefetchThreshold) { + unsigned distance = pt_entry->indirectCounter * + maxPrefetchDistance / maxIndirectCounterValue; + for (int delta = 1; delta < distance; delta += 1) { + Addr pf_addr = pt_entry->baseAddr + + (pt_entry->index << pt_entry->shift); + addresses.push_back(AddrPriority(pf_addr, 0)); + } + } + } + } + } + } else { + pt_entry = prefetchTable.findVictim(pc); + assert(pt_entry != nullptr); + prefetchTable.insertEntry(pc, false /* unused */, pt_entry); + pt_entry->address = addr; + pt_entry->secure = is_secure; + } + } +} + +void +IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( + const PrefetchTableEntry *pt_entry, int64_t index) +{ + // The address of the pt_entry is used to index the IPD + Addr ipd_entry_addr = (Addr) pt_entry; + IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, + false/* unused */); + if (ipd_entry != nullptr) { + ipd.accessEntry(ipd_entry); + if (!ipd_entry->secondIndexSet) { + // Second time we see an index, fill idx2 + ipd_entry->idx2 = index; + ipd_entry->secondIndexSet = true; + ipdEntryTrackingMisses = ipd_entry; + } else { + // Third access! no pattern has been found so far, + // release the IPD entry + ipd_entry->reset(); + ipdEntryTrackingMisses = nullptr; + } + } else { + ipd_entry = ipd.findVictim(ipd_entry_addr); + assert(ipd_entry != nullptr); + ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); + ipd_entry->idx1 = index; + ipdEntryTrackingMisses = ipd_entry; + } +} + +void +IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) +{ + IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; + // If the second index is not set, we are just filling the baseAddr + // vector + assert(entry->numMisses < entry->baseAddr.size()); + std::vector &ba_array = entry->baseAddr[entry->numMisses]; + int idx = 0; + for (int shift : shiftValues) { + ba_array[idx] = miss_addr - (entry->idx1 << shift); + idx += 1; + } + entry->numMisses += 1; + if (entry->numMisses == entry->baseAddr.size()) { + // stop tracking misses once we have tracked enough + ipdEntryTrackingMisses = nullptr; + } +} +void +IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) +{ + IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; + // Second index is filled, compare the addresses generated during + // the previous misses (using idx1) against newly generated values + // using idx2, if a match is found, fill the additional fields + // of the PT entry + for (int midx = 0; midx < entry->numMisses; midx += 1) + { + std::vector &ba_array = entry->baseAddr[midx]; + int idx = 0; + for (int shift : shiftValues) { + if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { + // Match found! + // Fill the corresponding pt_entry + PrefetchTableEntry *pt_entry = + (PrefetchTableEntry *) entry->getTag(); + pt_entry->baseAddr = ba_array[idx]; + pt_entry->shift = shift; + pt_entry->enabled = true; + pt_entry->indirectCounter = 0; + // Release the current IPD Entry + entry->reset(); + // Do not track more misses + ipdEntryTrackingMisses = nullptr; + return; + } + idx += 1; + } + } +} + +void +IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) +{ + for (auto &pt_entry : prefetchTable) { + if (pt_entry.enabled) { + if (addr == pt_entry.baseAddr + + (pt_entry.index << pt_entry.shift)) { + if (pt_entry.indirectCounter < maxIndirectCounterValue) { + pt_entry.indirectCounter += 1; + pt_entry.increasedIndirectCounter = true; + } + } + } + } +} + +IndirectMemoryPrefetcher* +IndirectMemoryPrefetcherParams::create() +{ + return new IndirectMemoryPrefetcher(this); +} diff --git a/src/mem/cache/prefetch/indirect_memory.hh b/src/mem/cache/prefetch/indirect_memory.hh new file mode 100644 index 000000000..b67cdfb0a --- /dev/null +++ b/src/mem/cache/prefetch/indirect_memory.hh @@ -0,0 +1,194 @@ +/** + * 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 Indirect Memory Prefetcher + * + * References: + * IMP: Indirect memory prefetcher. + * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December). + * In Proceedings of the 48th International Symposium on Microarchitecture + * (pp. 178-190). ACM. + */ + +#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ +#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ + +#include + +#include "mem/cache/prefetch/associative_set.hh" +#include "mem/cache/prefetch/queued.hh" + +struct IndirectMemoryPrefetcherParams; + +class IndirectMemoryPrefetcher : public QueuedPrefetcher +{ + /** Maximum number of prefetches generated per event */ + const unsigned int maxPrefetchDistance; + /** Shift values considered */ + const std::vector shiftValues; + /** Counter threshold to start prefetching */ + const unsigned int prefetchThreshold; + /** Maximum value of the confidence indirectCounter */ + const unsigned int maxIndirectCounterValue; + /** streamCounter value to trigger the streaming prefetcher */ + const int streamCounterThreshold; + /** Number of prefetches generated when using the streaming prefetcher */ + const int streamingDistance; + + /** Prefetch Table Entry */ + struct PrefetchTableEntry : public TaggedEntry + { + /* Stream table fields */ + + /** Accessed address */ + Addr address; + /** Whether this address is in the secure region */ + bool secure; + /** Confidence counter of the stream */ + unsigned int streamCounter; + + /* Indirect table fields */ + + /** Enable bit of the indirect fields */ + bool enabled; + /** Current index value */ + int64_t index; + /** BaseAddr detected */ + Addr baseAddr; + /** Shift detected */ + int shift; + /** Confidence counter of the indirect fields */ + int indirectCounter; + /** + * This variable is set to indicate that there has been at least one + * match with the current index value. This information is later used + * when a new index is updated. If there were no increases in the + * indirectCounter, the counter is decremented. + */ + bool increasedIndirectCounter; + + PrefetchTableEntry() : TaggedEntry(), address(0), secure(false), + streamCounter(0), enabled(false), index(0), baseAddr(0), shift(0), + indirectCounter(0), increasedIndirectCounter(false) + {} + + void reset() override { + address = 0; + secure = false; + streamCounter = 0; + enabled = false; + index = 0; + baseAddr = 0; + shift = 0; + indirectCounter = 0; + increasedIndirectCounter = false; + } + }; + /** Prefetch table */ + AssociativeSet prefetchTable; + + /** Indirect Pattern Detector entrt */ + struct IndirectPatternDetectorEntry : public TaggedEntry + { + /** First index */ + int64_t idx1; + /** Second index */ + int64_t idx2; + /** Valid bit for the second index */ + bool secondIndexSet; + /** Number of misses currently recorded */ + int numMisses; + /** + * Potential BaseAddr candidates for each recorded miss. + * The number of candidates per miss is determined by the number of + * elements in the shiftValues array. + */ + std::vector> baseAddr; + + IndirectPatternDetectorEntry(unsigned int num_addresses, + unsigned int num_shifts) + : idx1(0), idx2(0), secondIndexSet(false), numMisses(0), + baseAddr(num_addresses, std::vector(num_shifts)) + {} + + void reset() override { + idx1 = 0; + idx2 = 0; + secondIndexSet = false; + numMisses = 0; + setInvalid(); + } + }; + /** Indirect Pattern Detector (IPD) table */ + AssociativeSet ipd; + + /** Entry currently tracking misses */ + IndirectPatternDetectorEntry *ipdEntryTrackingMisses; + + /** Byte order used to access the cache */ + const ByteOrder byteOrder; + + /** + * Allocate or update an entry in the IPD + * @param pt_entry Pointer to the associated page table entry + * @param index Detected first index value + */ + void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry, + int64_t index); + /** + * Update an IPD entry with a detected miss address, when the first index + * is being tracked + * @param miss_addr The address that caused the miss + */ + void trackMissIndex1(Addr miss_addr); + + /** + * Update an IPD entry with a detected miss address, when the second index + * is being tracked + * @param miss_addr The address that caused the miss + */ + void trackMissIndex2(Addr miss_addr); + + /** + * Checks if an access to the cache matches any active PT entry, if so, + * the indirect confidence counter is incremented + * @param addr address of the access + */ + void checkAccessMatchOnActiveEntries(Addr addr); + + public: + IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p); + ~IndirectMemoryPrefetcher() {} + + void calculatePrefetch(const PrefetchInfo &pfi, + std::vector &addresses) override; +}; +#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ -- 2.30.2