indirect_memory.cc revision 13963
113772Sjavier.bueno@metempsy.com/** 213772Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313772Sjavier.bueno@metempsy.com * All rights reserved. 413772Sjavier.bueno@metempsy.com * 513772Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613772Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713772Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813772Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913772Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013772Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113772Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213772Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313772Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413772Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513772Sjavier.bueno@metempsy.com * 1613772Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713772Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813772Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913772Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013772Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113772Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213772Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313772Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413772Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513772Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613772Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713772Sjavier.bueno@metempsy.com * 2813772Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913772Sjavier.bueno@metempsy.com */ 3013772Sjavier.bueno@metempsy.com 3113772Sjavier.bueno@metempsy.com #include "mem/cache/prefetch/indirect_memory.hh" 3213772Sjavier.bueno@metempsy.com 3313772Sjavier.bueno@metempsy.com #include "mem/cache/base.hh" 3413772Sjavier.bueno@metempsy.com #include "mem/cache/prefetch/associative_set_impl.hh" 3513772Sjavier.bueno@metempsy.com #include "params/IndirectMemoryPrefetcher.hh" 3613772Sjavier.bueno@metempsy.com 3713772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::IndirectMemoryPrefetcher( 3813772Sjavier.bueno@metempsy.com const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), 3913772Sjavier.bueno@metempsy.com maxPrefetchDistance(p->max_prefetch_distance), 4013772Sjavier.bueno@metempsy.com shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), 4113772Sjavier.bueno@metempsy.com streamCounterThreshold(p->stream_counter_threshold), 4213772Sjavier.bueno@metempsy.com streamingDistance(p->streaming_distance), 4313772Sjavier.bueno@metempsy.com prefetchTable(p->pt_table_assoc, p->pt_table_entries, 4413963Sodanrc@yahoo.com.br p->pt_table_indexing_policy, p->pt_table_replacement_policy, 4513963Sodanrc@yahoo.com.br PrefetchTableEntry(p->num_indirect_counter_bits)), 4613772Sjavier.bueno@metempsy.com ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, 4713772Sjavier.bueno@metempsy.com p->ipd_table_replacement_policy, 4813772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), 4913772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses(nullptr), 5013772Sjavier.bueno@metempsy.com#if THE_ISA != NULL_ISA 5113772Sjavier.bueno@metempsy.com byteOrder(TheISA::GuestByteOrder) 5213772Sjavier.bueno@metempsy.com#else 5313772Sjavier.bueno@metempsy.com byteOrder((ByteOrder) -1) 5413772Sjavier.bueno@metempsy.com#endif 5513772Sjavier.bueno@metempsy.com{ 5613775SAndrea.Mondelli@ucf.edu fatal_if(byteOrder == static_cast<ByteOrder>(-1), 5713775SAndrea.Mondelli@ucf.edu "This prefetcher requires a defined ISA\n"); 5813772Sjavier.bueno@metempsy.com} 5913772Sjavier.bueno@metempsy.com 6013772Sjavier.bueno@metempsy.comvoid 6113772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 6213772Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 6313772Sjavier.bueno@metempsy.com{ 6413772Sjavier.bueno@metempsy.com // This prefetcher requires a PC 6513772Sjavier.bueno@metempsy.com if (!pfi.hasPC()) { 6613772Sjavier.bueno@metempsy.com return; 6713772Sjavier.bueno@metempsy.com } 6813772Sjavier.bueno@metempsy.com 6913772Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 7013772Sjavier.bueno@metempsy.com Addr pc = pfi.getPC(); 7113772Sjavier.bueno@metempsy.com Addr addr = pfi.getAddr(); 7213772Sjavier.bueno@metempsy.com bool miss = pfi.isCacheMiss(); 7313772Sjavier.bueno@metempsy.com 7413772Sjavier.bueno@metempsy.com checkAccessMatchOnActiveEntries(addr); 7513772Sjavier.bueno@metempsy.com 7613772Sjavier.bueno@metempsy.com // First check if this is a miss, if the prefetcher is tracking misses 7713772Sjavier.bueno@metempsy.com if (ipdEntryTrackingMisses != nullptr && miss) { 7813772Sjavier.bueno@metempsy.com // Check if the entry tracking misses has already set its second index 7913772Sjavier.bueno@metempsy.com if (!ipdEntryTrackingMisses->secondIndexSet) { 8013772Sjavier.bueno@metempsy.com trackMissIndex1(addr); 8113772Sjavier.bueno@metempsy.com } else { 8213772Sjavier.bueno@metempsy.com trackMissIndex2(addr); 8313772Sjavier.bueno@metempsy.com } 8413772Sjavier.bueno@metempsy.com } else { 8513772Sjavier.bueno@metempsy.com // if misses are not being tracked, attempt to detect stream accesses 8613772Sjavier.bueno@metempsy.com PrefetchTableEntry *pt_entry = 8713772Sjavier.bueno@metempsy.com prefetchTable.findEntry(pc, false /* unused */); 8813772Sjavier.bueno@metempsy.com if (pt_entry != nullptr) { 8913772Sjavier.bueno@metempsy.com prefetchTable.accessEntry(pt_entry); 9013772Sjavier.bueno@metempsy.com 9113772Sjavier.bueno@metempsy.com if (pt_entry->address != addr) { 9213772Sjavier.bueno@metempsy.com // Streaming access found 9313772Sjavier.bueno@metempsy.com pt_entry->streamCounter += 1; 9413772Sjavier.bueno@metempsy.com if (pt_entry->streamCounter >= streamCounterThreshold) { 9513772Sjavier.bueno@metempsy.com int64_t delta = addr - pt_entry->address; 9613772Sjavier.bueno@metempsy.com for (unsigned int i = 1; i <= streamingDistance; i += 1) { 9713772Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(addr + delta * i, 0)); 9813772Sjavier.bueno@metempsy.com } 9913772Sjavier.bueno@metempsy.com } 10013772Sjavier.bueno@metempsy.com pt_entry->address = addr; 10113772Sjavier.bueno@metempsy.com pt_entry->secure = is_secure; 10213772Sjavier.bueno@metempsy.com 10313772Sjavier.bueno@metempsy.com 10413772Sjavier.bueno@metempsy.com // if this is a read, read the data from the cache and assume 10513772Sjavier.bueno@metempsy.com // it is an index (this is only possible if the data is already 10613772Sjavier.bueno@metempsy.com // in the cache), also, only indexes up to 8 bytes are 10713772Sjavier.bueno@metempsy.com // considered 10813772Sjavier.bueno@metempsy.com 10913772Sjavier.bueno@metempsy.com if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { 11013772Sjavier.bueno@metempsy.com int64_t index = 0; 11113827Sjavier.bueno@metempsy.com bool read_index = true; 11213772Sjavier.bueno@metempsy.com switch(pfi.getSize()) { 11313772Sjavier.bueno@metempsy.com case sizeof(uint8_t): 11413772Sjavier.bueno@metempsy.com index = pfi.get<uint8_t>(byteOrder); 11513772Sjavier.bueno@metempsy.com break; 11613772Sjavier.bueno@metempsy.com case sizeof(uint16_t): 11713772Sjavier.bueno@metempsy.com index = pfi.get<uint16_t>(byteOrder); 11813772Sjavier.bueno@metempsy.com break; 11913772Sjavier.bueno@metempsy.com case sizeof(uint32_t): 12013772Sjavier.bueno@metempsy.com index = pfi.get<uint32_t>(byteOrder); 12113772Sjavier.bueno@metempsy.com break; 12213772Sjavier.bueno@metempsy.com case sizeof(uint64_t): 12313772Sjavier.bueno@metempsy.com index = pfi.get<uint64_t>(byteOrder); 12413772Sjavier.bueno@metempsy.com break; 12513772Sjavier.bueno@metempsy.com default: 12613827Sjavier.bueno@metempsy.com // Ignore non-power-of-two sizes 12713827Sjavier.bueno@metempsy.com read_index = false; 12813772Sjavier.bueno@metempsy.com } 12913827Sjavier.bueno@metempsy.com if (read_index && !pt_entry->enabled) { 13013772Sjavier.bueno@metempsy.com // Not enabled (no pattern detected in this stream), 13113772Sjavier.bueno@metempsy.com // add or update an entry in the pattern detector and 13213772Sjavier.bueno@metempsy.com // start tracking misses 13313772Sjavier.bueno@metempsy.com allocateOrUpdateIPDEntry(pt_entry, index); 13413827Sjavier.bueno@metempsy.com } else if (read_index) { 13513772Sjavier.bueno@metempsy.com // Enabled entry, update the index 13613772Sjavier.bueno@metempsy.com pt_entry->index = index; 13713772Sjavier.bueno@metempsy.com if (!pt_entry->increasedIndirectCounter) { 13813963Sodanrc@yahoo.com.br pt_entry->indirectCounter--; 13913772Sjavier.bueno@metempsy.com } else { 14013772Sjavier.bueno@metempsy.com // Set this to false, to see if the new index 14113772Sjavier.bueno@metempsy.com // has any match 14213772Sjavier.bueno@metempsy.com pt_entry->increasedIndirectCounter = false; 14313772Sjavier.bueno@metempsy.com } 14413772Sjavier.bueno@metempsy.com 14513772Sjavier.bueno@metempsy.com // If the counter is high enough, start prefetching 14613772Sjavier.bueno@metempsy.com if (pt_entry->indirectCounter > prefetchThreshold) { 14713963Sodanrc@yahoo.com.br unsigned distance = maxPrefetchDistance * 14813963Sodanrc@yahoo.com.br pt_entry->indirectCounter.calcSaturation(); 14913772Sjavier.bueno@metempsy.com for (int delta = 1; delta < distance; delta += 1) { 15013772Sjavier.bueno@metempsy.com Addr pf_addr = pt_entry->baseAddr + 15113772Sjavier.bueno@metempsy.com (pt_entry->index << pt_entry->shift); 15213772Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(pf_addr, 0)); 15313772Sjavier.bueno@metempsy.com } 15413772Sjavier.bueno@metempsy.com } 15513772Sjavier.bueno@metempsy.com } 15613772Sjavier.bueno@metempsy.com } 15713772Sjavier.bueno@metempsy.com } 15813772Sjavier.bueno@metempsy.com } else { 15913772Sjavier.bueno@metempsy.com pt_entry = prefetchTable.findVictim(pc); 16013772Sjavier.bueno@metempsy.com assert(pt_entry != nullptr); 16113772Sjavier.bueno@metempsy.com prefetchTable.insertEntry(pc, false /* unused */, pt_entry); 16213772Sjavier.bueno@metempsy.com pt_entry->address = addr; 16313772Sjavier.bueno@metempsy.com pt_entry->secure = is_secure; 16413772Sjavier.bueno@metempsy.com } 16513772Sjavier.bueno@metempsy.com } 16613772Sjavier.bueno@metempsy.com} 16713772Sjavier.bueno@metempsy.com 16813772Sjavier.bueno@metempsy.comvoid 16913772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( 17013772Sjavier.bueno@metempsy.com const PrefetchTableEntry *pt_entry, int64_t index) 17113772Sjavier.bueno@metempsy.com{ 17213772Sjavier.bueno@metempsy.com // The address of the pt_entry is used to index the IPD 17313772Sjavier.bueno@metempsy.com Addr ipd_entry_addr = (Addr) pt_entry; 17413772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, 17513772Sjavier.bueno@metempsy.com false/* unused */); 17613772Sjavier.bueno@metempsy.com if (ipd_entry != nullptr) { 17713772Sjavier.bueno@metempsy.com ipd.accessEntry(ipd_entry); 17813772Sjavier.bueno@metempsy.com if (!ipd_entry->secondIndexSet) { 17913772Sjavier.bueno@metempsy.com // Second time we see an index, fill idx2 18013772Sjavier.bueno@metempsy.com ipd_entry->idx2 = index; 18113772Sjavier.bueno@metempsy.com ipd_entry->secondIndexSet = true; 18213772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = ipd_entry; 18313772Sjavier.bueno@metempsy.com } else { 18413772Sjavier.bueno@metempsy.com // Third access! no pattern has been found so far, 18513772Sjavier.bueno@metempsy.com // release the IPD entry 18613772Sjavier.bueno@metempsy.com ipd_entry->reset(); 18713772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 18813772Sjavier.bueno@metempsy.com } 18913772Sjavier.bueno@metempsy.com } else { 19013772Sjavier.bueno@metempsy.com ipd_entry = ipd.findVictim(ipd_entry_addr); 19113772Sjavier.bueno@metempsy.com assert(ipd_entry != nullptr); 19213772Sjavier.bueno@metempsy.com ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); 19313772Sjavier.bueno@metempsy.com ipd_entry->idx1 = index; 19413772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = ipd_entry; 19513772Sjavier.bueno@metempsy.com } 19613772Sjavier.bueno@metempsy.com} 19713772Sjavier.bueno@metempsy.com 19813772Sjavier.bueno@metempsy.comvoid 19913772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) 20013772Sjavier.bueno@metempsy.com{ 20113772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 20213772Sjavier.bueno@metempsy.com // If the second index is not set, we are just filling the baseAddr 20313772Sjavier.bueno@metempsy.com // vector 20413772Sjavier.bueno@metempsy.com assert(entry->numMisses < entry->baseAddr.size()); 20513772Sjavier.bueno@metempsy.com std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses]; 20613772Sjavier.bueno@metempsy.com int idx = 0; 20713772Sjavier.bueno@metempsy.com for (int shift : shiftValues) { 20813772Sjavier.bueno@metempsy.com ba_array[idx] = miss_addr - (entry->idx1 << shift); 20913772Sjavier.bueno@metempsy.com idx += 1; 21013772Sjavier.bueno@metempsy.com } 21113772Sjavier.bueno@metempsy.com entry->numMisses += 1; 21213772Sjavier.bueno@metempsy.com if (entry->numMisses == entry->baseAddr.size()) { 21313772Sjavier.bueno@metempsy.com // stop tracking misses once we have tracked enough 21413772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 21513772Sjavier.bueno@metempsy.com } 21613772Sjavier.bueno@metempsy.com} 21713772Sjavier.bueno@metempsy.comvoid 21813772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) 21913772Sjavier.bueno@metempsy.com{ 22013772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 22113772Sjavier.bueno@metempsy.com // Second index is filled, compare the addresses generated during 22213772Sjavier.bueno@metempsy.com // the previous misses (using idx1) against newly generated values 22313772Sjavier.bueno@metempsy.com // using idx2, if a match is found, fill the additional fields 22413772Sjavier.bueno@metempsy.com // of the PT entry 22513772Sjavier.bueno@metempsy.com for (int midx = 0; midx < entry->numMisses; midx += 1) 22613772Sjavier.bueno@metempsy.com { 22713772Sjavier.bueno@metempsy.com std::vector<Addr> &ba_array = entry->baseAddr[midx]; 22813772Sjavier.bueno@metempsy.com int idx = 0; 22913772Sjavier.bueno@metempsy.com for (int shift : shiftValues) { 23013772Sjavier.bueno@metempsy.com if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { 23113772Sjavier.bueno@metempsy.com // Match found! 23213772Sjavier.bueno@metempsy.com // Fill the corresponding pt_entry 23313772Sjavier.bueno@metempsy.com PrefetchTableEntry *pt_entry = 23413772Sjavier.bueno@metempsy.com (PrefetchTableEntry *) entry->getTag(); 23513772Sjavier.bueno@metempsy.com pt_entry->baseAddr = ba_array[idx]; 23613772Sjavier.bueno@metempsy.com pt_entry->shift = shift; 23713772Sjavier.bueno@metempsy.com pt_entry->enabled = true; 23813963Sodanrc@yahoo.com.br pt_entry->indirectCounter.reset(); 23913772Sjavier.bueno@metempsy.com // Release the current IPD Entry 24013772Sjavier.bueno@metempsy.com entry->reset(); 24113772Sjavier.bueno@metempsy.com // Do not track more misses 24213772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 24313772Sjavier.bueno@metempsy.com return; 24413772Sjavier.bueno@metempsy.com } 24513772Sjavier.bueno@metempsy.com idx += 1; 24613772Sjavier.bueno@metempsy.com } 24713772Sjavier.bueno@metempsy.com } 24813772Sjavier.bueno@metempsy.com} 24913772Sjavier.bueno@metempsy.com 25013772Sjavier.bueno@metempsy.comvoid 25113772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) 25213772Sjavier.bueno@metempsy.com{ 25313772Sjavier.bueno@metempsy.com for (auto &pt_entry : prefetchTable) { 25413772Sjavier.bueno@metempsy.com if (pt_entry.enabled) { 25513772Sjavier.bueno@metempsy.com if (addr == pt_entry.baseAddr + 25613772Sjavier.bueno@metempsy.com (pt_entry.index << pt_entry.shift)) { 25713963Sodanrc@yahoo.com.br pt_entry.indirectCounter++; 25813963Sodanrc@yahoo.com.br pt_entry.increasedIndirectCounter = true; 25913772Sjavier.bueno@metempsy.com } 26013772Sjavier.bueno@metempsy.com } 26113772Sjavier.bueno@metempsy.com } 26213772Sjavier.bueno@metempsy.com} 26313772Sjavier.bueno@metempsy.com 26413772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher* 26513772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcherParams::create() 26613772Sjavier.bueno@metempsy.com{ 26713772Sjavier.bueno@metempsy.com return new IndirectMemoryPrefetcher(this); 26813772Sjavier.bueno@metempsy.com} 269