gem5  v20.1.0.0
skewed_associative.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2018 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 
35 
36 #include "base/bitfield.hh"
37 #include "base/intmath.hh"
38 #include "base/logging.hh"
40 
42  : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1)
43 {
45  warn_once("Associativity higher than number of skewing functions. " \
46  "Expect sub-optimal skewing.\n");
47  }
48 
49  // Check if set is too big to do skewing. If using big sets, rewrite
50  // skewing functions accordingly to make good use of the hashing function
51  panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \
52  "for the skewing functions.");
53 
54  // We must have more than two sets, otherwise the MSB and LSB are the same
55  // bit, and the xor of them will always be 0
56  fatal_if(numSets <= 2, "The number of sets must be greater than 2");
57 }
58 
59 Addr
61 {
62  // Get relevant bits
63  const uint8_t lsb = bits<Addr>(addr, 0);
64  const uint8_t msb = bits<Addr>(addr, msbShift);
65  const uint8_t xor_bit = msb ^ lsb;
66 
67  // Shift-off LSB and set new MSB as xor of old LSB and MSB
68  return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit);
69 }
70 
71 Addr
73 {
74  // Get relevant bits. The original MSB is one bit away on the current MSB
75  // (which is the XOR bit). The original LSB can be retrieved from inverting
76  // the xor that generated the XOR bit.
77  const uint8_t msb = bits<Addr>(addr, msbShift - 1);
78  const uint8_t xor_bit = bits<Addr>(addr, msbShift);
79  const uint8_t lsb = msb ^ xor_bit;
80 
81  // Remove current MSB (XOR bit), shift left and add LSB back
82  const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0);
83  return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb);
84 }
85 
86 Addr
87 SkewedAssociative::skew(const Addr addr, const uint32_t way) const
88 {
89  // Assume an address of size A bits can be decomposed into
90  // {addr3, addr2, addr1, addr0}, where:
91  // addr0 (M bits) = Block offset;
92  // addr1 (N bits) = Set bits in conventional cache;
93  // addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits.
94  // We use addr1 and addr2, as proposed in the original paper
95  Addr addr1 = bits<Addr>(addr, msbShift, 0);
96  const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
97 
98  // Select and apply skewing function for given way
99  switch (way % NUM_SKEWING_FUNCTIONS) {
100  case 0:
101  addr1 = hash(addr1) ^ hash(addr2) ^ addr2;
102  break;
103  case 1:
104  addr1 = hash(addr1) ^ hash(addr2) ^ addr1;
105  break;
106  case 2:
107  addr1 = hash(addr1) ^ dehash(addr2) ^ addr2;
108  break;
109  case 3:
110  addr1 = hash(addr1) ^ dehash(addr2) ^ addr1;
111  break;
112  case 4:
113  addr1 = dehash(addr1) ^ hash(addr2) ^ addr2;
114  break;
115  case 5:
116  addr1 = dehash(addr1) ^ hash(addr2) ^ addr1;
117  break;
118  case 6:
119  addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2;
120  break;
121  case 7:
122  addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1;
123  break;
124  default:
125  panic("A skewing function has not been implemented for this way.");
126  }
127 
128  // If we have more than 8 ways, just pile them up on hashes. This is not
129  // the optimal solution, and can be improved by adding more skewing
130  // functions to the previous selector
131  for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
132  addr1 = hash(addr1);
133  }
134 
135  return addr1;
136 }
137 
138 Addr
139 SkewedAssociative::deskew(const Addr addr, const uint32_t way) const
140 {
141  // Get relevant bits of the addr
142  Addr addr1 = bits<Addr>(addr, msbShift, 0);
143  const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
144 
145  // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes
146  if (way >= NUM_SKEWING_FUNCTIONS) {
147  for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
148  addr1 = dehash(addr1);
149  }
150  }
151 
152  // Select and apply skewing function for given way
153  switch (way % 8) {
154  case 0:
155  return dehash(addr1 ^ hash(addr2) ^ addr2);
156  case 1:
157  addr1 = addr1 ^ hash(addr2);
158  for (int i = 0; i < msbShift; i++) {
159  addr1 = hash(addr1);
160  }
161  return addr1;
162  case 2:
163  return dehash(addr1 ^ dehash(addr2) ^ addr2);
164  case 3:
165  addr1 = addr1 ^ dehash(addr2);
166  for (int i = 0; i < msbShift; i++) {
167  addr1 = hash(addr1);
168  }
169  return addr1;
170  case 4:
171  return hash(addr1 ^ hash(addr2) ^ addr2);
172  case 5:
173  addr1 = addr1 ^ hash(addr2);
174  for (int i = 0; i <= msbShift; i++) {
175  addr1 = hash(addr1);
176  }
177  return addr1;
178  case 6:
179  return hash(addr1 ^ dehash(addr2) ^ addr2);
180  case 7:
181  addr1 = addr1 ^ dehash(addr2);
182  for (int i = 0; i <= msbShift; i++) {
183  addr1 = hash(addr1);
184  }
185  return addr1;
186  default:
187  panic("A skewing function has not been implemented for this way.");
188  }
189 }
190 
191 uint32_t
192 SkewedAssociative::extractSet(const Addr addr, const uint32_t way) const
193 {
194  return skew(addr >> setShift, way) & setMask;
195 }
196 
197 Addr
199  const ReplaceableEntry* entry) const
200 {
201  const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet();
202  return (tag << tagShift) |
203  ((deskew(addr_set, entry->getWay()) & setMask) << setShift);
204 }
205 
208 {
210 
211  // Parse all ways
212  for (uint32_t way = 0; way < assoc; ++way) {
213  // Apply hash to get set, and get way entry in it
214  entries.push_back(sets[extractSet(addr, way)][way]);
215  }
216 
217  return entries;
218 }
219 
221 SkewedAssociativeParams::create()
222 {
223  return new SkewedAssociative(this);
224 }
ReplaceableEntry
A replaceable entry is a basic entry in a 2d table-like structure that needs to have replacement func...
Definition: replaceable_entry.hh:53
BaseIndexingPolicy::setMask
const unsigned setMask
Mask out all bits that aren't part of the set index.
Definition: base.hh:84
warn_once
#define warn_once(...)
Definition: logging.hh:243
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
SkewedAssociative::NUM_SKEWING_FUNCTIONS
const int NUM_SKEWING_FUNCTIONS
The number of skewing functions implemented.
Definition: skewed_associative.hh:78
ReplaceableEntry::getSet
uint32_t getSet() const
Get set number.
Definition: replaceable_entry.hh:94
SkewedAssociative::hash
Addr hash(const Addr addr) const
The hash function itself.
Definition: skewed_associative.cc:60
SkewedAssociative::regenerateAddr
Addr regenerateAddr(const Addr tag, const ReplaceableEntry *entry) const override
Regenerate an entry's address from its tag and assigned set and way.
Definition: skewed_associative.cc:198
std::vector
STL vector class.
Definition: stl.hh:37
floorLog2
std::enable_if< std::is_integral< T >::value, int >::type floorLog2(T x)
Definition: intmath.hh:63
SkewedAssociative::extractSet
uint32_t extractSet(const Addr addr, const uint32_t way) const
Apply a skewing function to calculate address' set given a way.
Definition: skewed_associative.cc:192
BaseIndexingPolicy::sets
std::vector< std::vector< ReplaceableEntry * > > sets
The cache sets.
Definition: base.hh:89
replaceable_entry.hh
bitfield.hh
SkewedAssociative::deskew
Addr deskew(const Addr addr, const uint32_t way) const
Address deskewing function (inverse of the skew function) of the given way.
Definition: skewed_associative.cc:139
SkewedAssociative::getPossibleEntries
std::vector< ReplaceableEntry * > getPossibleEntries(const Addr addr) const override
Find all possible entries for insertion and replacement of an address.
Definition: skewed_associative.cc:207
SkewedAssociative::SkewedAssociative
SkewedAssociative(const Params *p)
Construct and initialize this policy.
Definition: skewed_associative.cc:41
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
SkewedAssociative::dehash
Addr dehash(const Addr addr) const
Inverse of the hash function.
Definition: skewed_associative.cc:72
SkewedAssociative::msbShift
const int msbShift
The amount to shift a set index to get its MSB.
Definition: skewed_associative.hh:83
skewed_associative.hh
BaseIndexingPolicy::setShift
const int setShift
The amount to shift the address to get the set.
Definition: base.hh:79
BaseIndexingPolicy::tagShift
const int tagShift
The amount to shift the address to get the tag.
Definition: base.hh:94
panic_if
#define panic_if(cond,...)
Conditional panic macro that checks the supplied condition and only panics if the condition is true a...
Definition: logging.hh:197
BaseIndexingPolicy::Params
BaseIndexingPolicyParams Params
Convenience typedef.
Definition: base.hh:100
SkewedAssociative
A skewed associative indexing policy.
Definition: skewed_associative.hh:69
addr
ip6_addr_t addr
Definition: inet.hh:423
BaseIndexingPolicy::assoc
const unsigned assoc
The associativity.
Definition: base.hh:69
BaseIndexingPolicy
A common base class for indexing table locations.
Definition: base.hh:63
SkewedAssociative::skew
Addr skew(const Addr addr, const uint32_t way) const
Address skewing function selection.
Definition: skewed_associative.cc:87
logging.hh
MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:323
intmath.hh
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:219
BaseIndexingPolicy::numSets
const uint32_t numSets
The number of sets in the cache.
Definition: base.hh:74
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:171
ReplaceableEntry::getWay
uint32_t getWay() const
Get way number.
Definition: replaceable_entry.hh:101

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