2 * Copyright (c) 2018-2019 Inria
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 * Authors: Daniel Carvalho
32 * Definition of a dictionary based cache compressor. Each entry is compared
33 * against a dictionary to search for matches.
35 * The dictionary is composed of 32-bit entries, and the comparison is done
38 * The patterns are implemented as individual classes that have a checking
39 * function isPattern(), to determine if the data fits the pattern, and a
40 * decompress() function, which decompresses the contents of a pattern.
41 * Every new pattern must inherit from the Pattern class and be added to the
45 #ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
46 #define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
55 #include "base/types.hh"
56 #include "mem/cache/compressors/base.hh"
58 struct BaseDictionaryCompressorParams;
60 class BaseDictionaryCompressor : public BaseCacheCompressor
63 /** Dictionary size. */
64 const std::size_t dictionarySize;
66 /** Number of valid entries in the dictionary. */
67 std::size_t numEntries;
70 * @defgroup CompressionStats Compression specific statistics.
74 /** Number of data entries that were compressed to each pattern. */
75 Stats::Vector patternStats;
82 * Trick function to get the number of patterns.
84 * @return The number of defined patterns.
86 virtual uint64_t getNumPatterns() const = 0;
89 * Get meta-name assigned to the given pattern.
91 * @param number The number of the pattern.
92 * @return The meta-name of the pattern.
94 virtual std::string getName(int number) const = 0;
97 typedef BaseDictionaryCompressorParams Params;
98 BaseDictionaryCompressor(const Params *p);
99 ~BaseDictionaryCompressor() = default;
101 void regStats() override;
105 * A template version of the dictionary compressor that allows to choose the
108 * @tparam The type of a dictionary entry (e.g., uint16_t, uint32_t, etc).
111 class DictionaryCompressor : public BaseDictionaryCompressor
115 * Compression data for the dictionary compressor. It consists of a vector
120 // Forward declaration of a pattern
122 class UncompressedPattern;
124 /** Convenience typedef for a dictionary entry. */
125 typedef std::array<uint8_t, sizeof(T)> DictionaryEntry;
128 * Create a factory to determine if input matches a pattern. The if else
129 * chains are constructed by recursion. The patterns should be explored
130 * sorted by size for correct behaviour.
132 template <class Head, class... Tail>
135 static std::unique_ptr<Pattern> getPattern(
136 const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
137 const int match_location)
139 // If match this pattern, instantiate it. If a negative match
140 // location is used, the patterns that use the dictionary bytes
141 // must return false. This is used when there are no dictionary
143 if (Head::isPattern(bytes, dict_bytes, match_location)) {
144 return std::unique_ptr<Pattern>(
145 new Head(bytes, match_location));
146 // Otherwise, go for next pattern
148 return Factory<Tail...>::getPattern(bytes, dict_bytes,
155 * Specialization to end the recursion. This must be called when all
156 * other patterns failed, and there is no choice but to leave data
157 * uncompressed. As such, this pattern must inherit from the uncompressed
160 template <class Head>
163 static_assert(std::is_base_of<UncompressedPattern, Head>::value,
164 "The last pattern must always be derived from the uncompressed "
167 static std::unique_ptr<Pattern>
168 getPattern(const DictionaryEntry& bytes,
169 const DictionaryEntry& dict_bytes, const int match_location)
171 return std::unique_ptr<Pattern>(new Head(bytes, match_location));
175 /** The dictionary. */
176 std::vector<DictionaryEntry> dictionary;
179 * Since the factory cannot be instantiated here, classes that inherit
180 * from this base class have to implement the call to their factory's
183 virtual std::unique_ptr<Pattern>
184 getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
185 const int match_location) const = 0;
190 * @param data Data to be compressed.
191 * @return The pattern this data matches.
193 std::unique_ptr<Pattern> compressValue(const T data);
196 * Decompress a pattern into a value that fits in a dictionary entry.
198 * @param pattern The pattern to be decompressed.
199 * @return The decompressed word.
201 T decompressValue(const Pattern* pattern);
203 /** Clear all dictionary entries. */
204 void resetDictionary();
207 * Add an entry to the dictionary.
209 * @param data The new entry.
211 virtual void addToDictionary(const DictionaryEntry data) = 0;
216 * @param data The cache line to be compressed.
217 * @return Cache line after compression.
219 std::unique_ptr<BaseCacheCompressor::CompressionData> compress(
220 const uint64_t* data);
225 * @param comp_data Compressed cache line.
226 * @param data The cache line to be decompressed.
228 void decompress(const CompressionData* comp_data, uint64_t* data) override;
231 * Turn a value into a dictionary entry.
233 * @param value The value to turn.
234 * @return A dictionary entry containing the value.
236 static DictionaryEntry toDictionaryEntry(T value);
239 * Turn a dictionary entry into a value.
241 * @param The dictionary entry to turn.
242 * @return The value that the dictionary entry contained.
244 static T fromDictionaryEntry(const DictionaryEntry& entry);
247 typedef BaseDictionaryCompressorParams Params;
248 DictionaryCompressor(const Params *p);
249 ~DictionaryCompressor() = default;
253 * The compressed data is composed of multiple pattern entries. To add a new
254 * pattern one should inherit from this class and implement isPattern() and
255 * decompress(). Then the new pattern must be added to the PatternFactory
256 * declaration in crescent order of size (in the DictionaryCompressor class).
259 class DictionaryCompressor<T>::Pattern
262 /** Pattern enum number. */
263 const int patternNumber;
265 /** Code associated to the pattern. */
268 /** Length, in bits, of the code and match location. */
269 const uint8_t length;
271 /** Number of unmatched bytes. */
272 const uint8_t numUnmatchedBytes;
274 /** Index representing the the match location. */
275 const int matchLocation;
277 /** Wether the pattern allocates a dictionary entry or not. */
282 * Default constructor.
284 * @param number Pattern number.
285 * @param code Code associated to this pattern.
286 * @param metadata_length Length, in bits, of the code and match location.
287 * @param num_unmatched_bytes Number of unmatched bytes.
288 * @param match_location Index of the match location.
290 Pattern(const int number, const uint64_t code,
291 const uint64_t metadata_length, const uint64_t num_unmatched_bytes,
292 const int match_location, const bool allocate = true)
293 : patternNumber(number), code(code), length(metadata_length),
294 numUnmatchedBytes(num_unmatched_bytes),
295 matchLocation(match_location), allocate(allocate)
299 /** Default destructor. */
300 virtual ~Pattern() = default;
303 * Get enum number associated to this pattern.
305 * @return The pattern enum number.
307 int getPatternNumber() const { return patternNumber; };
310 * Get code of this pattern.
314 uint8_t getCode() const { return code; }
317 * Get the index of the dictionary match location.
319 * @return The index of the match location.
321 uint8_t getMatchLocation() const { return matchLocation; }
324 * Get size, in bits, of the pattern (excluding prefix). Corresponds to
325 * unmatched_data_size + code_length.
332 return numUnmatchedBytes*CHAR_BIT + length;
336 * Determine if pattern allocates a dictionary entry.
338 * @return True if should allocate a dictionary entry.
340 bool shouldAllocate() const { return allocate; }
343 * Extract pattern's information to a string.
345 * @return A string containing the relevant pattern metadata.
350 return csprintf("pattern %s (encoding %x, size %u bits)",
351 getPatternNumber(), getCode(), getSizeBits());
355 * Decompress the pattern. Each pattern has its own way of interpreting
358 * @param dict_bytes The bytes in the corresponding matching entry.
359 * @return The decompressed pattern.
361 virtual DictionaryEntry decompress(
362 const DictionaryEntry dict_bytes) const = 0;
366 class DictionaryCompressor<T>::CompData : public CompressionData
369 /** The patterns matched in the original line. */
370 std::vector<std::unique_ptr<Pattern>> entries;
373 ~CompData() = default;
376 * Add a pattern entry to the list of patterns.
378 * @param entry The new pattern entry.
380 virtual void addEntry(std::unique_ptr<Pattern>);
384 * A pattern containing the original uncompressed data. This should be the
385 * worst case of every pattern factory, where if all other patterns fail,
386 * an instance of this pattern is created.
389 class DictionaryCompressor<T>::UncompressedPattern
390 : public DictionaryCompressor<T>::Pattern
393 /** A copy of the original data. */
394 const DictionaryEntry data;
397 UncompressedPattern(const int number,
399 const uint64_t metadata_length,
400 const int match_location,
401 const DictionaryEntry bytes)
402 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
403 sizeof(T), match_location, true),
409 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
410 const int match_location)
412 // An entry can always be uncompressed
417 decompress(const DictionaryEntry dict_bytes) const override
423 #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__