gem5  v20.1.0.0
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 Prefetcher {
61 
63  : TaggedEntry(), confidence(init_confidence)
64 {
65  invalidate();
66 }
67 
68 void
70 {
71  lastAddr = 0;
72  stride = 0;
73  confidence.reset();
74 }
75 
76 Stride::Stride(const StridePrefetcherParams *p)
77  : Queued(p),
78  initConfidence(p->confidence_counter_bits, p->initial_confidence),
79  threshConf(p->confidence_threshold/100.0),
80  useRequestorId(p->use_requestor_id),
81  degree(p->degree),
82  pcTableInfo(p->table_assoc, p->table_entries, p->table_indexing_policy,
83  p->table_replacement_policy)
84 {
85 }
86 
88 Stride::findTable(int context)
89 {
90  // Check if table for given context exists
91  auto it = pcTables.find(context);
92  if (it != pcTables.end())
93  return &it->second;
94 
95  // If table does not exist yet, create one
96  return allocateNewContext(context);
97 }
98 
101 {
102  // Create new table
103  auto insertion_result = pcTables.insert(std::make_pair(context,
107 
108  DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context);
109 
110  // Get iterator to new pc table, and then return a pointer to the new table
111  return &(insertion_result.first->second);
112 }
113 
114 void
116  std::vector<AddrPriority> &addresses)
117 {
118  if (!pfi.hasPC()) {
119  DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
120  return;
121  }
122 
123  // Get required packet info
124  Addr pf_addr = pfi.getAddr();
125  Addr pc = pfi.getPC();
126  bool is_secure = pfi.isSecure();
127  RequestorID requestor_id = useRequestorId ? pfi.getRequestorId() : 0;
128 
129  // Get corresponding pc table
130  PCTable* pcTable = findTable(requestor_id);
131 
132  // Search for entry in the pc table
133  StrideEntry *entry = pcTable->findEntry(pc, is_secure);
134 
135  if (entry != nullptr) {
136  pcTable->accessEntry(entry);
137 
138  // Hit in table
139  int new_stride = pf_addr - entry->lastAddr;
140  bool stride_match = (new_stride == entry->stride);
141 
142  // Adjust confidence for stride entry
143  if (stride_match && new_stride != 0) {
144  entry->confidence++;
145  } else {
146  entry->confidence--;
147  // If confidence has dropped below the threshold, train new stride
148  if (entry->confidence.calcSaturation() < threshConf) {
149  entry->stride = new_stride;
150  }
151  }
152 
153  DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
154  "conf %d\n", pc, pf_addr, is_secure ? "s" : "ns",
155  new_stride, stride_match ? "match" : "change",
156  (int)entry->confidence);
157 
158  entry->lastAddr = pf_addr;
159 
160  // Abort prefetch generation if below confidence threshold
161  if (entry->confidence.calcSaturation() < threshConf) {
162  return;
163  }
164 
165  // Generate up to degree prefetches
166  for (int d = 1; d <= degree; d++) {
167  // Round strides up to atleast 1 cacheline
168  int prefetch_stride = new_stride;
169  if (abs(new_stride) < blkSize) {
170  prefetch_stride = (new_stride < 0) ? -blkSize : blkSize;
171  }
172 
173  Addr new_addr = pf_addr + d * prefetch_stride;
174  addresses.push_back(AddrPriority(new_addr, 0));
175  }
176  } else {
177  // Miss in table
178  DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pf_addr,
179  is_secure ? "s" : "ns");
180 
181  StrideEntry* entry = pcTable->findVictim(pc);
182 
183  // Insert new entry's data
184  entry->lastAddr = pf_addr;
185  pcTable->insertEntry(pc, is_secure, entry);
186  }
187 }
188 
189 inline uint32_t
191 {
192  const Addr hash1 = pc >> 1;
193  const Addr hash2 = hash1 >> tagShift;
194  return (hash1 ^ hash2) & setMask;
195 }
196 
197 Addr
199 {
200  return addr;
201 }
202 
203 } // namespace Prefetcher
204 
206 StridePrefetcherHashedSetAssociativeParams::create()
207 {
209 }
210 
212 StridePrefetcherParams::create()
213 {
214  return new Prefetcher::Stride(this);
215 }
associative_set_impl.hh
Prefetcher::Queued::AddrPriority
std::pair< Addr, int32_t > AddrPriority
Definition: queued.hh:182
Prefetcher::Stride
Definition: stride.hh:88
Prefetcher::Stride::useRequestorId
const bool useRequestorId
Definition: stride.hh:97
BaseIndexingPolicy::setMask
const unsigned setMask
Mask out all bits that aren't part of the set index.
Definition: base.hh:84
Prefetcher::Stride::PCTableInfo::replacementPolicy
BaseReplacementPolicy *const replacementPolicy
Definition: stride.hh:110
Prefetcher::Stride::StrideEntry::lastAddr
Addr lastAddr
Definition: stride.hh:129
Prefetcher::Base::blkSize
unsigned blkSize
The block size of the parent cache.
Definition: base.hh:262
TaggedEntry
Copyright (c) 2018 Metempsy Technology Consulting All rights reserved.
Definition: associative_set.hh:39
Prefetcher::Base::PrefetchInfo::getPC
Addr getPC() const
Returns the program counter that generated this request.
Definition: base.hh:135
AssociativeSet
Associative container based on the previosuly defined Entry type Each element is indexed by a key of ...
Definition: associative_set.hh:117
random.hh
Prefetcher::Stride::allocateNewContext
PCTable * allocateNewContext(int context)
Create a PC table for the given context.
Definition: stride.cc:100
Prefetcher::Stride::PCTable
AssociativeSet< StrideEntry > PCTable
Definition: stride.hh:133
std::vector
STL vector class.
Definition: stl.hh:37
Prefetcher::Stride::pcTables
std::unordered_map< int, PCTable > pcTables
Definition: stride.hh:134
Prefetcher::Stride::threshConf
const double threshConf
Confidence threshold for prefetch generation.
Definition: stride.hh:95
Prefetcher::Stride::calculatePrefetch
void calculatePrefetch(const PrefetchInfo &pfi, std::vector< AddrPriority > &addresses) override
Definition: stride.cc:115
Prefetcher::Stride::StrideEntry::stride
int stride
Definition: stride.hh:130
AssociativeSet::findEntry
Entry * findEntry(Addr addr, bool is_secure) const
Find an entry within the set.
Definition: associative_set_impl.hh:55
Prefetcher::Stride::Stride
Stride(const StridePrefetcherParams *p)
Definition: stride.cc:76
RequestorID
uint16_t RequestorID
Definition: request.hh:85
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:73
Prefetcher::StridePrefetcherHashedSetAssociative::extractSet
uint32_t extractSet(const Addr addr) const override
Apply a hash function to calculate address set.
Definition: stride.cc:190
Prefetcher::Base::PrefetchInfo::getRequestorId
RequestorID getRequestorId() const
Gets the requestor ID that generated this address.
Definition: base.hh:154
Prefetcher::Stride::StrideEntry::StrideEntry
StrideEntry(const SatCounter &init_confidence)
Definition: stride.cc:62
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:234
SatCounter::calcSaturation
double calcSaturation() const
Calculate saturation percentile of the current counter's value with regard to its maximum possible va...
Definition: sat_counter.hh:297
ArmISA::d
Bitfield< 9 > d
Definition: miscregs_types.hh:60
MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:240
Prefetcher
Copyright (c) 2018 Metempsy Technology Consulting All rights reserved.
Definition: base.hh:78
stride.hh
AssociativeSet::insertEntry
void insertEntry(Addr addr, bool is_secure, Entry *entry)
Indicate that an entry has just been inserted.
Definition: associative_set_impl.hh:110
base.hh
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
AssociativeSet::findVictim
Entry * findVictim(Addr addr)
Find a victim to be replaced.
Definition: associative_set_impl.hh:80
Prefetcher::Queued
Definition: queued.hh:54
Prefetcher::Stride::findTable
PCTable * findTable(int context)
Try to find a table of entries for the given context.
Definition: stride.cc:88
Prefetcher::Stride::initConfidence
const SatCounter initConfidence
Initial confidence counter value for the pc tables.
Definition: stride.hh:92
Prefetcher::Base::PrefetchInfo::isSecure
bool isSecure() const
Returns true if the address targets the secure memory space.
Definition: base.hh:126
SatCounter
Implements an n bit saturating counter and provides methods to increment, decrement,...
Definition: sat_counter.hh:54
BaseIndexingPolicy::tagShift
const int tagShift
The amount to shift the address to get the tag.
Definition: base.hh:94
Prefetcher::StridePrefetcherHashedSetAssociative
Override the default set associative to apply a specific hash function when extracting a set.
Definition: stride.hh:73
Prefetcher::StridePrefetcherHashedSetAssociative::extractTag
Addr extractTag(const Addr addr) const override
Generate the tag from the given address.
Definition: stride.cc:198
Prefetcher::Stride::PCTableInfo::assoc
const int assoc
Definition: stride.hh:106
Prefetcher::Stride::pcTableInfo
const struct Prefetcher::Stride::PCTableInfo pcTableInfo
addr
ip6_addr_t addr
Definition: inet.hh:423
Prefetcher::Base::PrefetchInfo
Class containing the information needed by the prefetch to train and generate new prefetch requests.
Definition: base.hh:90
ArmISA::stride
Bitfield< 21, 20 > stride
Definition: miscregs_types.hh:441
logging.hh
Prefetcher::Stride::PCTableInfo::numEntries
const int numEntries
Definition: stride.hh:107
Prefetcher::Stride::StrideEntry::confidence
SatCounter confidence
Definition: stride.hh:131
trace.hh
Prefetcher::Stride::StrideEntry::invalidate
void invalidate() override
Invalidates the entry.
Definition: stride.cc:69
Prefetcher::Stride::StrideEntry
Tagged by hashed PCs.
Definition: stride.hh:123
MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:323
intmath.hh
Prefetcher::Base::PrefetchInfo::getAddr
Addr getAddr() const
Obtains the address value of this Prefetcher address.
Definition: base.hh:117
Prefetcher::Base::PrefetchInfo::hasPC
bool hasPC() const
Returns true if the associated program counter is valid.
Definition: base.hh:145
Prefetcher::Stride::degree
const int degree
Definition: stride.hh:99
Prefetcher::Stride::PCTableInfo::indexingPolicy
BaseIndexingPolicy *const indexingPolicy
Definition: stride.hh:109

Generated on Wed Sep 30 2020 14:02:12 for gem5 by doxygen 1.8.17