blob: d73f464074fc79aeeb14b0d537f9d7bc73df382f [file] [log] [blame]
/**
* Copyright (c) 2018 Metempsy Technology Consulting
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "mem/cache/prefetch/irregular_stream_buffer.hh"
#include "debug/HWPrefetch.hh"
#include "mem/cache/prefetch/associative_set_impl.hh"
#include "params/IrregularStreamBufferPrefetcher.hh"
namespace Prefetcher {
IrregularStreamBuffer::IrregularStreamBuffer(
const IrregularStreamBufferPrefetcherParams &p)
: Queued(p),
chunkSize(p.chunk_size),
prefetchCandidatesPerEntry(p.prefetch_candidates_per_entry),
degree(p.degree),
trainingUnit(p.training_unit_assoc, p.training_unit_entries,
p.training_unit_indexing_policy,
p.training_unit_replacement_policy),
psAddressMappingCache(p.address_map_cache_assoc,
p.address_map_cache_entries,
p.ps_address_map_cache_indexing_policy,
p.ps_address_map_cache_replacement_policy,
AddressMappingEntry(prefetchCandidatesPerEntry,
p.num_counter_bits)),
spAddressMappingCache(p.address_map_cache_assoc,
p.address_map_cache_entries,
p.sp_address_map_cache_indexing_policy,
p.sp_address_map_cache_replacement_policy,
AddressMappingEntry(prefetchCandidatesPerEntry,
p.num_counter_bits)),
structuralAddressCounter(0)
{
assert(isPowerOf2(prefetchCandidatesPerEntry));
}
void
IrregularStreamBuffer::calculatePrefetch(const PrefetchInfo &pfi,
std::vector<AddrPriority> &addresses)
{
// This prefetcher requires a PC
if (!pfi.hasPC()) {
return;
}
bool is_secure = pfi.isSecure();
Addr pc = pfi.getPC();
Addr addr = blockIndex(pfi.getAddr());
// Training, if the entry exists, then we found a correlation between
// the entry lastAddress (named as correlated_addr_A) and the address of
// the current access (named as correlated_addr_B)
TrainingUnitEntry *entry = trainingUnit.findEntry(pc, is_secure);
bool correlated_addr_found = false;
Addr correlated_addr_A = 0;
Addr correlated_addr_B = 0;
if (entry != nullptr && entry->lastAddressSecure == is_secure) {
trainingUnit.accessEntry(entry);
correlated_addr_found = true;
correlated_addr_A = entry->lastAddress;
correlated_addr_B = addr;
} else {
entry = trainingUnit.findVictim(pc);
assert(entry != nullptr);
trainingUnit.insertEntry(pc, is_secure, entry);
}
// Update the entry
entry->lastAddress = addr;
entry->lastAddressSecure = is_secure;
if (correlated_addr_found) {
// If a correlation was found, update the Physical-to-Structural
// table accordingly
AddressMapping &mapping_A = getPSMapping(correlated_addr_A, is_secure);
AddressMapping &mapping_B = getPSMapping(correlated_addr_B, is_secure);
if (mapping_A.counter > 0 && mapping_B.counter > 0) {
// Entry for A and B
if (mapping_B.address == (mapping_A.address + 1)) {
mapping_B.counter++;
} else {
if (mapping_B.counter == 1) {
// Counter would hit 0, reassign address while keeping
// counter at 1
mapping_B.address = mapping_A.address + 1;
addStructuralToPhysicalEntry(mapping_B.address, is_secure,
correlated_addr_B);
} else {
mapping_B.counter--;
}
}
} else {
if (mapping_A.counter == 0) {
// if A is not valid, generate a new structural address
mapping_A.counter++;
mapping_A.address = structuralAddressCounter;
structuralAddressCounter += chunkSize;
addStructuralToPhysicalEntry(mapping_A.address,
is_secure, correlated_addr_A);
}
mapping_B.counter.reset();
mapping_B.counter++;
mapping_B.address = mapping_A.address + 1;
// update SP-AMC
addStructuralToPhysicalEntry(mapping_B.address, is_secure,
correlated_addr_B);
}
}
// Use the PS mapping to predict future accesses using the current address
// - Look for the structured address
// - if it exists, use it to generate prefetches for the subsequent
// addresses in ascending order, as many as indicated by the degree
// (given the structured address S, prefetch S+1, S+2, .. up to S+degree)
Addr amc_address = addr / prefetchCandidatesPerEntry;
Addr map_index = addr % prefetchCandidatesPerEntry;
AddressMappingEntry *ps_am = psAddressMappingCache.findEntry(amc_address,
is_secure);
if (ps_am != nullptr) {
AddressMapping &mapping = ps_am->mappings[map_index];
if (mapping.counter > 0) {
Addr sp_address = mapping.address / prefetchCandidatesPerEntry;
Addr sp_index = mapping.address % prefetchCandidatesPerEntry;
AddressMappingEntry *sp_am =
spAddressMappingCache.findEntry(sp_address, is_secure);
if (sp_am == nullptr) {
// The entry has been evicted, can not generate prefetches
return;
}
for (unsigned d = 1;
d <= degree && (sp_index + d) < prefetchCandidatesPerEntry;
d += 1)
{
AddressMapping &spm = sp_am->mappings[sp_index + d];
//generate prefetch
if (spm.counter > 0) {
Addr pf_addr = spm.address << lBlkSize;
addresses.push_back(AddrPriority(pf_addr, 0));
}
}
}
}
}
IrregularStreamBuffer::AddressMapping&
IrregularStreamBuffer::getPSMapping(Addr paddr, bool is_secure)
{
Addr amc_address = paddr / prefetchCandidatesPerEntry;
Addr map_index = paddr % prefetchCandidatesPerEntry;
AddressMappingEntry *ps_entry =
psAddressMappingCache.findEntry(amc_address, is_secure);
if (ps_entry != nullptr) {
// A PS-AMC line already exists
psAddressMappingCache.accessEntry(ps_entry);
} else {
ps_entry = psAddressMappingCache.findVictim(amc_address);
assert(ps_entry != nullptr);
psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry);
}
return ps_entry->mappings[map_index];
}
void
IrregularStreamBuffer::addStructuralToPhysicalEntry(
Addr structural_address, bool is_secure, Addr physical_address)
{
Addr amc_address = structural_address / prefetchCandidatesPerEntry;
Addr map_index = structural_address % prefetchCandidatesPerEntry;
AddressMappingEntry *sp_entry =
spAddressMappingCache.findEntry(amc_address, is_secure);
if (sp_entry != nullptr) {
spAddressMappingCache.accessEntry(sp_entry);
} else {
sp_entry = spAddressMappingCache.findVictim(amc_address);
assert(sp_entry != nullptr);
spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry);
}
AddressMapping &mapping = sp_entry->mappings[map_index];
mapping.address = physical_address;
mapping.counter.reset();
mapping.counter++;
}
} // namespace Prefetcher