Daniel Carvalho has submitted this change. ( https://gem5-review.googlesource.com/c/public/gem5/+/24538 )

Change subject: mem-cache: Fix DCPT with CircularQueue
......................................................................

mem-cache: Fix DCPT with CircularQueue

This patch fixes the following bugs:

- Previously when deltaPointer was 0 or 1, getting the last or penultimate deltas would be wrong for non-pow2 deltas.size(). For example, if the last added delta was to position 0, the previous should be in position 19, if deltas.size() = 20.
  However, 0-1=4294967295, and 4294967295%20=15.

- When searching for the previous late and penultimate, the oldest entry was being
  skipped.

Change-Id: Id800b60b77531ac4c2920bb90c15cc8cebb137a9
Signed-off-by: Daniel R. Carvalho <oda...@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/24538
Reviewed-by: Nikos Nikoleris <nikos.nikole...@arm.com>
Reviewed-by: Javier Bueno Hedo <javier.bu...@metempsy.com>
Maintainer: Nikos Nikoleris <nikos.nikole...@arm.com>
Tested-by: kokoro <noreply+kok...@google.com>
---
M src/mem/cache/prefetch/delta_correlating_prediction_tables.cc
M src/mem/cache/prefetch/delta_correlating_prediction_tables.hh
2 files changed, 26 insertions(+), 36 deletions(-)

Approvals:
  Nikos Nikoleris: Looks good to me, approved; Looks good to me, approved
  Javier Bueno Hedo: Looks good to me, but someone else must approve
  kokoro: Regressions pass



diff --git a/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc b/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc
index ba9d22f..11ea89d 100644
--- a/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc
+++ b/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc
@@ -48,11 +48,11 @@
 {
     TaggedEntry::invalidate();

-    for (auto &delta : deltas) {
-        delta = 0;
+    deltas.flush();
+    while (!deltas.full()) {
+        deltas.push_back(0);
     }
     lastAddress = 0;
-    deltaPointer = 0;
 }

 void
@@ -74,8 +74,7 @@
                 delta = 0;
             }
         }
-        deltas[deltaPointer] = delta;
-        deltaPointer = (deltaPointer + 1) % deltas.size();
+        deltas.push_back(delta);
         lastAddress = address;
     }
 }
@@ -84,15 +83,14 @@
 DeltaCorrelatingPredictionTables::DCPTEntry::getCandidates(
     std::vector<Queued::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];
+    assert(deltas.full());
+
+    // Get the two most recent deltas
+    const int delta_penultimate = *(deltas.end() - 2);
+    const int delta_last = *(deltas.end() - 1);

     // a delta 0 means that it overflowed, we can not match it
-    if (delta_0 == 0 || delta_1 == 0) {
+    if (delta_last == 0 || delta_penultimate == 0) {
         return;
     }

@@ -100,26 +98,22 @@
     // 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)) {
+    auto it = deltas.begin();
+    for (; it != (deltas.end() - 2); ++it) {
+        const int prev_delta_penultimate = *it;
+        const int prev_delta_last = *(it + 1);
+ if ((prev_delta_penultimate >> mask) == (delta_penultimate >> mask) &&
+            (prev_delta_last >> mask) == (delta_last >> mask)) {
+ // Pattern found. Skip the matching pair and issue prefetches with
+            // the remaining deltas
+            it += 2;
             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()];
+            while (it != deltas.end()) {
+                const int pf_delta = *(it++);
                 addr += pf_delta;
                 pfs.push_back(Queued::AddrPriority(addr, 0));
-                i += 1;
-            } while (i < deltas.size() - 2);
+            }
+            break;
         }
     }
 }
diff --git a/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh b/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh
index c051eca..28c9987 100644
--- a/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh
+++ b/src/mem/cache/prefetch/delta_correlating_prediction_tables.hh
@@ -29,6 +29,7 @@
 #ifndef __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_
 #define __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_

+#include "base/circular_queue.hh"
 #include "mem/cache/prefetch/associative_set.hh"
 #include "mem/cache/prefetch/queued.hh"

@@ -64,20 +65,15 @@
     {
         /** 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;
+        CircularQueue<Addr> deltas;

         /**
          * Constructor
          * @param num_deltas number of deltas stored in the entry
          */
         DCPTEntry(unsigned int num_deltas)
- : TaggedEntry(), lastAddress(0), deltaPointer(0), deltas(num_deltas)
+          : TaggedEntry(), lastAddress(0), deltas(num_deltas)
         {
         }


--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/24538
To unsubscribe, or for help writing mail filters, visit https://gem5-review.googlesource.com/settings

Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: Id800b60b77531ac4c2920bb90c15cc8cebb137a9
Gerrit-Change-Number: 24538
Gerrit-PatchSet: 3
Gerrit-Owner: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-Reviewer: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-Reviewer: Javier Bueno Hedo <javier.bu...@metempsy.com>
Gerrit-Reviewer: Nikos Nikoleris <nikos.nikole...@arm.com>
Gerrit-Reviewer: kokoro <noreply+kok...@google.com>
Gerrit-MessageType: merged
_______________________________________________
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s

Reply via email to