indirect_memory.cc revision 13827:2764e4b4de5d
1/** 2 * Copyright (c) 2018 Metempsy Technology Consulting 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: Javier Bueno 29 */ 30 31 #include "mem/cache/prefetch/indirect_memory.hh" 32 33 #include "mem/cache/base.hh" 34 #include "mem/cache/prefetch/associative_set_impl.hh" 35 #include "params/IndirectMemoryPrefetcher.hh" 36 37IndirectMemoryPrefetcher::IndirectMemoryPrefetcher( 38 const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), 39 maxPrefetchDistance(p->max_prefetch_distance), 40 shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), 41 maxIndirectCounterValue(p->max_indirect_counter_value), 42 streamCounterThreshold(p->stream_counter_threshold), 43 streamingDistance(p->streaming_distance), 44 prefetchTable(p->pt_table_assoc, p->pt_table_entries, 45 p->pt_table_indexing_policy, p->pt_table_replacement_policy), 46 ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, 47 p->ipd_table_replacement_policy, 48 IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), 49 ipdEntryTrackingMisses(nullptr), 50#if THE_ISA != NULL_ISA 51 byteOrder(TheISA::GuestByteOrder) 52#else 53 byteOrder((ByteOrder) -1) 54#endif 55{ 56 fatal_if(byteOrder == static_cast<ByteOrder>(-1), 57 "This prefetcher requires a defined ISA\n"); 58} 59 60void 61IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 62 std::vector<AddrPriority> &addresses) 63{ 64 // This prefetcher requires a PC 65 if (!pfi.hasPC()) { 66 return; 67 } 68 69 bool is_secure = pfi.isSecure(); 70 Addr pc = pfi.getPC(); 71 Addr addr = pfi.getAddr(); 72 bool miss = pfi.isCacheMiss(); 73 74 checkAccessMatchOnActiveEntries(addr); 75 76 // First check if this is a miss, if the prefetcher is tracking misses 77 if (ipdEntryTrackingMisses != nullptr && miss) { 78 // Check if the entry tracking misses has already set its second index 79 if (!ipdEntryTrackingMisses->secondIndexSet) { 80 trackMissIndex1(addr); 81 } else { 82 trackMissIndex2(addr); 83 } 84 } else { 85 // if misses are not being tracked, attempt to detect stream accesses 86 PrefetchTableEntry *pt_entry = 87 prefetchTable.findEntry(pc, false /* unused */); 88 if (pt_entry != nullptr) { 89 prefetchTable.accessEntry(pt_entry); 90 91 if (pt_entry->address != addr) { 92 // Streaming access found 93 pt_entry->streamCounter += 1; 94 if (pt_entry->streamCounter >= streamCounterThreshold) { 95 int64_t delta = addr - pt_entry->address; 96 for (unsigned int i = 1; i <= streamingDistance; i += 1) { 97 addresses.push_back(AddrPriority(addr + delta * i, 0)); 98 } 99 } 100 pt_entry->address = addr; 101 pt_entry->secure = is_secure; 102 103 104 // if this is a read, read the data from the cache and assume 105 // it is an index (this is only possible if the data is already 106 // in the cache), also, only indexes up to 8 bytes are 107 // considered 108 109 if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { 110 int64_t index = 0; 111 bool read_index = true; 112 switch(pfi.getSize()) { 113 case sizeof(uint8_t): 114 index = pfi.get<uint8_t>(byteOrder); 115 break; 116 case sizeof(uint16_t): 117 index = pfi.get<uint16_t>(byteOrder); 118 break; 119 case sizeof(uint32_t): 120 index = pfi.get<uint32_t>(byteOrder); 121 break; 122 case sizeof(uint64_t): 123 index = pfi.get<uint64_t>(byteOrder); 124 break; 125 default: 126 // Ignore non-power-of-two sizes 127 read_index = false; 128 } 129 if (read_index && !pt_entry->enabled) { 130 // Not enabled (no pattern detected in this stream), 131 // add or update an entry in the pattern detector and 132 // start tracking misses 133 allocateOrUpdateIPDEntry(pt_entry, index); 134 } else if (read_index) { 135 // Enabled entry, update the index 136 pt_entry->index = index; 137 if (!pt_entry->increasedIndirectCounter) { 138 if (pt_entry->indirectCounter > 0) { 139 pt_entry->indirectCounter -= 1; 140 } 141 } else { 142 // Set this to false, to see if the new index 143 // has any match 144 pt_entry->increasedIndirectCounter = false; 145 } 146 147 // If the counter is high enough, start prefetching 148 if (pt_entry->indirectCounter > prefetchThreshold) { 149 unsigned distance = pt_entry->indirectCounter * 150 maxPrefetchDistance / maxIndirectCounterValue; 151 for (int delta = 1; delta < distance; delta += 1) { 152 Addr pf_addr = pt_entry->baseAddr + 153 (pt_entry->index << pt_entry->shift); 154 addresses.push_back(AddrPriority(pf_addr, 0)); 155 } 156 } 157 } 158 } 159 } 160 } else { 161 pt_entry = prefetchTable.findVictim(pc); 162 assert(pt_entry != nullptr); 163 prefetchTable.insertEntry(pc, false /* unused */, pt_entry); 164 pt_entry->address = addr; 165 pt_entry->secure = is_secure; 166 } 167 } 168} 169 170void 171IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( 172 const PrefetchTableEntry *pt_entry, int64_t index) 173{ 174 // The address of the pt_entry is used to index the IPD 175 Addr ipd_entry_addr = (Addr) pt_entry; 176 IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, 177 false/* unused */); 178 if (ipd_entry != nullptr) { 179 ipd.accessEntry(ipd_entry); 180 if (!ipd_entry->secondIndexSet) { 181 // Second time we see an index, fill idx2 182 ipd_entry->idx2 = index; 183 ipd_entry->secondIndexSet = true; 184 ipdEntryTrackingMisses = ipd_entry; 185 } else { 186 // Third access! no pattern has been found so far, 187 // release the IPD entry 188 ipd_entry->reset(); 189 ipdEntryTrackingMisses = nullptr; 190 } 191 } else { 192 ipd_entry = ipd.findVictim(ipd_entry_addr); 193 assert(ipd_entry != nullptr); 194 ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); 195 ipd_entry->idx1 = index; 196 ipdEntryTrackingMisses = ipd_entry; 197 } 198} 199 200void 201IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) 202{ 203 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 204 // If the second index is not set, we are just filling the baseAddr 205 // vector 206 assert(entry->numMisses < entry->baseAddr.size()); 207 std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses]; 208 int idx = 0; 209 for (int shift : shiftValues) { 210 ba_array[idx] = miss_addr - (entry->idx1 << shift); 211 idx += 1; 212 } 213 entry->numMisses += 1; 214 if (entry->numMisses == entry->baseAddr.size()) { 215 // stop tracking misses once we have tracked enough 216 ipdEntryTrackingMisses = nullptr; 217 } 218} 219void 220IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) 221{ 222 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 223 // Second index is filled, compare the addresses generated during 224 // the previous misses (using idx1) against newly generated values 225 // using idx2, if a match is found, fill the additional fields 226 // of the PT entry 227 for (int midx = 0; midx < entry->numMisses; midx += 1) 228 { 229 std::vector<Addr> &ba_array = entry->baseAddr[midx]; 230 int idx = 0; 231 for (int shift : shiftValues) { 232 if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { 233 // Match found! 234 // Fill the corresponding pt_entry 235 PrefetchTableEntry *pt_entry = 236 (PrefetchTableEntry *) entry->getTag(); 237 pt_entry->baseAddr = ba_array[idx]; 238 pt_entry->shift = shift; 239 pt_entry->enabled = true; 240 pt_entry->indirectCounter = 0; 241 // Release the current IPD Entry 242 entry->reset(); 243 // Do not track more misses 244 ipdEntryTrackingMisses = nullptr; 245 return; 246 } 247 idx += 1; 248 } 249 } 250} 251 252void 253IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) 254{ 255 for (auto &pt_entry : prefetchTable) { 256 if (pt_entry.enabled) { 257 if (addr == pt_entry.baseAddr + 258 (pt_entry.index << pt_entry.shift)) { 259 if (pt_entry.indirectCounter < maxIndirectCounterValue) { 260 pt_entry.indirectCounter += 1; 261 pt_entry.increasedIndirectCounter = true; 262 } 263 } 264 } 265 } 266} 267 268IndirectMemoryPrefetcher* 269IndirectMemoryPrefetcherParams::create() 270{ 271 return new IndirectMemoryPrefetcher(this); 272} 273