irregular_stream_buffer.cc revision 13828:73addeac3dd3
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/irregular_stream_buffer.hh" 32 33#include "debug/HWPrefetch.hh" 34#include "mem/cache/prefetch/associative_set_impl.hh" 35#include "params/IrregularStreamBufferPrefetcher.hh" 36 37IrregularStreamBufferPrefetcher::IrregularStreamBufferPrefetcher( 38 const IrregularStreamBufferPrefetcherParams *p) 39 : QueuedPrefetcher(p), maxCounterValue(p->max_counter_value), 40 chunkSize(p->chunk_size), 41 prefetchCandidatesPerEntry(p->prefetch_candidates_per_entry), 42 degree(p->degree), 43 trainingUnit(p->training_unit_assoc, p->training_unit_entries, 44 p->training_unit_indexing_policy, 45 p->training_unit_replacement_policy), 46 psAddressMappingCache(p->address_map_cache_assoc, 47 p->address_map_cache_entries, 48 p->ps_address_map_cache_indexing_policy, 49 p->ps_address_map_cache_replacement_policy, 50 AddressMappingEntry(prefetchCandidatesPerEntry)), 51 spAddressMappingCache(p->address_map_cache_assoc, 52 p->address_map_cache_entries, 53 p->sp_address_map_cache_indexing_policy, 54 p->sp_address_map_cache_replacement_policy, 55 AddressMappingEntry(prefetchCandidatesPerEntry)), 56 structuralAddressCounter(0) 57{ 58 assert(isPowerOf2(prefetchCandidatesPerEntry)); 59} 60 61void 62IrregularStreamBufferPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 63 std::vector<AddrPriority> &addresses) 64{ 65 // This prefetcher requires a PC 66 if (!pfi.hasPC()) { 67 return; 68 } 69 bool is_secure = pfi.isSecure(); 70 Addr pc = pfi.getPC(); 71 Addr addr = blockIndex(pfi.getAddr()); 72 73 // Training, if the entry exists, then we found a correlation between 74 // the entry lastAddress (named as correlated_addr_A) and the address of 75 // the current access (named as correlated_addr_B) 76 TrainingUnitEntry *entry = trainingUnit.findEntry(pc, is_secure); 77 bool correlated_addr_found = false; 78 Addr correlated_addr_A = 0; 79 Addr correlated_addr_B = 0; 80 if (entry != nullptr && entry->lastAddressSecure == is_secure) { 81 trainingUnit.accessEntry(entry); 82 correlated_addr_found = true; 83 correlated_addr_A = entry->lastAddress; 84 correlated_addr_B = addr; 85 } else { 86 entry = trainingUnit.findVictim(pc); 87 assert(entry != nullptr); 88 89 trainingUnit.insertEntry(pc, is_secure, entry); 90 } 91 // Update the entry 92 entry->lastAddress = addr; 93 entry->lastAddressSecure = is_secure; 94 95 if (correlated_addr_found) { 96 // If a correlation was found, update the Physical-to-Structural 97 // table accordingly 98 AddressMapping &mapping_A = getPSMapping(correlated_addr_A, is_secure); 99 AddressMapping &mapping_B = getPSMapping(correlated_addr_B, is_secure); 100 if (mapping_A.counter > 0 && mapping_B.counter > 0) { 101 // Entry for A and B 102 if (mapping_B.address == (mapping_A.address + 1)) { 103 if (mapping_B.counter < maxCounterValue) { 104 mapping_B.counter += 1; 105 } 106 } else { 107 if (mapping_B.counter == 1) { 108 // counter would hit 0, reassign address 109 mapping_B.counter = 1; 110 mapping_B.address = mapping_A.address + 1; 111 addStructuralToPhysicalEntry(mapping_B.address, is_secure, 112 correlated_addr_B); 113 } else { 114 mapping_B.counter -= 1; 115 } 116 } 117 } else { 118 if (mapping_A.counter == 0) { 119 // if A is not valid, generate a new structural address 120 mapping_A.counter = 1; 121 mapping_A.address = structuralAddressCounter; 122 structuralAddressCounter += chunkSize; 123 addStructuralToPhysicalEntry(mapping_A.address, 124 is_secure, correlated_addr_A); 125 } 126 mapping_B.counter = 1; 127 mapping_B.address = mapping_A.address + 1; 128 // update SP-AMC 129 addStructuralToPhysicalEntry(mapping_B.address, is_secure, 130 correlated_addr_B); 131 } 132 } 133 134 // Use the PS mapping to predict future accesses using the current address 135 // - Look for the structured address 136 // - if it exists, use it to generate prefetches for the subsequent 137 // addresses in ascending order, as many as indicated by the degree 138 // (given the structured address S, prefetch S+1, S+2, .. up to S+degree) 139 Addr amc_address = addr / prefetchCandidatesPerEntry; 140 Addr map_index = addr % prefetchCandidatesPerEntry; 141 AddressMappingEntry *ps_am = psAddressMappingCache.findEntry(amc_address, 142 is_secure); 143 if (ps_am != nullptr) { 144 AddressMapping &mapping = ps_am->mappings[map_index]; 145 if (mapping.counter > 0) { 146 Addr sp_address = mapping.address / prefetchCandidatesPerEntry; 147 Addr sp_index = mapping.address % prefetchCandidatesPerEntry; 148 AddressMappingEntry *sp_am = 149 spAddressMappingCache.findEntry(sp_address, is_secure); 150 if (sp_am == nullptr) { 151 // The entry has been evicted, can not generate prefetches 152 return; 153 } 154 for (unsigned d = 1; 155 d <= degree && (sp_index + d) < prefetchCandidatesPerEntry; 156 d += 1) 157 { 158 AddressMapping &spm = sp_am->mappings[sp_index + d]; 159 //generate prefetch 160 if (spm.counter > 0) { 161 Addr pf_addr = spm.address << lBlkSize; 162 addresses.push_back(AddrPriority(pf_addr, 0)); 163 } 164 } 165 } 166 } 167} 168 169IrregularStreamBufferPrefetcher::AddressMapping& 170IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr, bool is_secure) 171{ 172 Addr amc_address = paddr / prefetchCandidatesPerEntry; 173 Addr map_index = paddr % prefetchCandidatesPerEntry; 174 AddressMappingEntry *ps_entry = 175 psAddressMappingCache.findEntry(amc_address, is_secure); 176 if (ps_entry != nullptr) { 177 // A PS-AMC line already exists 178 psAddressMappingCache.accessEntry(ps_entry); 179 } else { 180 ps_entry = psAddressMappingCache.findVictim(amc_address); 181 assert(ps_entry != nullptr); 182 183 psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry); 184 } 185 return ps_entry->mappings[map_index]; 186} 187 188void 189IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry( 190 Addr structural_address, bool is_secure, Addr physical_address) 191{ 192 Addr amc_address = structural_address / prefetchCandidatesPerEntry; 193 Addr map_index = structural_address % prefetchCandidatesPerEntry; 194 AddressMappingEntry *sp_entry = 195 spAddressMappingCache.findEntry(amc_address, is_secure); 196 if (sp_entry != nullptr) { 197 spAddressMappingCache.accessEntry(sp_entry); 198 } else { 199 sp_entry = spAddressMappingCache.findVictim(amc_address); 200 assert(sp_entry != nullptr); 201 202 spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry); 203 } 204 AddressMapping &mapping = sp_entry->mappings[map_index]; 205 mapping.address = physical_address; 206 mapping.counter = 1; 207} 208 209IrregularStreamBufferPrefetcher* 210IrregularStreamBufferPrefetcherParams::create() 211{ 212 return new IrregularStreamBufferPrefetcher(this); 213} 214