From 7a8debf0fa391a5e34fd1f47a4d1ae7ad6e3028d Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Thu, 5 Sep 2019 17:39:38 +0200 Subject: mem-cache: Templatize DictionaryCompressor Templatize DictionaryCompressor so that the dictionary entries' sizes can be changed. Change-Id: I3d89e3c692a721cefcd7e3c55d2ccdefa425f614 Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/21148 Tested-by: kokoro Reviewed-by: Bobby R. Bruce Maintainer: Nikos Nikoleris --- src/mem/cache/compressors/Compressors.py | 18 +- src/mem/cache/compressors/SConscript | 2 +- .../compressors/base_dictionary_compressor.cc | 61 ++++++ src/mem/cache/compressors/cpack.cc | 7 +- src/mem/cache/compressors/cpack.hh | 85 +++++---- src/mem/cache/compressors/dictionary_compressor.cc | 212 --------------------- src/mem/cache/compressors/dictionary_compressor.hh | 168 +++++++++------- .../compressors/dictionary_compressor_impl.hh | 212 +++++++++++++++++++++ 8 files changed, 428 insertions(+), 337 deletions(-) create mode 100644 src/mem/cache/compressors/base_dictionary_compressor.cc delete mode 100644 src/mem/cache/compressors/dictionary_compressor.cc create mode 100644 src/mem/cache/compressors/dictionary_compressor_impl.hh (limited to 'src/mem/cache/compressors') diff --git a/src/mem/cache/compressors/Compressors.py b/src/mem/cache/compressors/Compressors.py index b6315ad8d..4ed72190c 100644 --- a/src/mem/cache/compressors/Compressors.py +++ b/src/mem/cache/compressors/Compressors.py @@ -40,6 +40,14 @@ class BaseCacheCompressor(SimObject): "in bytes, in which a block must be compressed to. Otherwise it is " "stored in its uncompressed state") +class BaseDictionaryCompressor(BaseCacheCompressor): + type = 'BaseDictionaryCompressor' + abstract = True + cxx_header = "mem/cache/compressors/dictionary_compressor.hh" + + dictionary_size = Param.Int(Parent.cache_line_size, + "Number of dictionary entries") + class BDI(BaseCacheCompressor): type = 'BDI' cxx_class = 'BDI' @@ -49,15 +57,7 @@ class BDI(BaseCacheCompressor): "combinations of base and delta for the compressors. False if using" \ "only the lowest possible delta size for each base size."); -class DictionaryCompressor(BaseCacheCompressor): - type = 'DictionaryCompressor' - abstract = True - cxx_header = "mem/cache/compressors/dictionary_compressor.hh" - - dictionary_size = Param.Int(Parent.cache_line_size, - "Number of dictionary entries") - -class CPack(DictionaryCompressor): +class CPack(BaseDictionaryCompressor): type = 'CPack' cxx_class = 'CPack' cxx_header = "mem/cache/compressors/cpack.hh" diff --git a/src/mem/cache/compressors/SConscript b/src/mem/cache/compressors/SConscript index 68cf7ef10..052dbe04f 100644 --- a/src/mem/cache/compressors/SConscript +++ b/src/mem/cache/compressors/SConscript @@ -33,6 +33,6 @@ Import('*') SimObject('Compressors.py') Source('base.cc') +Source('base_dictionary_compressor.cc') Source('bdi.cc') Source('cpack.cc') -Source('dictionary_compressor.cc') diff --git a/src/mem/cache/compressors/base_dictionary_compressor.cc b/src/mem/cache/compressors/base_dictionary_compressor.cc new file mode 100644 index 000000000..e41d87599 --- /dev/null +++ b/src/mem/cache/compressors/base_dictionary_compressor.cc @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2018-2019 Inria + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Daniel Carvalho + */ + +/** @file + * Implementation of a base sim object for the templated dictionary-based + * cache compressor. + */ + +#include "mem/cache/compressors/dictionary_compressor.hh" +#include "params/BaseDictionaryCompressor.hh" + +BaseDictionaryCompressor::BaseDictionaryCompressor(const Params *p) + : BaseCacheCompressor(p), dictionarySize(p->dictionary_size), numEntries(0) +{ +} + +void +BaseDictionaryCompressor::regStats() +{ + BaseCacheCompressor::regStats(); + + // We store the frequency of each pattern + patternStats + .init(getNumPatterns()) + .name(name() + ".pattern") + .desc("Number of data entries that were compressed to this pattern.") + ; + + for (unsigned i = 0; i < getNumPatterns(); ++i) { + patternStats.subname(i, getName(i)); + patternStats.subdesc(i, "Number of data entries that match pattern " + + getName(i)); + } +} diff --git a/src/mem/cache/compressors/cpack.cc b/src/mem/cache/compressors/cpack.cc index 9e0cc2d42..5603b0bf6 100644 --- a/src/mem/cache/compressors/cpack.cc +++ b/src/mem/cache/compressors/cpack.cc @@ -34,15 +34,16 @@ #include "mem/cache/compressors/cpack.hh" +#include "mem/cache/compressors/dictionary_compressor_impl.hh" #include "params/CPack.hh" CPack::CPack(const Params *p) - : DictionaryCompressor(p) + : DictionaryCompressor(p) { } void -CPack::addToDictionary(std::array data) +CPack::addToDictionary(DictionaryEntry data) { assert(numEntries < dictionarySize); dictionary[numEntries++] = data; @@ -52,7 +53,7 @@ std::unique_ptr CPack::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) { std::unique_ptr comp_data = - DictionaryCompressor::compress(data); + DictionaryCompressor::compress(data); // Set compression latency (Accounts for pattern matching, length // generation, packaging and shifting) diff --git a/src/mem/cache/compressors/cpack.hh b/src/mem/cache/compressors/cpack.hh index bd258b372..75a091c27 100644 --- a/src/mem/cache/compressors/cpack.hh +++ b/src/mem/cache/compressors/cpack.hh @@ -36,7 +36,6 @@ #ifndef __MEM_CACHE_COMPRESSORS_CPACK_HH__ #define __MEM_CACHE_COMPRESSORS_CPACK_HH__ -#include #include #include #include @@ -46,9 +45,11 @@ struct CPackParams; -class CPack : public DictionaryCompressor +class CPack : public DictionaryCompressor { private: + using DictionaryEntry = DictionaryCompressor::DictionaryEntry; + // Forward declaration of all possible patterns class PatternZZZZ; class PatternXXXX; @@ -88,14 +89,14 @@ class CPack : public DictionaryCompressor }; std::unique_ptr getPattern( - const std::array& bytes, - const std::array& dict_bytes, + const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, const int match_location) const override { return PatternFactory::getPattern(bytes, dict_bytes, match_location); } - void addToDictionary(std::array data) override; + void addToDictionary(DictionaryEntry data) override; /** * Apply compression. @@ -126,19 +127,19 @@ class CPack : public DictionaryCompressor class CPack::PatternZZZZ : public DictionaryCompressor::Pattern { public: - PatternZZZZ(const std::array bytes, const int match_location) + PatternZZZZ(const DictionaryEntry bytes, const int match_location) : Pattern(ZZZZ, 0x0, 2, 0, 0, false) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) && (bytes[0] == 0); } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return {0, 0, 0, 0}; } @@ -150,23 +151,23 @@ class CPack::PatternXXXX : public DictionaryCompressor::Pattern /** * A copy of the word. */ - const std::array bytes; + const DictionaryEntry bytes; public: - PatternXXXX(const std::array bytes, const int match_location) + PatternXXXX(const DictionaryEntry bytes, const int match_location) : Pattern(XXXX, 0x1, 2, 4, 0, true), bytes(bytes) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { // It can always be an unmatch, as it is set to this class when other // patterns fail return true; } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return bytes; } @@ -175,18 +176,18 @@ class CPack::PatternXXXX : public DictionaryCompressor::Pattern class CPack::PatternMMMM : public DictionaryCompressor::Pattern { public: - PatternMMMM(const std::array bytes, const int match_location) + PatternMMMM(const DictionaryEntry bytes, const int match_location) : Pattern(MMMM, 0x2, 6, 0, match_location, true) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { return (bytes == dict_bytes) && (match_location >= 0); } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return dict_bytes; } @@ -202,13 +203,13 @@ class CPack::PatternMMXX : public DictionaryCompressor::Pattern const uint8_t byte1; public: - PatternMMXX(const std::array bytes, const int match_location) + PatternMMXX(const DictionaryEntry bytes, const int match_location) : Pattern(MMXX, 0xC, 8, 2, match_location, true), byte0(bytes[0]), byte1(bytes[1]) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { // Notice we don't compare bytes[0], as otherwise we'd be unnecessarily // discarding MMXM. If that pattern is added this should be modified @@ -217,8 +218,8 @@ class CPack::PatternMMXX : public DictionaryCompressor::Pattern } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return {byte0, byte1, dict_bytes[2], dict_bytes[3]}; } @@ -233,19 +234,19 @@ class CPack::PatternZZZX : public DictionaryCompressor::Pattern const uint8_t byte; public: - PatternZZZX(const std::array bytes, const int match_location) + PatternZZZX(const DictionaryEntry bytes, const int match_location) : Pattern(ZZZX, 0xD, 4, 1, 0, false), byte(bytes[0]) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) && (bytes[0] != 0); } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return {byte, 0, 0, 0}; } @@ -260,21 +261,21 @@ class CPack::PatternMMMX : public DictionaryCompressor::Pattern const uint8_t byte; public: - PatternMMMX(const std::array bytes, const int match_location) + PatternMMMX(const DictionaryEntry bytes, const int match_location) : Pattern(MMMX, 0xE, 8, 1, match_location, true), byte(bytes[0]) {} - static bool isPattern(const std::array& bytes, - const std::array& dict_bytes, - const int match_location) + static bool isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) { return (bytes[3] == dict_bytes[3]) && (bytes[2] == dict_bytes[2]) && (bytes[1] == dict_bytes[1]) && (bytes[0] != dict_bytes[0]) && (match_location >= 0); } - std::array - decompress(const std::array dict_bytes) const override + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override { return {byte, dict_bytes[1], dict_bytes[2], dict_bytes[3]}; } diff --git a/src/mem/cache/compressors/dictionary_compressor.cc b/src/mem/cache/compressors/dictionary_compressor.cc deleted file mode 100644 index c53d14a9b..000000000 --- a/src/mem/cache/compressors/dictionary_compressor.cc +++ /dev/null @@ -1,212 +0,0 @@ -/* - * Copyright (c) 2018-2019 Inria - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Authors: Daniel Carvalho - */ - -/** @file - * Implementation of a dictionary based cache compressor. - */ - -#include "mem/cache/compressors/dictionary_compressor.hh" - -#include - -#include "debug/CacheComp.hh" -#include "params/DictionaryCompressor.hh" - -DictionaryCompressor::CompData::CompData(const std::size_t dictionary_size) - : CompressionData() -{ -} - -DictionaryCompressor::CompData::~CompData() -{ -} - -DictionaryCompressor::DictionaryCompressor(const Params *p) - : BaseCacheCompressor(p), dictionarySize(p->dictionary_size) -{ - dictionary.resize(dictionarySize); - - resetDictionary(); -} - -void -DictionaryCompressor::resetDictionary() -{ - // Reset number of valid entries - numEntries = 0; - - // Set all entries as 0 - std::array zero_word = {0, 0, 0, 0}; - std::fill(dictionary.begin(), dictionary.end(), zero_word); -} - -std::unique_ptr -DictionaryCompressor::compressWord(const uint32_t data) -{ - // Split data in bytes - const std::array bytes = { - static_cast(data & 0xFF), - static_cast((data >> 8) & 0xFF), - static_cast((data >> 16) & 0xFF), - static_cast((data >> 24) & 0xFF) - }; - - // Start as a no-match pattern. A negative match location is used so that - // patterns that depend on the dictionary entry don't match - std::unique_ptr pattern = getPattern(bytes, {0, 0, 0, 0}, -1); - - // Search for word on dictionary - for (std::size_t i = 0; i < numEntries; i++) { - // Try matching input with possible patterns - std::unique_ptr temp_pattern = - getPattern(bytes, dictionary[i], i); - - // Check if found pattern is better than previous - if (temp_pattern->getSizeBits() < pattern->getSizeBits()) { - pattern = std::move(temp_pattern); - } - } - - // Update stats - patternStats[pattern->getPatternNumber()]++; - - // Push into dictionary - if (pattern->shouldAllocate()) { - addToDictionary(bytes); - } - - return pattern; -} - -std::unique_ptr -DictionaryCompressor::compress(const uint64_t* data) -{ - std::unique_ptr comp_data = - std::unique_ptr(new CompData(dictionarySize)); - - // Compression size - std::size_t size = 0; - - // Reset dictionary - resetDictionary(); - - // Compress every word sequentially - for (std::size_t i = 0; i < blkSize/8; i++) { - const uint32_t first_word = ((data[i])&0xFFFFFFFF00000000) >> 32; - const uint32_t second_word = (data[i])&0x00000000FFFFFFFF; - - // Compress both words - std::unique_ptr first_pattern = compressWord(first_word); - std::unique_ptr second_pattern = compressWord(second_word); - - // Update total line compression size - size += first_pattern->getSizeBits() + second_pattern->getSizeBits(); - - // Print debug information - DPRINTF(CacheComp, "Compressed %08x to %s\n", first_word, - first_pattern->print()); - DPRINTF(CacheComp, "Compressed %08x to %s\n", second_word, - second_pattern->print()); - - // Append to pattern list - comp_data->entries.push_back(std::move(first_pattern)); - comp_data->entries.push_back(std::move(second_pattern)); - } - - // Set final compression size - comp_data->setSizeBits(size); - - // Return compressed line - return std::move(comp_data); -} - -uint32_t -DictionaryCompressor::decompressWord(const Pattern* pattern) -{ - // Search for matching entry - std::vector>::iterator entry_it = - dictionary.begin(); - std::advance(entry_it, pattern->getMatchLocation()); - - // Decompress the match. If the decompressed value must be added to - // the dictionary, do it - const std::array data = pattern->decompress(*entry_it); - if (pattern->shouldAllocate()) { - addToDictionary(data); - } - - // Return word - return (((((data[3] << 8) | data[2]) << 8) | data[1]) << 8) | data[0]; -} - -void -DictionaryCompressor::decompress(const CompressionData* comp_data, - uint64_t* data) -{ - const CompData* casted_comp_data = static_cast(comp_data); - - // Reset dictionary - resetDictionary(); - - // Decompress every entry sequentially - std::vector decomp_words; - for (const auto& entry : casted_comp_data->entries) { - const uint32_t word = decompressWord(&*entry); - decomp_words.push_back(word); - - // Print debug information - DPRINTF(CacheComp, "Decompressed %s to %x\n", entry->print(), word); - } - - // Concatenate the decompressed words to generate the cache lines - for (std::size_t i = 0; i < blkSize/8; i++) { - data[i] = (static_cast(decomp_words[2*i]) << 32) | - decomp_words[2*i+1]; - } -} - -void -DictionaryCompressor::regStats() -{ - BaseCacheCompressor::regStats(); - - // We store the frequency of each pattern - patternStats - .init(getNumPatterns()) - .name(name() + ".pattern") - .desc("Number of data entries that were compressed to this pattern.") - ; - - for (unsigned i = 0; i < getNumPatterns(); ++i) { - patternStats.subname(i, getName(i)); - patternStats.subdesc(i, "Number of data entries that match pattern " + - getName(i)); - } -} diff --git a/src/mem/cache/compressors/dictionary_compressor.hh b/src/mem/cache/compressors/dictionary_compressor.hh index 87e69ccc8..7467d5a17 100644 --- a/src/mem/cache/compressors/dictionary_compressor.hh +++ b/src/mem/cache/compressors/dictionary_compressor.hh @@ -55,9 +55,60 @@ #include "base/types.hh" #include "mem/cache/compressors/base.hh" -struct DictionaryCompressorParams; +struct BaseDictionaryCompressorParams; -class DictionaryCompressor : public BaseCacheCompressor +class BaseDictionaryCompressor : public BaseCacheCompressor +{ + protected: + /** Dictionary size. */ + const std::size_t dictionarySize; + + /** Number of valid entries in the dictionary. */ + std::size_t numEntries; + + /** + * @defgroup CompressionStats Compression specific statistics. + * @{ + */ + + /** Number of data entries that were compressed to each pattern. */ + Stats::Vector patternStats; + + /** + * @} + */ + + /** + * Trick function to get the number of patterns. + * + * @return The number of defined patterns. + */ + virtual uint64_t getNumPatterns() const = 0; + + /** + * Get meta-name assigned to the given pattern. + * + * @param number The number of the pattern. + * @return The meta-name of the pattern. + */ + virtual std::string getName(int number) const = 0; + + public: + typedef BaseDictionaryCompressorParams Params; + BaseDictionaryCompressor(const Params *p); + ~BaseDictionaryCompressor() = default; + + void regStats() override; +}; + +/** + * A template version of the dictionary compressor that allows to choose the + * dictionary size. + * + * @tparam The type of a dictionary entry (e.g., uint16_t, uint32_t, etc). + */ +template +class DictionaryCompressor : public BaseDictionaryCompressor { protected: /** @@ -69,6 +120,9 @@ class DictionaryCompressor : public BaseCacheCompressor // Forward declaration of a pattern class Pattern; + /** Convenience typedef for a dictionary entry. */ + typedef std::array DictionaryEntry; + /** * Create a factory to determine if input matches a pattern. The if else * chains are constructed by recursion. The patterns should be explored @@ -78,8 +132,8 @@ class DictionaryCompressor : public BaseCacheCompressor struct Factory { static std::unique_ptr getPattern( - const std::array& bytes, - const std::array& dict_bytes, const int match_location) + const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes, + const int match_location) { // If match this pattern, instantiate it. If a negative match // location is used, the patterns that use the dictionary bytes @@ -100,9 +154,9 @@ class DictionaryCompressor : public BaseCacheCompressor template struct Factory { - static std::unique_ptr getPattern( - const std::array& bytes, - const std::array& dict_bytes, const int match_location) + static std::unique_ptr + getPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, const int match_location) { // Instantiate last pattern. Should be the XXXX pattern. return std::unique_ptr(new Head(bytes, match_location)); @@ -110,51 +164,15 @@ class DictionaryCompressor : public BaseCacheCompressor }; /** The dictionary. */ - std::vector> dictionary; - - /** Dictionary size. */ - const std::size_t dictionarySize; - - /** Number of valid entries in the dictionary. */ - std::size_t numEntries; - - /** - * @defgroup CompressionStats Compression specific statistics. - * @{ - */ - - /** - * Number of data entries that were compressed to each pattern. - */ - Stats::Vector patternStats; - - /** - * @} - */ - - /** - * Trick function to get the number of patterns. - * - * @return The number of defined patterns. - */ - virtual uint64_t getNumPatterns() const = 0; - - /** - * Get meta-name assigned to the given pattern. - * - * @param number The number of the pattern. - * @return The meta-name of the pattern. - */ - virtual std::string getName(int number) const = 0; + std::vector dictionary; /** * Since the factory cannot be instantiated here, classes that inherit * from this base class have to implement the call to their factory's * getPattern. */ - virtual std::unique_ptr getPattern( - const std::array& bytes, - const std::array& dict_bytes, + virtual std::unique_ptr + getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes, const int match_location) const = 0; /** @@ -163,15 +181,15 @@ class DictionaryCompressor : public BaseCacheCompressor * @param data Data to be compressed. * @return The pattern this data matches. */ - std::unique_ptr compressWord(const uint32_t data); + std::unique_ptr compressValue(const T data); /** - * Decompress a word. + * Decompress a pattern into a value that fits in a dictionary entry. * * @param pattern The pattern to be decompressed. * @return The decompressed word. */ - uint32_t decompressWord(const Pattern* pattern); + T decompressValue(const Pattern* pattern); /** Clear all dictionary entries. */ void resetDictionary(); @@ -181,7 +199,7 @@ class DictionaryCompressor : public BaseCacheCompressor * * @param data The new entry. */ - virtual void addToDictionary(std::array data) = 0; + virtual void addToDictionary(const DictionaryEntry data) = 0; /** * Apply compression. @@ -200,18 +218,26 @@ class DictionaryCompressor : public BaseCacheCompressor */ void decompress(const CompressionData* comp_data, uint64_t* data) override; - public: - /** Convenience typedef. */ - typedef DictionaryCompressorParams Params; - - /** Default constructor. */ - DictionaryCompressor(const Params *p); + /** + * Turn a value into a dictionary entry. + * + * @param value The value to turn. + * @return A dictionary entry containing the value. + */ + static DictionaryEntry toDictionaryEntry(T value); - /** Default destructor. */ - ~DictionaryCompressor() {}; + /** + * Turn a dictionary entry into a value. + * + * @param The dictionary entry to turn. + * @return The value that the dictionary entry contained. + */ + static T fromDictionaryEntry(const DictionaryEntry& entry); - /** Register local statistics. */ - void regStats() override; + public: + typedef BaseDictionaryCompressorParams Params; + DictionaryCompressor(const Params *p); + ~DictionaryCompressor() = default; }; /** @@ -220,7 +246,8 @@ class DictionaryCompressor : public BaseCacheCompressor * decompress(). Then the new pattern must be added to the PatternFactory * declaration in crescent order of size (in the DictionaryCompressor class). */ -class DictionaryCompressor::Pattern +template +class DictionaryCompressor::Pattern { protected: /** Pattern enum number. */ @@ -322,25 +349,26 @@ class DictionaryCompressor::Pattern * @param dict_bytes The bytes in the corresponding matching entry. * @return The decompressed pattern. */ - virtual std::array decompress( - const std::array dict_bytes) const = 0; + virtual DictionaryEntry decompress( + const DictionaryEntry dict_bytes) const = 0; }; -class DictionaryCompressor::CompData : public CompressionData +template +class DictionaryCompressor::CompData : public CompressionData { public: /** The patterns matched in the original line. */ std::vector> entries; + CompData(); + ~CompData() = default; + /** - * Default constructor. + * Add a pattern entry to the list of patterns. * - * @param dictionary_size Number of entries in the dictionary. + * @param entry The new pattern entry. */ - CompData(const std::size_t dictionary_size); - - /** Default destructor. */ - ~CompData(); + virtual void addEntry(std::unique_ptr); }; #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__ diff --git a/src/mem/cache/compressors/dictionary_compressor_impl.hh b/src/mem/cache/compressors/dictionary_compressor_impl.hh new file mode 100644 index 000000000..66827d774 --- /dev/null +++ b/src/mem/cache/compressors/dictionary_compressor_impl.hh @@ -0,0 +1,212 @@ +/* + * Copyright (c) 2018-2019 Inria + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Daniel Carvalho + */ + +/** @file + * Implementation of a dictionary based cache compressor. + */ + +#ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__ +#define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__ + +#include + +#include "debug/CacheComp.hh" +#include "mem/cache/compressors/dictionary_compressor.hh" +#include "params/BaseDictionaryCompressor.hh" + +template +DictionaryCompressor::CompData::CompData() + : CompressionData() +{ +} + +template +void +DictionaryCompressor::CompData::addEntry(std::unique_ptr pattern) +{ + // Increase size + setSizeBits(getSizeBits() + pattern->getSizeBits()); + + // Push new entry to list + entries.push_back(std::move(pattern)); +} + +template +DictionaryCompressor::DictionaryCompressor(const Params *p) + : BaseDictionaryCompressor(p) +{ + dictionary.resize(dictionarySize); + + resetDictionary(); +} + +template +void +DictionaryCompressor::resetDictionary() +{ + // Reset number of valid entries + numEntries = 0; + + // Set all entries as 0 + std::fill(dictionary.begin(), dictionary.end(), toDictionaryEntry(0)); +} + +template +std::unique_ptr::Pattern> +DictionaryCompressor::compressValue(const T data) +{ + // Split data in bytes + const DictionaryEntry bytes = toDictionaryEntry(data); + + // Start as a no-match pattern. A negative match location is used so that + // patterns that depend on the dictionary entry don't match + std::unique_ptr pattern = + getPattern(bytes, toDictionaryEntry(0), -1); + + // Search for word on dictionary + for (std::size_t i = 0; i < numEntries; i++) { + // Try matching input with possible patterns + std::unique_ptr temp_pattern = + getPattern(bytes, dictionary[i], i); + + // Check if found pattern is better than previous + if (temp_pattern->getSizeBits() < pattern->getSizeBits()) { + pattern = std::move(temp_pattern); + } + } + + // Update stats + patternStats[pattern->getPatternNumber()]++; + + // Push into dictionary + if (pattern->shouldAllocate()) { + addToDictionary(bytes); + } + + return pattern; +} + +template +std::unique_ptr +DictionaryCompressor::compress(const uint64_t* data) +{ + std::unique_ptr comp_data = + std::unique_ptr(new CompData()); + + // Reset dictionary + resetDictionary(); + + // Compress every value sequentially + const std::vector values((T*)data, (T*)data + blkSize / sizeof(T)); + for (const auto& value : values) { + std::unique_ptr pattern = compressValue(value); + DPRINTF(CacheComp, "Compressed %016x to %s\n", value, + pattern->print()); + comp_data->addEntry(std::move(pattern)); + } + + // Return compressed line + return std::move(comp_data); +} + +template +T +DictionaryCompressor::decompressValue(const Pattern* pattern) +{ + // Search for matching entry + auto entry_it = dictionary.begin(); + std::advance(entry_it, pattern->getMatchLocation()); + + // Decompress the match. If the decompressed value must be added to + // the dictionary, do it + const DictionaryEntry data = pattern->decompress(*entry_it); + if (pattern->shouldAllocate()) { + addToDictionary(data); + } + + // Return value + return fromDictionaryEntry(data); +} + +template +void +DictionaryCompressor::decompress(const CompressionData* comp_data, + uint64_t* data) +{ + const CompData* casted_comp_data = static_cast(comp_data); + + // Reset dictionary + resetDictionary(); + + // Decompress every entry sequentially + std::vector decomp_values; + for (const auto& entry : casted_comp_data->entries) { + const T value = decompressValue(&*entry); + decomp_values.push_back(value); + DPRINTF(CacheComp, "Decompressed %s to %x\n", entry->print(), value); + } + + // Concatenate the decompressed values to generate the original data + for (std::size_t i = 0; i < blkSize/8; i++) { + data[i] = 0; + const std::size_t values_per_entry = sizeof(uint64_t)/sizeof(T); + for (int j = values_per_entry - 1; j >= 0; j--) { + data[i] |= + static_cast(decomp_values[values_per_entry*i+j]) << + (j*8*sizeof(T)); + } + } +} + +template +typename DictionaryCompressor::DictionaryEntry +DictionaryCompressor::toDictionaryEntry(T value) +{ + DictionaryEntry entry; + for (int i = 0; i < sizeof(T); i++) { + entry[i] = value & 0xFF; + value >>= 8; + } + return entry; +} + +template +T +DictionaryCompressor::fromDictionaryEntry(const DictionaryEntry& entry) +{ + T value = 0; + for (int i = sizeof(T) - 1; i >= 0; i--) { + value <<= 8; + value |= entry[i]; + } + return value; +} + +#endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__ -- cgit v1.2.3