diff options
| -rw-r--r-- | src/mem/cache/compressors/Compressors.py | 30 | ||||
| -rw-r--r-- | src/mem/cache/compressors/SConscript | 1 | ||||
| -rw-r--r-- | src/mem/cache/compressors/base_delta.cc | 107 | ||||
| -rw-r--r-- | src/mem/cache/compressors/base_delta.hh | 206 | ||||
| -rw-r--r-- | src/mem/cache/compressors/base_delta_impl.hh | 103 | ||||
| -rw-r--r-- | src/mem/cache/compressors/dictionary_compressor.hh | 83 |
6 files changed, 529 insertions, 1 deletions
diff --git a/src/mem/cache/compressors/Compressors.py b/src/mem/cache/compressors/Compressors.py index 721b6a251..607491ad4 100644 --- a/src/mem/cache/compressors/Compressors.py +++ b/src/mem/cache/compressors/Compressors.py @@ -48,6 +48,36 @@ class BaseDictionaryCompressor(BaseCacheCompressor): dictionary_size = Param.Int(Parent.cache_line_size, "Number of dictionary entries") +class Base64Delta8(BaseDictionaryCompressor): + type = 'Base64Delta8' + cxx_class = 'Base64Delta8' + cxx_header = "mem/cache/compressors/base_delta.hh" + +class Base64Delta16(BaseDictionaryCompressor): + type = 'Base64Delta16' + cxx_class = 'Base64Delta16' + cxx_header = "mem/cache/compressors/base_delta.hh" + +class Base64Delta32(BaseDictionaryCompressor): + type = 'Base64Delta32' + cxx_class = 'Base64Delta32' + cxx_header = "mem/cache/compressors/base_delta.hh" + +class Base32Delta8(BaseDictionaryCompressor): + type = 'Base32Delta8' + cxx_class = 'Base32Delta8' + cxx_header = "mem/cache/compressors/base_delta.hh" + +class Base32Delta16(BaseDictionaryCompressor): + type = 'Base32Delta16' + cxx_class = 'Base32Delta16' + cxx_header = "mem/cache/compressors/base_delta.hh" + +class Base16Delta8(BaseDictionaryCompressor): + type = 'Base16Delta8' + cxx_class = 'Base16Delta8' + cxx_header = "mem/cache/compressors/base_delta.hh" + class BDI(BaseCacheCompressor): type = 'BDI' cxx_class = 'BDI' diff --git a/src/mem/cache/compressors/SConscript b/src/mem/cache/compressors/SConscript index 05c1edede..517ec522a 100644 --- a/src/mem/cache/compressors/SConscript +++ b/src/mem/cache/compressors/SConscript @@ -34,6 +34,7 @@ SimObject('Compressors.py') Source('base.cc') Source('base_dictionary_compressor.cc') +Source('base_delta.cc') Source('bdi.cc') Source('cpack.cc') Source('fpcd.cc') diff --git a/src/mem/cache/compressors/base_delta.cc b/src/mem/cache/compressors/base_delta.cc new file mode 100644 index 000000000..66349282f --- /dev/null +++ b/src/mem/cache/compressors/base_delta.cc @@ -0,0 +1,107 @@ +/* + * Copyright (c) 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 the specialized sub-compressors used by BDI. @see BDI + */ + +#include "mem/cache/compressors/base_delta_impl.hh" +#include "params/Base16Delta8.hh" +#include "params/Base32Delta16.hh" +#include "params/Base32Delta8.hh" +#include "params/Base64Delta16.hh" +#include "params/Base64Delta32.hh" +#include "params/Base64Delta8.hh" + +Base64Delta8::Base64Delta8(const Params *p) + : BaseDelta<uint64_t, 8>(p) +{ +} + +Base64Delta16::Base64Delta16(const Params *p) + : BaseDelta<uint64_t, 16>(p) +{ +} + +Base64Delta32::Base64Delta32(const Params *p) + : BaseDelta<uint64_t, 32>(p) +{ +} + +Base32Delta8::Base32Delta8(const Params *p) + : BaseDelta<uint32_t, 8>(p) +{ +} + +Base32Delta16::Base32Delta16(const Params *p) + : BaseDelta<uint32_t, 16>(p) +{ +} + +Base16Delta8::Base16Delta8(const Params *p) + : BaseDelta<uint16_t, 8>(p) +{ +} + +Base64Delta8* +Base64Delta8Params::create() +{ + return new Base64Delta8(this); +} + +Base64Delta16* +Base64Delta16Params::create() +{ + return new Base64Delta16(this); +} + +Base64Delta32* +Base64Delta32Params::create() +{ + return new Base64Delta32(this); +} + +Base32Delta8* +Base32Delta8Params::create() +{ + return new Base32Delta8(this); +} + +Base32Delta16* +Base32Delta16Params::create() +{ + return new Base32Delta16(this); +} + +Base16Delta8* +Base16Delta8Params::create() +{ + return new Base16Delta8(this); +} diff --git a/src/mem/cache/compressors/base_delta.hh b/src/mem/cache/compressors/base_delta.hh new file mode 100644 index 000000000..b20814441 --- /dev/null +++ b/src/mem/cache/compressors/base_delta.hh @@ -0,0 +1,206 @@ +/* + * Copyright (c) 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 + * Definition of a base delta immediate compressor. @see BDI + */ + +#ifndef __MEM_CACHE_COMPRESSORS_BASE_DELTA_HH__ +#define __MEM_CACHE_COMPRESSORS_BASE_DELTA_HH__ + +#include <array> +#include <cstdint> +#include <map> +#include <memory> + +#include "base/bitfield.hh" +#include "mem/cache/compressors/dictionary_compressor.hh" + +struct BaseDictionaryCompressorParams; +struct Base64Delta8Params; +struct Base64Delta16Params; +struct Base64Delta32Params; +struct Base32Delta8Params; +struct Base32Delta16Params; +struct Base16Delta8Params; + +/** + * Base class for all base-delta-immediate compressors. Although not proposed + * like this in the original paper, the sub-compressors of BDI are dictionary + * based with 2 possible patterns: no match, where a dictionary entry must be + * allocated, and masked delta match with a dictionary entry, where the delta + * must be stored instead. The maximum number of dictionary entries is 2, and + * one of them is reserved for a zero base if using immediate compression. + * + * @tparam BaseType Type of a base (dictionary) entry. + */ +template <class BaseType, std::size_t DeltaSizeBits> +class BaseDelta : public DictionaryCompressor<BaseType> +{ + protected: + static constexpr int DEFAULT_MAX_NUM_BASES = 2; + + using DictionaryEntry = + typename DictionaryCompressor<BaseType>::DictionaryEntry; + + // Forward declaration of all possible patterns + class PatternX; + class PatternM; + + /** + * The patterns proposed in the paper. Each letter represents a byte: + * Z is a null byte, M is a dictionary match, X is a new value. + * These are used as indexes to reference the pattern data. If a new + * pattern is added, it must be done before NUM_PATTERNS. + */ + typedef enum { + X, M, NUM_PATTERNS + } PatternNumber; + + uint64_t getNumPatterns() const override { return NUM_PATTERNS; } + + /** + * Convenience factory declaration. The templates must be organized by + * size, with the smallest first, and "no-match" last. + */ + using PatternFactory = typename DictionaryCompressor<BaseType>::template + Factory<PatternM, PatternX>; + + std::unique_ptr<typename DictionaryCompressor<BaseType>::Pattern> + getPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, + const int match_location) const override + { + return PatternFactory::getPattern(bytes, dict_bytes, match_location); + } + + std::string + getName(int number) const override + { + static std::map<int, std::string> pattern_names = { + {X, "X"}, {M, "M"} + }; + + return pattern_names[number]; + } + + void resetDictionary() override; + + void addToDictionary(DictionaryEntry data) override; + + std::unique_ptr<BaseCacheCompressor::CompressionData> + compress(const uint64_t* data, Cycles& comp_lat, + Cycles& decomp_lat) override; + + public: + typedef BaseDictionaryCompressorParams Params; + BaseDelta(const Params *p); + ~BaseDelta() = default; +}; + +template <class BaseType, std::size_t DeltaSizeBits> +class BaseDelta<BaseType, DeltaSizeBits>::PatternX + : public DictionaryCompressor<BaseType>::UncompressedPattern +{ + public: + // A delta entry containing the value 0 is added even if it is an entirely + // new base + PatternX(const DictionaryEntry bytes, const int match_location) + : DictionaryCompressor<BaseType>::UncompressedPattern(X, 0, + std::ceil(std::log2(DEFAULT_MAX_NUM_BASES)) + DeltaSizeBits, + match_location, bytes) + { + } +}; + +template <class BaseType, std::size_t DeltaSizeBits> +class BaseDelta<BaseType, DeltaSizeBits>::PatternM : public + DictionaryCompressor<BaseType>::template DeltaPattern<DeltaSizeBits> +{ + public: + // The number of bits reserved for the bitmask entry is proportional to + // the maximum number of bases + PatternM(const DictionaryEntry bytes, const int match_location) + : DictionaryCompressor<BaseType>::template DeltaPattern<DeltaSizeBits>( + M, 1, std::ceil(std::log2(DEFAULT_MAX_NUM_BASES)), match_location, + bytes) + { + } +}; + +class Base64Delta8 : public BaseDelta<uint64_t, 8> +{ + public: + typedef Base64Delta8Params Params; + Base64Delta8(const Params *p); + ~Base64Delta8() = default; +}; + +class Base64Delta16 : public BaseDelta<uint64_t, 16> +{ + public: + typedef Base64Delta16Params Params; + Base64Delta16(const Params *p); + ~Base64Delta16() = default; +}; + +class Base64Delta32 : public BaseDelta<uint64_t, 32> +{ + public: + typedef Base64Delta32Params Params; + Base64Delta32(const Params *p); + ~Base64Delta32() = default; +}; + +class Base32Delta8 : public BaseDelta<uint32_t, 8> +{ + public: + typedef Base32Delta8Params Params; + Base32Delta8(const Params *p); + ~Base32Delta8() = default; +}; + +class Base32Delta16 : public BaseDelta<uint32_t, 16> +{ + public: + typedef Base32Delta16Params Params; + Base32Delta16(const Params *p); + ~Base32Delta16() = default; +}; + +class Base16Delta8 : public BaseDelta<uint16_t, 8> +{ + public: + typedef Base16Delta8Params Params; + Base16Delta8(const Params *p); + ~Base16Delta8() = default; +}; + +#endif //__MEM_CACHE_COMPRESSORS_BASE_DELTA_HH__ diff --git a/src/mem/cache/compressors/base_delta_impl.hh b/src/mem/cache/compressors/base_delta_impl.hh new file mode 100644 index 000000000..7685a3d80 --- /dev/null +++ b/src/mem/cache/compressors/base_delta_impl.hh @@ -0,0 +1,103 @@ +/* + * Copyright (c) 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 delta immediate compressor. @see BDI + */ + +#ifndef __MEM_CACHE_COMPRESSORS_BASE_DELTA_IMPL_HH__ +#define __MEM_CACHE_COMPRESSORS_BASE_DELTA_IMPL_HH__ + +#include "debug/CacheComp.hh" +#include "mem/cache/compressors/base_delta.hh" +#include "mem/cache/compressors/dictionary_compressor_impl.hh" + +template <class BaseType, std::size_t DeltaSizeBits> +BaseDelta<BaseType, DeltaSizeBits>::BaseDelta(const Params *p) + : DictionaryCompressor<BaseType>(p) +{ +} + +template <class BaseType, std::size_t DeltaSizeBits> +void +BaseDelta<BaseType, DeltaSizeBits>::resetDictionary() +{ + DictionaryCompressor<BaseType>::resetDictionary(); + + // Add zero base for the immediate values + addToDictionary(DictionaryCompressor<BaseType>::toDictionaryEntry(0)); +} + +template <class BaseType, std::size_t DeltaSizeBits> +void +BaseDelta<BaseType, DeltaSizeBits>::addToDictionary(DictionaryEntry data) +{ + assert(DictionaryCompressor<BaseType>::numEntries < + DictionaryCompressor<BaseType>::dictionarySize); + DictionaryCompressor<BaseType>::dictionary[ + DictionaryCompressor<BaseType>::numEntries++] = data; +} + +template <class BaseType, std::size_t DeltaSizeBits> +std::unique_ptr<BaseCacheCompressor::CompressionData> +BaseDelta<BaseType, DeltaSizeBits>::compress(const uint64_t* data, + Cycles& comp_lat, Cycles& decomp_lat) +{ + std::unique_ptr<BaseCacheCompressor::CompressionData> comp_data = + DictionaryCompressor<BaseType>::compress(data); + + // If there are more bases than the maximum, the compressor failed. + // Otherwise, we have to take into account all bases that have not + // been used, considering that there is an implicit zero base that + // does not need to be added to the final size. + const int diff = DEFAULT_MAX_NUM_BASES - + DictionaryCompressor<BaseType>::numEntries; + if (diff < 0) { + comp_data->setSizeBits(DictionaryCompressor<BaseType>::blkSize * 8); + DPRINTF(CacheComp, "Base%dDelta%d compression failed\n", + 8 * sizeof(BaseType), DeltaSizeBits); + } else if (diff > 0) { + comp_data->setSizeBits(comp_data->getSizeBits() + + 8 * sizeof(BaseType) * diff); + } + + // Set compression latency (Assumes 1 cycle per entry and 1 cycle for + // packing) + comp_lat = Cycles(1 + (DictionaryCompressor<BaseType>::blkSize / + sizeof(BaseType))); + + // Set decompression latency + decomp_lat = Cycles(1); + + // Return compressed line + return comp_data; +} + +#endif //__MEM_CACHE_COMPRESSORS_BASE_DELTA_IMPL_HH__ diff --git a/src/mem/cache/compressors/dictionary_compressor.hh b/src/mem/cache/compressors/dictionary_compressor.hh index 8a7df4dc6..1615990b4 100644 --- a/src/mem/cache/compressors/dictionary_compressor.hh +++ b/src/mem/cache/compressors/dictionary_compressor.hh @@ -50,6 +50,7 @@ #include <map> #include <memory> #include <string> +#include <type_traits> #include <vector> #include "base/types.hh" @@ -131,6 +132,8 @@ class DictionaryCompressor : public BaseDictionaryCompressor class LocatedMaskedPattern; template <class RepT> class RepeatedValuePattern; + template <std::size_t DeltaSizeBits> + class DeltaPattern; /** * Create a factory to determine if input matches a pattern. The if else @@ -209,7 +212,7 @@ class DictionaryCompressor : public BaseDictionaryCompressor T decompressValue(const Pattern* pattern); /** Clear all dictionary entries. */ - void resetDictionary(); + virtual void resetDictionary(); /** * Add an entry to the dictionary. @@ -644,4 +647,82 @@ class DictionaryCompressor<T>::RepeatedValuePattern } }; +/** + * A pattern that checks whether the difference of the value and the dictionary + * entries' is below a certain threshold. If so, the pattern is successful, + * and only the delta bits need to be stored. + * + * For example, if the delta can only contain up to 4 bits, and the dictionary + * contains the entry 0xA231, the value 0xA232 would be compressible, and + * the delta 0x1 would be stored. The value 0xA249, on the other hand, would + * not be compressible, since its delta (0x18) needs 5 bits to be stored. + * + * @tparam DeltaSizeBits Size of a delta entry, in number of bits, which + * determines the threshold. Must always be smaller + * than the dictionary entry type's size. + */ +template <class T> +template <std::size_t DeltaSizeBits> +class DictionaryCompressor<T>::DeltaPattern + : public DictionaryCompressor<T>::Pattern +{ + private: + static_assert(DeltaSizeBits < (sizeof(T) * 8), + "Delta size must be smaller than base size"); + + /** + * The original value. In theory we should keep only the deltas, but + * the dictionary entry is not inserted in the dictionary before the + * call to the constructor, so the delta cannot be calculated then. + */ + const DictionaryEntry bytes; + + public: + DeltaPattern(const int number, + const uint64_t code, + const uint64_t metadata_length, + const int match_location, + const DictionaryEntry bytes) + : DictionaryCompressor<T>::Pattern(number, code, metadata_length, + DeltaSizeBits, match_location, false), + bytes(bytes) + { + } + + /** + * Compares a given value against a base to calculate their delta, and + * then determines whether it fits a limited sized container. + * + * @param bytes Value to be compared against base. + * @param base_bytes Base value. + * @return Whether the value fits in the container. + */ + static bool + isValidDelta(const DictionaryEntry& bytes, + const DictionaryEntry& base_bytes) + { + const typename std::make_signed<T>::type limit = DeltaSizeBits ? + mask(DeltaSizeBits - 1) : 0; + const T value = + DictionaryCompressor<T>::fromDictionaryEntry(bytes); + const T base = + DictionaryCompressor<T>::fromDictionaryEntry(base_bytes); + const typename std::make_signed<T>::type delta = value - base; + return (delta >= -limit) && (delta <= limit); + } + + static bool + isPattern(const DictionaryEntry& bytes, + const DictionaryEntry& dict_bytes, const int match_location) + { + return (match_location >= 0) && isValidDelta(bytes, dict_bytes); + } + + DictionaryEntry + decompress(const DictionaryEntry dict_bytes) const override + { + return bytes; + } +}; + #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__ |