src/mem/cache/compressors/cpack.cc

   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  * Implementation of the CPack cache compressor.
  33  */
  34
  35 #include "mem/cache/compressors/cpack.hh"
  36
  37 #include <algorithm>
  38 #include <cstdint>
  39
  40 #include "debug/CacheComp.hh"
  41 #include "params/CPack.hh"
  42
  43 CPack::CompData::CompData(const std::size_t dictionary_size)
  44     : CompressionData()
  45 {
  46 }
  47
  48 CPack::CompData::~CompData()
  49 {
  50 }
  51
  52 CPack::CPack(const Params *p)
  53     : BaseCacheCompressor(p), dictionarySize(2*blkSize/8)
  54 {
  55     dictionary.resize(dictionarySize);
  56
  57     resetDictionary();
  58 }
  59
  60 void
  61 CPack::resetDictionary()
  62 {
  63     // Reset number of valid entries
  64     numEntries = 0;
  65
  66     // Set all entries as 0
  67     std::array<uint8_t, 4> zero_word = {0, 0, 0, 0};
  68     std::fill(dictionary.begin(), dictionary.end(), zero_word);
  69 }
  70
  71 std::unique_ptr<CPack::Pattern>
  72 CPack::compressWord(const uint32_t data)
  73 {
  74     // Split data in bytes
  75     const std::array<uint8_t, 4> bytes = {
  76         static_cast<uint8_t>(data & 0xFF),
  77         static_cast<uint8_t>((data >> 8) & 0xFF),
  78         static_cast<uint8_t>((data >> 16) & 0xFF),
  79         static_cast<uint8_t>((data >> 24) & 0xFF)
  80     };
  81
  82     // Start as a no-match pattern. A negative match location is used so that
  83     // patterns that depend on the dictionary entry don't match
  84     std::unique_ptr<Pattern> pattern =
  85         PatternFactory::getPattern(bytes, {0, 0, 0, 0}, -1);
  86
  87     // Search for word on dictionary
  88     for (std::size_t i = 0; i < numEntries; i++) {
  89         // Try matching input with possible patterns
  90         std::unique_ptr<Pattern> temp_pattern =
  91             PatternFactory::getPattern(bytes, dictionary[i], i);
  92
  93         // Check if found pattern is better than previous
  94         if (temp_pattern->getSizeBits() < pattern->getSizeBits()) {
  95             pattern = std::move(temp_pattern);
  96         }
  97     }
  98
  99     // Update stats
 100     patternStats[pattern->getPatternNumber()]++;
 101
 102     // Push into dictionary
 103     if ((numEntries < dictionarySize) && pattern->shouldAllocate()) {
 104         dictionary[numEntries++] = bytes;
 105     }
 106
 107     return pattern;
 108 }
 109
 110 std::unique_ptr<BaseCacheCompressor::CompressionData>
 111 CPack::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat)
 112 {
 113     std::unique_ptr<CompData> comp_data =
 114         std::unique_ptr<CompData>(new CompData(dictionarySize));
 115
 116     // Compression size
 117     std::size_t size = 0;
 118
 119     // Reset dictionary
 120     resetDictionary();
 121
 122     // Compress every word sequentially
 123     for (std::size_t i = 0; i < blkSize/8; i++) {
 124         const uint32_t first_word = ((data[i])&0xFFFFFFFF00000000) >> 32;
 125         const uint32_t second_word = (data[i])&0x00000000FFFFFFFF;
 126
 127         // Compress both words
 128         std::unique_ptr<Pattern> first_pattern = compressWord(first_word);
 129         std::unique_ptr<Pattern> second_pattern = compressWord(second_word);
 130
 131         // Update total line compression size
 132         size += first_pattern->getSizeBits() + second_pattern->getSizeBits();
 133
 134         // Print debug information
 135         DPRINTF(CacheComp, "Compressed %08x to %s\n", first_word,
 136                 first_pattern->print());
 137         DPRINTF(CacheComp, "Compressed %08x to %s\n", second_word,
 138                 second_pattern->print());
 139
 140         // Append to pattern list
 141         comp_data->entries.push_back(std::move(first_pattern));
 142         comp_data->entries.push_back(std::move(second_pattern));
 143     }
 144
 145     // Set final compression size
 146     comp_data->setSizeBits(size);
 147
 148     // Set compression latency (Accounts for pattern matching, length
 149     // generation, packaging and shifting)
 150     comp_lat = Cycles(blkSize/8+5);
 151
 152     // Set decompression latency (1 qword per cycle)
 153     decomp_lat = Cycles(blkSize/8);
 154
 155     // Return compressed line
 156     return std::move(comp_data);
 157 }
 158
 159 uint32_t
 160 CPack::decompressWord(const Pattern* pattern)
 161 {
 162     std::array<uint8_t, 4> data;
 163
 164     // Search for matching entry
 165     std::vector<std::array<uint8_t, 4>>::iterator entry_it =
 166         dictionary.begin();
 167     std::advance(entry_it, pattern->getMatchLocation());
 168
 169     // Decompress the match. If the decompressed value must be added to
 170     // the dictionary, do it
 171     if (pattern->decompress(*entry_it, data)) {
 172         dictionary[numEntries++] = data;
 173     }
 174
 175     // Return word
 176     return (((((data[3] << 8) | data[2]) << 8) | data[1]) << 8) | data[0];
 177 }
 178
 179 void
 180 CPack::decompress(const CompressionData* comp_data, uint64_t* data)
 181 {
 182     const CompData* cpack_comp_data = static_cast<const CompData*>(comp_data);
 183
 184     // Reset dictionary
 185     resetDictionary();
 186
 187     // Decompress every entry sequentially
 188     std::vector<uint32_t> decomp_words;
 189     for (const auto& entry : cpack_comp_data->entries) {
 190         const uint32_t word = decompressWord(&*entry);
 191         decomp_words.push_back(word);
 192
 193         // Print debug information
 194         DPRINTF(CacheComp, "Decompressed %s to %x\n", entry->print(), word);
 195     }
 196
 197     // Concatenate the decompressed words to generate the cache lines
 198     for (std::size_t i = 0; i < blkSize/8; i++) {
 199         data[i] = (static_cast<uint64_t>(decomp_words[2*i]) << 32) |
 200                         decomp_words[2*i+1];
 201     }
 202 }
 203
 204 void
 205 CPack::regStats()
 206 {
 207     BaseCacheCompressor::regStats();
 208
 209     // We store the frequency of each pattern
 210     patternStats
 211         .init(Pattern::getNumPatterns())
 212         .name(name() + ".pattern")
 213         .desc("Number of data entries that were compressed to this pattern.")
 214         ;
 215
 216     for (unsigned i = 0; i < Pattern::getNumPatterns(); ++i) {
 217         patternStats.subname(i, Pattern::getName(i));
 218         patternStats.subdesc(i, "Number of data entries that match pattern " +
 219                                 Pattern::getName(i));
 220     }
 221 }
 222
 223 CPack*
 224 CPackParams::create()
 225 {
 226     return new CPack(this);
 227 }