From 93b4845ed20d9d36c4564429e998f1184a47a8e3 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Fri, 12 Jul 2019 11:40:16 +0200 Subject: [PATCH] mem-cache: Implement FPC-D cache compression Implementation of Frequent Pattern Compression with limited Dictionary support (FPC-D) cache compressor, as described in "Opportunistic Compression for Direct-Mapped DRAM Caches", by Alameldeen et al. Change-Id: I26cc1646f95400b6a006f89754f6b2952f5b4aeb Signed-off-by: Daniel R. Carvalho Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/21154 Tested-by: kokoro Reviewed-by: Bobby R. Bruce Maintainer: Bobby R. Bruce --- src/mem/cache/compressors/Compressors.py | 7 + src/mem/cache/compressors/SConscript | 1 + .../compressors/dictionary_compressor.hh | 36 ++ src/mem/cache/compressors/fpcd.cc | 80 +++++ src/mem/cache/compressors/fpcd.hh | 323 ++++++++++++++++++ 5 files changed, 447 insertions(+) create mode 100644 src/mem/cache/compressors/fpcd.cc create mode 100644 src/mem/cache/compressors/fpcd.hh diff --git a/src/mem/cache/compressors/Compressors.py b/src/mem/cache/compressors/Compressors.py index 4ed72190c..4db6d4316 100644 --- a/src/mem/cache/compressors/Compressors.py +++ b/src/mem/cache/compressors/Compressors.py @@ -61,3 +61,10 @@ class CPack(BaseDictionaryCompressor): type = 'CPack' cxx_class = 'CPack' cxx_header = "mem/cache/compressors/cpack.hh" + +class FPCD(BaseDictionaryCompressor): + type = 'FPCD' + cxx_class = 'FPCD' + cxx_header = "mem/cache/compressors/fpcd.hh" + + dictionary_size = 2 diff --git a/src/mem/cache/compressors/SConscript b/src/mem/cache/compressors/SConscript index 052dbe04f..4df20d2a3 100644 --- a/src/mem/cache/compressors/SConscript +++ b/src/mem/cache/compressors/SConscript @@ -36,3 +36,4 @@ Source('base.cc') Source('base_dictionary_compressor.cc') Source('bdi.cc') Source('cpack.cc') +Source('fpcd.cc') diff --git a/src/mem/cache/compressors/dictionary_compressor.hh b/src/mem/cache/compressors/dictionary_compressor.hh index cf44a321d..8a7df4dc6 100644 --- a/src/mem/cache/compressors/dictionary_compressor.hh +++ b/src/mem/cache/compressors/dictionary_compressor.hh @@ -127,6 +127,8 @@ class DictionaryCompressor : public BaseDictionaryCompressor class MaskedPattern; template class MaskedValuePattern; + template + class LocatedMaskedPattern; template class RepeatedValuePattern; @@ -540,6 +542,40 @@ class DictionaryCompressor::MaskedValuePattern } }; +/** + * A pattern that narrows the MaskedPattern by allowing a only single possible + * dictionary entry to be matched against. + * + * @tparam mask A mask containing the bits that must match. + * @tparam location The index of the single entry allowed to match. + */ +template +template +class DictionaryCompressor::LocatedMaskedPattern + : public MaskedPattern +{ + public: + LocatedMaskedPattern(const int number, + const uint64_t code, + const uint64_t metadata_length, + const int match_location, + const DictionaryEntry bytes) + : MaskedPattern(number, code, metadata_length, match_location, + bytes) + { + } + + static bool + isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes, + const int match_location) + { + // Besides doing the regular masked pattern matching, the match + // location must match perfectly with this instance's + return (match_location == location) && + MaskedPattern::isPattern(bytes, dict_bytes, match_location); + } +}; + /** * A pattern that checks if dictionary entry sized values are solely composed * of multiple copies of a single value. diff --git a/src/mem/cache/compressors/fpcd.cc b/src/mem/cache/compressors/fpcd.cc new file mode 100644 index 000000000..68143397b --- /dev/null +++ b/src/mem/cache/compressors/fpcd.cc @@ -0,0 +1,80 @@ +/* + * 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 FPC-D cache compressor. + */ + +#include "mem/cache/compressors/fpcd.hh" + +#include "mem/cache/compressors/dictionary_compressor_impl.hh" +#include "params/FPCD.hh" + +FPCD::FPCD(const Params *p) + : DictionaryCompressor(p) +{ +} + +void +FPCD::addToDictionary(DictionaryEntry data) +{ + // The dictionary behaves as a table with FIFO as replacement policy + if (numEntries == 2) { + dictionary[penultimateIndex] = dictionary[previousIndex]; + dictionary[previousIndex] = data; + } else { + dictionary[numEntries++] = data; + } +} + +std::unique_ptr +FPCD::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) +{ + std::unique_ptr comp_data = + DictionaryCompressor::compress(data); + + // Set compression latency (Accounts for zero checks, ones check, match + // previous check, match penultimate check, repeated values check, pattern + // selection, shifting, at a rate of 16B per cycle) + comp_lat = Cycles(blkSize/2); + + // Set decompression latency. The original claim of 2 cycles is likely + // too unrealistic + decomp_lat = Cycles(4); + + // Return compressed line + return comp_data; +} + +FPCD* +FPCDParams::create() +{ + return new FPCD(this); +} diff --git a/src/mem/cache/compressors/fpcd.hh b/src/mem/cache/compressors/fpcd.hh new file mode 100644 index 000000000..94fa61df5 --- /dev/null +++ b/src/mem/cache/compressors/fpcd.hh @@ -0,0 +1,323 @@ +/* + * 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 the Frequent Pattern Compression with limited Dictionary + * support (FPC-D) cache compressor, as described in "Opportunistic + * Compression for Direct-Mapped DRAM Caches", by Alameldeen et al. + * + * It is a pattern compressor that can only have 2 dictionary entries, and + * as such the pattern encodings are specialized to inform to which entry it + * refers. These entries are replaced in a FIFO manner. + */ + +#ifndef __MEM_CACHE_COMPRESSORS_FPCD_HH__ +#define __MEM_CACHE_COMPRESSORS_FPCD_HH__ + +#include +#include +#include +#include + +#include "base/types.hh" +#include "mem/cache/compressors/dictionary_compressor.hh" + +struct FPCDParams; + +class FPCD : public DictionaryCompressor +{ + private: + using DictionaryEntry = DictionaryCompressor::DictionaryEntry; + + /** Number of bits in a FPCD pattern prefix. */ + static constexpr int prefixSize = 4; + + /** Index of the previous dictionary entry. */ + static constexpr int previousIndex = 1; + + /** Index of the penultimate dictionary entry. */ + static constexpr int penultimateIndex = 0; + + // Declaration of all possible patterns, from lowest to highest sizes. + // Penultimate is prioritized over previous to reduce the ripple effect + // of propagating values during decompression + class PatternZZZZ; + class PatternFFFF; + class PatternMMMMPenultimate; + class PatternMMMMPrevious; + class PatternZZZX; + class PatternXZZZ; + class PatternRRRR; + class PatternMMMXPenultimate; + class PatternMMMXPrevious; + class PatternZZXX; + class PatternZXZX; + class PatternFFXX; + class PatternXXZZ; + class PatternMMXXPenultimate; + class PatternMMXXPrevious; + class PatternXXXX; + + /** + * 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, R is + * a repeated 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 { + ZZZZ, FFFF, MMMMPenultimate, MMMMPrevious, ZZZX, XZZZ, RRRR, + MMMXPenultimate, MMMXPrevious, ZZXX, ZXZX, FFXX, XXZZ, + MMXXPenultimate, MMXXPrevious, XXXX, NUM_PATTERNS + } PatternNumber; + + /** + * Convenience factory declaration. The templates must be organized by + * size, with the smallest first, and "no-match" last. + */ + using PatternFactory = + Factory; + + uint64_t getNumPatterns() const override { return NUM_PATTERNS; } + + std::string + getName(int number) const override + { + static std::map pattern_names = { + {ZZZZ, "ZZZZ"}, {FFFF, "FFFF"}, + {MMMMPenultimate, "MMMMPenultimate"}, + {MMMMPrevious, "MMMMPrevious"}, {ZZZX, "ZZZX"}, + {XZZZ, "XZZZ"}, {RRRR, "RRRR"}, + {MMMXPenultimate, "MMMXPenultimate"}, + {MMMXPrevious, "MMMXPrevious"}, + {ZZXX, "ZZXX"}, + {ZXZX, "ZXZX"}, {FFXX, "FFXX"}, {XXZZ, "XXZZ"}, + {MMXXPenultimate, "MMXXPenultimate"}, + {MMXXPrevious, "MMXXPrevious"}, {XXXX, "XXXX"} + }; + + return pattern_names[(PatternNumber)number]; + }; + + std::unique_ptr + getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes, + const int match_location) const override + { + return PatternFactory::getPattern(bytes, dict_bytes, match_location); + } + + void addToDictionary(DictionaryEntry data) override; + + std::unique_ptr compress( + const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override; + + public: + typedef FPCDParams Params; + FPCD(const Params *p); + ~FPCD() = default; +}; + +class FPCD::PatternZZZZ : public MaskedValuePattern<0, 0xFFFFFFFF> +{ + public: + PatternZZZZ(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0xFFFFFFFF>(ZZZZ, 0x0, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternFFFF : public MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF> +{ + public: + PatternFFFF(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0xFFFFFFFF, 0xFFFFFFFF>(FFFF, 0x1, + prefixSize, match_location, bytes, true) + { + } +}; + +class FPCD::PatternMMMMPrevious + : public LocatedMaskedPattern<0xFFFFFFFF, previousIndex> +{ + public: + PatternMMMMPrevious(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFFFFFF, previousIndex>(MMMMPrevious, + 0x2, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternMMMMPenultimate + : public LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex> +{ + public: + PatternMMMMPenultimate(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFFFFFF, penultimateIndex>( + MMMMPenultimate, 0x3, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternZZZX : public MaskedValuePattern<0, 0xFFFFFF00> +{ + public: + PatternZZZX(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0xFFFFFF00>(ZZZX, 0x4, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternXZZZ : public MaskedValuePattern<0, 0x00FFFFFF> +{ + public: + PatternXZZZ(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0x00FFFFFF>(XZZZ, 0x5, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternRRRR : public RepeatedValuePattern +{ + public: + PatternRRRR(const DictionaryEntry bytes, const int match_location) + : RepeatedValuePattern(RRRR, 0x6, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternMMMXPrevious + : public LocatedMaskedPattern<0xFFFFFF00, previousIndex> +{ + public: + PatternMMMXPrevious(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFFFF00, previousIndex>(MMMXPrevious, + 0x7, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternMMMXPenultimate + : public LocatedMaskedPattern<0xFFFFFF00, penultimateIndex> +{ + public: + PatternMMMXPenultimate(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFFFF00, penultimateIndex>( + MMMXPenultimate, 0x8, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternZZXX : public MaskedValuePattern<0, 0xFFFF0000> +{ + public: + PatternZZXX(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0xFFFF0000>(ZZXX, 0x9, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternZXZX : public MaskedValuePattern<0, 0xFF00FF00> +{ + public: + PatternZXZX(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0xFF00FF00>(ZXZX, 0xA, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternFFXX : public MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000> +{ + public: + PatternFFXX(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0xFFFFFFFF, 0xFFFF0000>(FFXX, 0xB, + prefixSize, match_location, bytes, true) + { + } +}; + +class FPCD::PatternXXZZ : public MaskedValuePattern<0, 0x0000FFFF> +{ + public: + PatternXXZZ(const DictionaryEntry bytes, const int match_location) + : MaskedValuePattern<0, 0x0000FFFF>(XXZZ, 0xC, prefixSize, + match_location, bytes, true) + { + } +}; + +class FPCD::PatternMMXXPrevious + : public LocatedMaskedPattern<0xFFFF0000, previousIndex> +{ + public: + PatternMMXXPrevious(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFF0000, previousIndex>(MMXXPrevious, + 0xD, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternMMXXPenultimate + : public LocatedMaskedPattern<0xFFFF0000, penultimateIndex> +{ + public: + PatternMMXXPenultimate(const DictionaryEntry bytes, + const int match_location) + : LocatedMaskedPattern<0xFFFF0000, penultimateIndex>( + MMXXPenultimate, 0xE, prefixSize, match_location, bytes) + { + } +}; + +class FPCD::PatternXXXX : public UncompressedPattern +{ + public: + PatternXXXX(const DictionaryEntry bytes, const int match_location) + : UncompressedPattern(XXXX, 0xF, prefixSize, match_location, + bytes) + { + } +}; + +#endif //__MEM_CACHE_COMPRESSORS_FPCD_HH__ -- 2.30.2