From 01a8783d5840b18c90c3ed245cd32f0ea4a56149 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Mon, 30 Dec 2019 01:10:30 +0100 Subject: [PATCH] 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 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/24538 Reviewed-by: Nikos Nikoleris Reviewed-by: Javier Bueno Hedo Maintainer: Nikos Nikoleris Tested-by: kokoro --- .../delta_correlating_prediction_tables.cc | 52 ++++++++----------- .../delta_correlating_prediction_tables.hh | 10 ++-- 2 files changed, 26 insertions(+), 36 deletions(-) diff --git a/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc b/src/mem/cache/prefetch/delta_correlating_prediction_tables.cc index ba9d22f0e..11ea89d6d 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 @@ DeltaCorrelatingPredictionTables::DCPTEntry::invalidate() { 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 @@ DeltaCorrelatingPredictionTables::DCPTEntry::addAddress(Addr address, delta = 0; } } - deltas[deltaPointer] = delta; - deltaPointer = (deltaPointer + 1) % deltas.size(); + deltas.push_back(delta); lastAddress = address; } } @@ -84,15 +83,14 @@ void DeltaCorrelatingPredictionTables::DCPTEntry::getCandidates( std::vector &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 @@ DeltaCorrelatingPredictionTables::DCPTEntry::getCandidates( // 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 c051eca9a..28c99875d 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 @@ class DeltaCorrelatingPredictionTables : public SimObject { /** 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 deltas; + CircularQueue 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) { } -- 2.30.2