Cache替换策略

2023-11-16 15:48:16

LRU, Least Recently Used, LRU算法根据各block(cache line)使用的情况，总是选择那个最长时间未被使用的block进行替换。这种策略比较好的反映了程序局部性规律。

gem5中该替换策略的代码：

void
LRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Reset last touch timestamp
    std::static_pointer_cast<LRUReplData>(
        replacement_data)->lastTouchTick = Tick(0);
}

void
LRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Update last touch timestamp
    std::static_pointer_cast<LRUReplData>(
        replacement_data)->lastTouchTick = curTick();
}

void
LRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Set last touch timestamp
    std::static_pointer_cast<LRUReplData>(
        replacement_data)->lastTouchTick = curTick();
}

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

    // Visit all candidates to find victim
    ReplaceableEntry* victim = candidates[0];
    for (const auto& candidate : candidates) {
        // Update victim entry if necessary
        if (std::static_pointer_cast<LRUReplData>(
                    candidate->replacementData)->lastTouchTick <
                std::static_pointer_cast<LRUReplData>(
                    victim->replacementData)->lastTouchTick) {
            victim = candidate;
        }
    }

    return victim;
}

View Code

MRU（Most Recently Used）和LRU类似，差别在于选择最近被使用的block进行替换。

gem5中该替换策略的代码：

void
MRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Reset last touch timestamp
    std::static_pointer_cast<MRUReplData>(
        replacement_data)->lastTouchTick = Tick(0);
}

void
MRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Update last touch timestamp
    std::static_pointer_cast<MRUReplData>(
        replacement_data)->lastTouchTick = curTick();
}

void
MRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Set last touch timestamp
    std::static_pointer_cast<MRUReplData>(
        replacement_data)->lastTouchTick = curTick();
}

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

    // Visit all candidates to find victim
    ReplaceableEntry* victim = candidates[0];
    for (const auto& candidate : candidates) {
        std::shared_ptr<MRUReplData> candidate_replacement_data =
            std::static_pointer_cast<MRUReplData>(candidate->replacementData);

        // Stop searching entry if a cache line that doesn‘t warm up is found.
        if (candidate_replacement_data->lastTouchTick == 0) {
            victim = candidate;
            break;
        } else if (candidate_replacement_data->lastTouchTick >
                std::static_pointer_cast<MRUReplData>(
                    victim->replacementData)->lastTouchTick) {
            victim = candidate;
        }
    }

    return victim;
}

View Code

Random，随机选择一个block进行替换。

gem5中该替换策略的代码：

void
RandomRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Unprioritize replacement data victimization
    std::static_pointer_cast<RandomReplData>(
        replacement_data)->valid = false;
}

void
RandomRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
{
}

void
RandomRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Unprioritize replacement data victimization
    std::static_pointer_cast<RandomReplData>(
        replacement_data)->valid = true;
}

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

    // Choose one candidate at random
    ReplaceableEntry* victim = candidates[random_mt.random<unsigned>(0,
                                    candidates.size() - 1)];

    // Visit all candidates to search for an invalid entry. If one is found,
    // its eviction is prioritized
    for (const auto& candidate : candidates) {
        if (!std::static_pointer_cast<RandomReplData>(
                    candidate->replacementData)->valid) {
            victim = candidate;
            break;
        }
    }

View Code

LFU（Least Frequently Used），最近最少被使用次数的block被替换，每个block都有一个引用计数，每次替换该block，都会对该计数加1。

gem5中该替换策略的代码：

void
LFURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Reset reference count
    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 0;
}

void
LFURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Update reference count
    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount++;
}

void
LFURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Reset reference count
    std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 1;
}

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

    // Visit all candidates to find victim
    ReplaceableEntry* victim = candidates[0];
    for (const auto& candidate : candidates) {
        // Update victim entry if necessary
        if (std::static_pointer_cast<LFUReplData>(
                    candidate->replacementData)->refCount <
                std::static_pointer_cast<LFUReplData>(
                    victim->replacementData)->refCount) {
            victim = candidate;
        }
    }

    return victim;
}

View Code

FIFO(First in First out), 最先使用过的block，最先被替换。

gem5中该替换策略的代码：

void
FIFORP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const
{
    // Reset insertion tick
    std::static_pointer_cast<FIFOReplData>(
        replacement_data)->tickInserted = Tick(0);
}

void
FIFORP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // A touch does not modify the insertion tick
}

void
FIFORP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    // Set insertion tick
    std::static_pointer_cast<FIFOReplData>(
        replacement_data)->tickInserted = curTick();
}

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

    // Visit all candidates to find victim
    ReplaceableEntry* victim = candidates[0];
    for (const auto& candidate : candidates) {
        // Update victim entry if necessary
        if (std::static_pointer_cast<FIFOReplData>(
                    candidate->replacementData)->tickInserted <
                std::static_pointer_cast<FIFOReplData>(
                    victim->replacementData)->tickInserted) {
            victim = candidate;
        }
    }

    return victim;
}

View Code

BIP，(Bimodal Insertion Policy）替换策略，是LRU和MRU的结合体，大概率采用MRU替换，小概率采用LRU策略。

gem5中该替换策略的代码

struct BIPRPParams;

class BIPRP : public LRURP
{
  protected:
    /**
     * Bimodal throtle parameter. Value in the range [0,100] used to decide
     * if a new entry is inserted at the MRU or LRU position.
     */
    const unsigned btp;

  public:
    /** Convenience typedef. */
    typedef BIPRPParams Params;

    /**
     * Construct and initiliaze this replacement policy.
     */
    BIPRP(const Params *p);

    /**
     * Destructor.
     */
    ~BIPRP() {}

    /**
     * Reset replacement data for an entry. Used when an entry is inserted.
     * Uses the bimodal throtle parameter to decide whether the new entry
     * should be inserted as MRU, or LRU.
     *
     * @param replacement_data Replacement data to be reset.
     */
    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
                                                                     override;
};
void
BIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
{
    std::shared_ptr<LRUReplData> casted_replacement_data =
        std::static_pointer_cast<LRUReplData>(replacement_data);

    // Entries are inserted as MRU if lower than btp, LRU otherwise
    if (random_mt.random<unsigned>(1, 100) <= btp) {
        casted_replacement_data->lastTouchTick = curTick();
    } else {
        // Make their timestamps as old as possible, so that they become LRU
        casted_replacement_data->lastTouchTick = 1;
    }
}

View Code

Cache替换策略

码农公寓

相关文章