diff options
Diffstat (limited to 'src/mem/cache/compressors/dictionary_compressor_impl.hh')
-rw-r--r-- | src/mem/cache/compressors/dictionary_compressor_impl.hh | 212 |
1 files changed, 212 insertions, 0 deletions
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 <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((T*)data, (T*)data + blkSize / sizeof(T)); + 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__ |