signature_path.cc revision 13553
113553Sjavier.bueno@metempsy.com/** 213553Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313553Sjavier.bueno@metempsy.com * All rights reserved. 413553Sjavier.bueno@metempsy.com * 513553Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613553Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713553Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813553Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913553Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013553Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113553Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213553Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313553Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413553Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513553Sjavier.bueno@metempsy.com * 1613553Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713553Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813553Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913553Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013553Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113553Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213553Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313553Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413553Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513553Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613553Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713553Sjavier.bueno@metempsy.com * 2813553Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913553Sjavier.bueno@metempsy.com */ 3013553Sjavier.bueno@metempsy.com 3113553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/signature_path.hh" 3213553Sjavier.bueno@metempsy.com 3313553Sjavier.bueno@metempsy.com#include <cassert> 3413553Sjavier.bueno@metempsy.com 3513553Sjavier.bueno@metempsy.com#include "debug/HWPrefetch.hh" 3613553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3713553Sjavier.bueno@metempsy.com#include "params/SignaturePathPrefetcher.hh" 3813553Sjavier.bueno@metempsy.com 3913553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::SignaturePathPrefetcher( 4013553Sjavier.bueno@metempsy.com const SignaturePathPrefetcherParams *p) 4113553Sjavier.bueno@metempsy.com : QueuedPrefetcher(p), 4213553Sjavier.bueno@metempsy.com stridesPerPatternEntry(p->strides_per_pattern_entry), 4313553Sjavier.bueno@metempsy.com signatureShift(p->signature_shift), 4413553Sjavier.bueno@metempsy.com signatureBits(p->signature_bits), 4513553Sjavier.bueno@metempsy.com maxCounterValue(p->max_counter_value), 4613553Sjavier.bueno@metempsy.com prefetchConfidenceThreshold(p->prefetch_confidence_threshold), 4713553Sjavier.bueno@metempsy.com lookaheadConfidenceThreshold(p->lookahead_confidence_threshold), 4813553Sjavier.bueno@metempsy.com signatureTable(p->signature_table_assoc, p->signature_table_entries, 4913553Sjavier.bueno@metempsy.com p->signature_table_indexing_policy, 5013553Sjavier.bueno@metempsy.com p->signature_table_replacement_policy), 5113553Sjavier.bueno@metempsy.com patternTable(p->pattern_table_assoc, p->pattern_table_entries, 5213553Sjavier.bueno@metempsy.com p->pattern_table_indexing_policy, 5313553Sjavier.bueno@metempsy.com p->pattern_table_replacement_policy, 5413553Sjavier.bueno@metempsy.com PatternEntry(stridesPerPatternEntry)) 5513553Sjavier.bueno@metempsy.com{ 5613553Sjavier.bueno@metempsy.com} 5713553Sjavier.bueno@metempsy.com 5813553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::PatternStrideEntry & 5913553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride, 6013553Sjavier.bueno@metempsy.com uint8_t max_counter_value) 6113553Sjavier.bueno@metempsy.com{ 6213553Sjavier.bueno@metempsy.com PatternStrideEntry *pstride_entry = findStride(stride); 6313553Sjavier.bueno@metempsy.com if (pstride_entry == nullptr) { 6413553Sjavier.bueno@metempsy.com // Specific replacement algorithm for this table, 6513553Sjavier.bueno@metempsy.com // pick the entry with the lowest counter value, 6613553Sjavier.bueno@metempsy.com // then decrease the counter of all entries 6713553Sjavier.bueno@metempsy.com 6813553Sjavier.bueno@metempsy.com // If all counters have the max value, this will be the pick 6913553Sjavier.bueno@metempsy.com PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]); 7013553Sjavier.bueno@metempsy.com 7113553Sjavier.bueno@metempsy.com uint8_t current_counter = max_counter_value; 7213553Sjavier.bueno@metempsy.com for (auto &entry : strideEntries) { 7313553Sjavier.bueno@metempsy.com if (entry.counter < current_counter) { 7413553Sjavier.bueno@metempsy.com victim_pstride_entry = &entry; 7513553Sjavier.bueno@metempsy.com current_counter = entry.counter; 7613553Sjavier.bueno@metempsy.com } 7713553Sjavier.bueno@metempsy.com if (entry.counter > 0) { 7813553Sjavier.bueno@metempsy.com entry.counter -= 1; 7913553Sjavier.bueno@metempsy.com } 8013553Sjavier.bueno@metempsy.com } 8113553Sjavier.bueno@metempsy.com pstride_entry = victim_pstride_entry; 8213553Sjavier.bueno@metempsy.com pstride_entry->counter = 0; 8313553Sjavier.bueno@metempsy.com pstride_entry->stride = stride; 8413553Sjavier.bueno@metempsy.com } 8513553Sjavier.bueno@metempsy.com return *pstride_entry; 8613553Sjavier.bueno@metempsy.com} 8713553Sjavier.bueno@metempsy.com 8813553Sjavier.bueno@metempsy.comvoid 8913553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t block, 9013553Sjavier.bueno@metempsy.com bool is_secure, std::vector<AddrPriority> &addresses) 9113553Sjavier.bueno@metempsy.com{ 9213553Sjavier.bueno@metempsy.com /** 9313553Sjavier.bueno@metempsy.com * block is relative to the provided ppn. Assuming a page size of 4kB and 9413553Sjavier.bueno@metempsy.com * a block size of 64B, the range of the stride of this prefetcher is 9513553Sjavier.bueno@metempsy.com * -63,63 (pageBytes/blkSize) as the last accessed block also ranges from 9613553Sjavier.bueno@metempsy.com * 0,63, the block value is expected to be between -63 and 126 9713553Sjavier.bueno@metempsy.com * Negative block means that we are accessing the lower contiguous page, 9813553Sjavier.bueno@metempsy.com * 64 or greater point to the next contiguous. 9913553Sjavier.bueno@metempsy.com */ 10013553Sjavier.bueno@metempsy.com assert(block > -((stride_t)(pageBytes/blkSize))); 10113553Sjavier.bueno@metempsy.com assert(block < 2*((stride_t)(pageBytes/blkSize))); 10213553Sjavier.bueno@metempsy.com 10313553Sjavier.bueno@metempsy.com Addr pf_ppn; 10413553Sjavier.bueno@metempsy.com stride_t pf_block; 10513553Sjavier.bueno@metempsy.com if (block < 0) { 10613553Sjavier.bueno@metempsy.com pf_ppn = ppn - 1; 10713553Sjavier.bueno@metempsy.com pf_block = block + (pageBytes/blkSize); 10813553Sjavier.bueno@metempsy.com } else if (block >= (pageBytes/blkSize)) { 10913553Sjavier.bueno@metempsy.com pf_ppn = ppn + 1; 11013553Sjavier.bueno@metempsy.com pf_block = block - (pageBytes/blkSize); 11113553Sjavier.bueno@metempsy.com } else { 11213553Sjavier.bueno@metempsy.com pf_ppn = ppn; 11313553Sjavier.bueno@metempsy.com pf_block = block; 11413553Sjavier.bueno@metempsy.com } 11513553Sjavier.bueno@metempsy.com 11613553Sjavier.bueno@metempsy.com Addr new_addr = pf_ppn * pageBytes; 11713553Sjavier.bueno@metempsy.com new_addr += pf_block * (Addr)blkSize; 11813553Sjavier.bueno@metempsy.com 11913553Sjavier.bueno@metempsy.com DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 12013553Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(new_addr, 0)); 12113553Sjavier.bueno@metempsy.com} 12213553Sjavier.bueno@metempsy.com 12313553Sjavier.bueno@metempsy.comvoid 12413553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride) 12513553Sjavier.bueno@metempsy.com{ 12613553Sjavier.bueno@metempsy.com assert(stride != 0); 12713553Sjavier.bueno@metempsy.com // The pattern table is indexed by signatures 12813553Sjavier.bueno@metempsy.com PatternEntry &p_entry = getPatternEntry(signature); 12913553Sjavier.bueno@metempsy.com PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride, 13013553Sjavier.bueno@metempsy.com maxCounterValue); 13113553Sjavier.bueno@metempsy.com if (ps_entry.counter < maxCounterValue) { 13213553Sjavier.bueno@metempsy.com ps_entry.counter += 1; 13313553Sjavier.bueno@metempsy.com } 13413553Sjavier.bueno@metempsy.com} 13513553Sjavier.bueno@metempsy.com 13613553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::SignatureEntry & 13713553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure, 13813553Sjavier.bueno@metempsy.com stride_t block, bool &miss) 13913553Sjavier.bueno@metempsy.com{ 14013553Sjavier.bueno@metempsy.com SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure); 14113553Sjavier.bueno@metempsy.com if (signature_entry != nullptr) { 14213553Sjavier.bueno@metempsy.com signatureTable.accessEntry(signature_entry); 14313553Sjavier.bueno@metempsy.com miss = false; 14413553Sjavier.bueno@metempsy.com } else { 14513553Sjavier.bueno@metempsy.com signature_entry = signatureTable.findVictim(ppn); 14613553Sjavier.bueno@metempsy.com assert(signature_entry != nullptr); 14713553Sjavier.bueno@metempsy.com 14813553Sjavier.bueno@metempsy.com signatureTable.insertEntry(ppn, is_secure, signature_entry); 14913553Sjavier.bueno@metempsy.com signature_entry->signature = block; 15013553Sjavier.bueno@metempsy.com signature_entry->lastBlock = block; 15113553Sjavier.bueno@metempsy.com miss = true; 15213553Sjavier.bueno@metempsy.com } 15313553Sjavier.bueno@metempsy.com return *signature_entry; 15413553Sjavier.bueno@metempsy.com} 15513553Sjavier.bueno@metempsy.com 15613553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::PatternEntry & 15713553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::getPatternEntry(Addr signature) 15813553Sjavier.bueno@metempsy.com{ 15913553Sjavier.bueno@metempsy.com PatternEntry* pattern_entry = patternTable.findEntry(signature, false); 16013553Sjavier.bueno@metempsy.com if (pattern_entry != nullptr) { 16113553Sjavier.bueno@metempsy.com // Signature found 16213553Sjavier.bueno@metempsy.com patternTable.accessEntry(pattern_entry); 16313553Sjavier.bueno@metempsy.com } else { 16413553Sjavier.bueno@metempsy.com // Signature not found 16513553Sjavier.bueno@metempsy.com pattern_entry = patternTable.findVictim(signature); 16613553Sjavier.bueno@metempsy.com assert(pattern_entry != nullptr); 16713553Sjavier.bueno@metempsy.com 16813553Sjavier.bueno@metempsy.com patternTable.insertEntry(signature, false, pattern_entry); 16913553Sjavier.bueno@metempsy.com } 17013553Sjavier.bueno@metempsy.com return *pattern_entry; 17113553Sjavier.bueno@metempsy.com} 17213553Sjavier.bueno@metempsy.com 17313553Sjavier.bueno@metempsy.comvoid 17413553Sjavier.bueno@metempsy.comSignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 17513553Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 17613553Sjavier.bueno@metempsy.com{ 17713553Sjavier.bueno@metempsy.com Addr request_addr = pfi.getAddr(); 17813553Sjavier.bueno@metempsy.com Addr ppn = request_addr / pageBytes; 17913553Sjavier.bueno@metempsy.com stride_t current_block = (request_addr % pageBytes) / blkSize; 18013553Sjavier.bueno@metempsy.com stride_t stride; 18113553Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 18213553Sjavier.bueno@metempsy.com 18313553Sjavier.bueno@metempsy.com // Get the SignatureEntry of this page to: 18413553Sjavier.bueno@metempsy.com // - compute the current stride 18513553Sjavier.bueno@metempsy.com // - obtain the current signature of accesses 18613553Sjavier.bueno@metempsy.com bool miss; 18713553Sjavier.bueno@metempsy.com SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure, 18813553Sjavier.bueno@metempsy.com current_block, miss); 18913553Sjavier.bueno@metempsy.com if (miss) { 19013553Sjavier.bueno@metempsy.com // No history for this page, can't continue 19113553Sjavier.bueno@metempsy.com return; 19213553Sjavier.bueno@metempsy.com } 19313553Sjavier.bueno@metempsy.com 19413553Sjavier.bueno@metempsy.com stride = current_block - signature_entry.lastBlock; 19513553Sjavier.bueno@metempsy.com if (stride == 0) { 19613553Sjavier.bueno@metempsy.com // Can't continue with a stride 0 19713553Sjavier.bueno@metempsy.com return; 19813553Sjavier.bueno@metempsy.com } 19913553Sjavier.bueno@metempsy.com 20013553Sjavier.bueno@metempsy.com // Update the confidence of the current signature 20113553Sjavier.bueno@metempsy.com updatePatternTable(signature_entry.signature, stride); 20213553Sjavier.bueno@metempsy.com 20313553Sjavier.bueno@metempsy.com // Update the current SignatureEntry signature and lastBlock 20413553Sjavier.bueno@metempsy.com signature_entry.signature = 20513553Sjavier.bueno@metempsy.com updateSignature(signature_entry.signature, stride); 20613553Sjavier.bueno@metempsy.com signature_entry.lastBlock = current_block; 20713553Sjavier.bueno@metempsy.com 20813553Sjavier.bueno@metempsy.com signature_t current_signature = signature_entry.signature; 20913553Sjavier.bueno@metempsy.com double current_confidence = 1.0; 21013553Sjavier.bueno@metempsy.com stride_t current_stride = signature_entry.lastBlock; 21113553Sjavier.bueno@metempsy.com 21213553Sjavier.bueno@metempsy.com do { 21313553Sjavier.bueno@metempsy.com // With the updated signature, attempt to generate prefetches 21413553Sjavier.bueno@metempsy.com // - search the PatternTable and select all entries with enough 21513553Sjavier.bueno@metempsy.com // confidence, these are prefetch candidates 21613553Sjavier.bueno@metempsy.com // - select the entry with the highest counter as the "lookahead" 21713553Sjavier.bueno@metempsy.com PatternEntry *current_pattern_entry = 21813553Sjavier.bueno@metempsy.com patternTable.findEntry(current_signature, false); 21913553Sjavier.bueno@metempsy.com PatternStrideEntry const *lookahead = nullptr; 22013553Sjavier.bueno@metempsy.com if (current_pattern_entry != nullptr) { 22113553Sjavier.bueno@metempsy.com uint8_t max_counter = 0; 22213553Sjavier.bueno@metempsy.com for (auto const &entry : current_pattern_entry->strideEntries) { 22313553Sjavier.bueno@metempsy.com //select the entry with the maximum counter value as lookahead 22413553Sjavier.bueno@metempsy.com if (max_counter < entry.counter) { 22513553Sjavier.bueno@metempsy.com max_counter = entry.counter; 22613553Sjavier.bueno@metempsy.com lookahead = &entry; 22713553Sjavier.bueno@metempsy.com } 22813553Sjavier.bueno@metempsy.com double prefetch_confidence = 22913553Sjavier.bueno@metempsy.com (double) entry.counter / maxCounterValue; 23013553Sjavier.bueno@metempsy.com 23113553Sjavier.bueno@metempsy.com if (prefetch_confidence >= prefetchConfidenceThreshold) { 23213553Sjavier.bueno@metempsy.com assert(entry.stride != 0); 23313553Sjavier.bueno@metempsy.com //prefetch candidate 23413553Sjavier.bueno@metempsy.com addPrefetch(ppn, current_stride + entry.stride, 23513553Sjavier.bueno@metempsy.com is_secure, addresses); 23613553Sjavier.bueno@metempsy.com } 23713553Sjavier.bueno@metempsy.com } 23813553Sjavier.bueno@metempsy.com } 23913553Sjavier.bueno@metempsy.com if (lookahead != nullptr) { 24013553Sjavier.bueno@metempsy.com // If a lookahead was selected, compute its confidence using 24113553Sjavier.bueno@metempsy.com // the counter of its entry and the accumulated confidence 24213553Sjavier.bueno@metempsy.com // if the confidence is high enough, generate a new signature 24313553Sjavier.bueno@metempsy.com double lookahead_confidence; 24413553Sjavier.bueno@metempsy.com if (lookahead->counter == maxCounterValue) { 24513553Sjavier.bueno@metempsy.com // maximum confidence is 0.95, guaranteeing that 24613553Sjavier.bueno@metempsy.com // current confidence will eventually fall beyond 24713553Sjavier.bueno@metempsy.com // the threshold 24813553Sjavier.bueno@metempsy.com lookahead_confidence = 0.95; 24913553Sjavier.bueno@metempsy.com } else { 25013553Sjavier.bueno@metempsy.com lookahead_confidence = 25113553Sjavier.bueno@metempsy.com ((double) lookahead->counter / maxCounterValue); 25213553Sjavier.bueno@metempsy.com } 25313553Sjavier.bueno@metempsy.com current_confidence *= lookahead_confidence; 25413553Sjavier.bueno@metempsy.com current_signature = 25513553Sjavier.bueno@metempsy.com updateSignature(current_signature, lookahead->stride); 25613553Sjavier.bueno@metempsy.com current_stride += lookahead->stride; 25713553Sjavier.bueno@metempsy.com } else { 25813553Sjavier.bueno@metempsy.com current_confidence = 0.0; 25913553Sjavier.bueno@metempsy.com } 26013553Sjavier.bueno@metempsy.com // If the accumulated confidence is high enough, keep repeating 26113553Sjavier.bueno@metempsy.com // this process with the updated signature 26213553Sjavier.bueno@metempsy.com } 26313553Sjavier.bueno@metempsy.com while (current_confidence > lookaheadConfidenceThreshold); 26413553Sjavier.bueno@metempsy.com 26513553Sjavier.bueno@metempsy.com if (addresses.empty()) { 26613553Sjavier.bueno@metempsy.com // Enable the next line prefetcher if no prefetch candidates are found 26713553Sjavier.bueno@metempsy.com addPrefetch(ppn, current_block + 1, is_secure, addresses); 26813553Sjavier.bueno@metempsy.com } 26913553Sjavier.bueno@metempsy.com} 27013553Sjavier.bueno@metempsy.com 27113553Sjavier.bueno@metempsy.comSignaturePathPrefetcher* 27213553Sjavier.bueno@metempsy.comSignaturePathPrefetcherParams::create() 27313553Sjavier.bueno@metempsy.com{ 27413553Sjavier.bueno@metempsy.com return new SignaturePathPrefetcher(this); 27513553Sjavier.bueno@metempsy.com} 276