mem-cache: Added the Delta Correlating Prediction Tables Prefetcher
Reference:
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)
Change-Id: I7b5d7ede9284862a427cfd5693a47652a69ed49d
Reviewed-on: https://gem5-review.googlesource.com/c/16062
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>
diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py
index 827a66b..7077417 100644
--- a/src/mem/cache/prefetch/Prefetcher.py
+++ b/src/mem/cache/prefetch/Prefetcher.py
@@ -237,3 +237,32 @@
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 f9582b5..a5d84fd 100644
--- a/src/mem/cache/prefetch/SConscript
+++ b/src/mem/cache/prefetch/SConscript
@@ -34,6 +34,7 @@
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 06f7749..de275f8 100644
--- a/src/mem/cache/prefetch/base.hh
+++ b/src/mem/cache/prefetch/base.hh
@@ -76,7 +76,8 @@
};
std::vector<PrefetchListener *> listeners;
- protected:
+
+ public:
/**
* Class containing the information needed by the prefetch to train and
@@ -168,6 +169,8 @@
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 0000000..4dbd596
--- /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 0000000..86cf957
--- /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 1c63977..97a7ec6 100644
--- a/src/mem/cache/prefetch/queued.hh
+++ b/src/mem/cache/prefetch/queued.hh
@@ -89,7 +89,6 @@
return !(*this > that);
}
};
- using AddrPriority = std::pair<Addr, int32_t>;
std::list<DeferredPacket> pfq;
@@ -126,6 +125,8 @@
Stats::Scalar pfSpanPage;
public:
+ using AddrPriority = std::pair<Addr, int32_t>;
+
QueuedPrefetcher(const QueuedPrefetcherParams *p);
virtual ~QueuedPrefetcher();
