src/mem/cache/compressors/multi.cc

   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  * Implementation of the a multi compressor that choses the best compression
  31  * among multiple compressors.
  32  */
  33
  34 #include "mem/cache/compressors/multi.hh"
  35
  36 #include <cmath>
  37 #include <queue>
  38
  39 #include "base/bitfield.hh"
  40 #include "base/logging.hh"
  41 #include "base/trace.hh"
  42 #include "debug/CacheComp.hh"
  43 #include "params/MultiCompressor.hh"
  44
  45 namespace Compressor {
  46
  47 Multi::MultiCompData::MultiCompData(unsigned index,
  48     std::unique_ptr<Base::CompressionData> comp_data)
  49     : CompressionData(), index(index), compData(std::move(comp_data))
  50 {
  51     setSizeBits(compData->getSizeBits());
  52 }
  53
  54 uint8_t
  55 Multi::MultiCompData::getIndex() const
  56 {
  57     return index;
  58 }
  59
  60 Multi::Multi(const Params *p)
  61   : Base(p), compressors(p->compressors),
  62     numEncodingBits(p->encoding_in_tags ? 0 :
  63         std::log2(alignToPowerOfTwo(compressors.size()))),
  64     multiStats(stats, *this)
  65 {
  66     fatal_if(compressors.size() == 0, "There must be at least one compressor");
  67 }
  68
  69 Multi::~Multi()
  70 {
  71     for (auto& compressor : compressors) {
  72         delete compressor;
  73     }
  74 }
  75
  76 std::unique_ptr<Base::CompressionData>
  77 Multi::compress(const std::vector<Chunk>& chunks, Cycles& comp_lat,
  78     Cycles& decomp_lat)
  79 {
  80     struct Results
  81     {
  82         unsigned index;
  83         std::unique_ptr<Base::CompressionData> compData;
  84         Cycles decompLat;
  85         uint8_t compressionFactor;
  86
  87         Results(unsigned index,
  88             std::unique_ptr<Base::CompressionData> comp_data,
  89             Cycles decomp_lat, std::size_t blk_size)
  90             : index(index), compData(std::move(comp_data)),
  91               decompLat(decomp_lat)
  92         {
  93             const std::size_t size = compData->getSize();
  94             // If the compressed size is worse than the uncompressed size,
  95             // we assume the size is the uncompressed size, and thus the
  96             // compression factor is 1
  97             compressionFactor = (size > blk_size) ? 1 :
  98                 alignToPowerOfTwo(std::floor(blk_size / (double) size));
  99         }
 100     };
 101     struct ResultsComparator
 102     {
 103         bool
 104         operator()(const std::shared_ptr<Results>& lhs,
 105             const std::shared_ptr<Results>& rhs) const
 106         {
 107             const std::size_t lhs_cf = lhs->compressionFactor;
 108             const std::size_t rhs_cf = rhs->compressionFactor;
 109
 110             if (lhs_cf == rhs_cf) {
 111                 // When they have similar compressed sizes, give the one
 112                 // with fastest decompression privilege
 113                 return lhs->decompLat > rhs->decompLat;
 114             }
 115             return lhs_cf < rhs_cf;
 116         }
 117     };
 118
 119     // Each sub-compressor can have its own chunk size; therefore, revert
 120     // the chunks to raw data, so that they handle the conversion internally
 121     uint64_t data[blkSize / sizeof(uint64_t)];
 122     std::memset(data, 0, blkSize);
 123     fromChunks(chunks, data);
 124
 125     // Find the ranking of the compressor outputs
 126     std::priority_queue<std::shared_ptr<Results>,
 127         std::vector<std::shared_ptr<Results>>, ResultsComparator> results;
 128     Cycles max_comp_lat;
 129     for (unsigned i = 0; i < compressors.size(); i++) {
 130         Cycles temp_decomp_lat;
 131         auto temp_comp_data =
 132             compressors[i]->compress(data, comp_lat, temp_decomp_lat);
 133         temp_comp_data->setSizeBits(temp_comp_data->getSizeBits() +
 134             numEncodingBits);
 135         results.push(std::make_shared<Results>(i, std::move(temp_comp_data),
 136             temp_decomp_lat, blkSize));
 137         max_comp_lat = std::max(max_comp_lat, comp_lat);
 138     }
 139
 140     // Assign best compressor to compression data
 141     const unsigned best_index = results.top()->index;
 142     std::unique_ptr<CompressionData> multi_comp_data =
 143         std::unique_ptr<MultiCompData>(
 144             new MultiCompData(best_index, std::move(results.top()->compData)));
 145     DPRINTF(CacheComp, "Best compressor: %d\n", best_index);
 146
 147     // Set decompression latency of the best compressor
 148     decomp_lat = results.top()->decompLat;
 149
 150     // Update compressor ranking stats
 151     for (int rank = 0; rank < compressors.size(); rank++) {
 152         multiStats.ranks[results.top()->index][rank]++;
 153         results.pop();
 154     }
 155
 156     // Set compression latency (compression latency of the slowest compressor
 157     // and 1 cycle to pack)
 158     comp_lat = Cycles(max_comp_lat + 1);
 159
 160     return multi_comp_data;
 161 }
 162
 163 void
 164 Multi::decompress(const CompressionData* comp_data,
 165     uint64_t* cache_line)
 166 {
 167     const MultiCompData* casted_comp_data =
 168         static_cast<const MultiCompData*>(comp_data);
 169     compressors[casted_comp_data->getIndex()]->decompress(
 170         casted_comp_data->compData.get(), cache_line);
 171 }
 172
 173 Multi::MultiStats::MultiStats(BaseStats& base_group, Multi& _compressor)
 174   : Stats::Group(&base_group), compressor(_compressor),
 175     ranks(this, "ranks",
 176         "Number of times each compressor had the nth best compression")
 177 {
 178 }
 179
 180 void
 181 Multi::MultiStats::regStats()
 182 {
 183     Stats::Group::regStats();
 184
 185     const std::size_t num_compressors = compressor.compressors.size();
 186     ranks.init(num_compressors, num_compressors);
 187     for (unsigned compressor = 0; compressor < num_compressors; compressor++) {
 188         ranks.subname(compressor, std::to_string(compressor));
 189         ranks.subdesc(compressor, "Number of times compressor " +
 190             std::to_string(compressor) + " had the nth best compression.");
 191         for (unsigned rank = 0; rank < num_compressors; rank++) {
 192             ranks.ysubname(rank, std::to_string(rank));
 193         }
 194     }
 195 }
 196
 197 } // namespace Compressor
 198
 199 Compressor::Multi*
 200 MultiCompressorParams::create()
 201 {
 202     return new Compressor::Multi(this);
 203 }