path: root/src/mem/cache/prefetch/access_map_pattern_matching.cc

/**
 * 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.
 *
 * Authors: Javier Bueno
 */

#include "mem/cache/prefetch/access_map_pattern_matching.hh"

#include "debug/HWPrefetch.hh"
#include "mem/cache/prefetch/associative_set_impl.hh"
#include "params/AMPMPrefetcher.hh"
#include "params/AccessMapPatternMatching.hh"

AccessMapPatternMatching::AccessMapPatternMatching(
    const AccessMapPatternMatchingParams *p)
    : ClockedObject(p), blkSize(p->block_size), limitStride(p->limit_stride),
      startDegree(p->start_degree), hotZoneSize(p->hot_zone_size),
      highCoverageThreshold(p->high_coverage_threshold),
      lowCoverageThreshold(p->low_coverage_threshold),
      highAccuracyThreshold(p->high_accuracy_threshold),
      lowAccuracyThreshold(p->low_accuracy_threshold),
      highCacheHitThreshold(p->high_cache_hit_threshold),
      lowCacheHitThreshold(p->low_cache_hit_threshold),
      epochCycles(p->epoch_cycles),
      offChipMemoryLatency(p->offchip_memory_latency),
      accessMapTable(p->access_map_table_assoc, p->access_map_table_entries,
                     p->access_map_table_indexing_policy,
                     p->access_map_table_replacement_policy,
                     AccessMapEntry(hotZoneSize / blkSize)),
      numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0),
      numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree),
      epochEvent([this]{ processEpochEvent(); }, name())
{
    fatal_if(!isPowerOf2(hotZoneSize),
        "the hot zone size must be a power of 2");
}

void
AccessMapPatternMatching::startup()
{
    schedule(epochEvent, clockEdge(epochCycles));
}

void
AccessMapPatternMatching::processEpochEvent()
{
    schedule(epochEvent, clockEdge(epochCycles));
    double prefetch_accuracy =
        ((double) numGoodPrefetches) / ((double) numTotalPrefetches);
    double prefetch_coverage =
        ((double) numGoodPrefetches) / ((double) numRawCacheMisses);
    double cache_hit_ratio = ((double) numRawCacheHits) /
        ((double) (numRawCacheHits + numRawCacheMisses));
    double num_requests = (double) (numRawCacheMisses - numGoodPrefetches +
        numTotalPrefetches);
    double memory_bandwidth = num_requests * offChipMemoryLatency /
        clockEdge(epochCycles);

    if (prefetch_coverage > highCoverageThreshold &&
        (prefetch_accuracy > highAccuracyThreshold ||
        cache_hit_ratio < lowCacheHitThreshold)) {
        usefulDegree += 1;
    } else if ((prefetch_coverage < lowCoverageThreshold &&
               (prefetch_accuracy < lowAccuracyThreshold ||
                cache_hit_ratio > highCacheHitThreshold)) ||
               (prefetch_accuracy < lowAccuracyThreshold &&
                cache_hit_ratio > highCacheHitThreshold)) {
        usefulDegree -= 1;
    }
    degree = std::min((unsigned) memory_bandwidth, usefulDegree);
    // reset epoch stats
    numGoodPrefetches = 0.0;
    numTotalPrefetches = 0.0;
    numRawCacheMisses = 0.0;
    numRawCacheHits = 0.0;
}

AccessMapPatternMatching::AccessMapEntry *
AccessMapPatternMatching::getAccessMapEntry(Addr am_addr,
                bool is_secure)
{
    AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure);
    if (am_entry != nullptr) {
        accessMapTable.accessEntry(am_entry);
    } else {
        am_entry = accessMapTable.findVictim(am_addr);
        assert(am_entry != nullptr);

        accessMapTable.insertEntry(am_addr, is_secure, am_entry);
    }
    return am_entry;
}

void
AccessMapPatternMatching::setEntryState(AccessMapEntry &entry,
    Addr block, enum AccessMapState state)
{
    enum AccessMapState old = entry.states[block];
    entry.states[block] = state;

    //do not update stats when initializing
    if (state == AM_INIT) return;

    switch (old) {
        case AM_INIT:
            if (state == AM_PREFETCH) {
                numTotalPrefetches += 1;
            } else if (state == AM_ACCESS) {
                numRawCacheMisses += 1;
            }
            break;
        case AM_PREFETCH:
            if (state == AM_ACCESS) {
                numGoodPrefetches += 1;
                numRawCacheMisses += 1;
            }
            break;
        case AM_ACCESS:
            if (state == AM_ACCESS) {
                numRawCacheHits += 1;
            }
            break;
        default:
            panic("Impossible path\n");
            break;
    }
}

void
AccessMapPatternMatching::calculatePrefetch(
    const BasePrefetcher::PrefetchInfo &pfi,
    std::vector<QueuedPrefetcher::AddrPriority> &addresses)
{
    assert(addresses.empty());

    bool is_secure = pfi.isSecure();
    Addr am_addr = pfi.getAddr() / hotZoneSize;
    Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize;
    uint64_t lines_per_zone = hotZoneSize / blkSize;

    // Get the entries of the curent block (am_addr), the previous, and the
    // following ones
    AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure);
    AccessMapEntry *am_entry_prev = (am_addr > 0) ?
        getAccessMapEntry(am_addr-1, is_secure) : nullptr;
    AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ?
        getAccessMapEntry(am_addr+1, is_secure) : nullptr;
    assert(am_entry_curr != am_entry_prev);
    assert(am_entry_curr != am_entry_next);
    assert(am_entry_prev != am_entry_next);
    assert(am_entry_curr != nullptr);

    //Mark the current access as Accessed
    setEntryState(*am_entry_curr, current_block, AM_ACCESS);

    /**
     * Create a contiguous copy of the 3 entries states.
     * With this, we avoid doing boundaries checking in the loop that looks
     * for prefetch candidates, mark out of range positions with AM_INVALID
     */
    std::vector<AccessMapState> states(3 * lines_per_zone);
    for (unsigned idx = 0; idx < lines_per_zone; idx += 1) {
        states[idx] =
            am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID;
        states[idx + lines_per_zone] = am_entry_curr->states[idx];
        states[idx + 2 * lines_per_zone] =
            am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID;
    }

    /**
     * am_entry_prev->states => states[               0 ..   lines_per_zone-1]
     * am_entry_curr->states => states[  lines_per_zone .. 2*lines_per_zone-1]
     * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1]
     */

    // index of the current_block in the new vector
    Addr states_current_block = current_block + lines_per_zone;
    // consider strides 1..lines_per_zone/2
    int max_stride = limitStride == 0 ? lines_per_zone / 2 : limitStride + 1;
    for (int stride = 1; stride < max_stride; stride += 1) {
        // Test accessed positive strides
        if (checkCandidate(states, states_current_block, stride)) {
            // candidate found, current_block - stride
            Addr pf_addr;
            if (stride > current_block) {
                // The index (current_block - stride) falls in the range of
                // the previous zone (am_entry_prev), adjust the address
                // accordingly
                Addr blk = states_current_block - stride;
                pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize;
                setEntryState(*am_entry_prev, blk, AM_PREFETCH);
            } else {
                // The index (current_block - stride) falls within
                // am_entry_curr
                Addr blk = current_block - stride;
                pf_addr = am_addr * hotZoneSize + blk * blkSize;
                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
            }
            addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0));
            if (addresses.size() == degree) {
                break;
            }
        }

        // Test accessed negative strides
        if (checkCandidate(states, states_current_block, -stride)) {
            // candidate found, current_block + stride
            Addr pf_addr;
            if (current_block + stride >= lines_per_zone) {
                // The index (current_block + stride) falls in the range of
                // the next zone (am_entry_next), adjust the address
                // accordingly
                Addr blk = (states_current_block + stride) % lines_per_zone;
                pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize;
                setEntryState(*am_entry_next, blk, AM_PREFETCH);
            } else {
                // The index (current_block + stride) falls within
                // am_entry_curr
                Addr blk = current_block + stride;
                pf_addr = am_addr * hotZoneSize + blk * blkSize;
                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
            }
            addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0));
            if (addresses.size() == degree) {
                break;
            }
        }
    }
}

AccessMapPatternMatching*
AccessMapPatternMatchingParams::create()
{
    return new AccessMapPatternMatching(this);
}

AMPMPrefetcher::AMPMPrefetcher(const AMPMPrefetcherParams *p)
  : QueuedPrefetcher(p), ampm(*p->ampm)
{
}

void
AMPMPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
    std::vector<AddrPriority> &addresses)
{
    ampm.calculatePrefetch(pfi, addresses);
}

AMPMPrefetcher*
AMPMPrefetcherParams::create()
{
    return new AMPMPrefetcher(this);
}