src/mem/cache/tags/dueling.test.cc - public/gem5 - Git at Google

 /*
  * Copyright (c) 2019, 2020 Inria
  * 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.
  */

 #include <gtest/gtest.h>

 #include <cstddef>
 #include <cstdint>
 #include <memory>
 #include <tuple>
 #include <vector>

 #include "base/sat_counter.hh"
 #include "mem/cache/tags/dueling.hh"

 using namespace gem5;

 /**
  * Test whether dueler provides correct sampling functionality and assigns
  * teams correctly.
  */
 TEST(DuelerTest, SetSample)
 {
     const int num_sampled_ids = 3;
     bool team;
     Dueler dueler;

     // Initially nobody is sampled
     for (int id = 0; id < 64; id++) {
         ASSERT_FALSE(dueler.isSample(1ULL << id, team));
     }

     // Mark the first num_sampled_ids as samples and assign alternating teams
     team = false;
     for (int id = 0; id < num_sampled_ids; id++) {
         team = !team;
         dueler.setSample(1ULL << id, team);
     }

     // Make sure that only the entries marked as samples previously are samples
     bool expected_team = false;
     for (int id = 0; id < 64; id++) {
         expected_team = !expected_team;
         const bool is_sample = dueler.isSample(1ULL << id, team);
         if (id < num_sampled_ids) {
             ASSERT_TRUE(is_sample);
             ASSERT_EQ(team, expected_team);
         } else {
             ASSERT_FALSE(is_sample);
         }
     }

 }

 // We assume that the monitors are assigned sequential powers of
 // two ids starting from 1
 static uint64_t monitor_id = 0;

 class DuelingMonitorTest : public testing::TestWithParam<
     std::tuple<unsigned, std::size_t, std::size_t, unsigned, double, double>>
 {
   protected:
     /** A vector simulating a table-like structure. */
     std::vector<Dueler> entries;

     /** The constituency size, acquired from params. */
     std::size_t constituencySize;

     /** The size of a team, acquired from params. */
     std::size_t teamSize;

     /** The number of bits in the selector, acquired from params. */
     unsigned numBits;

     /** The low threshold to change winner, acquired from params. */
     double lowThreshold;

     /** The high threshold to change winner, acquired from params. */
     double highThreshold;

     /** The monitor instance being tested. */
     std::unique_ptr<DuelingMonitor> monitor;

     void
     SetUp() override
     {
         const unsigned num_entries = std::get<0>(GetParam());
         constituencySize = std::get<1>(GetParam());
         teamSize = std::get<2>(GetParam());
         numBits = std::get<3>(GetParam());
         lowThreshold = std::get<4>(GetParam());
         highThreshold = std::get<5>(GetParam());

         monitor.reset(new DuelingMonitor(constituencySize, teamSize, numBits,
             lowThreshold, highThreshold));

         // Initialize entries
         entries.resize(num_entries);
         for (auto& entry : entries) {
             monitor->initEntry(&entry);
         }
     }

     void
     TearDown() override
     {
         // Due to the way the DuelingMonitor works, this id is not testable
         // anymore, so move to the next
         monitor_id++;
     }
 };

 /**
  * Test whether entry initialization creates exactly the amount of samples
  * requested.
  */
 TEST_P(DuelingMonitorTest, CountSamples)
 {
     const int expected_num_samples =
         (entries.size() / constituencySize) * teamSize;

     // Check whether the number of samples match expectation.
     // Both teams must also have the same number of samples
     int count_samples_true = 0;
     int count_samples_false = 0;
     bool team;
     for (auto& entry : entries) {
         if (entry.isSample(1ULL << monitor_id, team)) {
             if (team) {
                 count_samples_true++;
             } else {
                 count_samples_false++;
             }
         }
     }
     ASSERT_EQ(count_samples_true, count_samples_false);
     ASSERT_EQ(count_samples_true, expected_num_samples);
 }

 /** Test winner selection with multiple different threshold configurations. */
 TEST_P(DuelingMonitorTest, WinnerSelection)
 {
     SatCounter32 expected_selector(numBits);
     expected_selector.saturate();
     expected_selector >>= 1;

     // Initialize entries, and save a pointer to a sample of each
     // team, and one no sample
     int team_true_index = -1;
     int team_false_index = -1;
     int no_sample_index = -1;
     for (int index = 0; index < entries.size(); index++) {
         bool team;
         if (entries[index].isSample(1ULL << monitor_id, team)) {
             if (team) {
                 team_true_index = index;
             } else {
                 team_false_index = index;
             }
         } else {
             no_sample_index = index;
         }
     }
     ASSERT_TRUE(team_true_index >= 0);
     ASSERT_TRUE(team_false_index >= 0);

     // Duel for team true only. If the monitor starts predicting false
     // the threshold to use is the higher one. Otherwise, we should
     // start expecting true to be the winner, and thus we use the
     // low threshold
     bool current_winner = monitor->getWinner();
     double threshold = current_winner ? lowThreshold : highThreshold;
     for (; expected_selector.calcSaturation() < 1.0;
         expected_selector++) {
         ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
             monitor->getWinner());
         monitor->sample(&entries[team_true_index]);
     }
     current_winner = monitor->getWinner();
     ASSERT_TRUE(current_winner);

     // Duel for no sample. Should not change winner
     if (no_sample_index >= 0) {
         for (int i = 0; i < 200; i++) {
             monitor->sample(&entries[no_sample_index]);
         }
         ASSERT_EQ(current_winner, monitor->getWinner());
     }

     // Duel for team false only. Now that we know that team true
     // is winning, the low threshold must be passed in order to
     // make team false win the duel
     threshold = lowThreshold;
     for (; expected_selector.calcSaturation() > 0.0;
         expected_selector--) {
         ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
             monitor->getWinner());
         monitor->sample(&entries[team_false_index]);
     }
     current_winner = monitor->getWinner();
     ASSERT_FALSE(current_winner);

     // Duel for no sample. Should not change winner
     if (no_sample_index >= 0) {
         for (int i = 0; i < 200; i++) {
             monitor->sample(&entries[no_sample_index]);
         }
         ASSERT_EQ(current_winner, monitor->getWinner());
     }
 }

 // Test a few possible parameter combinations. There is a limitation on
 // the number of tests due to the maximum number of different ids. Because
 // of that, if a new test is added and it fails for no reason, make sure
 // that this limit has not been surpassed
 INSTANTIATE_TEST_CASE_P(DuelingMonitorTests, DuelingMonitorTest,
     ::testing::Values(
         // Combinations of constituencies and teams
         std::make_tuple(32, 2, 1, 1, 0.5, 0.5),
         std::make_tuple(32, 4, 1, 1, 0.5, 0.5),
         std::make_tuple(32, 4, 2, 1, 0.5, 0.5),
         std::make_tuple(32, 8, 1, 1, 0.5, 0.5),
         std::make_tuple(32, 8, 2, 1, 0.5, 0.5),
         std::make_tuple(32, 8, 4, 1, 0.5, 0.5),
         std::make_tuple(32, 16, 1, 1, 0.5, 0.5),
         std::make_tuple(32, 16, 2, 1, 0.5, 0.5),
         std::make_tuple(32, 16, 4, 1, 0.5, 0.5),
         std::make_tuple(32, 16, 8, 1, 0.5, 0.5),

         // Tests for the thresholds
         std::make_tuple(16, 4, 1, 3, 0.5, 0.5),
         std::make_tuple(16, 4, 1, 3, 0.1, 0.7),
         std::make_tuple(16, 4, 1, 3, 0.4, 0.6),
         std::make_tuple(16, 4, 1, 3, 0.8, 0.9),

         // Test for larger tables
         std::make_tuple(2048, 32, 4, 4, 0.4, 0.6))
 );
	/*
	* Copyright (c) 2019, 2020 Inria
	* 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.
	*/

	#include <gtest/gtest.h>

	#include <cstddef>
	#include <cstdint>
	#include <memory>
	#include <tuple>
	#include <vector>

	#include "base/sat_counter.hh"
	#include "mem/cache/tags/dueling.hh"

	using namespace gem5;

	/**
	* Test whether dueler provides correct sampling functionality and assigns
	* teams correctly.
	*/
	TEST(DuelerTest, SetSample)
	{
	const int num_sampled_ids = 3;
	bool team;
	Dueler dueler;

	// Initially nobody is sampled
	for (int id = 0; id < 64; id++) {
	ASSERT_FALSE(dueler.isSample(1ULL << id, team));
	}

	// Mark the first num_sampled_ids as samples and assign alternating teams
	team = false;
	for (int id = 0; id < num_sampled_ids; id++) {
	team = !team;
	dueler.setSample(1ULL << id, team);
	}

	// Make sure that only the entries marked as samples previously are samples
	bool expected_team = false;
	for (int id = 0; id < 64; id++) {
	expected_team = !expected_team;
	const bool is_sample = dueler.isSample(1ULL << id, team);
	if (id < num_sampled_ids) {
	ASSERT_TRUE(is_sample);
	ASSERT_EQ(team, expected_team);
	} else {
	ASSERT_FALSE(is_sample);
	}
	}

	}

	// We assume that the monitors are assigned sequential powers of
	// two ids starting from 1
	static uint64_t monitor_id = 0;

	class DuelingMonitorTest : public testing::TestWithParam<
	std::tuple<unsigned, std::size_t, std::size_t, unsigned, double, double>>
	{
	protected:
	/** A vector simulating a table-like structure. */
	std::vector<Dueler> entries;

	/** The constituency size, acquired from params. */
	std::size_t constituencySize;

	/** The size of a team, acquired from params. */
	std::size_t teamSize;

	/** The number of bits in the selector, acquired from params. */
	unsigned numBits;

	/** The low threshold to change winner, acquired from params. */
	double lowThreshold;

	/** The high threshold to change winner, acquired from params. */
	double highThreshold;

	/** The monitor instance being tested. */
	std::unique_ptr<DuelingMonitor> monitor;

	void
	SetUp() override
	{
	const unsigned num_entries = std::get<0>(GetParam());
	constituencySize = std::get<1>(GetParam());
	teamSize = std::get<2>(GetParam());
	numBits = std::get<3>(GetParam());
	lowThreshold = std::get<4>(GetParam());
	highThreshold = std::get<5>(GetParam());

	monitor.reset(new DuelingMonitor(constituencySize, teamSize, numBits,
	lowThreshold, highThreshold));

	// Initialize entries
	entries.resize(num_entries);
	for (auto& entry : entries) {
	monitor->initEntry(&entry);
	}
	}

	void
	TearDown() override
	{
	// Due to the way the DuelingMonitor works, this id is not testable
	// anymore, so move to the next
	monitor_id++;
	}
	};

	/**
	* Test whether entry initialization creates exactly the amount of samples
	* requested.
	*/
	TEST_P(DuelingMonitorTest, CountSamples)
	{
	const int expected_num_samples =
	(entries.size() / constituencySize) * teamSize;

	// Check whether the number of samples match expectation.
	// Both teams must also have the same number of samples
	int count_samples_true = 0;
	int count_samples_false = 0;
	bool team;
	for (auto& entry : entries) {
	if (entry.isSample(1ULL << monitor_id, team)) {
	if (team) {
	count_samples_true++;
	} else {
	count_samples_false++;
	}
	}
	}
	ASSERT_EQ(count_samples_true, count_samples_false);
	ASSERT_EQ(count_samples_true, expected_num_samples);
	}

	/** Test winner selection with multiple different threshold configurations. */
	TEST_P(DuelingMonitorTest, WinnerSelection)
	{
	SatCounter32 expected_selector(numBits);
	expected_selector.saturate();
	expected_selector >>= 1;

	// Initialize entries, and save a pointer to a sample of each
	// team, and one no sample
	int team_true_index = -1;
	int team_false_index = -1;
	int no_sample_index = -1;
	for (int index = 0; index < entries.size(); index++) {
	bool team;
	if (entries[index].isSample(1ULL << monitor_id, team)) {
	if (team) {
	team_true_index = index;
	} else {
	team_false_index = index;
	}
	} else {
	no_sample_index = index;
	}
	}
	ASSERT_TRUE(team_true_index >= 0);
	ASSERT_TRUE(team_false_index >= 0);

	// Duel for team true only. If the monitor starts predicting false
	// the threshold to use is the higher one. Otherwise, we should
	// start expecting true to be the winner, and thus we use the
	// low threshold
	bool current_winner = monitor->getWinner();
	double threshold = current_winner ? lowThreshold : highThreshold;
	for (; expected_selector.calcSaturation() < 1.0;
	expected_selector++) {
	ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
	monitor->getWinner());
	monitor->sample(&entries[team_true_index]);
	}
	current_winner = monitor->getWinner();
	ASSERT_TRUE(current_winner);

	// Duel for no sample. Should not change winner
	if (no_sample_index >= 0) {
	for (int i = 0; i < 200; i++) {
	monitor->sample(&entries[no_sample_index]);
	}
	ASSERT_EQ(current_winner, monitor->getWinner());
	}

	// Duel for team false only. Now that we know that team true
	// is winning, the low threshold must be passed in order to
	// make team false win the duel
	threshold = lowThreshold;
	for (; expected_selector.calcSaturation() > 0.0;
	expected_selector--) {
	ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
	monitor->getWinner());
	monitor->sample(&entries[team_false_index]);
	}
	current_winner = monitor->getWinner();
	ASSERT_FALSE(current_winner);

	// Duel for no sample. Should not change winner
	if (no_sample_index >= 0) {
	for (int i = 0; i < 200; i++) {
	monitor->sample(&entries[no_sample_index]);
	}
	ASSERT_EQ(current_winner, monitor->getWinner());
	}
	}

	// Test a few possible parameter combinations. There is a limitation on
	// the number of tests due to the maximum number of different ids. Because
	// of that, if a new test is added and it fails for no reason, make sure
	// that this limit has not been surpassed
	INSTANTIATE_TEST_CASE_P(DuelingMonitorTests, DuelingMonitorTest,
	::testing::Values(
	// Combinations of constituencies and teams
	std::make_tuple(32, 2, 1, 1, 0.5, 0.5),
	std::make_tuple(32, 4, 1, 1, 0.5, 0.5),
	std::make_tuple(32, 4, 2, 1, 0.5, 0.5),
	std::make_tuple(32, 8, 1, 1, 0.5, 0.5),
	std::make_tuple(32, 8, 2, 1, 0.5, 0.5),
	std::make_tuple(32, 8, 4, 1, 0.5, 0.5),
	std::make_tuple(32, 16, 1, 1, 0.5, 0.5),
	std::make_tuple(32, 16, 2, 1, 0.5, 0.5),
	std::make_tuple(32, 16, 4, 1, 0.5, 0.5),
	std::make_tuple(32, 16, 8, 1, 0.5, 0.5),

	// Tests for the thresholds
	std::make_tuple(16, 4, 1, 3, 0.5, 0.5),
	std::make_tuple(16, 4, 1, 3, 0.1, 0.7),
	std::make_tuple(16, 4, 1, 3, 0.4, 0.6),
	std::make_tuple(16, 4, 1, 3, 0.8, 0.9),

	// Test for larger tables
	std::make_tuple(2048, 32, 4, 4, 0.4, 0.6))
	);