src/mem/cache/compressors/fpcd.hh

   1 /*
   2  * Copyright (c) 2019-2020 Inria
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @file
  30  * Definition of the Frequent Pattern Compression with limited Dictionary
  31  * support (FPC-D) cache compressor, as described in "Opportunistic
  32  * Compression for Direct-Mapped DRAM Caches", by Alameldeen et al.
  33  *
  34  * It is a pattern compressor that can only have 2 dictionary entries, and
  35  * as such the pattern encodings are specialized to inform to which entry it
  36  * refers. These entries are replaced in a FIFO manner.
  37  */
  38
  39 #ifndef __MEM_CACHE_COMPRESSORS_FPCD_HH__
  40 #define __MEM_CACHE_COMPRESSORS_FPCD_HH__
  41
  42 #include <cstdint>
  43 #include <map>
  44 #include <memory>
  45 #include <string>
  46
  47 #include "base/types.hh"
  48 #include "mem/cache/compressors/dictionary_compressor.hh"
  49
  50 struct FPCDParams;
  51
  52 namespace Compressor {
  53
  54 class FPCD : public DictionaryCompressor<uint32_t>
  55 {
  56   private:
  57     using DictionaryEntry = DictionaryCompressor<uint32_t>::DictionaryEntry;
  58
  59     /** Number of bits in a FPCD pattern prefix. */
  60     static constexpr int prefixSize = 4;
  61
  62     /** Index of the previous dictionary entry. */
  63     static constexpr int previousIndex = 1;
  64
  65     /** Index of the penultimate dictionary entry. */
  66     static constexpr int penultimateIndex = 0;
  67
  68     // Declaration of all possible patterns, from lowest to highest sizes.
  69     // Penultimate is prioritized over previous to reduce the ripple effect
  70     // of propagating values during decompression
  71     class PatternZZZZ;
  72     class PatternFFFF;
  73     class PatternMMMMPenultimate;
  74     class PatternMMMMPrevious;
  75     class PatternZZZX;
  76     class PatternXZZZ;
  77     class PatternRRRR;
  78     class PatternMMMXPenultimate;
  79     class PatternMMMXPrevious;
  80     class PatternZZXX;
  81     class PatternZXZX;
  82     class PatternFFXX;
  83     class PatternXXZZ;
  84     class PatternMMXXPenultimate;
  85     class PatternMMXXPrevious;
  86     class PatternXXXX;
  87
  88     /**
  89      * The patterns proposed in the paper. Each letter represents a byte:
  90      * Z is a null byte, M is a dictionary match, X is a new value, R is
  91      * a repeated value.
  92      * These are used as indexes to reference the pattern data. If a new
  93      * pattern is added, it must be done before NUM_PATTERNS.
  94      */
  95     typedef enum {
  96         ZZZZ, FFFF, MMMMPenultimate, MMMMPrevious, ZZZX, XZZZ, RRRR,
  97         MMMXPenultimate, MMMXPrevious, ZZXX, ZXZX, FFXX, XXZZ,
  98         MMXXPenultimate, MMXXPrevious, XXXX, NUM_PATTERNS
  99     } PatternNumber;
 100
 101     /**
 102      * Convenience factory declaration. The templates must be organized by
 103      * size, with the smallest first, and "no-match" last.
 104      */
 105     using PatternFactory =
 106         Factory<PatternZZZZ, PatternFFFF, PatternMMMMPrevious,
 107                 PatternMMMMPenultimate, PatternZZZX, PatternXZZZ,
 108                 PatternRRRR, PatternMMMXPrevious, PatternMMMXPenultimate,
 109                 PatternZZXX, PatternZXZX, PatternFFXX, PatternXXZZ,
 110                 PatternMMXXPrevious, PatternMMXXPenultimate, PatternXXXX>;
 111
 112     uint64_t getNumPatterns() const override { return NUM_PATTERNS; }
 113
 114     std::string
 115     getName(int number) const override
 116     {
 117         static std::map<PatternNumber, std::string> pattern_names = {
 118             {ZZZZ, "ZZZZ"}, {FFFF, "FFFF"},
 119             {MMMMPenultimate, "MMMMPenultimate"},
 120             {MMMMPrevious, "MMMMPrevious"}, {ZZZX, "ZZZX"},
 121             {XZZZ, "XZZZ"}, {RRRR, "RRRR"},
 122             {MMMXPenultimate, "MMMXPenultimate"},
 123             {MMMXPrevious, "MMMXPrevious"},
 124             {ZZXX, "ZZXX"},
 125             {ZXZX, "ZXZX"}, {FFXX, "FFXX"}, {XXZZ, "XXZZ"},
 126             {MMXXPenultimate, "MMXXPenultimate"},
 127             {MMXXPrevious, "MMXXPrevious"}, {XXXX, "XXXX"}
 128         };
 129
 130         return pattern_names[(PatternNumber)number];
 131     };
 132
 133     std::unique_ptr<Pattern>
 134     getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
 135         const int match_location) const override
 136     {
 137         return PatternFactory::getPattern(bytes, dict_bytes, match_location);
 138     }
 139
 140     void addToDictionary(DictionaryEntry data) override;
 141
 142     std::unique_ptr<Base::CompressionData> compress(
 143         const std::vector<Base::Chunk>& chunks,
 144         Cycles& comp_lat, Cycles& decomp_lat) override;
 145
 146   public:
 147     typedef FPCDParams Params;
 148     FPCD(const Params *p);
 149     ~FPCD() = default;
 150 };
 151
 152 class FPCD::PatternZZZZ : public MaskedValuePattern<0, 0xFFFFFFFF>
 153 {
 154   public:
 155     PatternZZZZ(const DictionaryEntry bytes, const int match_location)
 156         : MaskedValuePattern<0, 0xFFFFFFFF>(ZZZZ, 0x0, prefixSize,
 157           match_location, bytes, true)
 158     {
 159     }
 160 };
 161
 162 class FPCD::PatternFFFF : public MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF>
 163 {
 164   public:
 165     PatternFFFF(const DictionaryEntry bytes, const int match_location)
 166         : MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF>(FFFF, 0x1,
 167           prefixSize, match_location, bytes, true)
 168     {
 169     }
 170 };
 171
 172 class FPCD::PatternMMMMPrevious
 173     : public LocatedMaskedPattern<0xFFFFFFFF, previousIndex>
 174 {
 175   public:
 176     PatternMMMMPrevious(const DictionaryEntry bytes,
 177         const int match_location)
 178         : LocatedMaskedPattern<0xFFFFFFFF, previousIndex>(MMMMPrevious,
 179           0x2, prefixSize, match_location, bytes)
 180     {
 181     }
 182 };
 183
 184 class FPCD::PatternMMMMPenultimate
 185     : public LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex>
 186 {
 187   public:
 188     PatternMMMMPenultimate(const DictionaryEntry bytes,
 189         const int match_location)
 190         : LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex>(
 191           MMMMPenultimate, 0x3, prefixSize, match_location, bytes)
 192     {
 193     }
 194 };
 195
 196 class FPCD::PatternZZZX : public MaskedValuePattern<0, 0xFFFFFF00>
 197 {
 198   public:
 199     PatternZZZX(const DictionaryEntry bytes, const int match_location)
 200         : MaskedValuePattern<0, 0xFFFFFF00>(ZZZX, 0x4, prefixSize,
 201           match_location, bytes, true)
 202     {
 203     }
 204 };
 205
 206 class FPCD::PatternXZZZ : public MaskedValuePattern<0, 0x00FFFFFF>
 207 {
 208   public:
 209     PatternXZZZ(const DictionaryEntry bytes, const int match_location)
 210         : MaskedValuePattern<0, 0x00FFFFFF>(XZZZ, 0x5, prefixSize,
 211           match_location, bytes, true)
 212     {
 213     }
 214 };
 215
 216 class FPCD::PatternRRRR : public RepeatedValuePattern<uint8_t>
 217 {
 218   public:
 219     PatternRRRR(const DictionaryEntry bytes, const int match_location)
 220         : RepeatedValuePattern<uint8_t>(RRRR, 0x6, prefixSize,
 221           match_location, bytes, true)
 222     {
 223     }
 224 };
 225
 226 class FPCD::PatternMMMXPrevious
 227     : public LocatedMaskedPattern<0xFFFFFF00, previousIndex>
 228 {
 229   public:
 230     PatternMMMXPrevious(const DictionaryEntry bytes,
 231         const int match_location)
 232         : LocatedMaskedPattern<0xFFFFFF00, previousIndex>(MMMXPrevious,
 233           0x7, prefixSize, match_location, bytes)
 234     {
 235     }
 236 };
 237
 238 class FPCD::PatternMMMXPenultimate
 239     : public LocatedMaskedPattern<0xFFFFFF00, penultimateIndex>
 240 {
 241   public:
 242     PatternMMMXPenultimate(const DictionaryEntry bytes,
 243         const int match_location)
 244         : LocatedMaskedPattern<0xFFFFFF00, penultimateIndex>(
 245           MMMXPenultimate, 0x8, prefixSize, match_location, bytes)
 246     {
 247     }
 248 };
 249
 250 class FPCD::PatternZZXX : public MaskedValuePattern<0, 0xFFFF0000>
 251 {
 252   public:
 253     PatternZZXX(const DictionaryEntry bytes, const int match_location)
 254         : MaskedValuePattern<0, 0xFFFF0000>(ZZXX, 0x9, prefixSize,
 255           match_location, bytes, true)
 256     {
 257     }
 258 };
 259
 260 class FPCD::PatternZXZX : public MaskedValuePattern<0, 0xFF00FF00>
 261 {
 262   public:
 263     PatternZXZX(const DictionaryEntry bytes, const int match_location)
 264         : MaskedValuePattern<0, 0xFF00FF00>(ZXZX, 0xA, prefixSize,
 265           match_location, bytes, true)
 266     {
 267     }
 268 };
 269
 270 class FPCD::PatternFFXX : public MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000>
 271 {
 272   public:
 273     PatternFFXX(const DictionaryEntry bytes, const int match_location)
 274         : MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000>(FFXX, 0xB,
 275           prefixSize, match_location, bytes, true)
 276     {
 277     }
 278 };
 279
 280 class FPCD::PatternXXZZ : public MaskedValuePattern<0, 0x0000FFFF>
 281 {
 282   public:
 283     PatternXXZZ(const DictionaryEntry bytes, const int match_location)
 284         : MaskedValuePattern<0, 0x0000FFFF>(XXZZ, 0xC, prefixSize,
 285           match_location, bytes, true)
 286     {
 287     }
 288 };
 289
 290 class FPCD::PatternMMXXPrevious
 291     : public LocatedMaskedPattern<0xFFFF0000, previousIndex>
 292 {
 293   public:
 294     PatternMMXXPrevious(const DictionaryEntry bytes,
 295         const int match_location)
 296         : LocatedMaskedPattern<0xFFFF0000, previousIndex>(MMXXPrevious,
 297           0xD, prefixSize, match_location, bytes)
 298     {
 299     }
 300 };
 301
 302 class FPCD::PatternMMXXPenultimate
 303     : public LocatedMaskedPattern<0xFFFF0000, penultimateIndex>
 304 {
 305   public:
 306     PatternMMXXPenultimate(const DictionaryEntry bytes,
 307         const int match_location)
 308         : LocatedMaskedPattern<0xFFFF0000, penultimateIndex>(
 309           MMXXPenultimate, 0xE, prefixSize, match_location, bytes)
 310     {
 311     }
 312 };
 313
 314 class FPCD::PatternXXXX : public UncompressedPattern
 315 {
 316   public:
 317     PatternXXXX(const DictionaryEntry bytes, const int match_location)
 318         : UncompressedPattern(XXXX, 0xF, prefixSize, match_location,
 319           bytes)
 320     {
 321     }
 322 };
 323
 324 } // namespace Compressor
 325
 326 #endif //__MEM_CACHE_COMPRESSORS_FPCD_HH__