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 void
  77 Multi::setCache(BaseCache *_cache)
  78 {
  79     Base::setCache(_cache);
  80     for (auto& compressor : compressors) {
  81         compressor->setCache(_cache);
  82     }
  83 }
  84
  85 std::unique_ptr<Base::CompressionData>
  86 Multi::compress(const std::vector<Chunk>& chunks, Cycles& comp_lat,
  87     Cycles& decomp_lat)
  88 {
  89     struct Results
  90     {
  91         unsigned index;
  92         std::unique_ptr<Base::CompressionData> compData;
  93         Cycles decompLat;
  94         uint8_t compressionFactor;
  95
  96         Results(unsigned index,
  97             std::unique_ptr<Base::CompressionData> comp_data,
  98             Cycles decomp_lat, std::size_t blk_size)
  99             : index(index), compData(std::move(comp_data)),
 100               decompLat(decomp_lat)
 101         {
 102             const std::size_t size = compData->getSize();
 103             // If the compressed size is worse than the uncompressed size,
 104             // we assume the size is the uncompressed size, and thus the
 105             // compression factor is 1.
 106             //
 107             // Some compressors (notably the zero compressor) may rely on
 108             // extra information being stored in the tags, or added in
 109             // another compression layer. Their size can be 0, so it is
 110             // assigned the highest possible compression factor (the original
 111             // block's size).
 112             compressionFactor = (size > blk_size) ? 1 :
 113                 ((size == 0) ? blk_size :
 114                 alignToPowerOfTwo(std::floor(blk_size / (double) size)));
 115         }
 116     };
 117     struct ResultsComparator
 118     {
 119         bool
 120         operator()(const std::shared_ptr<Results>& lhs,
 121             const std::shared_ptr<Results>& rhs) const
 122         {
 123             const std::size_t lhs_cf = lhs->compressionFactor;
 124             const std::size_t rhs_cf = rhs->compressionFactor;
 125
 126             if (lhs_cf == rhs_cf) {
 127                 // When they have similar compressed sizes, give the one
 128                 // with fastest decompression privilege
 129                 return lhs->decompLat > rhs->decompLat;
 130             }
 131             return lhs_cf < rhs_cf;
 132         }
 133     };
 134
 135     // Each sub-compressor can have its own chunk size; therefore, revert
 136     // the chunks to raw data, so that they handle the conversion internally
 137     uint64_t data[blkSize / sizeof(uint64_t)];
 138     std::memset(data, 0, blkSize);
 139     fromChunks(chunks, data);
 140
 141     // Find the ranking of the compressor outputs
 142     std::priority_queue<std::shared_ptr<Results>,
 143         std::vector<std::shared_ptr<Results>>, ResultsComparator> results;
 144     Cycles max_comp_lat;
 145     for (unsigned i = 0; i < compressors.size(); i++) {
 146         Cycles temp_decomp_lat;
 147         auto temp_comp_data =
 148             compressors[i]->compress(data, comp_lat, temp_decomp_lat);
 149         temp_comp_data->setSizeBits(temp_comp_data->getSizeBits() +
 150             numEncodingBits);
 151         results.push(std::make_shared<Results>(i, std::move(temp_comp_data),
 152             temp_decomp_lat, blkSize));
 153         max_comp_lat = std::max(max_comp_lat, comp_lat);
 154     }
 155
 156     // Assign best compressor to compression data
 157     const unsigned best_index = results.top()->index;
 158     std::unique_ptr<CompressionData> multi_comp_data =
 159         std::unique_ptr<MultiCompData>(
 160             new MultiCompData(best_index, std::move(results.top()->compData)));
 161     DPRINTF(CacheComp, "Best compressor: %d\n", best_index);
 162
 163     // Set decompression latency of the best compressor
 164     decomp_lat = results.top()->decompLat + decompExtraLatency;
 165
 166     // Update compressor ranking stats
 167     for (int rank = 0; rank < compressors.size(); rank++) {
 168         multiStats.ranks[results.top()->index][rank]++;
 169         results.pop();
 170     }
 171
 172     // Set compression latency (compression latency of the slowest compressor
 173     // and 1 cycle to pack)
 174     comp_lat = Cycles(max_comp_lat + compExtraLatency);
 175
 176     return multi_comp_data;
 177 }
 178
 179 void
 180 Multi::decompress(const CompressionData* comp_data,
 181     uint64_t* cache_line)
 182 {
 183     const MultiCompData* casted_comp_data =
 184         static_cast<const MultiCompData*>(comp_data);
 185     compressors[casted_comp_data->getIndex()]->decompress(
 186         casted_comp_data->compData.get(), cache_line);
 187 }
 188
 189 Multi::MultiStats::MultiStats(BaseStats& base_group, Multi& _compressor)
 190   : Stats::Group(&base_group), compressor(_compressor),
 191     ADD_STAT(ranks, UNIT_COUNT,
 192              "Number of times each compressor had the nth best compression")
 193 {
 194 }
 195
 196 void
 197 Multi::MultiStats::regStats()
 198 {
 199     Stats::Group::regStats();
 200
 201     const std::size_t num_compressors = compressor.compressors.size();
 202     ranks.init(num_compressors, num_compressors);
 203     for (unsigned compressor = 0; compressor < num_compressors; compressor++) {
 204         ranks.subname(compressor, std::to_string(compressor));
 205         ranks.subdesc(compressor, "Number of times compressor " +
 206             std::to_string(compressor) + " had the nth best compression.");
 207         for (unsigned rank = 0; rank < num_compressors; rank++) {
 208             ranks.ysubname(rank, std::to_string(rank));
 209         }
 210     }
 211 }
 212
 213 } // namespace Compressor