gem5  v21.1.0.2
RubyPrefetcher.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020 Inria
3  * Copyright (c) 2020 ARM Limited
4  * All rights reserved
5  *
6  * The license below extends only to copyright in the software and shall
7  * not be construed as granting a license to any other intellectual
8  * property including but not limited to intellectual property relating
9  * to a hardware implementation of the functionality of the software
10  * licensed hereunder. You may use the software subject to the license
11  * terms below provided that you ensure that this notice is replicated
12  * unmodified and in its entirety in all distributions of the software,
13  * modified or unmodified, in source code or in binary form.
14  *
15  * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
16  * All rights reserved.
17  *
18  * Redistribution and use in source and binary forms, with or without
19  * modification, are permitted provided that the following conditions are
20  * met: redistributions of source code must retain the above copyright
21  * notice, this list of conditions and the following disclaimer;
22  * redistributions in binary form must reproduce the above copyright
23  * notice, this list of conditions and the following disclaimer in the
24  * documentation and/or other materials provided with the distribution;
25  * neither the name of the copyright holders nor the names of its
26  * contributors may be used to endorse or promote products derived from
27  * this software without specific prior written permission.
28  *
29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40  */
41 
43 
44 #include <cassert>
45 
46 #include "base/bitfield.hh"
47 #include "debug/RubyPrefetcher.hh"
50 
51 namespace gem5
52 {
53 
54 namespace ruby
55 {
56 
58  : SimObject(p), m_num_streams(p.num_streams),
59  m_array(p.num_streams), m_train_misses(p.train_misses),
60  m_num_startup_pfs(p.num_startup_pfs),
61  unitFilter(p.unit_filter),
62  negativeFilter(p.unit_filter),
63  nonUnitFilter(p.nonunit_filter),
64  m_prefetch_cross_pages(p.cross_page),
65  m_page_shift(p.sys->getPageShift()),
66  rubyPrefetcherStats(this)
67 {
68  assert(m_num_streams > 0);
70 }
71 
74  : statistics::Group(parent, "RubyPrefetcher"),
75  ADD_STAT(numMissObserved, "Number of misses observed"),
76  ADD_STAT(numAllocatedStreams, "Number of streams allocated for "
77  "prefetching"),
78  ADD_STAT(numPrefetchRequested, "Number of prefetch requests made"),
79  ADD_STAT(numHits, "Number of prefetched blocks accessed "
80  "(for the first time)"),
81  ADD_STAT(numPartialHits, "Number of misses observed for a block being "
82  "prefetched"),
83  ADD_STAT(numPagesCrossed, "Number of prefetches across pages"),
84  ADD_STAT(numMissedPrefetchedBlocks, "Number of misses for blocks that "
85  "were prefetched, yet missed")
86 {
87 }
88 
89 void
90 RubyPrefetcher::observeMiss(Addr address, const RubyRequestType& type)
91 {
92  DPRINTF(RubyPrefetcher, "Observed miss for %#x\n", address);
93  Addr line_addr = makeLineAddress(address);
95 
96  // check to see if we have already issued a prefetch for this block
97  uint32_t index = 0;
98  PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
99  if (pfEntry != NULL) {
100  if (pfEntry->requestIssued[index]) {
101  if (pfEntry->requestCompleted[index]) {
102  // We prefetched too early and now the prefetch block no
103  // longer exists in the cache
105  return;
106  } else {
107  // The controller has issued the prefetch request,
108  // but the request for the block arrived earlier.
110  observePfMiss(line_addr);
111  return;
112  }
113  } else {
114  // The request is still in the prefetch queue of the controller.
115  // Or was evicted because of other requests.
116  return;
117  }
118  }
119 
120  // Check if address is in any of the stride filters
121  if (accessUnitFilter(&unitFilter, line_addr, 1, type)) {
122  DPRINTF(RubyPrefetcher, " *** hit in unit stride buffer\n");
123  return;
124  }
125  if (accessUnitFilter(&negativeFilter, line_addr, -1, type)) {
126  DPRINTF(RubyPrefetcher, " *** hit in unit negative unit buffer\n");
127  return;
128  }
129  if (accessNonunitFilter(line_addr, type)) {
130  DPRINTF(RubyPrefetcher, " *** hit in non-unit stride buffer\n");
131  return;
132  }
133 }
134 
135 void
137 {
139  DPRINTF(RubyPrefetcher, "Observed partial hit for %#x\n", address);
140  issueNextPrefetch(address, NULL);
141 }
142 
143 void
145 {
147  DPRINTF(RubyPrefetcher, "Observed hit for %#x\n", address);
148  issueNextPrefetch(address, NULL);
149 }
150 
151 void
153 {
154  // get our corresponding stream fetcher
155  if (stream == NULL) {
156  uint32_t index = 0;
157  stream = getPrefetchEntry(address, index);
158  }
159 
160  // if (for some reason), this stream is unallocated, return.
161  if (stream == NULL) {
162  DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
163  return;
164  }
165 
166  // extend this prefetching stream by 1 (or more)
167  Addr page_addr = pageAddress(stream->m_address);
168  Addr line_addr = makeNextStrideAddress(stream->m_address,
169  stream->m_stride);
170 
171  // possibly stop prefetching at page boundaries
172  if (page_addr != pageAddress(line_addr)) {
173  if (!m_prefetch_cross_pages) {
174  // Deallocate the stream since we are not prefetching
175  // across page boundries
176  stream->m_is_valid = false;
177  return;
178  }
180  }
181 
182  // launch next prefetch
184  stream->m_address = line_addr;
185  stream->m_use_time = m_controller->curCycle();
186  DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
187  m_controller->enqueuePrefetch(line_addr, stream->m_type);
188 }
189 
190 uint32_t
192 {
193  uint32_t lru_index = 0;
194  Cycles lru_access = m_array[lru_index].m_use_time;
195 
196  for (uint32_t i = 0; i < m_num_streams; i++) {
197  if (!m_array[i].m_is_valid) {
198  return i;
199  }
200  if (m_array[i].m_use_time < lru_access) {
201  lru_access = m_array[i].m_use_time;
202  lru_index = i;
203  }
204  }
205 
206  return lru_index;
207 }
208 
209 void
211  uint32_t index, const RubyRequestType& type)
212 {
214 
215  // initialize the stream prefetcher
216  PrefetchEntry *mystream = &(m_array[index]);
217  mystream->m_address = makeLineAddress(address);
218  mystream->m_stride = stride;
219  mystream->m_use_time = m_controller->curCycle();
220  mystream->m_is_valid = true;
221  mystream->m_type = type;
222 
223  // create a number of initial prefetches for this stream
224  Addr page_addr = pageAddress(mystream->m_address);
225  Addr line_addr = makeLineAddress(mystream->m_address);
226 
227  // insert a number of prefetches into the prefetch table
228  for (int k = 0; k < m_num_startup_pfs; k++) {
229  line_addr = makeNextStrideAddress(line_addr, stride);
230  // possibly stop prefetching at page boundaries
231  if (page_addr != pageAddress(line_addr)) {
232  if (!m_prefetch_cross_pages) {
233  // deallocate this stream prefetcher
234  mystream->m_is_valid = false;
235  return;
236  }
238  }
239 
240  // launch prefetch
242  DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
243  m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
244  }
245 
246  // update the address to be the last address prefetched
247  mystream->m_address = line_addr;
248 }
249 
252 {
253  // search all streams for a match
254  for (int i = 0; i < m_num_streams; i++) {
255  // search all the outstanding prefetches for this stream
256  if (m_array[i].m_is_valid) {
257  for (int j = 0; j < m_num_startup_pfs; j++) {
258  if (makeNextStrideAddress(m_array[i].m_address,
259  -(m_array[i].m_stride*j)) == address) {
260  return &(m_array[i]);
261  }
262  }
263  }
264  }
265  return NULL;
266 }
267 
268 bool
270  Addr line_addr, int stride, const RubyRequestType& type)
271 {
272  for (auto& entry : *filter) {
273  if (entry.addr == line_addr) {
274  entry.addr = makeNextStrideAddress(entry.addr, stride);
275  entry.hits++;
276  if (entry.hits >= m_train_misses) {
277  // Allocate a new prefetch stream
278  initializeStream(line_addr, stride, getLRUindex(), type);
279  }
280  return true;
281  }
282  }
283 
284  // Enter this address in the filter
285  filter->push_back(UnitFilterEntry(
286  makeNextStrideAddress(line_addr, stride)));
287 
288  return false;
289 }
290 
291 bool
293  const RubyRequestType& type)
294 {
296  Addr page_addr = pageAddress(line_addr);
297 
298  for (auto& entry : nonUnitFilter) {
299  if (pageAddress(entry.addr) == page_addr) {
300  // hit in the non-unit filter
301  // compute the actual stride (for this reference)
302  int delta = line_addr - entry.addr;
303 
304  if (delta != 0) {
305  // no zero stride prefetches
306  // check that the stride matches (for the last N times)
307  if (delta == entry.stride) {
308  // -> stride hit
309  // increment count (if > 2) allocate stream
310  entry.hits++;
311  if (entry.hits > m_train_misses) {
312  // This stride HAS to be the multiplicative constant of
313  // dataBlockBytes (bc makeNextStrideAddress is
314  // calculated based on this multiplicative constant!)
315  const int stride = entry.stride /
317 
318  // clear this filter entry
319  entry.clear();
320 
321  initializeStream(line_addr, stride, getLRUindex(),
322  type);
323  }
324  } else {
325  // If delta didn't match reset entry's hit count
326  entry.hits = 0;
327  }
328 
329  // update the last address seen & the stride
330  entry.addr = line_addr;
331  entry.stride = delta;
332  return true;
333  } else {
334  return false;
335  }
336  }
337  }
338 
339  // not found: enter this address in the table
340  nonUnitFilter.push_back(NonUnitFilterEntry(line_addr));
341 
342  return false;
343 }
344 
345 void
346 RubyPrefetcher::print(std::ostream& out) const
347 {
348  out << name() << " Prefetcher State\n";
349  // print out unit filter
350  out << "unit table:\n";
351  for (const auto& entry : unitFilter) {
352  out << entry.addr << std::endl;
353  }
354 
355  out << "negative table:\n";
356  for (const auto& entry : negativeFilter) {
357  out << entry.addr << std::endl;
358  }
359 
360  // print out non-unit stride filter
361  out << "non-unit table:\n";
362  for (const auto& entry : nonUnitFilter) {
363  out << entry.addr << " "
364  << entry.stride << " "
365  << entry.hits << std::endl;
366  }
367 
368  // print out allocated stream buffers
369  out << "streams:\n";
370  for (int i = 0; i < m_num_streams; i++) {
371  out << m_array[i].m_address << " "
372  << m_array[i].m_stride << " "
373  << m_array[i].m_is_valid << " "
374  << m_array[i].m_use_time << std::endl;
375  }
376 }
377 
378 Addr
380 {
381  return mbits<Addr>(addr, 63, m_page_shift);
382 }
383 
384 } // namespace ruby
385 } // namespace gem5
gem5::ruby::RubyPrefetcher::observePfHit
void observePfHit(Addr address)
Implement the prefetch hit(miss) callback interface.
Definition: RubyPrefetcher.cc:144
gem5::ruby::PrefetchEntry::m_address
Addr m_address
The base address for the stream prefetch.
Definition: RubyPrefetcher.hh:81
gem5::ruby::RubyPrefetcher::getPrefetchEntry
PrefetchEntry * getPrefetchEntry(Addr address, uint32_t &index)
get pointer to the matching stream entry, returns NULL if not found index holds the multiple of the s...
Definition: RubyPrefetcher.cc:251
gem5::ruby::RubyPrefetcher::observePfMiss
void observePfMiss(Addr address)
Definition: RubyPrefetcher.cc:136
gem5::ruby::PrefetchEntry::requestCompleted
std::bitset< MAX_PF_INFLIGHT > requestCompleted
Definition: RubyPrefetcher.hh:98
gem5::Clocked::curCycle
Cycles curCycle() const
Determine the current cycle, corresponding to a tick aligned to a clock edge.
Definition: clocked_object.hh:195
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::ruby::RubyPrefetcher::getLRUindex
uint32_t getLRUindex(void)
Returns an unused stream buffer (or if all are used, returns the least recently used (accessed) strea...
Definition: RubyPrefetcher.cc:191
gem5::ruby::PrefetchEntry::m_stride
int m_stride
stride distance to get next address from
Definition: RubyPrefetcher.hh:84
gem5::ruby::RubyPrefetcher::m_num_streams
uint32_t m_num_streams
number of prefetch streams available
Definition: RubyPrefetcher.hh:209
gem5::ruby::RubySystem::getBlockSizeBytes
static uint32_t getBlockSizeBytes()
Definition: RubySystem.hh:72
gem5::ruby::PrefetchEntry::m_type
RubyRequestType m_type
L1D prefetches loads and stores.
Definition: RubyPrefetcher.hh:93
gem5::ruby::RubyPrefetcher
Definition: RubyPrefetcher.hh:101
gem5::ruby::RubyPrefetcher::m_num_startup_pfs
uint32_t m_num_startup_pfs
number of initial prefetches to startup a stream
Definition: RubyPrefetcher.hh:216
gem5::ruby::PrefetchEntry::m_is_valid
bool m_is_valid
valid bit for each stream
Definition: RubyPrefetcher.hh:90
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::ruby::RubyPrefetcher::initializeStream
void initializeStream(Addr address, int stride, uint32_t index, const RubyRequestType &type)
allocate a new stream buffer at a specific index
Definition: RubyPrefetcher.cc:210
gem5::ruby::makeLineAddress
Addr makeLineAddress(Addr addr)
Definition: Address.cc:60
gem5::ruby::AbstractController::enqueuePrefetch
virtual void enqueuePrefetch(const Addr &, const RubyRequestType &)
Function for enqueuing a prefetch request.
Definition: AbstractController.hh:143
gem5::ruby::RubyPrefetcher::m_train_misses
uint32_t m_train_misses
number of misses I must see before allocating a stream
Definition: RubyPrefetcher.hh:214
gem5::Cycles
Cycles is a wrapper class for representing cycle counts, i.e.
Definition: types.hh:78
gem5::ruby::RubyPrefetcher::accessNonunitFilter
bool accessNonunitFilter(Addr line_addr, const RubyRequestType &type)
Access a non-unit stride filter to determine if there is a hit, and update it otherwise.
Definition: RubyPrefetcher.cc:292
gem5::ruby::RubyPrefetcher::m_array
std::vector< PrefetchEntry > m_array
an array of the active prefetch streams
Definition: RubyPrefetcher.hh:211
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numHits
statistics::Scalar numHits
Count of successful prefetches.
Definition: RubyPrefetcher.hh:254
gem5::ruby::RubyPrefetcher::nonUnitFilter
CircularQueue< NonUnitFilterEntry > nonUnitFilter
A non-unit stride filter array: helps reduce BW requirement of prefetching.
Definition: RubyPrefetcher.hh:234
gem5::ArmISA::j
Bitfield< 24 > j
Definition: misc_types.hh:57
gem5::ruby::RubyPrefetcher::observeMiss
void observeMiss(Addr address, const RubyRequestType &type)
Observe a memory miss from the cache.
Definition: RubyPrefetcher.cc:90
RubyPrefetcher.hh
gem5::ruby::RubyPrefetcher::m_page_shift
const Addr m_page_shift
Definition: RubyPrefetcher.hh:241
bitfield.hh
gem5::ruby::RubyPrefetcher::pageAddress
Addr pageAddress(Addr addr) const
determine the page aligned address
Definition: RubyPrefetcher.cc:379
gem5::Named::name
virtual std::string name() const
Definition: named.hh:47
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
ADD_STAT
#define ADD_STAT(n,...)
Convenience macro to add a stat to a statistics group.
Definition: group.hh:75
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numPagesCrossed
statistics::Scalar numPagesCrossed
Count of pages crossed.
Definition: RubyPrefetcher.hh:258
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::ruby::PrefetchEntry::m_use_time
Cycles m_use_time
the last time that any prefetched request was used
Definition: RubyPrefetcher.hh:87
gem5::X86ISA::type
type
Definition: misc.hh:733
gem5::ruby::PrefetchEntry::requestIssued
std::bitset< MAX_PF_INFLIGHT > requestIssued
Bitset for tracking prefetches for which addresses have been issued, which ones have completed.
Definition: RubyPrefetcher.hh:97
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numMissObserved
statistics::Scalar numMissObserved
Count of accesses to the prefetcher.
Definition: RubyPrefetcher.hh:248
gem5::ruby::RubyPrefetcher::unitFilter
CircularQueue< UnitFilterEntry > unitFilter
A unit stride filter array: helps reduce BW requirement of prefetching.
Definition: RubyPrefetcher.hh:222
gem5::SimObject
Abstract superclass for simulation objects.
Definition: sim_object.hh:146
RubySystem.hh
MAX_PF_INFLIGHT
#define MAX_PF_INFLIGHT
Definition: RubyPrefetcher.hh:60
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::ruby::RubyPrefetcher::issueNextPrefetch
void issueNextPrefetch(Addr address, PrefetchEntry *stream)
Definition: RubyPrefetcher.cc:152
RubySlicc_ComponentMapping.hh
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numMissedPrefetchedBlocks
statistics::Scalar numMissedPrefetchedBlocks
Count of misses incurred for blocks that were prefetched.
Definition: RubyPrefetcher.hh:260
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::RubyPrefetcherStats
RubyPrefetcherStats(statistics::Group *parent)
Definition: RubyPrefetcher.cc:73
gem5::ruby::RubyPrefetcher::m_prefetch_cross_pages
bool m_prefetch_cross_pages
Used for allowing prefetches across pages.
Definition: RubyPrefetcher.hh:237
gem5::ruby::RubyPrefetcher::UnitFilterEntry
Definition: RubyPrefetcher.hh:133
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numAllocatedStreams
statistics::Scalar numAllocatedStreams
Count of prefetch streams allocated.
Definition: RubyPrefetcher.hh:250
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numPartialHits
statistics::Scalar numPartialHits
Count of partial successful prefetches.
Definition: RubyPrefetcher.hh:256
gem5::statistics::Group
Statistics container.
Definition: group.hh:93
gem5::ruby::RubyPrefetcher::negativeFilter
CircularQueue< UnitFilterEntry > negativeFilter
A negative unit stride filter array: helps reduce BW requirement of prefetching.
Definition: RubyPrefetcher.hh:228
gem5::ruby::RubyPrefetcher::accessUnitFilter
bool accessUnitFilter(CircularQueue< UnitFilterEntry > *const filter, Addr line_addr, int stride, const RubyRequestType &type)
Access a unit stride filter to determine if there is a hit, and update it otherwise.
Definition: RubyPrefetcher.cc:269
gem5::MipsISA::k
Bitfield< 23 > k
Definition: dt_constants.hh:81
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::ArmISA::stride
Bitfield< 21, 20 > stride
Definition: misc_types.hh:446
gem5::CircularQueue
Circular queue.
Definition: circular_queue.hh:69
gem5::ruby::makeNextStrideAddress
Addr makeNextStrideAddress(Addr addr, int stride)
Definition: Address.cc:73
gem5::ruby::PrefetchEntry
Definition: RubyPrefetcher.hh:68
gem5::ruby::RubyPrefetcher::rubyPrefetcherStats
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats rubyPrefetcherStats
gem5::ruby::RubyPrefetcher::RubyPrefetcherStats::numPrefetchRequested
statistics::Scalar numPrefetchRequested
Count of prefetch requests made.
Definition: RubyPrefetcher.hh:252
gem5::ruby::RubyPrefetcher::m_controller
AbstractController * m_controller
Definition: RubyPrefetcher.hh:239
gem5::ruby::RubyPrefetcher::print
void print(std::ostream &out) const
Print out some statistics.
Definition: RubyPrefetcher.cc:346
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition: types.hh:84
gem5::ruby::RubyPrefetcher::NonUnitFilterEntry
Definition: RubyPrefetcher.hh:146
gem5::ruby::RubyPrefetcher::Params
RubyPrefetcherParams Params
Definition: RubyPrefetcher.hh:104
gem5::ruby::RubyPrefetcher::RubyPrefetcher
RubyPrefetcher(const Params &p)
Definition: RubyPrefetcher.cc:57

Generated on Tue Sep 21 2021 12:25:41 for gem5 by doxygen 1.8.17