src/mem/cache/compressors/bdi.hh

   1 /*
   2  * Copyright (c) 2018 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  * Authors: Daniel Carvalho
  29  */
  30
  31 /** @file
  32  * Definition of "Base-Delta-Immediate Compression: Practical Data Compression
  33  * for On-Chip Caches".
  34  */
  35
  36 #ifndef __MEM_CACHE_COMPRESSORS_BDI_HH__
  37 #define __MEM_CACHE_COMPRESSORS_BDI_HH__
  38
  39 #include <cstdint>
  40 #include <memory>
  41 #include <vector>
  42
  43 #include "base/types.hh"
  44 #include "mem/cache/compressors/base.hh"
  45
  46 struct BDIParams;
  47
  48 /**
  49  * Default maximum number of bases in the original BDI.
  50  */
  51 #define BDI_DEFAULT_MAX_NUM_BASES 2
  52
  53 class BDI : public BaseCacheCompressor
  54 {
  55   protected:
  56     /**
  57      * Forward declaration of comp data classes.
  58      */
  59     class BDICompData;
  60     class BDICompDataZeros;
  61     class BDICompDataRep;
  62     class BDICompDataUncompressed;
  63     template <class TB, class TD> class BDICompDataBaseDelta;
  64
  65     /**
  66      * The possible encoding values. If modified, ENCODING_NAMES must be too.
  67      */
  68     enum ENCODING {ZERO, REP_VALUES, BASE8_1, BASE8_2, BASE8_4, BASE4_1,
  69                    BASE4_2, BASE2_1, UNCOMPRESSED, NUM_ENCODINGS};
  70
  71     /**
  72      * The respective encoding names. They are indexed by the ENCODING enum.
  73      * The values are assigned in the source file, and should be modified if
  74      * ENCODING is changed.
  75      */
  76     static const char* ENCODING_NAMES[];
  77
  78     /**
  79      * If set, create multiple compressor instances for each possible
  80      * combination of base and delta size. Otherwise, just create a
  81      * compressor for each base size with the highest available delta
  82      * size. This can be used to save area and power (having less
  83      * compressors). True by default.
  84      */
  85     const bool useMoreCompressors;
  86
  87     /**
  88      * Number of qwords in a cache line.
  89      */
  90     const std::size_t qwordsPerCacheLine;
  91
  92     /**
  93      * @defgroup CompressionStats Compression specific statistics.
  94      * @{
  95      */
  96
  97     /**
  98      * Number of data entries that were compressed to each encoding.
  99      */
 100     Stats::Vector encodingStats;
 101
 102     /**
 103      * @}
 104      */
 105
 106     /**
 107      * Check if the cache line consists of only zero values.
 108      *
 109      * @param data The cache line.
 110      * @return True if it is a ZERO cache line.
 111      */
 112     bool isZeroPackable(const uint64_t* data) const;
 113
 114     /**
 115      * Check if the cache line consists only of same values.
 116      *
 117      * @param data The cache line.
 118      * @return True if it is a REP_VALUES cache line.
 119      */
 120     bool isSameValuePackable(const uint64_t* data) const;
 121
 122     /**
 123      * Instantiate a BaseDelta compressor with given TB and TD, and try to
 124      * compress the cache line. If the compression fails, it returns a nullptr.
 125      * @sa BDICompDataBaseDelta
 126      *
 127      * @tparam TB Type of a base entry.
 128      * @tparam TD Type of a delta entry.
 129      * @param data The cache line to be compressed.
 130      * @param encoding Encoding value for given TB-TD combination.
 131      * @return Cache line after compression or nullptr.
 132      */
 133     template <class TB, class TD>
 134     std::unique_ptr<BDICompData> tryCompress(const uint64_t* data,
 135                                              const uint8_t encoding) const;
 136
 137     /**
 138      * Apply compression.
 139      *
 140      * @param data The cache line to be compressed.
 141      * @param comp_lat Compression latency in number of cycles.
 142      * @param decomp_lat Decompression latency in number of cycles.
 143      * @param comp_size Compressed data size.
 144      */
 145     std::unique_ptr<BaseCacheCompressor::CompressionData> compress(
 146         const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override;
 147
 148     /**
 149      * Decompress data.
 150      *
 151      * @param comp_data Compressed cache line.
 152      * @param data The cache line to be decompressed.
 153      * @return Decompression latency in number of cycles.
 154      */
 155     void decompress(const BaseCacheCompressor::CompressionData* comp_data,
 156                                            uint64_t* data) override;
 157
 158   public:
 159     /** Convenience typedef. */
 160     typedef BDIParams Params;
 161
 162     /**
 163      * Default constructor.
 164      */
 165     BDI(const Params *p);
 166
 167     /**
 168      * Default destructor.
 169      */
 170     ~BDI() = default;
 171
 172     /**
 173      * Register local statistics.
 174      */
 175     void regStats() override;
 176 };
 177
 178 /**
 179  * Template for the BDI compression data.
 180  */
 181 class BDI::BDICompData : public CompressionData
 182 {
 183   private:
 184     /**
 185      * Data encoding.
 186      * @sa BDI
 187      */
 188     const uint8_t _encoding;
 189
 190   protected:
 191     /**
 192      * Number of bits needed for the encoding field.
 193      */
 194     static const std::size_t encodingBits = 4;
 195
 196     /**
 197      * Calculate and set compressed data size.
 198      * Each BDI compressor generates compressed data with different sizes.
 199     */
 200     virtual void calculateCompressedSize() = 0;
 201
 202   public:
 203     /**
 204      * Default constructor.
 205      *
 206      * @param encoding The encoding value.
 207      */
 208     BDICompData(const uint8_t encoding);
 209
 210     /**
 211      * Default destructor.
 212      */
 213     virtual ~BDICompData() = default;
 214
 215     /**
 216      * Get and decompress data at given index.
 217      *
 218      * The index is given relative to 64-bit entries, therefore if the base
 219      * size of the given compressed data is smaller than that, this function
 220      * joins multiple base-delta entries to generate the respective 64-bit
 221      * entry.
 222      *
 223      * @param index The index of the compressed data.
 224      * @return Decompressed data for the given index.
 225      */
 226     virtual uint64_t access(const int index) const = 0;
 227
 228     /**
 229      * Get encoding.
 230      *
 231      * @return The encoding.
 232      */
 233     uint8_t getEncoding() const;
 234
 235     /**
 236      * Get encoding name.
 237      *
 238      * @return The encoding name.
 239      */
 240     std::string getName() const;
 241 };
 242
 243 /**
 244  * BDI compressed data containing the ZERO encoding.
 245  */
 246 class BDI::BDICompDataZeros : public BDICompData
 247 {
 248   protected:
 249     /**
 250      * Calculate compressed data size using ZERO encoding.
 251      */
 252     void calculateCompressedSize() override;
 253
 254   public:
 255     /**
 256      * Default constructor.
 257     */
 258     BDICompDataZeros();
 259
 260     /**
 261      * Get and decompress data at given index. Must always return 0.
 262      *
 263      * @param index The index of the compressed data.
 264      * @return Decompressed data for the given index.
 265      */
 266     uint64_t access(const int index) const override;
 267 };
 268
 269 /**
 270  * BDI compressed data containing the REP_VALUES encoding.
 271  */
 272 class BDI::BDICompDataRep : public BDICompData
 273 {
 274   private:
 275     /**
 276      * The repeated value.
 277      */
 278     uint64_t base;
 279
 280   protected:
 281     /**
 282      * Calculate compressed data size using REP_VALUES encoding.
 283      */
 284     void calculateCompressedSize() override;
 285
 286   public:
 287     /**
 288      * Default constructor.
 289      *
 290      * @param rep_value The repeated value.
 291      */
 292     BDICompDataRep(const uint64_t rep_value);
 293
 294     /**
 295      * Get and decompress data at given index. Must always return the same
 296      * value as data[0].
 297      *
 298      * @param index The index of the compressed data.
 299      * @return Decompressed data for the given index.
 300      */
 301     uint64_t access(const int index) const override;
 302 };
 303
 304 /**
 305  * BDI compressed data containing the UNCOMPRESSED encoding.
 306  */
 307 class BDI::BDICompDataUncompressed : public BDICompData
 308 {
 309   private:
 310     /**
 311      * Uncompressed cache line size (in bytes).
 312      */
 313     const std::size_t blkSize;
 314
 315     /**
 316      * The compressed data is the original cache line.
 317      */
 318     const std::vector<uint64_t> _data;
 319
 320   protected:
 321     /**
 322      * Calculate compressed data size using UNCOMPRESSED encoding.
 323      */
 324     void calculateCompressedSize() override;
 325
 326   public:
 327     /**
 328      * Default constructor.
 329      *
 330      * @param data The data on which compression was applied.
 331      * @param blk_size Size of a cache line in bytes.
 332      */
 333     BDICompDataUncompressed(const uint64_t* data,
 334                             const std::size_t blk_size);
 335
 336     /**
 337      * Get and decompress data at given index. Must return the same
 338      * value as _data[index].
 339      *
 340      * @param index The index of the compressed data.
 341      * @return Decompressed data for the given index.
 342      */
 343     uint64_t access(const int index) const override;
 344 };
 345
 346 /**
 347  * Template class for BDI compressed data containing all the BASE_DELTA
 348  * encodings. TB's size must always be greater than TD's.
 349  *
 350  * @tparam TB Type of a base entry.
 351  * @tparam TD Type of a delta entry.
 352 */
 353 template <class TB, class TD>
 354 class BDI::BDICompDataBaseDelta : public BDICompData
 355 {
 356   protected:
 357     /**
 358      * Maximum number of bases.
 359      */
 360     const std::size_t maxNumBases;
 361
 362     /**
 363      * Bit mask to differentiate between the bases.
 364      */
 365     std::vector<uint8_t> bitMask;
 366
 367     /**
 368      * Bases. bases[0] is 0 and is not stored in a hardware implementation.
 369      */
 370     std::vector<TB> bases;
 371
 372     /**
 373      * Array of deltas (or immediate values).
 374      */
 375     std::vector<TD> deltas;
 376
 377     /**
 378      * Add a base to the bases vector.
 379      *
 380      * @param base The base to be added.
 381      * @return True on success, false if already used all base slots.
 382      */
 383     bool addBase(const TB base);
 384
 385     /**
 386      * Add a delta to the deltas vector.
 387      *
 388      * @param base_index Base to which the delta refers.
 389      * @param delta The delta value.
 390      */
 391     void addDelta(const std::size_t base_index, const TD delta);
 392
 393     /**
 394      * Calculate compressed data size using number of bases, the base size and
 395      * the delta size.
 396      */
 397     void calculateCompressedSize() override;
 398
 399   public:
 400     /**
 401      * Default constructor.
 402      *
 403      * @param encoding The encoding value for this compressor.
 404      * @param blk_size Size of a cache line in bytes.
 405      * @param max_num_bases Maximum number of bases allowed to be stored.
 406      */
 407     BDICompDataBaseDelta(const uint8_t encoding, const std::size_t blk_size,
 408         const std::size_t max_num_bases = BDI_DEFAULT_MAX_NUM_BASES);
 409
 410     /**
 411      * Get and decompress data at given index.
 412      *
 413      * @param index The index of the compressed data.
 414      * @return Decompressed data for the given index.
 415      */
 416     uint64_t access(const int index) const override;
 417
 418     /**
 419      * Apply base delta compression.
 420      *
 421      * @param data The data on which compression was applied.
 422      * @param blk_size Size of a cache line in bytes.
 423      * @return True on success.
 424      */
 425     bool compress(const uint64_t* data, const std::size_t blk_size);
 426 };
 427
 428 #endif //__MEM_CACHE_COMPRESSORS_BDI_HH__