diff options
| -rw-r--r-- | src/mem/cache/prefetch/Prefetcher.py | 29 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/SConscript | 1 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/base.hh | 5 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/delta_correlating_prediction_tables.cc | 174 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/delta_correlating_prediction_tables.hh | 137 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/queued.hh | 3 |
6 files changed, 347 insertions, 2 deletions
diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py index 827a66b0f..707741757 100644 --- a/src/mem/cache/prefetch/Prefetcher.py +++ b/src/mem/cache/prefetch/Prefetcher.py @@ -237,3 +237,32 @@ class AccessMapPatternMatchingPrefetcher(QueuedPrefetcher): epoch_cycles = Param.Cycles(256000, "Cycles in an epoch period") offchip_memory_latency = Param.Latency("30ns", "Memory latency used to compute the required memory bandwidth") + +class DeltaCorrelatingPredictionTables(SimObject): + type = 'DeltaCorrelatingPredictionTables' + cxx_class = 'DeltaCorrelatingPredictionTables' + cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh" + deltas_per_entry = Param.Unsigned(20, + "Number of deltas stored in each table entry") + delta_bits = Param.Unsigned(12, "Bits per delta") + delta_mask_bits = Param.Unsigned(8, + "Lower bits to mask when comparing deltas") + table_entries = Param.MemorySize("128", + "Number of entries in the table") + table_assoc = Param.Unsigned(128, + "Associativity of the table") + table_indexing_policy = Param.BaseIndexingPolicy( + SetAssociative(entry_size = 1, assoc = Parent.table_assoc, + size = Parent.table_entries), + "Indexing policy of the table") + table_replacement_policy = Param.BaseReplacementPolicy(LRURP(), + "Replacement policy of the table") + +class DCPTPrefetcher(QueuedPrefetcher): + type = 'DCPTPrefetcher' + cxx_class = 'DCPTPrefetcher' + cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh" + dcpt = Param.DeltaCorrelatingPredictionTables( + DeltaCorrelatingPredictionTables(), + "Delta Correlating Prediction Tables object") + diff --git a/src/mem/cache/prefetch/SConscript b/src/mem/cache/prefetch/SConscript index f9582b580..a5d84fd20 100644 --- a/src/mem/cache/prefetch/SConscript +++ b/src/mem/cache/prefetch/SConscript @@ -34,6 +34,7 @@ SimObject('Prefetcher.py') Source('access_map_pattern_matching.cc') Source('base.cc') +Source('delta_correlating_prediction_tables.cc') Source('queued.cc') Source('signature_path.cc') Source('signature_path_v2.cc') diff --git a/src/mem/cache/prefetch/base.hh b/src/mem/cache/prefetch/base.hh index 06f77492d..de275f85c 100644 --- a/src/mem/cache/prefetch/base.hh +++ b/src/mem/cache/prefetch/base.hh @@ -76,7 +76,8 @@ class BasePrefetcher : public ClockedObject }; std::vector<PrefetchListener *> listeners; - protected: + + public: /** * Class containing the information needed by the prefetch to train and @@ -168,6 +169,8 @@ class BasePrefetcher : public ClockedObject PrefetchInfo(PrefetchInfo const &pfi, Addr addr); }; + protected: + // PARAMETERS /** Pointr to the parent cache. */ diff --git a/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc b/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc new file mode 100644 index 000000000..4dbd596a2 --- /dev/null +++ b/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc @@ -0,0 +1,174 @@ +/** + * 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/delta_correlating_prediction_tables.hh" + +#include "debug/HWPrefetch.hh" +#include "mem/cache/prefetch/associative_set_impl.hh" +#include "params/DCPTPrefetcher.hh" +#include "params/DeltaCorrelatingPredictionTables.hh" + +DeltaCorrelatingPredictionTables::DeltaCorrelatingPredictionTables( + DeltaCorrelatingPredictionTablesParams *p) : SimObject(p), + deltaBits(p->delta_bits), deltaMaskBits(p->delta_mask_bits), + table(p->table_assoc, p->table_entries, p->table_indexing_policy, + p->table_replacement_policy, DCPTEntry(p->deltas_per_entry)) +{ +} + +void +DeltaCorrelatingPredictionTables::DCPTEntry::reset() +{ + for (auto &delta : deltas) { + delta = 0; + } + lastAddress = 0; + deltaPointer = 0; +} + +void +DeltaCorrelatingPredictionTables::DCPTEntry::addAddress(Addr address, + unsigned int delta_bits) +{ + if ((address - lastAddress) != 0) { + Addr delta = address - lastAddress; + // Account for the sign bit + Addr max_positive_delta = (1 << (delta_bits-1)) - 1; + if (address > lastAddress) { + // check positive delta overflow + if (delta > max_positive_delta) { + delta = 0; + } + } else { + // check negative delta overflow + if (lastAddress - address > (max_positive_delta + 1)) { + delta = 0; + } + } + deltas[deltaPointer] = delta; + deltaPointer = (deltaPointer + 1) % deltas.size(); + lastAddress = address; + } +} + +void +DeltaCorrelatingPredictionTables::DCPTEntry::getCandidates( + std::vector<QueuedPrefetcher::AddrPriority> &pfs, unsigned int mask) const +{ + // most recent index + unsigned int last = (deltaPointer - 1) % deltas.size(); + // second most recent index + unsigned int last_prev = (deltaPointer - 2) % deltas.size(); + int delta_0 = deltas[last_prev]; + int delta_1 = deltas[last]; + + // a delta 0 means that it overflowed, we can not match it + if (delta_0 == 0 || delta_1 == 0) { + return; + } + + // Try to find the two most recent deltas in a previous position on the + // delta circular array, if found, start issuing prefetches using the + // remaining deltas (adding each delta to the last Addr to generate the + // prefetched address. + + // oldest index + int idx_0 = deltaPointer + 1; + // second oldest index + int idx_1 = deltaPointer + 2; + for (int i = 0; i < deltas.size() - 2; i += 1) { + int this_delta_0 = deltas[(idx_0 + i) % deltas.size()]; + int this_delta_1 = deltas[(idx_1 + i) % deltas.size()]; + if ((this_delta_0 >> mask) == (delta_0 >> mask) && + (this_delta_1 >> mask) == (delta_1 >> mask)) { + Addr addr = lastAddress; + // Pattern found, issue prefetches with the remaining deltas after + // this pair + i += 2; // skip the matching pair + do { + int pf_delta = deltas[(idx_0 + i) % deltas.size()]; + addr += pf_delta; + pfs.push_back(QueuedPrefetcher::AddrPriority(addr, 0)); + i += 1; + } while (i < deltas.size() - 2); + } + } +} + +void +DeltaCorrelatingPredictionTables::calculatePrefetch( + const BasePrefetcher::PrefetchInfo &pfi, + std::vector<QueuedPrefetcher::AddrPriority> &addresses) +{ + if (!pfi.hasPC()) { + DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); + return; + } + Addr address = pfi.getAddr(); + Addr pc = pfi.getPC(); + // Look up table entry, is_secure is unused in findEntry because we + // index using the pc + DCPTEntry *entry = table.findEntry(pc, false /* unused */); + if (entry != nullptr) { + entry->addAddress(address, deltaBits); + //Delta correlating + entry->getCandidates(addresses, deltaMaskBits); + } else { + entry = table.findVictim(pc); + + table.insertEntry(pc, false /* unused */, entry); + + entry->lastAddress = address; + } +} + +DeltaCorrelatingPredictionTables * +DeltaCorrelatingPredictionTablesParams::create() +{ + return new DeltaCorrelatingPredictionTables(this); +} + +DCPTPrefetcher::DCPTPrefetcher(const DCPTPrefetcherParams *p) + : QueuedPrefetcher(p), dcpt(*p->dcpt) +{ +} + +void +DCPTPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) +{ + dcpt.calculatePrefetch(pfi, addresses); +} + +DCPTPrefetcher* +DCPTPrefetcherParams::create() +{ + return new DCPTPrefetcher(this); +} diff --git a/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh b/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh new file mode 100644 index 000000000..86cf9574c --- /dev/null +++ b/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh @@ -0,0 +1,137 @@ +/** + * 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 __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_ +#define __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_ + +#include "mem/cache/prefetch/associative_set.hh" +#include "mem/cache/prefetch/queued.hh" + +struct DeltaCorrelatingPredictionTablesParams; + +/** + * Delta Correlating Prediction Tables Prefetcher + * References: + * Multi-level hardware prefetching using low complexity delta correlating + * prediction tables with partial matching. + * Marius Grannaes, Magnus Jahre, and Lasse Natvig. 2010. + * In Proceedings of the 5th international conference on High Performance + * Embedded Architectures and Compilers (HiPEAC'10) + * + * The filter feature is not implemented as gem5 already drops redundant + * prefetches. + * The main prefetcher logic is implemented on a separate SimObject as there + * are other prefetcher that can rehuse this component. + */ + +class DeltaCorrelatingPredictionTables : public SimObject +{ + /** Number of bits of each delta */ + const unsigned int deltaBits; + /** Number of lower bits to ignore from the deltas */ + const unsigned int deltaMaskBits; + + /** DCPT Table entry datatype */ + struct DCPTEntry : public TaggedEntry + { + /** Last accessed address */ + Addr lastAddress; + /** + * Position of the first free entry, or the oldest element, if it is + * full + */ + unsigned int deltaPointer; + /** Stored deltas */ + std::vector<Addr> deltas; + + /** + * Constructor + * @param num_deltas number of deltas stored in the entry + */ + DCPTEntry(unsigned int num_deltas) : lastAddress(0), deltaPointer(0), + deltas(num_deltas) + {} + + /** Reset callback called when invalidating the entry */ + void reset() override; + + /** + * Adds an address to the entry, if the entry already existed, a delta + * will be generated + * @param address address to add + * @param delta_num_bits number of bits of the delta + */ + void addAddress(Addr address, unsigned int delta_num_bits); + + /** + * Attempt to generate prefetch candidates using the two most recent + * deltas. Prefetch candidates are added to the provided vector. + * @param pfs reference to a vector where candidates will be added + * @param mask_bits the number of lower bits that should be masked + * (ignored) when comparing deltas + */ + void getCandidates(std::vector<QueuedPrefetcher::AddrPriority> &pfs, + unsigned int mask_bits) const; + + }; + /** The main table */ + AssociativeSet<DCPTEntry> table; + + public: + DeltaCorrelatingPredictionTables( + DeltaCorrelatingPredictionTablesParams *p); + ~DeltaCorrelatingPredictionTables() + {} + + /** + * Computes the prefetch candidates given a prefetch event. + * @param pfi The prefetch event information + * @param addresses prefetch candidates generated + */ + void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi, + std::vector<QueuedPrefetcher::AddrPriority> &addresses); + +}; + +struct DCPTPrefetcherParams; + +/** The prefetcher object using the DCPT */ +class DCPTPrefetcher : public QueuedPrefetcher +{ + /** DCPT object */ + DeltaCorrelatingPredictionTables &dcpt; + public: + DCPTPrefetcher(const DCPTPrefetcherParams *p); + ~DCPTPrefetcher() + {} + void calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) override; +}; +#endif//__MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_ diff --git a/src/mem/cache/prefetch/queued.hh b/src/mem/cache/prefetch/queued.hh index 1c63977b4..97a7ec6bc 100644 --- a/src/mem/cache/prefetch/queued.hh +++ b/src/mem/cache/prefetch/queued.hh @@ -89,7 +89,6 @@ class QueuedPrefetcher : public BasePrefetcher return !(*this > that); } }; - using AddrPriority = std::pair<Addr, int32_t>; std::list<DeferredPacket> pfq; @@ -126,6 +125,8 @@ class QueuedPrefetcher : public BasePrefetcher Stats::Scalar pfSpanPage; public: + using AddrPriority = std::pair<Addr, int32_t>; + QueuedPrefetcher(const QueuedPrefetcherParams *p); virtual ~QueuedPrefetcher(); |