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

Generated on Wed Dec 21 2022 10:22:37 for gem5 by doxygen 1.9.1