From 77a49860f98a86f467bae242e6c52f6b7150631c Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Wed, 13 Jun 2018 16:39:38 +0200 Subject: mem-cache: Create BDI Compressor Implement Base-Delta-Immediate compression, as described in 'Base-Delta-Immediate Compression: Practical Data Compression for On-Chip Caches' Change-Id: I7980c340ab53a086b748f4b2108de4adc775fac8 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/11412 Tested-by: kokoro Reviewed-by: Nikos Nikoleris Maintainer: Nikos Nikoleris --- src/mem/cache/compressors/bdi.hh | 428 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 428 insertions(+) create mode 100644 src/mem/cache/compressors/bdi.hh (limited to 'src/mem/cache/compressors/bdi.hh') diff --git a/src/mem/cache/compressors/bdi.hh b/src/mem/cache/compressors/bdi.hh new file mode 100644 index 000000000..9a145fa81 --- /dev/null +++ b/src/mem/cache/compressors/bdi.hh @@ -0,0 +1,428 @@ +/* + * Copyright (c) 2018 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 "Base-Delta-Immediate Compression: Practical Data Compression + * for On-Chip Caches". + */ + +#ifndef __MEM_CACHE_COMPRESSORS_BDI_HH__ +#define __MEM_CACHE_COMPRESSORS_BDI_HH__ + +#include +#include +#include + +#include "base/types.hh" +#include "mem/cache/compressors/base.hh" + +struct BDIParams; + +/** + * Default maximum number of bases in the original BDI. + */ +#define BDI_DEFAULT_MAX_NUM_BASES 2 + +class BDI : public BaseCacheCompressor +{ + protected: + /** + * Forward declaration of comp data classes. + */ + class BDICompData; + class BDICompDataZeros; + class BDICompDataRep; + class BDICompDataUncompressed; + template class BDICompDataBaseDelta; + + /** + * The possible encoding values. If modified, ENCODING_NAMES must be too. + */ + enum ENCODING {ZERO, REP_VALUES, BASE8_1, BASE8_2, BASE8_4, BASE4_1, + BASE4_2, BASE2_1, UNCOMPRESSED, NUM_ENCODINGS}; + + /** + * The respective encoding names. They are indexed by the ENCODING enum. + * The values are assigned in the source file, and should be modified if + * ENCODING is changed. + */ + static const char* ENCODING_NAMES[]; + + /** + * If set, create multiple compressor instances for each possible + * combination of base and delta size. Otherwise, just create a + * compressor for each base size with the highest available delta + * size. This can be used to save area and power (having less + * compressors). True by default. + */ + const bool useMoreCompressors; + + /** + * Number of qwords in a cache line. + */ + const std::size_t qwordsPerCacheLine; + + /** + * @defgroup CompressionStats Compression specific statistics. + * @{ + */ + + /** + * Number of data entries that were compressed to each encoding. + */ + Stats::Vector encodingStats; + + /** + * @} + */ + + /** + * Check if the cache line consists of only zero values. + * + * @param data The cache line. + * @return True if it is a ZERO cache line. + */ + bool isZeroPackable(const uint64_t* data) const; + + /** + * Check if the cache line consists only of same values. + * + * @param data The cache line. + * @return True if it is a REP_VALUES cache line. + */ + bool isSameValuePackable(const uint64_t* data) const; + + /** + * Instantiate a BaseDelta compressor with given TB and TD, and try to + * compress the cache line. If the compression fails, it returns a nullptr. + * @sa BDICompDataBaseDelta + * + * @tparam TB Type of a base entry. + * @tparam TD Type of a delta entry. + * @param data The cache line to be compressed. + * @param encoding Encoding value for given TB-TD combination. + * @return Cache line after compression or nullptr. + */ + template + std::unique_ptr tryCompress(const uint64_t* data, + const uint8_t encoding) const; + + /** + * Apply compression. + * + * @param data The cache line to be compressed. + * @param comp_lat Compression latency in number of cycles. + * @param decomp_lat Decompression latency in number of cycles. + * @param comp_size Compressed data size. + */ + std::unique_ptr compress( + const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override; + + /** + * Decompress data. + * + * @param comp_data Compressed cache line. + * @param data The cache line to be decompressed. + * @return Decompression latency in number of cycles. + */ + void decompress(const BaseCacheCompressor::CompressionData* comp_data, + uint64_t* data) override; + + public: + /** Convenience typedef. */ + typedef BDIParams Params; + + /** + * Default constructor. + */ + BDI(const Params *p); + + /** + * Default destructor. + */ + ~BDI() = default; + + /** + * Register local statistics. + */ + void regStats() override; +}; + +/** + * Template for the BDI compression data. + */ +class BDI::BDICompData : public CompressionData +{ + private: + /** + * Data encoding. + * @sa BDI + */ + const uint8_t _encoding; + + protected: + /** + * Number of bits needed for the encoding field. + */ + static const std::size_t encodingBits = 4; + + /** + * Calculate and set compressed data size. + * Each BDI compressor generates compressed data with different sizes. + */ + virtual void calculateCompressedSize() = 0; + + public: + /** + * Default constructor. + * + * @param encoding The encoding value. + */ + BDICompData(const uint8_t encoding); + + /** + * Default destructor. + */ + virtual ~BDICompData() = default; + + /** + * Get and decompress data at given index. + * + * The index is given relative to 64-bit entries, therefore if the base + * size of the given compressed data is smaller than that, this function + * joins multiple base-delta entries to generate the respective 64-bit + * entry. + * + * @param index The index of the compressed data. + * @return Decompressed data for the given index. + */ + virtual uint64_t access(const int index) const = 0; + + /** + * Get encoding. + * + * @return The encoding. + */ + uint8_t getEncoding() const; + + /** + * Get encoding name. + * + * @return The encoding name. + */ + std::string getName() const; +}; + +/** + * BDI compressed data containing the ZERO encoding. + */ +class BDI::BDICompDataZeros : public BDICompData +{ + protected: + /** + * Calculate compressed data size using ZERO encoding. + */ + void calculateCompressedSize() override; + + public: + /** + * Default constructor. + */ + BDICompDataZeros(); + + /** + * Get and decompress data at given index. Must always return 0. + * + * @param index The index of the compressed data. + * @return Decompressed data for the given index. + */ + uint64_t access(const int index) const override; +}; + +/** + * BDI compressed data containing the REP_VALUES encoding. + */ +class BDI::BDICompDataRep : public BDICompData +{ + private: + /** + * The repeated value. + */ + uint64_t base; + + protected: + /** + * Calculate compressed data size using REP_VALUES encoding. + */ + void calculateCompressedSize() override; + + public: + /** + * Default constructor. + * + * @param rep_value The repeated value. + */ + BDICompDataRep(const uint64_t rep_value); + + /** + * Get and decompress data at given index. Must always return the same + * value as data[0]. + * + * @param index The index of the compressed data. + * @return Decompressed data for the given index. + */ + uint64_t access(const int index) const override; +}; + +/** + * BDI compressed data containing the UNCOMPRESSED encoding. + */ +class BDI::BDICompDataUncompressed : public BDICompData +{ + private: + /** + * Uncompressed cache line size (in bytes). + */ + const std::size_t blkSize; + + /** + * The compressed data is the original cache line. + */ + const std::vector _data; + + protected: + /** + * Calculate compressed data size using UNCOMPRESSED encoding. + */ + void calculateCompressedSize() override; + + public: + /** + * Default constructor. + * + * @param data The data on which compression was applied. + * @param blk_size Size of a cache line in bytes. + */ + BDICompDataUncompressed(const uint64_t* data, + const std::size_t blk_size); + + /** + * Get and decompress data at given index. Must return the same + * value as _data[index]. + * + * @param index The index of the compressed data. + * @return Decompressed data for the given index. + */ + uint64_t access(const int index) const override; +}; + +/** + * Template class for BDI compressed data containing all the BASE_DELTA + * encodings. TB's size must always be greater than TD's. + * + * @tparam TB Type of a base entry. + * @tparam TD Type of a delta entry. +*/ +template +class BDI::BDICompDataBaseDelta : public BDICompData +{ + protected: + /** + * Maximum number of bases. + */ + const std::size_t maxNumBases; + + /** + * Bit mask to differentiate between the bases. + */ + std::vector bitMask; + + /** + * Bases. bases[0] is 0 and is not stored in a hardware implementation. + */ + std::vector bases; + + /** + * Array of deltas (or immediate values). + */ + std::vector deltas; + + /** + * Add a base to the bases vector. + * + * @param base The base to be added. + * @return True on success, false if already used all base slots. + */ + bool addBase(const TB base); + + /** + * Add a delta to the deltas vector. + * + * @param base_index Base to which the delta refers. + * @param delta The delta value. + */ + void addDelta(const std::size_t base_index, const TD delta); + + /** + * Calculate compressed data size using number of bases, the base size and + * the delta size. + */ + void calculateCompressedSize() override; + + public: + /** + * Default constructor. + * + * @param encoding The encoding value for this compressor. + * @param blk_size Size of a cache line in bytes. + * @param max_num_bases Maximum number of bases allowed to be stored. + */ + BDICompDataBaseDelta(const uint8_t encoding, const std::size_t blk_size, + const std::size_t max_num_bases = BDI_DEFAULT_MAX_NUM_BASES); + + /** + * Get and decompress data at given index. + * + * @param index The index of the compressed data. + * @return Decompressed data for the given index. + */ + uint64_t access(const int index) const override; + + /** + * Apply base delta compression. + * + * @param data The data on which compression was applied. + * @param blk_size Size of a cache line in bytes. + * @return True on success. + */ + bool compress(const uint64_t* data, const std::size_t blk_size); +}; + +#endif //__MEM_CACHE_COMPRESSORS_BDI_HH__ -- cgit v1.2.3