mem-cache: Irregular Stream Buffer Prefetcher

Based in the description of the following publication:
Akanksha Jain and Calvin Lin. 2013. Linearizing irregular memory accesses
for improved correlated prefetching. In Proceedings of the 46th Annual
IEEE/ACM International Symposium on Microarchitecture (MICRO-46). ACM,
New York, NY, USA, 247-259.

Change-Id: Ibeb6abc93ca40ad634df6ed5cf8becb0a49d1165
Reviewed-on: https://gem5-review.googlesource.com/c/15215
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>

4 files changed, 385 insertions, 0 deletions

diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py
index 707741757..2c31de9fc 100644
--- a/src/mem/cache/prefetch/Prefetcher.py
+++ b/src/mem/cache/prefetch/Prefetcher.py
@@ -266,3 +266,46 @@ class DCPTPrefetcher(QueuedPrefetcher):
         DeltaCorrelatingPredictionTables(),
         "Delta Correlating Prediction Tables object")
 
+class IrregularStreamBufferPrefetcher(QueuedPrefetcher):
+    type = "IrregularStreamBufferPrefetcher"
+    cxx_class = "IrregularStreamBufferPrefetcher"
+    cxx_header = "mem/cache/prefetch/irregular_stream_buffer.hh"
+
+    max_counter_value = Param.Unsigned(3,
+        "Maximum value of the confidence counter")
+    chunk_size = Param.Unsigned(256,
+        "Maximum number of addresses in a temporal stream")
+    degree = Param.Unsigned(4, "Number of prefetches to generate")
+    training_unit_assoc = Param.Unsigned(128,
+        "Associativity of the training unit")
+    training_unit_entries = Param.MemorySize("128",
+        "Number of entries of the training unit")
+    training_unit_indexing_policy = Param.BaseIndexingPolicy(
+        SetAssociative(entry_size = 1, assoc = Parent.training_unit_assoc,
+        size = Parent.training_unit_entries),
+        "Indexing policy of the training unit")
+    training_unit_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
+        "Replacement policy of the training unit")
+
+    prefetch_candidates_per_entry = Param.Unsigned(16,
+        "Number of prefetch candidates stored in a SP-AMC entry")
+    address_map_cache_assoc = Param.Unsigned(128,
+        "Associativity of the PS/SP AMCs")
+    address_map_cache_entries = Param.MemorySize("128",
+        "Number of entries of the PS/SP AMCs")
+    ps_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
+        SetAssociative(entry_size = 1,
+        assoc = Parent.address_map_cache_assoc,
+        size = Parent.address_map_cache_entries),
+        "Indexing policy of the Physical-to-Structural Address Map Cache")
+    ps_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
+        LRURP(),
+        "Replacement policy of the Physical-to-Structural Address Map Cache")
+    sp_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
+        SetAssociative(entry_size = 1,
+        assoc = Parent.address_map_cache_assoc,
+        size = Parent.address_map_cache_entries),
+        "Indexing policy of the Structural-to-Physical Address Mao Cache")
+    sp_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
+        LRURP(),
+        "Replacement policy of the Structural-to-Physical Address Map Cache")
diff --git a/src/mem/cache/prefetch/SConscript b/src/mem/cache/prefetch/SConscript
index a5d84fd20..0a209ff18 100644
--- a/src/mem/cache/prefetch/SConscript
+++ b/src/mem/cache/prefetch/SConscript
@@ -35,6 +35,7 @@ SimObject('Prefetcher.py')
 Source('access_map_pattern_matching.cc')
 Source('base.cc')
 Source('delta_correlating_prediction_tables.cc')
+Source('irregular_stream_buffer.cc')
 Source('queued.cc')
 Source('signature_path.cc')
 Source('signature_path_v2.cc')
diff --git a/src/mem/cache/prefetch/irregular_stream_buffer.cc b/src/mem/cache/prefetch/irregular_stream_buffer.cc
new file mode 100644
index 000000000..45aba0b32
--- /dev/null
+++ b/src/mem/cache/prefetch/irregular_stream_buffer.cc
@@ -0,0 +1,210 @@
+/**
+ * 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/irregular_stream_buffer.hh"
+
+#include "debug/HWPrefetch.hh"
+#include "mem/cache/prefetch/associative_set_impl.hh"
+#include "params/IrregularStreamBufferPrefetcher.hh"
+
+IrregularStreamBufferPrefetcher::IrregularStreamBufferPrefetcher(
+    const IrregularStreamBufferPrefetcherParams *p)
+    : QueuedPrefetcher(p), maxCounterValue(p->max_counter_value),
+        chunkSize(p->chunk_size),
+        prefetchCandidatesPerEntry(p->prefetch_candidates_per_entry),
+        degree(p->degree),
+        trainingUnit(p->training_unit_assoc, p->training_unit_entries,
+                     p->training_unit_indexing_policy,
+                     p->training_unit_replacement_policy),
+        psAddressMappingCache(p->address_map_cache_assoc,
+                              p->address_map_cache_entries,
+                              p->ps_address_map_cache_indexing_policy,
+                              p->ps_address_map_cache_replacement_policy,
+                              AddressMappingEntry(prefetchCandidatesPerEntry)),
+        spAddressMappingCache(p->address_map_cache_assoc,
+                              p->address_map_cache_entries,
+                              p->sp_address_map_cache_indexing_policy,
+                              p->sp_address_map_cache_replacement_policy,
+                              AddressMappingEntry(prefetchCandidatesPerEntry)),
+        structuralAddressCounter(0)
+{
+    assert(isPowerOf2(prefetchCandidatesPerEntry));
+}
+
+void
+IrregularStreamBufferPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
+    std::vector<AddrPriority> &addresses)
+{
+    // This prefetcher requires a PC
+    if (!pfi.hasPC()) {
+        return;
+    }
+    bool is_secure = pfi.isSecure();
+    Addr pc = pfi.getPC();
+    Addr addr = blockIndex(pfi.getAddr());
+
+    // Training, if the entry exists, then we found a correlation between
+    // the entry lastAddress (named as correlated_addr_A) and the address of
+    // the current access (named as correlated_addr_B)
+    TrainingUnitEntry *entry = trainingUnit.findEntry(pc, is_secure);
+    bool correlated_addr_found = false;
+    Addr correlated_addr_A = 0;
+    Addr correlated_addr_B = 0;
+    if (entry != nullptr && entry->lastAddressSecure == is_secure) {
+        trainingUnit.accessEntry(entry);
+        correlated_addr_found = true;
+        correlated_addr_A = entry->lastAddress;
+        correlated_addr_B = addr;
+    } else {
+        entry = trainingUnit.findVictim(pc);
+        assert(entry != nullptr);
+
+        trainingUnit.insertEntry(pc, is_secure, entry);
+    }
+    // Update the entry
+    entry->lastAddress = addr;
+    entry->lastAddressSecure = is_secure;
+
+    if (correlated_addr_found) {
+        // If a correlation was found, update the Physical-to-Structural
+        // table accordingly
+        AddressMapping &mapping_A = getPSMapping(correlated_addr_A, is_secure);
+        AddressMapping &mapping_B = getPSMapping(correlated_addr_B, is_secure);
+        if (mapping_A.counter > 0 && mapping_B.counter > 0) {
+            // Entry for A and B
+            if (mapping_B.address == (mapping_A.address + 1)) {
+                if (mapping_B.counter < maxCounterValue) {
+                    mapping_B.counter += 1;
+                }
+            } else {
+                if (mapping_B.counter == 1) {
+                    // counter would hit 0, reassign address
+                    mapping_B.counter = 1;
+                    mapping_B.address = mapping_A.address + 1;
+                    addStructuralToPhysicalEntry(mapping_B.address, is_secure,
+                            correlated_addr_B);
+                } else {
+                    mapping_B.counter -= 1;
+                }
+            }
+        } else {
+            if (mapping_A.counter == 0) {
+                // if A is not valid, generate a new structural address
+                mapping_A.counter = 1;
+                mapping_A.address = structuralAddressCounter;
+                structuralAddressCounter += chunkSize;
+                addStructuralToPhysicalEntry(mapping_A.address,
+                        is_secure, correlated_addr_A);
+            }
+            mapping_B.counter = 1;
+            mapping_B.address = mapping_A.address + 1;
+            // update SP-AMC
+            addStructuralToPhysicalEntry(mapping_B.address, is_secure,
+                    correlated_addr_B);
+        }
+    }
+
+    // Use the PS mapping to predict future accesses using the current address
+    // - Look for the structured address
+    // - if it exists, use it to generate prefetches for the subsequent
+    //   addresses in ascending order, as many as indicated by the degree
+    //   (given the structured address S, prefetch S+1, S+2, .. up to S+degree)
+    Addr amc_address = addr / prefetchCandidatesPerEntry;
+    Addr map_index   = addr % prefetchCandidatesPerEntry;
+    AddressMappingEntry *ps_am = psAddressMappingCache.findEntry(amc_address,
+                                                                 is_secure);
+    if (ps_am != nullptr) {
+        AddressMapping &mapping = ps_am->mappings[map_index];
+        if (mapping.counter > 0) {
+            Addr sp_address = mapping.address / prefetchCandidatesPerEntry;
+            Addr sp_index   = mapping.address % prefetchCandidatesPerEntry;
+            AddressMappingEntry *sp_am =
+                spAddressMappingCache.findEntry(sp_address, is_secure);
+            assert(sp_am != nullptr);
+            for (unsigned d = 1;
+                    d <= degree && (sp_index + d) < prefetchCandidatesPerEntry;
+                    d += 1)
+            {
+                AddressMapping &spm = sp_am->mappings[sp_index + d];
+                //generate prefetch
+                if (spm.counter > 0) {
+                    Addr pf_addr = spm.address << lBlkSize;
+                    addresses.push_back(AddrPriority(pf_addr, 0));
+                }
+            }
+        }
+    }
+}
+
+IrregularStreamBufferPrefetcher::AddressMapping&
+IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr, bool is_secure)
+{
+    Addr amc_address = paddr / prefetchCandidatesPerEntry;
+    Addr map_index   = paddr % prefetchCandidatesPerEntry;
+    AddressMappingEntry *ps_entry =
+        psAddressMappingCache.findEntry(amc_address, is_secure);
+    if (ps_entry != nullptr) {
+        // A PS-AMC line already exists
+        psAddressMappingCache.accessEntry(ps_entry);
+    } else {
+        ps_entry = psAddressMappingCache.findVictim(amc_address);
+        assert(ps_entry != nullptr);
+
+        psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry);
+    }
+    return ps_entry->mappings[map_index];
+}
+
+void
+IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry(
+    Addr structural_address, bool is_secure, Addr physical_address)
+{
+    Addr amc_address = structural_address / prefetchCandidatesPerEntry;
+    Addr map_index   = structural_address % prefetchCandidatesPerEntry;
+    AddressMappingEntry *sp_entry =
+        spAddressMappingCache.findEntry(amc_address, is_secure);
+    if (sp_entry != nullptr) {
+        spAddressMappingCache.accessEntry(sp_entry);
+    } else {
+        sp_entry = spAddressMappingCache.findVictim(amc_address);
+        assert(sp_entry != nullptr);
+
+        spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry);
+    }
+    AddressMapping &mapping = sp_entry->mappings[map_index];
+    mapping.address = physical_address;
+    mapping.counter = 1;
+}
+
+IrregularStreamBufferPrefetcher*
+IrregularStreamBufferPrefetcherParams::create()
+{
+    return new IrregularStreamBufferPrefetcher(this);
+}
diff --git a/src/mem/cache/prefetch/irregular_stream_buffer.hh b/src/mem/cache/prefetch/irregular_stream_buffer.hh
new file mode 100644
index 000000000..47038cbb7
--- /dev/null
+++ b/src/mem/cache/prefetch/irregular_stream_buffer.hh
@@ -0,0 +1,131 @@
+/**
+ * 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 Irregular Stream Buffer prefetcher
+ * Reference:
+ *   Jain, A., & Lin, C. (2013, December). Linearizing irregular memory
+ *   accesses for improved correlated prefetching. In Proceedings of the
+ *   46th Annual IEEE/ACM International Symposium on Microarchitecture
+ *   (pp. 247-259). ACM.
+ */
+
+#ifndef __MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__
+#define __MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__
+
+#include "base/callback.hh"
+#include "mem/cache/prefetch/associative_set.hh"
+#include "mem/cache/prefetch/queued.hh"
+
+struct IrregularStreamBufferPrefetcherParams;
+
+class IrregularStreamBufferPrefetcher : public QueuedPrefetcher
+{
+    /** Maximum value of the confidence counters */
+    const unsigned maxCounterValue;
+    /** Size in bytes of a temporal stream */
+    const size_t chunkSize;
+    /** Number of prefetch candidates per Physical-to-Structural entry */
+    const unsigned prefetchCandidatesPerEntry;
+    /** Number of maximum prefetches requests created when predicting */
+    const unsigned degree;
+
+    /**
+     * Training Unit Entry datatype, it holds the last accessed address and
+     * its secure flag
+     */
+    struct TrainingUnitEntry : public TaggedEntry {
+        Addr lastAddress;
+        bool lastAddressSecure;
+    };
+    /** Map of PCs to Training unit entries */
+    AssociativeSet<TrainingUnitEntry> trainingUnit;
+
+    /** Address Mapping entry, holds an address and a confidence counter */
+    struct AddressMapping {
+        Addr address;
+        unsigned counter;
+        AddressMapping() : address(0), counter(0)
+        {}
+    };
+
+    /**
+     * Maps a set of contiguous addresses to another set of (not necessarily
+     * contiguos) addresses, with their corresponding confidence counters
+     */
+    struct AddressMappingEntry : public TaggedEntry {
+        std::vector<AddressMapping> mappings;
+        AddressMappingEntry(size_t num_mappings) : mappings(num_mappings)
+        {}
+        void reset() override
+        {
+            for (auto &entry : mappings) {
+                entry.address = 0;
+                entry.counter = 0;
+            }
+        }
+    };
+
+    /** Physical-to-Structured mappings table */
+    AssociativeSet<AddressMappingEntry> psAddressMappingCache;
+    /** Structured-to-Physical mappings table */
+    AssociativeSet<AddressMappingEntry> spAddressMappingCache;
+    /**
+     * Counter of allocated structural addresses, increased by "chunkSize",
+     * each time a new structured address is allocated
+     */
+    uint64_t structuralAddressCounter;
+
+    /**
+     * Add a mapping to the Structured-to-Physica mapping table
+     * @param structuralAddress structural address
+     * @param is_secure whether this page is inside the secure memory area
+     * @param physical_address corresponding physical address
+     */
+    void addStructuralToPhysicalEntry(Addr structuralAddress, bool is_secure,
+                                      Addr physical_address);
+
+    /**
+     * Obtain the Physical-to-Structured mapping entry of the given physical
+     * address. If the entry does not exist a new one is allocated, replacing
+     * an existing one if needed.
+     * @param paddr physical address
+     * @param is_secure whether this page is inside the secure memory area
+     * @result reference to the entry
+     */
+    AddressMapping& getPSMapping(Addr paddr, bool is_secure);
+  public:
+    IrregularStreamBufferPrefetcher(
+        const IrregularStreamBufferPrefetcherParams *p);
+    ~IrregularStreamBufferPrefetcher() {}
+    void calculatePrefetch(const PrefetchInfo &pfi,
+                           std::vector<AddrPriority> &addresses) override;
+};
+#endif//__MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__