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