gem5  v21.1.0.2
stride.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2018 Inria
3  * Copyright (c) 2012-2013, 2015 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) 2005 The Regents of The University of Michigan
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 
48 
49 #include <cassert>
50 
51 #include "base/intmath.hh"
52 #include "base/logging.hh"
53 #include "base/random.hh"
54 #include "base/trace.hh"
55 #include "debug/HWPrefetch.hh"
58 #include "params/StridePrefetcher.hh"
59 
60 namespace gem5
61 {
62 
64 namespace prefetch
65 {
66 
68  : TaggedEntry(), confidence(init_confidence)
69 {
70  invalidate();
71 }
72 
73 void
75 {
77  lastAddr = 0;
78  stride = 0;
79  confidence.reset();
80 }
81 
82 Stride::Stride(const StridePrefetcherParams &p)
83  : Queued(p),
84  initConfidence(p.confidence_counter_bits, p.initial_confidence),
85  threshConf(p.confidence_threshold/100.0),
86  useRequestorId(p.use_requestor_id),
87  degree(p.degree),
88  pcTableInfo(p.table_assoc, p.table_entries, p.table_indexing_policy,
89  p.table_replacement_policy)
90 {
91 }
92 
94 Stride::findTable(int context)
95 {
96  // Check if table for given context exists
97  auto it = pcTables.find(context);
98  if (it != pcTables.end())
99  return &it->second;
100 
101  // If table does not exist yet, create one
102  return allocateNewContext(context);
103 }
104 
107 {
108  // Create new table
109  auto insertion_result = pcTables.insert(std::make_pair(context,
113 
114  DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context);
115 
116  // Get iterator to new pc table, and then return a pointer to the new table
117  return &(insertion_result.first->second);
118 }
119 
120 void
122  std::vector<AddrPriority> &addresses)
123 {
124  if (!pfi.hasPC()) {
125  DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
126  return;
127  }
128 
129  // Get required packet info
130  Addr pf_addr = pfi.getAddr();
131  Addr pc = pfi.getPC();
132  bool is_secure = pfi.isSecure();
133  RequestorID requestor_id = useRequestorId ? pfi.getRequestorId() : 0;
134 
135  // Get corresponding pc table
136  PCTable* pcTable = findTable(requestor_id);
137 
138  // Search for entry in the pc table
139  StrideEntry *entry = pcTable->findEntry(pc, is_secure);
140 
141  if (entry != nullptr) {
142  pcTable->accessEntry(entry);
143 
144  // Hit in table
145  int new_stride = pf_addr - entry->lastAddr;
146  bool stride_match = (new_stride == entry->stride);
147 
148  // Adjust confidence for stride entry
149  if (stride_match && new_stride != 0) {
150  entry->confidence++;
151  } else {
152  entry->confidence--;
153  // If confidence has dropped below the threshold, train new stride
154  if (entry->confidence.calcSaturation() < threshConf) {
155  entry->stride = new_stride;
156  }
157  }
158 
159  DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
160  "conf %d\n", pc, pf_addr, is_secure ? "s" : "ns",
161  new_stride, stride_match ? "match" : "change",
162  (int)entry->confidence);
163 
164  entry->lastAddr = pf_addr;
165 
166  // Abort prefetch generation if below confidence threshold
167  if (entry->confidence.calcSaturation() < threshConf) {
168  return;
169  }
170 
171  // Generate up to degree prefetches
172  for (int d = 1; d <= degree; d++) {
173  // Round strides up to atleast 1 cacheline
174  int prefetch_stride = new_stride;
175  if (abs(new_stride) < blkSize) {
176  prefetch_stride = (new_stride < 0) ? -blkSize : blkSize;
177  }
178 
179  Addr new_addr = pf_addr + d * prefetch_stride;
180  addresses.push_back(AddrPriority(new_addr, 0));
181  }
182  } else {
183  // Miss in table
184  DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pf_addr,
185  is_secure ? "s" : "ns");
186 
187  StrideEntry* entry = pcTable->findVictim(pc);
188 
189  // Insert new entry's data
190  entry->lastAddr = pf_addr;
191  pcTable->insertEntry(pc, is_secure, entry);
192  }
193 }
194 
195 uint32_t
197 {
198  const Addr hash1 = pc >> 1;
199  const Addr hash2 = hash1 >> tagShift;
200  return (hash1 ^ hash2) & setMask;
201 }
202 
203 Addr
205 {
206  return addr;
207 }
208 
209 } // namespace prefetch
210 } // namespace gem5
gem5::prefetch::Base::PrefetchInfo::getAddr
Addr getAddr() const
Obtains the address value of this Prefetcher address.
Definition: base.hh:125
associative_set_impl.hh
gem5::prefetch::Stride::Stride
Stride(const StridePrefetcherParams &p)
Definition: stride.cc:82
gem5::prefetch::Stride::PCTableInfo::numEntries
const int numEntries
Definition: stride.hh:116
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::AssociativeSet::insertEntry
void insertEntry(Addr addr, bool is_secure, Entry *entry)
Indicate that an entry has just been inserted.
Definition: associative_set_impl.hh:113
gem5::prefetch::Queued::AddrPriority
std::pair< Addr, int32_t > AddrPriority
Definition: queued.hh:190
gem5::prefetch::Stride::PCTableInfo::indexingPolicy
BaseIndexingPolicy *const indexingPolicy
Definition: stride.hh:118
gem5::BaseIndexingPolicy::setMask
const unsigned setMask
Mask out all bits that aren't part of the set index.
Definition: base.hh:87
gem5::prefetch::Base::PrefetchInfo::isSecure
bool isSecure() const
Returns true if the address targets the secure memory space.
Definition: base.hh:134
gem5::prefetch::Stride::PCTable
AssociativeSet< StrideEntry > PCTable
Definition: stride.hh:141
gem5::prefetch::Stride::useRequestorId
const bool useRequestorId
Definition: stride.hh:106
random.hh
gem5::prefetch::Stride::PCTableInfo::replacementPolicy
replacement_policy::Base *const replacementPolicy
Definition: stride.hh:119
gem5::prefetch::Stride::StrideEntry::invalidate
void invalidate() override
Invalidate the block.
Definition: stride.cc:74
gem5::prefetch::Stride::initConfidence
const SatCounter8 initConfidence
Initial confidence counter value for the pc tables.
Definition: stride.hh:101
std::vector
STL vector class.
Definition: stl.hh:37
gem5::prefetch::Stride::PCTableInfo::assoc
const int assoc
Definition: stride.hh:115
gem5::prefetch::Stride::StrideEntry::confidence
SatCounter8 confidence
Definition: stride.hh:139
gem5::prefetch::Stride::allocateNewContext
PCTable * allocateNewContext(int context)
Create a PC table for the given context.
Definition: stride.cc:106
gem5::prefetch::Base::PrefetchInfo::getRequestorId
RequestorID getRequestorId() const
Gets the requestor ID that generated this address.
Definition: base.hh:162
gem5::prefetch::Stride::StrideEntry::lastAddr
Addr lastAddr
Definition: stride.hh:137
gem5::GenericSatCounter< uint8_t >
gem5::prefetch::Base::PrefetchInfo::getPC
Addr getPC() const
Returns the program counter that generated this request.
Definition: base.hh:143
gem5::prefetch::Stride::pcTableInfo
const struct gem5::prefetch::Stride::PCTableInfo pcTableInfo
gem5::TaggedEntry
A tagged entry is an entry containing a tag.
Definition: tagged_entry.hh:46
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
gem5::AssociativeSet
Associative container based on the previosuly defined Entry type Each element is indexed by a key of ...
Definition: associative_set.hh:45
gem5::ArmISA::d
Bitfield< 9 > d
Definition: misc_types.hh:63
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::prefetch::Stride::threshConf
const double threshConf
Confidence threshold for prefetch generation.
Definition: stride.hh:104
gem5::BaseIndexingPolicy::tagShift
const int tagShift
The amount to shift the address to get the tag.
Definition: base.hh:97
gem5::TaggedEntry::invalidate
virtual void invalidate()
Invalidate the block.
Definition: tagged_entry.hh:103
stride.hh
gem5::prefetch::Stride::StrideEntry::StrideEntry
StrideEntry(const SatCounter8 &init_confidence)
Definition: stride.cc:67
base.hh
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::AssociativeSet::findVictim
Entry * findVictim(Addr addr)
Find a victim to be replaced.
Definition: associative_set_impl.hh:83
gem5::prefetch::Queued
Definition: queued.hh:60
gem5::prefetch::Stride::calculatePrefetch
void calculatePrefetch(const PrefetchInfo &pfi, std::vector< AddrPriority > &addresses) override
Definition: stride.cc:121
gem5::prefetch::Stride::pcTables
std::unordered_map< int, PCTable > pcTables
Definition: stride.hh:142
gem5::MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:243
logging.hh
gem5::prefetch::Base::blkSize
unsigned blkSize
The block size of the parent cache.
Definition: base.hh:270
gem5::RequestorID
uint16_t RequestorID
Definition: request.hh:95
trace.hh
gem5::AssociativeSet::accessEntry
void accessEntry(Entry *entry)
Do an access to the entry, this is required to update the replacement information data.
Definition: associative_set_impl.hh:76
gem5::context_switch_task_id::Prefetcher
@ Prefetcher
Definition: request.hh:83
gem5::AssociativeSet::findEntry
Entry * findEntry(Addr addr, bool is_secure) const
Find an entry within the set.
Definition: associative_set_impl.hh:58
gem5::prefetch::StridePrefetcherHashedSetAssociative::extractSet
uint32_t extractSet(const Addr addr) const override
Apply a hash function to calculate address set.
Definition: stride.cc:196
intmath.hh
gem5::prefetch::Stride::StrideEntry
Tagged by hashed PCs.
Definition: stride.hh:131
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::prefetch::Stride::StrideEntry::stride
int stride
Definition: stride.hh:138
gem5::ArmISA::stride
Bitfield< 21, 20 > stride
Definition: misc_types.hh:446
gem5::prefetch::Stride::findTable
PCTable * findTable(int context)
Try to find a table of entries for the given context.
Definition: stride.cc:94
gem5::prefetch::Stride::degree
const int degree
Definition: stride.hh:108
gem5::prefetch::StridePrefetcherHashedSetAssociative::extractTag
Addr extractTag(const Addr addr) const override
Generate the tag from the given address.
Definition: stride.cc:204
gem5::prefetch::Base::PrefetchInfo
Class containing the information needed by the prefetch to train and generate new prefetch requests.
Definition: base.hh:97
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition: types.hh:84
gem5::prefetch::Base::PrefetchInfo::hasPC
bool hasPC() const
Returns true if the associated program counter is valid.
Definition: base.hh:153

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