gem5  v22.0.0.1
dueling.test.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2019, 2020 Inria
3  * All rights reserved
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met: redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer;
9  * redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution;
12  * neither the name of the copyright holders nor the names of its
13  * contributors may be used to endorse or promote products derived from
14  * this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #include <gtest/gtest.h>
30 
31 #include <cstddef>
32 #include <cstdint>
33 #include <memory>
34 #include <tuple>
35 #include <vector>
36 
37 #include "base/sat_counter.hh"
39 
40 using namespace gem5;
41 
46 TEST(DuelerTest, SetSample)
47 {
48  const int num_sampled_ids = 3;
49  bool team;
50  Dueler dueler;
51 
52  // Initially nobody is sampled
53  for (int id = 0; id < 64; id++) {
54  ASSERT_FALSE(dueler.isSample(1ULL << id, team));
55  }
56 
57  // Mark the first num_sampled_ids as samples and assign alternating teams
58  team = false;
59  for (int id = 0; id < num_sampled_ids; id++) {
60  team = !team;
61  dueler.setSample(1ULL << id, team);
62  }
63 
64  // Make sure that only the entries marked as samples previously are samples
65  bool expected_team = false;
66  for (int id = 0; id < 64; id++) {
67  expected_team = !expected_team;
68  const bool is_sample = dueler.isSample(1ULL << id, team);
69  if (id < num_sampled_ids) {
70  ASSERT_TRUE(is_sample);
71  ASSERT_EQ(team, expected_team);
72  } else {
73  ASSERT_FALSE(is_sample);
74  }
75  }
76 
77 }
78 
79 // We assume that the monitors are assigned sequential powers of
80 // two ids starting from 1
81 static uint64_t monitor_id = 0;
82 
83 class DuelingMonitorTest : public testing::TestWithParam<
84  std::tuple<unsigned, std::size_t, std::size_t, unsigned, double, double>>
85 {
86  protected:
89 
91  std::size_t constituencySize;
92 
94  std::size_t teamSize;
95 
97  unsigned numBits;
98 
100  double lowThreshold;
101 
104 
106  std::unique_ptr<DuelingMonitor> monitor;
107 
108  void
109  SetUp() override
110  {
111  const unsigned num_entries = std::get<0>(GetParam());
112  constituencySize = std::get<1>(GetParam());
113  teamSize = std::get<2>(GetParam());
114  numBits = std::get<3>(GetParam());
115  lowThreshold = std::get<4>(GetParam());
116  highThreshold = std::get<5>(GetParam());
117 
118  monitor.reset(new DuelingMonitor(constituencySize, teamSize, numBits,
119  lowThreshold, highThreshold));
120 
121  // Initialize entries
122  entries.resize(num_entries);
123  for (auto& entry : entries) {
124  monitor->initEntry(&entry);
125  }
126  }
127 
128  void
129  TearDown() override
130  {
131  // Due to the way the DuelingMonitor works, this id is not testable
132  // anymore, so move to the next
133  monitor_id++;
134  }
135 };
136 
142 {
143  const int expected_num_samples =
144  (entries.size() / constituencySize) * teamSize;
145 
146  // Check whether the number of samples match expectation.
147  // Both teams must also have the same number of samples
148  int count_samples_true = 0;
149  int count_samples_false = 0;
150  bool team;
151  for (auto& entry : entries) {
152  if (entry.isSample(1ULL << monitor_id, team)) {
153  if (team) {
154  count_samples_true++;
155  } else {
156  count_samples_false++;
157  }
158  }
159  }
160  ASSERT_EQ(count_samples_true, count_samples_false);
161  ASSERT_EQ(count_samples_true, expected_num_samples);
162 }
163 
165 TEST_P(DuelingMonitorTest, WinnerSelection)
166 {
167  SatCounter32 expected_selector(numBits);
168  expected_selector.saturate();
169  expected_selector >>= 1;
170 
171  // Initialize entries, and save a pointer to a sample of each
172  // team, and one no sample
173  int team_true_index = -1;
174  int team_false_index = -1;
175  int no_sample_index = -1;
176  for (int index = 0; index < entries.size(); index++) {
177  bool team;
178  if (entries[index].isSample(1ULL << monitor_id, team)) {
179  if (team) {
180  team_true_index = index;
181  } else {
182  team_false_index = index;
183  }
184  } else {
185  no_sample_index = index;
186  }
187  }
188  ASSERT_TRUE(team_true_index >= 0);
189  ASSERT_TRUE(team_false_index >= 0);
190 
191  // Duel for team true only. If the monitor starts predicting false
192  // the threshold to use is the higher one. Otherwise, we should
193  // start expecting true to be the winner, and thus we use the
194  // low threshold
195  bool current_winner = monitor->getWinner();
196  double threshold = current_winner ? lowThreshold : highThreshold;
197  for (; expected_selector.calcSaturation() < 1.0;
198  expected_selector++) {
199  ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
200  monitor->getWinner());
201  monitor->sample(&entries[team_true_index]);
202  }
203  current_winner = monitor->getWinner();
204  ASSERT_TRUE(current_winner);
205 
206  // Duel for no sample. Should not change winner
207  if (no_sample_index >= 0) {
208  for (int i = 0; i < 200; i++) {
209  monitor->sample(&entries[no_sample_index]);
210  }
211  ASSERT_EQ(current_winner, monitor->getWinner());
212  }
213 
214  // Duel for team false only. Now that we know that team true
215  // is winning, the low threshold must be passed in order to
216  // make team false win the duel
217  threshold = lowThreshold;
218  for (; expected_selector.calcSaturation() > 0.0;
219  expected_selector--) {
220  ASSERT_EQ(expected_selector.calcSaturation() >= threshold,
221  monitor->getWinner());
222  monitor->sample(&entries[team_false_index]);
223  }
224  current_winner = monitor->getWinner();
225  ASSERT_FALSE(current_winner);
226 
227  // Duel for no sample. Should not change winner
228  if (no_sample_index >= 0) {
229  for (int i = 0; i < 200; i++) {
230  monitor->sample(&entries[no_sample_index]);
231  }
232  ASSERT_EQ(current_winner, monitor->getWinner());
233  }
234 }
235 
236 // Test a few possible parameter combinations. There is a limitation on
237 // the number of tests due to the maximum number of different ids. Because
238 // of that, if a new test is added and it fails for no reason, make sure
239 // that this limit has not been surpassed
240 INSTANTIATE_TEST_CASE_P(DuelingMonitorTests, DuelingMonitorTest,
241  ::testing::Values(
242  // Combinations of constituencies and teams
243  std::make_tuple(32, 2, 1, 1, 0.5, 0.5),
244  std::make_tuple(32, 4, 1, 1, 0.5, 0.5),
245  std::make_tuple(32, 4, 2, 1, 0.5, 0.5),
246  std::make_tuple(32, 8, 1, 1, 0.5, 0.5),
247  std::make_tuple(32, 8, 2, 1, 0.5, 0.5),
248  std::make_tuple(32, 8, 4, 1, 0.5, 0.5),
249  std::make_tuple(32, 16, 1, 1, 0.5, 0.5),
250  std::make_tuple(32, 16, 2, 1, 0.5, 0.5),
251  std::make_tuple(32, 16, 4, 1, 0.5, 0.5),
252  std::make_tuple(32, 16, 8, 1, 0.5, 0.5),
253 
254  // Tests for the thresholds
255  std::make_tuple(16, 4, 1, 3, 0.5, 0.5),
256  std::make_tuple(16, 4, 1, 3, 0.1, 0.7),
257  std::make_tuple(16, 4, 1, 3, 0.4, 0.6),
258  std::make_tuple(16, 4, 1, 3, 0.8, 0.9),
259 
260  // Test for larger tables
261  std::make_tuple(2048, 32, 4, 4, 0.4, 0.6))
262 );
gem5::GenericSatCounter::calcSaturation
double calcSaturation() const
Calculate saturation percentile of the current counter's value with regard to its maximum possible va...
Definition: sat_counter.hh:303
gem5::Dueler::setSample
void setSample(uint64_t id, bool team)
Make this entry a sampling entry for a specific Dueling instance.
Definition: dueling.cc:45
DuelingMonitorTest::TearDown
void TearDown() override
Definition: dueling.test.cc:129
dueling.hh
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::Dueler::isSample
bool isSample(uint64_t id, bool &team) const
Check if entry is a sample for the given instance.
Definition: dueling.cc:57
std::vector< Dueler >
DuelingMonitorTest::numBits
unsigned numBits
The number of bits in the selector, acquired from params.
Definition: dueling.test.cc:97
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:67
sat_counter.hh
gem5::GenericSatCounter< uint32_t >
gem5::GenericSatCounter::saturate
uint8_t saturate()
Saturate the counter.
Definition: sat_counter.hh:321
DuelingMonitorTest::entries
std::vector< Dueler > entries
A vector simulating a table-like structure.
Definition: dueling.test.cc:88
monitor_id
static uint64_t monitor_id
Definition: dueling.test.cc:81
DuelingMonitorTest::teamSize
std::size_t teamSize
The size of a team, acquired from params.
Definition: dueling.test.cc:94
gem5::Dueler
A dueler is an entry that may or may not be accounted for sampling.
Definition: dueling.hh:52
TEST
TEST(DuelerTest, SetSample)
Test whether dueler provides correct sampling functionality and assigns teams correctly.
Definition: dueling.test.cc:46
DuelingMonitorTest::lowThreshold
double lowThreshold
The low threshold to change winner, acquired from params.
Definition: dueling.test.cc:100
DuelingMonitorTest::highThreshold
double highThreshold
The high threshold to change winner, acquired from params.
Definition: dueling.test.cc:103
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: gpu_translation_state.hh:37
gem5::DuelingMonitor
Duel between two sampled options to determine which is the winner.
Definition: dueling.hh:107
DuelingMonitorTest::SetUp
void SetUp() override
Definition: dueling.test.cc:109
DuelingMonitorTest::constituencySize
std::size_t constituencySize
The constituency size, acquired from params.
Definition: dueling.test.cc:91
TEST_P
TEST_P(DuelingMonitorTest, CountSamples)
Test whether entry initialization creates exactly the amount of samples requested.
Definition: dueling.test.cc:141
DuelingMonitorTest
Definition: dueling.test.cc:83
DuelingMonitorTest::monitor
std::unique_ptr< DuelingMonitor > monitor
The monitor instance being tested.
Definition: dueling.test.cc:106
INSTANTIATE_TEST_CASE_P
INSTANTIATE_TEST_CASE_P(DuelingMonitorTests, DuelingMonitorTest, ::testing::Values(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), 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), std::make_tuple(2048, 32, 4, 4, 0.4, 0.6)))

Generated on Sat Jun 18 2022 08:12:28 for gem5 by doxygen 1.8.17