tree_plru_rp.cc

Go to the documentation of this file.

#include "mem/cache/replacement_policies/tree_plru_rp.hh"

#include <cmath>

#include "base/intmath.hh"
#include "base/logging.hh"
#include "params/TreePLRURP.hh"

static uint64_t
parentIndex(const uint64_t index)
{
    return std::floor((index-1)/2);
}

static uint64_t
leftSubtreeIndex(const uint64_t index)
{
    return 2*index + 1;
}

static uint64_t
rightSubtreeIndex(const uint64_t index)
{
    return 2*index + 2;
}

static bool
isRightSubtree(const uint64_t index)
{
    return index%2 == 0;
}

TreePLRURP::TreePLRUReplData::TreePLRUReplData(
    const uint64_t index, std::shared_ptr<PLRUTree> tree)
    : index(index), tree(tree)
{
}

TreePLRURP::TreePLRURP(const Params *p)
    : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0),
      treeInstance(nullptr)
{
    fatal_if(!isPowerOf2(numLeaves),
             "Number of leaves must be non-zero and a power of 2");
}

void
TreePLRURP::invalidate(
    const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Cast replacement data
    std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
        std::static_pointer_cast<TreePLRUReplData>(replacement_data);
    PLRUTree* tree = treePLRU_replacement_data->tree.get();

    // Index of the tree entry we are currently checking
    // Make this entry the new LRU entry
    uint64_t tree_index = treePLRU_replacement_data->index;

    // Parse and update tree to make it point to the new LRU
    do {
        // Store whether we are coming from a left or right node
        const bool right = isRightSubtree(tree_index);

        // Go to the parent tree node
        tree_index = parentIndex(tree_index);

        // Update parent node to make it point to the node we just came from
        tree->at(tree_index) = right;
    } while (tree_index != 0);
}

void
TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Cast replacement data
    std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
        std::static_pointer_cast<TreePLRUReplData>(replacement_data);
    PLRUTree* tree = treePLRU_replacement_data->tree.get();

    // Index of the tree entry we are currently checking
    // Make this entry the MRU entry
    uint64_t tree_index = treePLRU_replacement_data->index;

    // Parse and update tree to make every bit point away from the new MRU
    do {
        // Store whether we are coming from a left or right node
        const bool right = isRightSubtree(tree_index);

        // Go to the parent tree node
        tree_index = parentIndex(tree_index);

        // Update node to not point to the touched leaf
        tree->at(tree_index) = !right;
    } while (tree_index != 0);
}

void
TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // A reset has the same functionality of a touch
    touch(replacement_data);
}

ReplaceableEntry*
TreePLRURP::getVictim(const ReplacementCandidates& candidates) const
{
    // There must be at least one replacement candidate
    assert(candidates.size() > 0);

    // Get tree
    const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
            candidates[0]->replacementData)->tree.get();

    // Index of the tree entry we are currently checking. Start with root.
    uint64_t tree_index = 0;

    // Parse tree
    while (tree_index < tree->size()) {
        // Go to the next tree entry
        if (tree->at(tree_index)) {
            tree_index = rightSubtreeIndex(tree_index);
        } else {
            tree_index = leftSubtreeIndex(tree_index);
        }
    }

    // The tree index is currently at the leaf of the victim displaced by the
    // number of non-leaf nodes
    return candidates[tree_index - (numLeaves - 1)];
}

std::shared_ptr<ReplacementData>
TreePLRURP::instantiateEntry()
{
    // Generate a tree instance every numLeaves created
    if (count % numLeaves == 0) {
        treeInstance = new PLRUTree(numLeaves - 1, false);
    }

    // Create replacement data using current tree instance
    TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
        (count % numLeaves) + numLeaves - 1,
        std::shared_ptr<PLRUTree>(treeInstance));

    // Update instance counter
    count++;

    return std::shared_ptr<ReplacementData>(treePLRUReplData);
}

TreePLRURP*
TreePLRURPParams::create()
{
    return new TreePLRURP(this);
}