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>

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();