Nikos Nikoleris has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/15316
Change subject: mem-cache: Add LRU replacement policy GTest
......................................................................
mem-cache: Add LRU replacement policy GTest
Change-Id: I0b9c6fd8dff79b6ac125127f68a50fbc88873be4
Signed-off-by: Nikos Nikoleris <nikos.nikole...@arm.com>
---
M src/mem/cache/replacement_policies/SConscript
A src/mem/cache/replacement_policies/lru_rp.test.cc
2 files changed, 185 insertions(+), 0 deletions(-)
diff --git a/src/mem/cache/replacement_policies/SConscript
b/src/mem/cache/replacement_policies/SConscript
index 468cf7d..643b9a4 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -37,6 +37,7 @@
Source('fifo_rp.cc')
Source('lfu_rp.cc')
Source('lru_rp.cc')
+GTest('LRURPtest', 'lru_rp.test.cc', 'lru_rp.cc')
Source('mru_rp.cc')
Source('random_rp.cc')
Source('second_chance_rp.cc')
diff --git a/src/mem/cache/replacement_policies/lru_rp.test.cc
b/src/mem/cache/replacement_policies/lru_rp.test.cc
new file mode 100644
index 0000000..efaf956
--- /dev/null
+++ b/src/mem/cache/replacement_policies/lru_rp.test.cc
@@ -0,0 +1,184 @@
+/*
+ * Copyright (c) 2019 ARM Limited
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder. You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
+ * 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: Nikos Nikoleris
+ */
+
+#include <gtest/gtest.h>
+
+#include <iostream>
+#include <list>
+#include <random>
+
+#include "mem/cache/replacement_policies/lru_rp.hh"
+#include "params/LRURP.hh"
+#include "sim/eventq.hh"
+
+#define NUM_BLOCKS 100
+#define NUM_TESTS 1000000
+
+class LRUTestData : public testing::Test
+{
+ protected:
+ void SetUp() override
+ {
+ EventQueue *event_queue = getEventQueue(0);
+ curEventQueue(event_queue);
+
+ LRURPParams lru_params;
+ lru_params.eventq_index = 0;
+ lru = new LRURP(&lru_params);
+
+ replacementSet.reserve(NUM_BLOCKS);
+
+ for (int i = 0; i < NUM_BLOCKS; i++) {
+ orderedSet.push_front(TestEntry());
+ ReplaceableEntry &blk = orderedSet.front();
+ blk.replacementData = lru->instantiateEntry();
+ lru->touch(blk.replacementData);
+
+ replacementSet.push_back(&blk);
+
+ tick();
+ }
+ };
+
+ void printSet()
+ {
+ std::cout << "[";
+ for (auto blk: orderedSet) {
+ std::cout << blk.getId() << ", ";
+ }
+ std::cout << "\b\b]\n";
+ }
+
+ void tick()
+ {
+ curEventQueue()->setCurTick(curTick() + 1);
+ }
+
+ class TestEntry : public ReplaceableEntry
+ {
+ public:
+ TestEntry() : ReplaceableEntry(), id(counter++) {}
+
+ int getId() { return id; }
+
+ private:
+ static int counter;
+ int id;
+ };
+
+ LRURP *lru;
+
+ std::list<TestEntry> orderedSet;
+ std::vector<ReplaceableEntry*> replacementSet;
+};
+
+int LRUTestData::TestEntry::counter = 0;
+
+TEST_F(LRUTestData, Replace)
+{
+ for (int i = 0; i < NUM_TESTS; i++) {
+ // Replace victim
+ ReplaceableEntry *victim = lru->getVictim(replacementSet);
+ // Make sure victim matches our records
+ ASSERT_EQ(victim, &orderedSet.back());
+
+ // Promote block to the MRU
+ lru->touch(victim->replacementData);
+ auto it = orderedSet.end();
+ --it;
+ orderedSet.splice(orderedSet.begin(), orderedSet, it);
+
+ tick();
+ }
+}
+
+TEST_F(LRUTestData, RandomAccessAndReplace)
+{
+ std::mt19937 gen(42);
+ std::uniform_int_distribution<> dis(0, NUM_BLOCKS - 1);
+
+ for (int i = 0; i < NUM_TESTS; i++) {
+ ASSERT_EQ(orderedSet.size(), NUM_BLOCKS);
+ // Access block
+ auto it = std::next(orderedSet.begin(), dis(gen));
+ // Promote accessed block to the MRU
+ lru->touch(it->replacementData);
+ orderedSet.splice(orderedSet.begin(), orderedSet, it);
+
+ tick();
+
+ // Replace victim
+ ReplaceableEntry *victim = lru->getVictim(replacementSet);
+ // Make sure victim matches our records
+ ASSERT_EQ(victim, &orderedSet.back());
+ // Promote new block to the MRU
+ lru->touch(victim->replacementData);
+ it = orderedSet.end();
+ --it;
+ orderedSet.splice(orderedSet.begin(), orderedSet, it);
+
+ tick();
+ }
+}
+
+TEST_F(LRUTestData, RandomInvalidateAndReplace)
+{
+ std::mt19937 gen(42);
+ std::uniform_int_distribution<> dis(0, NUM_BLOCKS - 1);
+
+ for (int i = 0; i < NUM_TESTS; i++) {
+ ASSERT_EQ(orderedSet.size(), NUM_BLOCKS);
+ // Access block
+ auto it = std::next(orderedSet.begin(), dis(gen));
+ // Demote invalidated block to the LRU
+ lru->invalidate(it->replacementData);
+ orderedSet.splice(orderedSet.end(), orderedSet, it);
+
+ // Replace victim
+ ReplaceableEntry *victim = lru->getVictim(replacementSet);
+ // Make sure victim matches our records
+ ASSERT_EQ(victim, &orderedSet.back());
+ orderedSet.back().getId();
+ // Promote new block to the MRU
+ lru->touch(victim->replacementData);
+ orderedSet.splice(orderedSet.begin(), orderedSet, it);
+
+ tick();
+ }
+}
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/15316
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: I0b9c6fd8dff79b6ac125127f68a50fbc88873be4
Gerrit-Change-Number: 15316
Gerrit-PatchSet: 1
Gerrit-Owner: Nikos Nikoleris <nikos.nikole...@arm.com>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
gem5-dev@gem5.org
http://m5sim.org/mailman/listinfo/gem5-dev
