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 <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/24538
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Javier Bueno Hedo <javier.bueno@metempsy.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>
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)
{
}
