src/mem/cache/compressors/base.cc

   1 /*
   2  * Copyright (c) 2018-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 a basic cache compressor.
  31  */
  32
  33 #include "mem/cache/compressors/base.hh"
  34
  35 #include <algorithm>
  36 #include <climits>
  37 #include <cmath>
  38 #include <cstdint>
  39 #include <string>
  40
  41 #include "base/trace.hh"
  42 #include "debug/CacheComp.hh"
  43 #include "mem/cache/base.hh"
  44 #include "mem/cache/tags/super_blk.hh"
  45 #include "params/BaseCacheCompressor.hh"
  46
  47 namespace Compressor {
  48
  49 // Uncomment this line if debugging compression
  50 //#define DEBUG_COMPRESSION
  51
  52 Base::CompressionData::CompressionData()
  53     : _size(0)
  54 {
  55 }
  56
  57 Base::CompressionData::~CompressionData()
  58 {
  59 }
  60
  61 void
  62 Base::CompressionData::setSizeBits(std::size_t size)
  63 {
  64     _size = size;
  65 }
  66
  67 std::size_t
  68 Base::CompressionData::getSizeBits() const
  69 {
  70     return _size;
  71 }
  72
  73 std::size_t
  74 Base::CompressionData::getSize() const
  75 {
  76     return std::ceil(_size/8);
  77 }
  78
  79 Base::Base(const Params &p)
  80   : SimObject(p), blkSize(p.block_size), chunkSizeBits(p.chunk_size_bits),
  81     sizeThreshold((blkSize * p.size_threshold_percentage) / 100),
  82     compChunksPerCycle(p.comp_chunks_per_cycle),
  83     compExtraLatency(p.comp_extra_latency),
  84     decompChunksPerCycle(p.decomp_chunks_per_cycle),
  85     decompExtraLatency(p.decomp_extra_latency),
  86     cache(nullptr), stats(*this)
  87 {
  88     fatal_if(64 % chunkSizeBits,
  89         "64 must be a multiple of the chunk granularity.");
  90
  91     fatal_if(((CHAR_BIT * blkSize) / chunkSizeBits) < compChunksPerCycle,
  92         "Compressor processes more chunks per cycle than the number of "
  93         "chunks in the input");
  94     fatal_if(((CHAR_BIT * blkSize) / chunkSizeBits) < decompChunksPerCycle,
  95         "Decompressor processes more chunks per cycle than the number of "
  96         "chunks in the input");
  97
  98     fatal_if(blkSize < sizeThreshold, "Compressed data must fit in a block");
  99 }
 100
 101 void
 102 Base::setCache(BaseCache *_cache)
 103 {
 104     assert(!cache);
 105     cache = _cache;
 106 }
 107
 108 std::vector<Base::Chunk>
 109 Base::toChunks(const uint64_t* data) const
 110 {
 111     // Number of chunks in a 64-bit value
 112     const unsigned num_chunks_per_64 =
 113         (sizeof(uint64_t) * CHAR_BIT) / chunkSizeBits;
 114
 115     // Turn a 64-bit array into a chunkSizeBits-array
 116     std::vector<Chunk> chunks((blkSize * CHAR_BIT) / chunkSizeBits, 0);
 117     for (int i = 0; i < chunks.size(); i++) {
 118         const int index_64 = std::floor(i / (double)num_chunks_per_64);
 119         const unsigned start = i % num_chunks_per_64;
 120         chunks[i] = bits(data[index_64],
 121             (start + 1) * chunkSizeBits - 1, start * chunkSizeBits);
 122     }
 123
 124     return chunks;
 125 }
 126
 127 void
 128 Base::fromChunks(const std::vector<Chunk>& chunks, uint64_t* data) const
 129 {
 130     // Number of chunks in a 64-bit value
 131     const unsigned num_chunks_per_64 =
 132         (sizeof(uint64_t) * CHAR_BIT) / chunkSizeBits;
 133
 134     // Turn a chunkSizeBits-array into a 64-bit array
 135     std::memset(data, 0, blkSize);
 136     for (int i = 0; i < chunks.size(); i++) {
 137         const int index_64 = std::floor(i / (double)num_chunks_per_64);
 138         const unsigned start = i % num_chunks_per_64;
 139         replaceBits(data[index_64], (start + 1) * chunkSizeBits - 1,
 140             start * chunkSizeBits, chunks[i]);
 141     }
 142 }
 143
 144 std::unique_ptr<Base::CompressionData>
 145 Base::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat)
 146 {
 147     // Apply compression
 148     std::unique_ptr<CompressionData> comp_data =
 149         compress(toChunks(data), comp_lat, decomp_lat);
 150
 151     // If we are in debug mode apply decompression just after the compression.
 152     // If the results do not match, we've got an error
 153     #ifdef DEBUG_COMPRESSION
 154     uint64_t decomp_data[blkSize/8];
 155
 156     // Apply decompression
 157     decompress(comp_data.get(), decomp_data);
 158
 159     // Check if decompressed line matches original cache line
 160     fatal_if(std::memcmp(data, decomp_data, blkSize),
 161              "Decompressed line does not match original line.");
 162     #endif
 163
 164     // Get compression size. If compressed size is greater than the size
 165     // threshold, the compression is seen as unsuccessful
 166     std::size_t comp_size_bits = comp_data->getSizeBits();
 167     if (comp_size_bits > sizeThreshold * CHAR_BIT) {
 168         comp_size_bits = blkSize * CHAR_BIT;
 169         comp_data->setSizeBits(comp_size_bits);
 170         stats.failedCompressions++;
 171     }
 172
 173     // Update stats
 174     stats.compressions++;
 175     stats.compressionSizeBits += comp_size_bits;
 176     if (comp_size_bits != 0) {
 177         stats.compressionSize[1 + std::ceil(std::log2(comp_size_bits))]++;
 178     } else {
 179         stats.compressionSize[0]++;
 180     }
 181
 182     // Print debug information
 183     DPRINTF(CacheComp, "Compressed cache line from %d to %d bits. " \
 184             "Compression latency: %llu, decompression latency: %llu\n",
 185             blkSize*8, comp_size_bits, comp_lat, decomp_lat);
 186
 187     return comp_data;
 188 }
 189
 190 Cycles
 191 Base::getDecompressionLatency(const CacheBlk* blk)
 192 {
 193     const CompressionBlk* comp_blk = static_cast<const CompressionBlk*>(blk);
 194
 195     // If block is compressed, return its decompression latency
 196     if (comp_blk && comp_blk->isCompressed()){
 197         const Cycles decomp_lat = comp_blk->getDecompressionLatency();
 198         DPRINTF(CacheComp, "Decompressing block: %s (%d cycles)\n",
 199                 comp_blk->print(), decomp_lat);
 200         stats.decompressions += 1;
 201         return decomp_lat;
 202     }
 203
 204     // Block is not compressed, so there is no decompression latency
 205     return Cycles(0);
 206 }
 207
 208 void
 209 Base::setDecompressionLatency(CacheBlk* blk, const Cycles lat)
 210 {
 211     // Sanity check
 212     assert(blk != nullptr);
 213
 214     // Assign latency
 215     static_cast<CompressionBlk*>(blk)->setDecompressionLatency(lat);
 216 }
 217
 218 void
 219 Base::setSizeBits(CacheBlk* blk, const std::size_t size_bits)
 220 {
 221     // Sanity check
 222     assert(blk != nullptr);
 223
 224     // Assign size
 225     static_cast<CompressionBlk*>(blk)->setSizeBits(size_bits);
 226 }
 227
 228 Base::BaseStats::BaseStats(Base& _compressor)
 229   : Stats::Group(&_compressor), compressor(_compressor),
 230     ADD_STAT(compressions, UNIT_COUNT, "Total number of compressions"),
 231     ADD_STAT(failedCompressions, UNIT_COUNT,
 232              "Total number of failed compressions"),
 233     ADD_STAT(compressionSize, UNIT_COUNT,
 234              "Number of blocks that were compressed to this power of two "
 235              "size"),
 236     ADD_STAT(compressionSizeBits, UNIT_BIT,
 237              "Total compressed data size, in bits"),
 238     ADD_STAT(avgCompressionSizeBits,
 239              UNIT_RATE(Stats::Units::Bit, Stats::Units::Count),
 240              "Average compression size, in bits"),
 241     ADD_STAT(decompressions, UNIT_COUNT, "Total number of decompressions")
 242 {
 243 }
 244
 245 void
 246 Base::BaseStats::regStats()
 247 {
 248     Stats::Group::regStats();
 249
 250     // Values comprised are {0, 1, 2, 4, ..., blkSize}
 251     compressionSize.init(std::log2(compressor.blkSize*8) + 2);
 252     compressionSize.subname(0, "0");
 253     compressionSize.subdesc(0,
 254         "Number of blocks that compressed to fit in 0 bits");
 255     for (unsigned i = 0; i <= std::log2(compressor.blkSize*8); ++i) {
 256         std::string str_i = std::to_string(1 << i);
 257         compressionSize.subname(1+i, str_i);
 258         compressionSize.subdesc(1+i,
 259             "Number of blocks that compressed to fit in " + str_i + " bits");
 260     }
 261
 262     avgCompressionSizeBits.flags(Stats::total | Stats::nozero | Stats::nonan);
 263     avgCompressionSizeBits = compressionSizeBits / compressions;
 264 }
 265
 266 } // namespace Compressor