brrip_rp.hh revision 12684
12SN/A/**
21762SN/A * Copyright (c) 2018 Inria
32SN/A * All rights reserved.
42SN/A *
52SN/A * Redistribution and use in source and binary forms, with or without
62SN/A * modification, are permitted provided that the following conditions are
72SN/A * met: redistributions of source code must retain the above copyright
82SN/A * notice, this list of conditions and the following disclaimer;
92SN/A * redistributions in binary form must reproduce the above copyright
102SN/A * notice, this list of conditions and the following disclaimer in the
112SN/A * documentation and/or other materials provided with the distribution;
122SN/A * neither the name of the copyright holders nor the names of its
132SN/A * contributors may be used to endorse or promote products derived from
142SN/A * this software without specific prior written permission.
152SN/A *
162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
272665SN/A *
282665SN/A * Authors: Daniel Carvalho
292665SN/A */
302665SN/A
312665SN/A/**
322SN/A * @file
332SN/A * Declaration of a Re-Reference Interval Prediction replacement policy.
341722SN/A *
355480Snate@binkert.org * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit
362SN/A * to determine if an entry is going to be re-referenced in the near or distant
372SN/A * future.
38146SN/A *
392SN/A * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a
402SN/A * re-reference prediction value to determine if entries are going to be re-
412158SN/A * used in the near future or not.
42146SN/A *
431805SN/A * The higher the value of the RRPV, the more distant the entry is from its
44146SN/A * next access.
451717SN/A *
462680SN/A * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP
475480Snate@binkert.org * that has a probability of not inserting entries as the LRU. This probability
482521SN/A * is controlled by the bimodal throtle parameter (btp).
4956SN/A *
505478SN/A * From the original paper, this implementation of RRIP is also called
513348SN/A * Static RRIP (SRRIP), as it always inserts entries with the same RRPV.
523348SN/A */
532521SN/A
545480Snate@binkert.org#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
551805SN/A#define __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
562SN/A
572SN/A#include "mem/cache/replacement_policies/base.hh"
582107SN/A#include "params/BRRIPRP.hh"
592SN/A
605480Snate@binkert.orgclass BRRIPRP : public BaseReplacementPolicy
615478SN/A{
624762SN/A  protected:
632SN/A    /** BRRIP-specific implementation of replacement data. */
64545SN/A    struct BRRIPReplData : ReplacementData
652521SN/A    {
662521SN/A        /**
672521SN/A         * Re-Reference Interval Prediction Value.
682521SN/A         * A value equal to max_RRPV + 1 indicates an invalid entry.
692SN/A         */
702SN/A        int rrpv;
712SN/A
72926SN/A        /**
73926SN/A         * Default constructor. Invalidate data.
74926SN/A         */
75926SN/A        BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {}
76926SN/A    };
77926SN/A
78926SN/A    /**
794395SN/A     * Maximum Re-Reference Prediction Value possible. An entry with this
801805SN/A     * value as the rrpv has the longest possible re-reference interval,
812SN/A     * that is, it is likely not to be used in the near future, and is
822SN/A     * among the best eviction candidates.
831634SN/A     * A maxRRPV of 1 implies in a NRU.
845480Snate@binkert.org     */
851634SN/A    const int maxRRPV;
862549SN/A
871806SN/A    /**
881634SN/A     * The hit priority (HP) policy replaces entries that do not receive cache
891634SN/A     * hits over any cache entry that receives a hit, while the frequency
901634SN/A     * priority (FP) policy replaces infrequently re-referenced entries.
911634SN/A     */
921634SN/A    const bool hitPriority;
932521SN/A
941634SN/A    /**
951634SN/A     * Bimodal throtle parameter. Value in the range [0,100] used to decide
962512SN/A     * if a new entry is inserted with long or distant re-reference.
975480Snate@binkert.org     */
982SN/A    const unsigned btp;
992SN/A
1002512SN/A  public:
1012512SN/A    /** Convenience typedef. */
1022512SN/A    typedef BRRIPRPParams Params;
1032512SN/A
104540SN/A    /**
1052641SN/A     * Construct and initiliaze this replacement policy.
1062522SN/A     */
1072641SN/A    BRRIPRP(const Params *p);
1082512SN/A
1092630SN/A    /**
1104986SN/A     * Destructor.
1112521SN/A     */
1122641SN/A    ~BRRIPRP() {}
113873SN/A
114873SN/A    /**
115873SN/A     * Invalidate replacement data to set it as the next probable victim.
116873SN/A     * Set RRPV as the the most distant re-reference.
117873SN/A     *
1182630SN/A     * @param replacement_data Replacement data to be invalidated.
119873SN/A     */
120873SN/A    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
1212630SN/A                                                              const override;
122873SN/A
123873SN/A    /**
1242630SN/A     * Touch an entry to update its replacement data.
125873SN/A     *
126873SN/A     * @param replacement_data Replacement data to be touched.
1272630SN/A     */
128873SN/A    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
129873SN/A                                                                     override;
1302512SN/A
1312512SN/A    /**
1322512SN/A     * Reset replacement data. Used when an entry is inserted.
1334870SN/A     * Set RRPV according to the insertion policy used.
134873SN/A     *
1355480Snate@binkert.org     * @param replacement_data Replacement data to be reset.
1362630SN/A     */
137873SN/A    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
138873SN/A                                                                     override;
139873SN/A
140873SN/A    /**
141873SN/A     * Find replacement victim using rrpv.
1425478SN/A     *
143873SN/A     * @param cands Replacement candidates, selected by indexing policy.
144873SN/A     * @return Replacement entry to be replaced.
1452630SN/A     */
146873SN/A    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
147873SN/A                                                                     override;
1482630SN/A
149873SN/A    /**
150873SN/A     * Instantiate a replacement data entry.
1512630SN/A     *
152873SN/A     * @return A shared pointer to the new replacement data.
153873SN/A     */
1542630SN/A    std::shared_ptr<ReplacementData> instantiateEntry() override;
155873SN/A};
156873SN/A
1572630SN/A#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
158873SN/A