Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/21148 )
Change subject: mem-cache: Templatize DictionaryCompressor
......................................................................
mem-cache: Templatize DictionaryCompressor
Templatize DictionaryCompressor so that the dictionary entries' sizes
can be changed.
Change-Id: I3d89e3c692a721cefcd7e3c55d2ccdefa425f614
Signed-off-by: Daniel R. Carvalho <oda...@yahoo.com.br>
---
M src/mem/cache/compressors/Compressors.py
M src/mem/cache/compressors/SConscript
A src/mem/cache/compressors/base_dictionary_compressor.cc
M src/mem/cache/compressors/cpack.cc
M src/mem/cache/compressors/cpack.hh
D src/mem/cache/compressors/dictionary_compressor.cc
M src/mem/cache/compressors/dictionary_compressor.hh
A src/mem/cache/compressors/dictionary_compressor_impl.hh
8 files changed, 444 insertions(+), 353 deletions(-)
diff --git a/src/mem/cache/compressors/Compressors.py
b/src/mem/cache/compressors/Compressors.py
index 7a063fe..b5e6f24 100644
--- a/src/mem/cache/compressors/Compressors.py
+++ b/src/mem/cache/compressors/Compressors.py
@@ -39,6 +39,14 @@
size_threshold = Param.Unsigned(Parent.cache_line_size, "Size in bytes
at "
"which a block, even if compressible, is stored uncompressed")
+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'
@@ -48,15 +56,7 @@
"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 68cf7ef..052dbe0 100644
--- a/src/mem/cache/compressors/SConscript
+++ b/src/mem/cache/compressors/SConscript
@@ -33,6 +33,6 @@
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 0000000..e41d875
--- /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 9e0cc2d..5603b0b 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<uint32_t>(p)
{
}
void
-CPack::addToDictionary(std::array<uint8_t, 4> data)
+CPack::addToDictionary(DictionaryEntry data)
{
assert(numEntries < dictionarySize);
dictionary[numEntries++] = data;
@@ -52,7 +53,7 @@
CPack::compress(const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat)
{
std::unique_ptr<BaseCacheCompressor::CompressionData> comp_data =
- DictionaryCompressor::compress(data);
+ DictionaryCompressor<uint32_t>::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 bd258b3..75a091c 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 <array>
#include <cstdint>
#include <map>
#include <memory>
@@ -46,9 +45,11 @@
struct CPackParams;
-class CPack : public DictionaryCompressor
+class CPack : public DictionaryCompressor<uint32_t>
{
private:
+ using DictionaryEntry =
DictionaryCompressor<uint32_t>::DictionaryEntry;
+
// Forward declaration of all possible patterns
class PatternZZZZ;
class PatternXXXX;
@@ -88,14 +89,14 @@
};
std::unique_ptr<Pattern> getPattern(
- const std::array<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4> data) override;
+ void addToDictionary(DictionaryEntry data) override;
/**
* Apply compression.
@@ -126,19 +127,19 @@
class CPack::PatternZZZZ : public DictionaryCompressor::Pattern
{
public:
- PatternZZZZ(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> dict_bytes) const override
+ DictionaryEntry
+ decompress(const DictionaryEntry dict_bytes) const override
{
return {0, 0, 0, 0};
}
@@ -150,23 +151,23 @@
/**
* A copy of the word.
*/
- const std::array<uint8_t, 4> bytes;
+ const DictionaryEntry bytes;
public:
- PatternXXXX(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> dict_bytes) const override
+ DictionaryEntry
+ decompress(const DictionaryEntry dict_bytes) const override
{
return bytes;
}
@@ -175,18 +176,18 @@
class CPack::PatternMMMM : public DictionaryCompressor::Pattern
{
public:
- PatternMMMM(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> dict_bytes) const override
+ DictionaryEntry
+ decompress(const DictionaryEntry dict_bytes) const override
{
return dict_bytes;
}
@@ -202,13 +203,13 @@
const uint8_t byte1;
public:
- PatternMMXX(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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 @@
}
- std::array<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> 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 @@
const uint8_t byte;
public:
- PatternZZZX(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> dict_bytes) const override
+ DictionaryEntry
+ decompress(const DictionaryEntry dict_bytes) const override
{
return {byte, 0, 0, 0};
}
@@ -260,21 +261,21 @@
const uint8_t byte;
public:
- PatternMMMX(const std::array<uint8_t, 4> 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<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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<uint8_t, 4>
- decompress(const std::array<uint8_t, 4> 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 c53d14a..0000000
--- 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 <algorithm>
-
-#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<uint8_t, 4> zero_word = {0, 0, 0, 0};
- std::fill(dictionary.begin(), dictionary.end(), zero_word);
-}
-
-std::unique_ptr<DictionaryCompressor::Pattern>
-DictionaryCompressor::compressWord(const uint32_t data)
-{
- // Split data in bytes
- const std::array<uint8_t, 4> bytes = {
- static_cast<uint8_t>(data & 0xFF),
- static_cast<uint8_t>((data >> 8) & 0xFF),
- static_cast<uint8_t>((data >> 16) & 0xFF),
- static_cast<uint8_t>((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> 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<Pattern> 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<BaseCacheCompressor::CompressionData>
-DictionaryCompressor::compress(const uint64_t* data)
-{
- std::unique_ptr<CompData> comp_data =
- std::unique_ptr<CompData>(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<Pattern> first_pattern = compressWord(first_word);
- std::unique_ptr<Pattern> 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<std::array<uint8_t, 4>>::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<uint8_t, 4> 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<const
CompData*>(comp_data);
-
- // Reset dictionary
- resetDictionary();
-
- // Decompress every entry sequentially
- std::vector<uint32_t> 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<uint64_t>(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 87e69cc..7467d5a 100644
--- a/src/mem/cache/compressors/dictionary_compressor.hh
+++ b/src/mem/cache/compressors/dictionary_compressor.hh
@@ -55,63 +55,11 @@
#include "base/types.hh"
#include "mem/cache/compressors/base.hh"
-struct DictionaryCompressorParams;
+struct BaseDictionaryCompressorParams;
-class DictionaryCompressor : public BaseCacheCompressor
+class BaseDictionaryCompressor : public BaseCacheCompressor
{
protected:
- /**
- * Compression data for the dictionary compressor. It consists of a
vector
- * of patterns.
- */
- class CompData;
-
- // Forward declaration of a pattern
- class Pattern;
-
- /**
- * Create a factory to determine if input matches a pattern. The if
else
- * chains are constructed by recursion. The patterns should be explored
- * sorted by size for correct behaviour.
- */
- template <class Head, class... Tail>
- struct Factory
- {
- static std::unique_ptr<Pattern> getPattern(
- const std::array<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& 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
- // must return false. This is used when there are no dictionary
- // entries yet
- if (Head::isPattern(bytes, dict_bytes, match_location)) {
- return std::unique_ptr<Pattern>(
- new Head(bytes, match_location));
- // Otherwise, go for next pattern
- } else {
- return Factory<Tail...>::getPattern(bytes, dict_bytes,
- match_location);
- }
- }
- };
-
- /** Specialization to end the recursion. */
- template <class Head>
- struct Factory<Head>
- {
- static std::unique_ptr<Pattern> getPattern(
- const std::array<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& dict_bytes, const int
match_location)
- {
- // Instantiate last pattern. Should be the XXXX pattern.
- return std::unique_ptr<Pattern>(new Head(bytes,
match_location));
- }
- };
-
- /** The dictionary. */
- std::vector<std::array<uint8_t, 4>> dictionary;
-
/** Dictionary size. */
const std::size_t dictionarySize;
@@ -123,9 +71,7 @@
* @{
*/
- /**
- * Number of data entries that were compressed to each pattern.
- */
+ /** Number of data entries that were compressed to each pattern. */
Stats::Vector patternStats;
/**
@@ -147,14 +93,86 @@
*/
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 T>
+class DictionaryCompressor : public BaseDictionaryCompressor
+{
+ protected:
+ /**
+ * Compression data for the dictionary compressor. It consists of a
vector
+ * of patterns.
+ */
+ class CompData;
+
+ // Forward declaration of a pattern
+ class Pattern;
+
+ /** Convenience typedef for a dictionary entry. */
+ typedef std::array<uint8_t, sizeof(T)> DictionaryEntry;
+
+ /**
+ * Create a factory to determine if input matches a pattern. The if
else
+ * chains are constructed by recursion. The patterns should be explored
+ * sorted by size for correct behaviour.
+ */
+ template <class Head, class... Tail>
+ struct Factory
+ {
+ static std::unique_ptr<Pattern> getPattern(
+ 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
+ // must return false. This is used when there are no dictionary
+ // entries yet
+ if (Head::isPattern(bytes, dict_bytes, match_location)) {
+ return std::unique_ptr<Pattern>(
+ new Head(bytes, match_location));
+ // Otherwise, go for next pattern
+ } else {
+ return Factory<Tail...>::getPattern(bytes, dict_bytes,
+ match_location);
+ }
+ }
+ };
+
+ /** Specialization to end the recursion. */
+ template <class Head>
+ struct Factory<Head>
+ {
+ static std::unique_ptr<Pattern>
+ getPattern(const DictionaryEntry& bytes,
+ const DictionaryEntry& dict_bytes, const int match_location)
+ {
+ // Instantiate last pattern. Should be the XXXX pattern.
+ return std::unique_ptr<Pattern>(new Head(bytes,
match_location));
+ }
+ };
+
+ /** The dictionary. */
+ std::vector<DictionaryEntry> 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<Pattern> getPattern(
- const std::array<uint8_t, 4>& bytes,
- const std::array<uint8_t, 4>& dict_bytes,
+ virtual std::unique_ptr<Pattern>
+ getPattern(const DictionaryEntry& bytes, const DictionaryEntry&
dict_bytes,
const int match_location) const = 0;
/**
@@ -163,15 +181,15 @@
* @param data Data to be compressed.
* @return The pattern this data matches.
*/
- std::unique_ptr<Pattern> compressWord(const uint32_t data);
+ std::unique_ptr<Pattern> 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 @@
*
* @param data The new entry.
*/
- virtual void addToDictionary(std::array<uint8_t, 4> data) = 0;
+ virtual void addToDictionary(const DictionaryEntry data) = 0;
/**
* Apply compression.
@@ -200,18 +218,26 @@
*/
void decompress(const CompressionData* comp_data, uint64_t* data)
override;
+ /**
+ * 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);
+
+ /**
+ * 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);
+
public:
- /** Convenience typedef. */
- typedef DictionaryCompressorParams Params;
-
- /** Default constructor. */
+ typedef BaseDictionaryCompressorParams Params;
DictionaryCompressor(const Params *p);
-
- /** Default destructor. */
- ~DictionaryCompressor() {};
-
- /** Register local statistics. */
- void regStats() override;
+ ~DictionaryCompressor() = default;
};
/**
@@ -220,7 +246,8 @@
* 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 T>
+class DictionaryCompressor<T>::Pattern
{
protected:
/** Pattern enum number. */
@@ -322,25 +349,26 @@
* @param dict_bytes The bytes in the corresponding matching entry.
* @return The decompressed pattern.
*/
- virtual std::array<uint8_t, 4> decompress(
- const std::array<uint8_t, 4> dict_bytes) const = 0;
+ virtual DictionaryEntry decompress(
+ const DictionaryEntry dict_bytes) const = 0;
};
-class DictionaryCompressor::CompData : public CompressionData
+template <class T>
+class DictionaryCompressor<T>::CompData : public CompressionData
{
public:
/** The patterns matched in the original line. */
std::vector<std::unique_ptr<Pattern>> entries;
- /**
- * Default constructor.
- *
- * @param dictionary_size Number of entries in the dictionary.
- */
- CompData(const std::size_t dictionary_size);
+ CompData();
+ ~CompData() = default;
- /** Default destructor. */
- ~CompData();
+ /**
+ * Add a pattern entry to the list of patterns.
+ *
+ * @param entry The new pattern entry.
+ */
+ virtual void addEntry(std::unique_ptr<Pattern>);
};
#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 0000000..b0a4fed
--- /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 <algorithm>
+
+#include "debug/CacheComp.hh"
+#include "mem/cache/compressors/dictionary_compressor.hh"
+#include "params/BaseDictionaryCompressor.hh"
+
+template <class T>
+DictionaryCompressor<T>::CompData::CompData()
+ : CompressionData()
+{
+}
+
+template <class T>
+void
+DictionaryCompressor<T>::CompData::addEntry(std::unique_ptr<Pattern>
pattern)
+{
+ // Increase size
+ setSizeBits(getSizeBits() + pattern->getSizeBits());
+
+ // Push new entry to list
+ entries.push_back(std::move(pattern));
+}
+
+template <class T>
+DictionaryCompressor<T>::DictionaryCompressor(const Params *p)
+ : BaseDictionaryCompressor(p)
+{
+ dictionary.resize(dictionarySize);
+
+ resetDictionary();
+}
+
+template <class T>
+void
+DictionaryCompressor<T>::resetDictionary()
+{
+ // Reset number of valid entries
+ numEntries = 0;
+
+ // Set all entries as 0
+ std::fill(dictionary.begin(), dictionary.end(), toDictionaryEntry(0));
+}
+
+template <typename T>
+std::unique_ptr<typename DictionaryCompressor<T>::Pattern>
+DictionaryCompressor<T>::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> 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<Pattern> 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 <class T>
+std::unique_ptr<BaseCacheCompressor::CompressionData>
+DictionaryCompressor<T>::compress(const uint64_t* data)
+{
+ std::unique_ptr<CompData> comp_data =
+ std::unique_ptr<CompData>(new CompData());
+
+ // Reset dictionary
+ resetDictionary();
+
+ // Compress every value sequentially
+ const std::vector<T> values = createRebasedVector<T>(data, blkSize /
8);
+ for (const auto& value : values) {
+ std::unique_ptr<Pattern> 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 <class T>
+T
+DictionaryCompressor<T>::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 <class T>
+void
+DictionaryCompressor<T>::decompress(const CompressionData* comp_data,
+ uint64_t* data)
+{
+ const CompData* casted_comp_data = static_cast<const
CompData*>(comp_data);
+
+ // Reset dictionary
+ resetDictionary();
+
+ // Decompress every entry sequentially
+ std::vector<T> 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<uint64_t>(decomp_values[values_per_entry*i+j])
<<
+ (j*8*sizeof(T));
+ }
+ }
+}
+
+template <class T>
+typename DictionaryCompressor<T>::DictionaryEntry
+DictionaryCompressor<T>::toDictionaryEntry(T value)
+{
+ DictionaryEntry entry;
+ for (int i = 0; i < sizeof(T); i++) {
+ entry[i] = value & 0xFF;
+ value >>= 8;
+ }
+ return entry;
+}
+
+template <class T>
+T
+DictionaryCompressor<T>::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__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/21148
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I3d89e3c692a721cefcd7e3c55d2ccdefa425f614
Gerrit-Change-Number: 21148
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
gem5-dev@gem5.org
http://m5sim.org/mailman/listinfo/gem5-dev