Ivan Pizarro has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/15095
Change subject: mem-cache: Implementation of the 'Sandbox Based Optimal
Offset Estimation' hardware prefetcher described in the paper
http://comparch-conf.gatech.edu/dpc2/resource/dpc2_brown.pdf
......................................................................
mem-cache: Implementation of the 'Sandbox Based Optimal Offset Estimation'
hardware prefetcher described in the paper
http://comparch-conf.gatech.edu/dpc2/resource/dpc2_brown.pdf
Change-Id: Ieb693b6b2c3d8bdfb6948389ca10e92c85454862
---
M src/mem/cache/prefetch/Prefetcher.py
M src/mem/cache/prefetch/SConscript
A src/mem/cache/prefetch/soe.cc
A src/mem/cache/prefetch/soe.hh
4 files changed, 278 insertions(+), 1 deletion(-)
diff --git a/src/mem/cache/prefetch/Prefetcher.py
b/src/mem/cache/prefetch/Prefetcher.py
index bae235d..e7710aa 100644
--- a/src/mem/cache/prefetch/Prefetcher.py
+++ b/src/mem/cache/prefetch/Prefetcher.py
@@ -137,3 +137,14 @@
cxx_header = "mem/cache/prefetch/tagged.hh"
degree = Param.Int(2, "Number of prefetches to generate")
+
+class SOEPrefetcher(QueuedPrefetcher):
+ type = 'SOEPrefetcher'
+ cxx_class = 'SOEPrefetcher'
+ cxx_header = "mem/cache/prefetch/soe.hh"
+ mshr_size = Param.Int(16, "Entries in the MSHR buffer")
+ latency_buffer_size = Param.Int(32, "Entries in the latency buffer")
+ prefetch_buffer_size = Param.Int(64, "Entries in the prefetch buffer")
+ sequential_prefetchers = Param.Int(9, "Number of sequential
prefetchers")
+ sandbox_entries = Param.Int(1024, "Size of the address buffer")
+ fill_latency = Param.Int(100, "Fix latency to fill a line after a
miss")
diff --git a/src/mem/cache/prefetch/SConscript
b/src/mem/cache/prefetch/SConscript
index 2665d18..fbcff94 100644
--- a/src/mem/cache/prefetch/SConscript
+++ b/src/mem/cache/prefetch/SConscript
@@ -36,4 +36,4 @@
Source('queued.cc')
Source('stride.cc')
Source('tagged.cc')
-
+Source('soe.cc')
diff --git a/src/mem/cache/prefetch/soe.cc b/src/mem/cache/prefetch/soe.cc
new file mode 100644
index 0000000..2035a5f
--- /dev/null
+++ b/src/mem/cache/prefetch/soe.cc
@@ -0,0 +1,132 @@
+/**
+ * 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: Ivan Pizarro
+ */
+
+#include "mem/cache/prefetch/soe.hh"
+
+#include "debug/HWPrefetch.hh"
+#include "params/SOEPrefetcher.hh"
+
+SOEPrefetcher::SOEPrefetcher(const SOEPrefetcherParams *p)
+ : QueuedPrefetcher(p),
+ mshr_size(p->mshr_size),
+ latency_buffer_size(p->latency_buffer_size),
+ prefetch_buffer_size(p->prefetch_buffer_size),
+ sequential_prefetchers(p->sequential_prefetchers),
+ sandbox_entries(p->sandbox_entries),
+ cache_line_size(p->block_size),
+ cache_line_shift(floorLog2(cache_line_size)),
+ score_threshold(p->sandbox_entries/4),
+ average_access_latency((Cycles)p->fill_latency)
+{
+ // Initialize a sandbox for every sequential prefetcher between
+ // -1 and the number of sequential prefetchers defined
+ for (int i = 0; i < sequential_prefetchers; i++) {
+ int stride = (i > 0) ? i : -1;
+ sandboxes.push_back(Sandbox(sandbox_entries, stride));
+ }
+
+ evaluation_finished = false;
+ best_sandbox = 0;
+ accesses = 0;
+}
+
+void
+SOEPrefetcher::Sandbox::insert(Addr addr, Cycles cycle)
+{
+ entries[index].valid = true;
+ entries[index].line = addr + stride;
+ entries[index].cycle_to_arrival = cycle;
+
+ index++;
+
+ if (index == entries.size()) {
+ index = 0;
+ }
+}
+
+void
+SOEPrefetcher::access(Addr access_line, Cycles cycle)
+{
+ accesses++;
+
+ for (int i = 0; i < sequential_prefetchers; i++)
+ {
+ // Search for the address in the FIFO queue
+ for (const SandboxEntry &e: sandboxes[i].entries) {
+ if (e.line == access_line) {
+ sandboxes[i].sandbox_score++;
+ if (e.cycle_to_arrival > cycle) {
+ sandboxes[i].late_score++;
+ }
+ }
+ }
+
+ sandboxes[i].insert(
+ access_line, cycle + average_access_latency);
+
+ if (sandboxes[i].score() > sandboxes[best_sandbox].score()) {
+ best_sandbox = i;
+ }
+ }
+
+ evaluation_finished |= (accesses == sandbox_entries);
+}
+
+void
+SOEPrefetcher::calculatePrefetch(const PacketPtr &pkt,
+ std::vector<AddrPriority> &addresses)
+{
+ Addr pkt_addr = pkt->getAddr();
+ Addr pkt_line = pkt_addr >> cache_line_shift;
+
+ // Add the address currently being access to the MSHR
+ if (mshr_queue.size() == mshr_size) {
+ mshr_queue.pop_front();
+ }
+
+ Cycles cycle = ticksToCycles(curTick());
+
+ mshr_queue.push_back(MshrEntry(pkt_line, cycle));
+
+ access(pkt_line, cycle);
+
+ if (evaluation_finished &&
+ sandboxes[best_sandbox].score() > score_threshold)
+ {
+ Addr pref_line = pkt_line + sandboxes[best_sandbox].stride;
+ addresses.push_back(AddrPriority(pref_line << cache_line_shift,
0));
+ }
+}
+
+SOEPrefetcher*
+SOEPrefetcherParams::create()
+{
+ return new SOEPrefetcher(this);
+}
diff --git a/src/mem/cache/prefetch/soe.hh b/src/mem/cache/prefetch/soe.hh
new file mode 100644
index 0000000..1d32fb3
--- /dev/null
+++ b/src/mem/cache/prefetch/soe.hh
@@ -0,0 +1,134 @@
+/**
+ * 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: Ivan Pizarro
+ */
+
+#ifndef __MEM_CACHE_PREFETCH_SOE_HH__
+#define __MEM_CACHE_PREFETCH_SOE_HH__
+
+#include <queue>
+#include <vector>
+
+#include "mem/cache/prefetch/queued.hh"
+#include "mem/packet.hh"
+
+struct SOEPrefetcherParams;
+
+class SOEPrefetcher : public QueuedPrefetcher
+{
+ private:
+
+ // Prefetcher parameters
+ const int mshr_size;
+ const int latency_buffer_size;
+ const int prefetch_buffer_size;
+ const int sequential_prefetchers;
+ const int sandbox_entries;
+
+ // Cache parameters
+ const int cache_line_size;
+ const int cache_line_shift;
+
+ // Threshold used to issue prefetchers
+ unsigned int score_threshold;
+
+ // MSHR structure
+ struct MshrEntry {
+ Addr address;
+ Cycles cycle;
+ MshrEntry(Addr _address, Cycles _cycle)
+ : address(_address), cycle(_cycle) { }
+ };
+
+ Cycles average_access_latency;
+
+ std::deque<MshrEntry> mshr_queue;
+
+ struct SandboxEntry {
+ // Cache line predicted by the candidate prefetcher
+ Addr line;
+ // Cycles until the simulated prefetch would be filled in the
cache
+ Cycles cycle_to_arrival;
+ // To indicate if it was initialized
+ bool valid;
+
+ SandboxEntry()
+ : valid(false)
+ {}
+ };
+
+ struct Sandbox {
+ // FIFO queue. Max entries is 'sandbox_entries'
+ std::vector<SandboxEntry> entries;
+ // Accesses during the eval period that were present in the
sandbox
+ unsigned int sandbox_score;
+ // Hits in the sandbox that wouldn't have been filled on time
+ unsigned int late_score;
+ // Index for the FIFO
+ unsigned int index;
+ // Sequential stride for this prefetcher
+ int stride;
+
+ Sandbox(unsigned int max_entries, int _stride)
+ : sandbox_score(0), late_score(0), index(0),
stride(_stride)
+ {
+ entries.resize(max_entries);
+ }
+
+ void insert(Addr, Cycles);
+
+ // Calculate the useful score
+ unsigned int score() {
+ return (sandbox_score - late_score);
+ }
+ };
+
+ std::vector<Sandbox> sandboxes;
+
+ // Indicate if the evaluation process finished and prefetches
+ // can be already be issued
+ bool evaluation_finished;
+
+ // Current best sandbox
+ unsigned int best_sandbox;
+
+ // Number of accesses notified to the prefetcher
+ unsigned int accesses;
+
+ // Process an access to the specified line address and update
+ // the sandbox counters counters
+ void access(Addr line, Cycles cycle);
+
+ public:
+ SOEPrefetcher(const SOEPrefetcherParams *p);
+
+ void calculatePrefetch(const PacketPtr &pkt,
+ std::vector<AddrPriority> &addresses)
override;
+};
+
+#endif // __MEM_CACHE_PREFETCH_SOE_HH__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/15095
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: Ieb693b6b2c3d8bdfb6948389ca10e92c85454862
Gerrit-Change-Number: 15095
Gerrit-PatchSet: 1
Gerrit-Owner: Ivan Pizarro <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
