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 * Authors: Daniel Carvalho
29 */
30
31/**
32 * @file
33 * Definitions of a skewed associative indexing policy.
34 */
35
36#include "mem/cache/tags/indexing_policies/skewed_associative.hh"
37
38#include "base/bitfield.hh"
39#include "base/intmath.hh"
40#include "base/logging.hh"
| 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 * Authors: Daniel Carvalho
29 */
30
31/**
32 * @file
33 * Definitions of a skewed associative indexing policy.
34 */
35
36#include "mem/cache/tags/indexing_policies/skewed_associative.hh"
37
38#include "base/bitfield.hh"
39#include "base/intmath.hh"
40#include "base/logging.hh"
|
42
43SkewedAssociative::SkewedAssociative(const Params *p)
44 : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1)
45{
46 if (assoc > NUM_SKEWING_FUNCTIONS) {
47 warn_once("Associativity higher than number of skewing functions. " \
48 "Expect sub-optimal skewing.\n");
49 }
50
51 // Check if set is too big to do skewing. If using big sets, rewrite
52 // skewing functions accordingly to make good use of the hashing function
53 panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \
54 "for the skewing functions.");
55
56 // We must have more than two sets, otherwise the MSB and LSB are the same
57 // bit, and the xor of them will always be 0
58 fatal_if(numSets <= 2, "The number of sets must be greater than 2");
59}
60
61Addr
62SkewedAssociative::hash(const Addr addr) const
63{
64 // Get relevant bits
65 const uint8_t lsb = bits<Addr>(addr, 0);
66 const uint8_t msb = bits<Addr>(addr, msbShift);
67 const uint8_t xor_bit = msb ^ lsb;
68
69 // Shift-off LSB and set new MSB as xor of old LSB and MSB
70 return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit);
71}
72
73Addr
74SkewedAssociative::dehash(const Addr addr) const
75{
76 // Get relevant bits. The original MSB is one bit away on the current MSB
77 // (which is the XOR bit). The original LSB can be retrieved from inverting
78 // the xor that generated the XOR bit.
79 const uint8_t msb = bits<Addr>(addr, msbShift - 1);
80 const uint8_t xor_bit = bits<Addr>(addr, msbShift);
81 const uint8_t lsb = msb ^ xor_bit;
82
83 // Remove current MSB (XOR bit), shift left and add LSB back
84 const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0);
85 return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb);
86}
87
88Addr
89SkewedAssociative::skew(const Addr addr, const uint32_t way) const
90{
91 // Assume an address of size A bits can be decomposed into
92 // {addr3, addr2, addr1, addr0}, where:
93 // addr0 (M bits) = Block offset;
94 // addr1 (N bits) = Set bits in conventional cache;
95 // addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits.
96 // We use addr1 and addr2, as proposed in the original paper
97 Addr addr1 = bits<Addr>(addr, msbShift, 0);
98 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
99
100 // Select and apply skewing function for given way
101 switch (way % NUM_SKEWING_FUNCTIONS) {
102 case 0:
103 addr1 = hash(addr1) ^ hash(addr2) ^ addr2;
104 break;
105 case 1:
106 addr1 = hash(addr1) ^ hash(addr2) ^ addr1;
107 break;
108 case 2:
109 addr1 = hash(addr1) ^ dehash(addr2) ^ addr2;
110 break;
111 case 3:
112 addr1 = hash(addr1) ^ dehash(addr2) ^ addr1;
113 break;
114 case 4:
115 addr1 = dehash(addr1) ^ hash(addr2) ^ addr2;
116 break;
117 case 5:
118 addr1 = dehash(addr1) ^ hash(addr2) ^ addr1;
119 break;
120 case 6:
121 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2;
122 break;
123 case 7:
124 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1;
125 break;
126 default:
127 panic("A skewing function has not been implemented for this way.");
128 }
129
130 // If we have more than 8 ways, just pile them up on hashes. This is not
131 // the optimal solution, and can be improved by adding more skewing
132 // functions to the previous selector
133 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
134 addr1 = hash(addr1);
135 }
136
137 return addr1;
138}
139
140Addr
141SkewedAssociative::deskew(const Addr addr, const uint32_t way) const
142{
143 // Get relevant bits of the addr
144 Addr addr1 = bits<Addr>(addr, msbShift, 0);
145 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
146
147 // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes
148 if (way >= NUM_SKEWING_FUNCTIONS) {
149 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
150 addr1 = dehash(addr1);
151 }
152 }
153
154 // Select and apply skewing function for given way
155 switch (way % 8) {
156 case 0:
157 return dehash(addr1 ^ hash(addr2) ^ addr2);
158 case 1:
159 addr1 = addr1 ^ hash(addr2);
160 for (int i = 0; i < msbShift; i++) {
161 addr1 = hash(addr1);
162 }
163 return addr1;
164 case 2:
165 return dehash(addr1 ^ dehash(addr2) ^ addr2);
166 case 3:
167 addr1 = addr1 ^ dehash(addr2);
168 for (int i = 0; i < msbShift; i++) {
169 addr1 = hash(addr1);
170 }
171 return addr1;
172 case 4:
173 return hash(addr1 ^ hash(addr2) ^ addr2);
174 case 5:
175 addr1 = addr1 ^ hash(addr2);
176 for (int i = 0; i <= msbShift; i++) {
177 addr1 = hash(addr1);
178 }
179 return addr1;
180 case 6:
181 return hash(addr1 ^ dehash(addr2) ^ addr2);
182 case 7:
183 addr1 = addr1 ^ dehash(addr2);
184 for (int i = 0; i <= msbShift; i++) {
185 addr1 = hash(addr1);
186 }
187 return addr1;
188 default:
189 panic("A skewing function has not been implemented for this way.");
190 }
191}
192
193uint32_t
194SkewedAssociative::extractSet(const Addr addr, const uint32_t way) const
195{
196 return skew(addr >> setShift, way) & setMask;
197}
198
199Addr
200SkewedAssociative::regenerateAddr(const Addr tag,
201 const ReplaceableEntry* entry) const
202{
203 const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet();
204 return (tag << tagShift) |
205 ((deskew(addr_set, entry->getWay()) & setMask) << setShift);
206}
207
208std::vector<ReplaceableEntry*>
209SkewedAssociative::getPossibleEntries(const Addr addr) const
210{
211 std::vector<ReplaceableEntry*> entries;
212
213 // Parse all ways
214 for (uint32_t way = 0; way < assoc; ++way) {
215 // Apply hash to get set, and get way entry in it
216 entries.push_back(sets[extractSet(addr, way)][way]);
217 }
218
219 return entries;
220}
221
222SkewedAssociative *
223SkewedAssociativeParams::create()
224{
225 return new SkewedAssociative(this);
226}
| 42
43SkewedAssociative::SkewedAssociative(const Params *p)
44 : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1)
45{
46 if (assoc > NUM_SKEWING_FUNCTIONS) {
47 warn_once("Associativity higher than number of skewing functions. " \
48 "Expect sub-optimal skewing.\n");
49 }
50
51 // Check if set is too big to do skewing. If using big sets, rewrite
52 // skewing functions accordingly to make good use of the hashing function
53 panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \
54 "for the skewing functions.");
55
56 // We must have more than two sets, otherwise the MSB and LSB are the same
57 // bit, and the xor of them will always be 0
58 fatal_if(numSets <= 2, "The number of sets must be greater than 2");
59}
60
61Addr
62SkewedAssociative::hash(const Addr addr) const
63{
64 // Get relevant bits
65 const uint8_t lsb = bits<Addr>(addr, 0);
66 const uint8_t msb = bits<Addr>(addr, msbShift);
67 const uint8_t xor_bit = msb ^ lsb;
68
69 // Shift-off LSB and set new MSB as xor of old LSB and MSB
70 return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit);
71}
72
73Addr
74SkewedAssociative::dehash(const Addr addr) const
75{
76 // Get relevant bits. The original MSB is one bit away on the current MSB
77 // (which is the XOR bit). The original LSB can be retrieved from inverting
78 // the xor that generated the XOR bit.
79 const uint8_t msb = bits<Addr>(addr, msbShift - 1);
80 const uint8_t xor_bit = bits<Addr>(addr, msbShift);
81 const uint8_t lsb = msb ^ xor_bit;
82
83 // Remove current MSB (XOR bit), shift left and add LSB back
84 const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0);
85 return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb);
86}
87
88Addr
89SkewedAssociative::skew(const Addr addr, const uint32_t way) const
90{
91 // Assume an address of size A bits can be decomposed into
92 // {addr3, addr2, addr1, addr0}, where:
93 // addr0 (M bits) = Block offset;
94 // addr1 (N bits) = Set bits in conventional cache;
95 // addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits.
96 // We use addr1 and addr2, as proposed in the original paper
97 Addr addr1 = bits<Addr>(addr, msbShift, 0);
98 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
99
100 // Select and apply skewing function for given way
101 switch (way % NUM_SKEWING_FUNCTIONS) {
102 case 0:
103 addr1 = hash(addr1) ^ hash(addr2) ^ addr2;
104 break;
105 case 1:
106 addr1 = hash(addr1) ^ hash(addr2) ^ addr1;
107 break;
108 case 2:
109 addr1 = hash(addr1) ^ dehash(addr2) ^ addr2;
110 break;
111 case 3:
112 addr1 = hash(addr1) ^ dehash(addr2) ^ addr1;
113 break;
114 case 4:
115 addr1 = dehash(addr1) ^ hash(addr2) ^ addr2;
116 break;
117 case 5:
118 addr1 = dehash(addr1) ^ hash(addr2) ^ addr1;
119 break;
120 case 6:
121 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2;
122 break;
123 case 7:
124 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1;
125 break;
126 default:
127 panic("A skewing function has not been implemented for this way.");
128 }
129
130 // If we have more than 8 ways, just pile them up on hashes. This is not
131 // the optimal solution, and can be improved by adding more skewing
132 // functions to the previous selector
133 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
134 addr1 = hash(addr1);
135 }
136
137 return addr1;
138}
139
140Addr
141SkewedAssociative::deskew(const Addr addr, const uint32_t way) const
142{
143 // Get relevant bits of the addr
144 Addr addr1 = bits<Addr>(addr, msbShift, 0);
145 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
146
147 // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes
148 if (way >= NUM_SKEWING_FUNCTIONS) {
149 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
150 addr1 = dehash(addr1);
151 }
152 }
153
154 // Select and apply skewing function for given way
155 switch (way % 8) {
156 case 0:
157 return dehash(addr1 ^ hash(addr2) ^ addr2);
158 case 1:
159 addr1 = addr1 ^ hash(addr2);
160 for (int i = 0; i < msbShift; i++) {
161 addr1 = hash(addr1);
162 }
163 return addr1;
164 case 2:
165 return dehash(addr1 ^ dehash(addr2) ^ addr2);
166 case 3:
167 addr1 = addr1 ^ dehash(addr2);
168 for (int i = 0; i < msbShift; i++) {
169 addr1 = hash(addr1);
170 }
171 return addr1;
172 case 4:
173 return hash(addr1 ^ hash(addr2) ^ addr2);
174 case 5:
175 addr1 = addr1 ^ hash(addr2);
176 for (int i = 0; i <= msbShift; i++) {
177 addr1 = hash(addr1);
178 }
179 return addr1;
180 case 6:
181 return hash(addr1 ^ dehash(addr2) ^ addr2);
182 case 7:
183 addr1 = addr1 ^ dehash(addr2);
184 for (int i = 0; i <= msbShift; i++) {
185 addr1 = hash(addr1);
186 }
187 return addr1;
188 default:
189 panic("A skewing function has not been implemented for this way.");
190 }
191}
192
193uint32_t
194SkewedAssociative::extractSet(const Addr addr, const uint32_t way) const
195{
196 return skew(addr >> setShift, way) & setMask;
197}
198
199Addr
200SkewedAssociative::regenerateAddr(const Addr tag,
201 const ReplaceableEntry* entry) const
202{
203 const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet();
204 return (tag << tagShift) |
205 ((deskew(addr_set, entry->getWay()) & setMask) << setShift);
206}
207
208std::vector<ReplaceableEntry*>
209SkewedAssociative::getPossibleEntries(const Addr addr) const
210{
211 std::vector<ReplaceableEntry*> entries;
212
213 // Parse all ways
214 for (uint32_t way = 0; way < assoc; ++way) {
215 // Apply hash to get set, and get way entry in it
216 entries.push_back(sets[extractSet(addr, way)][way]);
217 }
218
219 return entries;
220}
221
222SkewedAssociative *
223SkewedAssociativeParams::create()
224{
225 return new SkewedAssociative(this);
226}
|