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 uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override;
 144
 145   public:
 146     typedef FPCDParams Params;
 147     FPCD(const Params *p);
 148     ~FPCD() = default;
 149 };
 150
 151 class FPCD::PatternZZZZ : public MaskedValuePattern<0, 0xFFFFFFFF>
 152 {
 153   public:
 154     PatternZZZZ(const DictionaryEntry bytes, const int match_location)
 155         : MaskedValuePattern<0, 0xFFFFFFFF>(ZZZZ, 0x0, prefixSize,
 156           match_location, bytes, true)
 157     {
 158     }
 159 };
 160
 161 class FPCD::PatternFFFF : public MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF>
 162 {
 163   public:
 164     PatternFFFF(const DictionaryEntry bytes, const int match_location)
 165         : MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF>(FFFF, 0x1,
 166           prefixSize, match_location, bytes, true)
 167     {
 168     }
 169 };
 170
 171 class FPCD::PatternMMMMPrevious
 172     : public LocatedMaskedPattern<0xFFFFFFFF, previousIndex>
 173 {
 174   public:
 175     PatternMMMMPrevious(const DictionaryEntry bytes,
 176         const int match_location)
 177         : LocatedMaskedPattern<0xFFFFFFFF, previousIndex>(MMMMPrevious,
 178           0x2, prefixSize, match_location, bytes)
 179     {
 180     }
 181 };
 182
 183 class FPCD::PatternMMMMPenultimate
 184     : public LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex>
 185 {
 186   public:
 187     PatternMMMMPenultimate(const DictionaryEntry bytes,
 188         const int match_location)
 189         : LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex>(
 190           MMMMPenultimate, 0x3, prefixSize, match_location, bytes)
 191     {
 192     }
 193 };
 194
 195 class FPCD::PatternZZZX : public MaskedValuePattern<0, 0xFFFFFF00>
 196 {
 197   public:
 198     PatternZZZX(const DictionaryEntry bytes, const int match_location)
 199         : MaskedValuePattern<0, 0xFFFFFF00>(ZZZX, 0x4, prefixSize,
 200           match_location, bytes, true)
 201     {
 202     }
 203 };
 204
 205 class FPCD::PatternXZZZ : public MaskedValuePattern<0, 0x00FFFFFF>
 206 {
 207   public:
 208     PatternXZZZ(const DictionaryEntry bytes, const int match_location)
 209         : MaskedValuePattern<0, 0x00FFFFFF>(XZZZ, 0x5, prefixSize,
 210           match_location, bytes, true)
 211     {
 212     }
 213 };
 214
 215 class FPCD::PatternRRRR : public RepeatedValuePattern<uint8_t>
 216 {
 217   public:
 218     PatternRRRR(const DictionaryEntry bytes, const int match_location)
 219         : RepeatedValuePattern<uint8_t>(RRRR, 0x6, prefixSize,
 220           match_location, bytes, true)
 221     {
 222     }
 223 };
 224
 225 class FPCD::PatternMMMXPrevious
 226     : public LocatedMaskedPattern<0xFFFFFF00, previousIndex>
 227 {
 228   public:
 229     PatternMMMXPrevious(const DictionaryEntry bytes,
 230         const int match_location)
 231         : LocatedMaskedPattern<0xFFFFFF00, previousIndex>(MMMXPrevious,
 232           0x7, prefixSize, match_location, bytes)
 233     {
 234     }
 235 };
 236
 237 class FPCD::PatternMMMXPenultimate
 238     : public LocatedMaskedPattern<0xFFFFFF00, penultimateIndex>
 239 {
 240   public:
 241     PatternMMMXPenultimate(const DictionaryEntry bytes,
 242         const int match_location)
 243         : LocatedMaskedPattern<0xFFFFFF00, penultimateIndex>(
 244           MMMXPenultimate, 0x8, prefixSize, match_location, bytes)
 245     {
 246     }
 247 };
 248
 249 class FPCD::PatternZZXX : public MaskedValuePattern<0, 0xFFFF0000>
 250 {
 251   public:
 252     PatternZZXX(const DictionaryEntry bytes, const int match_location)
 253         : MaskedValuePattern<0, 0xFFFF0000>(ZZXX, 0x9, prefixSize,
 254           match_location, bytes, true)
 255     {
 256     }
 257 };
 258
 259 class FPCD::PatternZXZX : public MaskedValuePattern<0, 0xFF00FF00>
 260 {
 261   public:
 262     PatternZXZX(const DictionaryEntry bytes, const int match_location)
 263         : MaskedValuePattern<0, 0xFF00FF00>(ZXZX, 0xA, prefixSize,
 264           match_location, bytes, true)
 265     {
 266     }
 267 };
 268
 269 class FPCD::PatternFFXX : public MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000>
 270 {
 271   public:
 272     PatternFFXX(const DictionaryEntry bytes, const int match_location)
 273         : MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000>(FFXX, 0xB,
 274           prefixSize, match_location, bytes, true)
 275     {
 276     }
 277 };
 278
 279 class FPCD::PatternXXZZ : public MaskedValuePattern<0, 0x0000FFFF>
 280 {
 281   public:
 282     PatternXXZZ(const DictionaryEntry bytes, const int match_location)
 283         : MaskedValuePattern<0, 0x0000FFFF>(XXZZ, 0xC, prefixSize,
 284           match_location, bytes, true)
 285     {
 286     }
 287 };
 288
 289 class FPCD::PatternMMXXPrevious
 290     : public LocatedMaskedPattern<0xFFFF0000, previousIndex>
 291 {
 292   public:
 293     PatternMMXXPrevious(const DictionaryEntry bytes,
 294         const int match_location)
 295         : LocatedMaskedPattern<0xFFFF0000, previousIndex>(MMXXPrevious,
 296           0xD, prefixSize, match_location, bytes)
 297     {
 298     }
 299 };
 300
 301 class FPCD::PatternMMXXPenultimate
 302     : public LocatedMaskedPattern<0xFFFF0000, penultimateIndex>
 303 {
 304   public:
 305     PatternMMXXPenultimate(const DictionaryEntry bytes,
 306         const int match_location)
 307         : LocatedMaskedPattern<0xFFFF0000, penultimateIndex>(
 308           MMXXPenultimate, 0xE, prefixSize, match_location, bytes)
 309     {
 310     }
 311 };
 312
 313 class FPCD::PatternXXXX : public UncompressedPattern
 314 {
 315   public:
 316     PatternXXXX(const DictionaryEntry bytes, const int match_location)
 317         : UncompressedPattern(XXXX, 0xF, prefixSize, match_location,
 318           bytes)
 319     {
 320     }
 321 };
 322
 323 } // namespace Compressor
 324
 325 #endif //__MEM_CACHE_COMPRESSORS_FPCD_HH__