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>
diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py
index 7077417..2c31de9 100644
--- a/src/mem/cache/prefetch/Prefetcher.py
+++ b/src/mem/cache/prefetch/Prefetcher.py
@@ -266,3 +266,46 @@
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 a5d84fd..0a209ff 100644
--- a/src/mem/cache/prefetch/SConscript
+++ b/src/mem/cache/prefetch/SConscript
@@ -35,6 +35,7 @@
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 0000000..45aba0b
--- /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 0000000..47038cb
--- /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__
