dueling.test.cc

Go to the documentation of this file.

/*
 * 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(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:
    std::vector<Dueler> entries;

    std::size_t constituencySize;

    std::size_t teamSize;

    unsigned numBits;

    double lowThreshold;

    double highThreshold;

    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_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_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))
);