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 <noreply+kokoro@google.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

1 files changed, 428 insertions, 0 deletions

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 <cstdint>
+#include <memory>
+#include <vector>
+
+#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 TB, class TD> 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 <class TB, class TD>
+    std::unique_ptr<BDICompData> 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<BaseCacheCompressor::CompressionData> 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<uint64_t> _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 TB, class TD>
+class BDI::BDICompDataBaseDelta : public BDICompData
+{
+  protected:
+    /**
+     * Maximum number of bases.
+     */
+    const std::size_t maxNumBases;
+
+    /**
+     * Bit mask to differentiate between the bases.
+     */
+    std::vector<uint8_t> bitMask;
+
+    /**
+     * Bases. bases[0] is 0 and is not stored in a hardware implementation.
+     */
+    std::vector<TB> bases;
+
+    /**
+     * Array of deltas (or immediate values).
+     */
+    std::vector<TD> 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__