bdi.hh revision 13944:5000533e6b81
19243SN/A/* 212706Swendy.elsasser@arm.com * Copyright (c) 2018 Inria 39243SN/A * All rights reserved. 49243SN/A * 59243SN/A * Redistribution and use in source and binary forms, with or without 69243SN/A * modification, are permitted provided that the following conditions are 79243SN/A * met: redistributions of source code must retain the above copyright 89243SN/A * notice, this list of conditions and the following disclaimer; 99243SN/A * redistributions in binary form must reproduce the above copyright 109243SN/A * notice, this list of conditions and the following disclaimer in the 119243SN/A * documentation and/or other materials provided with the distribution; 129243SN/A * neither the name of the copyright holders nor the names of its 139243SN/A * contributors may be used to endorse or promote products derived from 149831SN/A * this software without specific prior written permission. 159831SN/A * 169831SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 179243SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 189243SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 199243SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 209243SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 219243SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 229243SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 239243SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 249243SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 259243SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 269243SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 279243SN/A * 289243SN/A * Authors: Daniel Carvalho 299243SN/A */ 309243SN/A 319243SN/A/** @file 329243SN/A * Definition of "Base-Delta-Immediate Compression: Practical Data Compression 339243SN/A * for On-Chip Caches". 349243SN/A */ 359243SN/A 369243SN/A#ifndef __MEM_CACHE_COMPRESSORS_BDI_HH__ 379243SN/A#define __MEM_CACHE_COMPRESSORS_BDI_HH__ 389243SN/A 399243SN/A#include <cstdint> 409243SN/A#include <memory> 419243SN/A#include <vector> 429967SN/A 4310618SOmar.Naji@arm.com#include "base/types.hh" 4411678Swendy.elsasser@arm.com#include "mem/cache/compressors/base.hh" 4512266Sradhika.jagtap@arm.com 469243SN/Astruct BDIParams; 479243SN/A 4811793Sbrandon.potter@amd.com/** 4911793Sbrandon.potter@amd.com * Default maximum number of bases in the original BDI. 5010146Sandreas.hansson@arm.com */ 519356SN/A#define BDI_DEFAULT_MAX_NUM_BASES 2 5210146Sandreas.hansson@arm.com 5310247Sandreas.hansson@arm.comclass BDI : public BaseCacheCompressor 5410208Sandreas.hansson@arm.com{ 559352SN/A protected: 569814SN/A /** 579243SN/A * Forward declaration of comp data classes. 589243SN/A */ 5910432SOmar.Naji@arm.com class BDICompData; 609243SN/A class BDICompDataZeros; 6110146Sandreas.hansson@arm.com class BDICompDataRep; 629243SN/A class BDICompDataUncompressed; 6310619Sandreas.hansson@arm.com template <class TB, class TD> class BDICompDataBaseDelta; 649243SN/A 6510211Sandreas.hansson@arm.com /** 6611678Swendy.elsasser@arm.com * The possible encoding values. If modified, ENCODING_NAMES must be too. 6712084Sspwilson2@wisc.edu */ 6812084Sspwilson2@wisc.edu enum ENCODING {ZERO, REP_VALUES, BASE8_1, BASE8_2, BASE8_4, BASE4_1, 6910489SOmar.Naji@arm.com BASE4_2, BASE2_1, UNCOMPRESSED, NUM_ENCODINGS}; 709831SN/A 719831SN/A /** 729831SN/A * The respective encoding names. They are indexed by the ENCODING enum. 739831SN/A * The values are assigned in the source file, and should be modified if 749831SN/A * ENCODING is changed. 7510140SN/A */ 7610646Sandreas.hansson@arm.com static const char* ENCODING_NAMES[]; 779243SN/A 7810394Swendy.elsasser@arm.com /** 7910394Swendy.elsasser@arm.com * If set, create multiple compressor instances for each possible 809566SN/A * combination of base and delta size. Otherwise, just create a 819243SN/A * compressor for each base size with the highest available delta 829243SN/A * size. This can be used to save area and power (having less 8310140SN/A * compressors). True by default. 8410140SN/A */ 8510147Sandreas.hansson@arm.com const bool useMoreCompressors; 8610147Sandreas.hansson@arm.com 8712706Swendy.elsasser@arm.com /** 8812706Swendy.elsasser@arm.com * Number of qwords in a cache line. 8910394Swendy.elsasser@arm.com */ 9010394Swendy.elsasser@arm.com const std::size_t qwordsPerCacheLine; 9111673SOmar.Naji@arm.com 9212706Swendy.elsasser@arm.com /** 9312706Swendy.elsasser@arm.com * @defgroup CompressionStats Compression specific statistics. 949243SN/A * @{ 959243SN/A */ 9610141SN/A 979726SN/A /** 989726SN/A * Number of data entries that were compressed to each encoding. 9912706Swendy.elsasser@arm.com */ 10012266Sradhika.jagtap@arm.com Stats::Vector encodingStats; 10112266Sradhika.jagtap@arm.com 1029243SN/A /** 10310620Sandreas.hansson@arm.com * @} 10410620Sandreas.hansson@arm.com */ 10510620Sandreas.hansson@arm.com 10610620Sandreas.hansson@arm.com /** 10710620Sandreas.hansson@arm.com * Check if the cache line consists of only zero values. 10810889Sandreas.hansson@arm.com * 10910889Sandreas.hansson@arm.com * @param data The cache line. 11010889Sandreas.hansson@arm.com * @return True if it is a ZERO cache line. 11110618SOmar.Naji@arm.com */ 11212081Sspwilson2@wisc.edu bool isZeroPackable(const uint64_t* data) const; 11310618SOmar.Naji@arm.com 11410246Sandreas.hansson@arm.com /** 11510246Sandreas.hansson@arm.com * Check if the cache line consists only of same values. 11610140SN/A * 11710140SN/A * @param data The cache line. 11810140SN/A * @return True if it is a REP_VALUES cache line. 11910140SN/A */ 12010140SN/A bool isSameValuePackable(const uint64_t* data) const; 1219243SN/A 1229243SN/A /** 1239567SN/A * Instantiate a BaseDelta compressor with given TB and TD, and try to 1249243SN/A * compress the cache line. If the compression fails, it returns a nullptr. 12510489SOmar.Naji@arm.com * @sa BDICompDataBaseDelta 12610489SOmar.Naji@arm.com * 12710489SOmar.Naji@arm.com * @tparam TB Type of a base entry. 12810489SOmar.Naji@arm.com * @tparam TD Type of a delta entry. 12910489SOmar.Naji@arm.com * @param data The cache line to be compressed. 13010489SOmar.Naji@arm.com * @param encoding Encoding value for given TB-TD combination. 13110489SOmar.Naji@arm.com * @return Cache line after compression or nullptr. 13210489SOmar.Naji@arm.com */ 13310489SOmar.Naji@arm.com template <class TB, class TD> 13410489SOmar.Naji@arm.com std::unique_ptr<BDICompData> tryCompress(const uint64_t* data, 1359243SN/A const uint8_t encoding) const; 1369243SN/A 1379831SN/A /** 1389831SN/A * Apply compression. 1399831SN/A * 1409831SN/A * @param data The cache line to be compressed. 1419831SN/A * @param comp_lat Compression latency in number of cycles. 1429243SN/A * @param decomp_lat Decompression latency in number of cycles. 14310207Sandreas.hansson@arm.com * @param comp_size Compressed data size. 14410207Sandreas.hansson@arm.com */ 14510207Sandreas.hansson@arm.com std::unique_ptr<BaseCacheCompressor::CompressionData> compress( 14610207Sandreas.hansson@arm.com const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override; 14710207Sandreas.hansson@arm.com 14810394Swendy.elsasser@arm.com /** 14910394Swendy.elsasser@arm.com * Decompress data. 15010394Swendy.elsasser@arm.com * 15110394Swendy.elsasser@arm.com * @param comp_data Compressed cache line. 15210394Swendy.elsasser@arm.com * @param data The cache line to be decompressed. 15310394Swendy.elsasser@arm.com * @return Decompression latency in number of cycles. 15410394Swendy.elsasser@arm.com */ 15510394Swendy.elsasser@arm.com void decompress(const BaseCacheCompressor::CompressionData* comp_data, 15610394Swendy.elsasser@arm.com uint64_t* data) override; 15710394Swendy.elsasser@arm.com 15810394Swendy.elsasser@arm.com public: 15910394Swendy.elsasser@arm.com /** Convenience typedef. */ 16010394Swendy.elsasser@arm.com typedef BDIParams Params; 16110394Swendy.elsasser@arm.com 16210394Swendy.elsasser@arm.com /** 16310394Swendy.elsasser@arm.com * Default constructor. 16410394Swendy.elsasser@arm.com */ 16510394Swendy.elsasser@arm.com BDI(const Params *p); 16610394Swendy.elsasser@arm.com 16710394Swendy.elsasser@arm.com /** 16810394Swendy.elsasser@arm.com * Default destructor. 16912706Swendy.elsasser@arm.com */ 17012706Swendy.elsasser@arm.com ~BDI() = default; 17112706Swendy.elsasser@arm.com 17212706Swendy.elsasser@arm.com /** 17312706Swendy.elsasser@arm.com * Register local statistics. 17412706Swendy.elsasser@arm.com */ 17510394Swendy.elsasser@arm.com void regStats() override; 17610561SOmar.Naji@arm.com}; 17710561SOmar.Naji@arm.com 17810394Swendy.elsasser@arm.com/** 17910394Swendy.elsasser@arm.com * Template for the BDI compression data. 18010394Swendy.elsasser@arm.com */ 18110394Swendy.elsasser@arm.comclass BDI::BDICompData : public CompressionData 18210394Swendy.elsasser@arm.com{ 18310394Swendy.elsasser@arm.com private: 1849243SN/A /** 1859243SN/A * Data encoding. 1869243SN/A * @sa BDI 18710146Sandreas.hansson@arm.com */ 18810140SN/A const uint8_t _encoding; 18910466Sandreas.hansson@arm.com 19010466Sandreas.hansson@arm.com protected: 19110466Sandreas.hansson@arm.com /** 19210146Sandreas.hansson@arm.com * Number of bits needed for the encoding field. 19310140SN/A */ 19410140SN/A static const std::size_t encodingBits = 4; 19510140SN/A 19610646Sandreas.hansson@arm.com /** 19710646Sandreas.hansson@arm.com * Calculate and set compressed data size. 19810646Sandreas.hansson@arm.com * Each BDI compressor generates compressed data with different sizes. 19910646Sandreas.hansson@arm.com */ 20010646Sandreas.hansson@arm.com virtual void calculateCompressedSize() = 0; 20110646Sandreas.hansson@arm.com 20210646Sandreas.hansson@arm.com public: 20310646Sandreas.hansson@arm.com /** 20410646Sandreas.hansson@arm.com * Default constructor. 20510646Sandreas.hansson@arm.com * 20610646Sandreas.hansson@arm.com * @param encoding The encoding value. 20710646Sandreas.hansson@arm.com */ 20810646Sandreas.hansson@arm.com BDICompData(const uint8_t encoding); 20910646Sandreas.hansson@arm.com 21010646Sandreas.hansson@arm.com /** 21110646Sandreas.hansson@arm.com * Default destructor. 21210646Sandreas.hansson@arm.com */ 21310646Sandreas.hansson@arm.com virtual ~BDICompData() = default; 21410646Sandreas.hansson@arm.com 21510646Sandreas.hansson@arm.com /** 21610646Sandreas.hansson@arm.com * Get and decompress data at given index. 21710646Sandreas.hansson@arm.com * 21810646Sandreas.hansson@arm.com * The index is given relative to 64-bit entries, therefore if the base 21910646Sandreas.hansson@arm.com * size of the given compressed data is smaller than that, this function 22010646Sandreas.hansson@arm.com * joins multiple base-delta entries to generate the respective 64-bit 22110646Sandreas.hansson@arm.com * entry. 22210646Sandreas.hansson@arm.com * 22310646Sandreas.hansson@arm.com * @param index The index of the compressed data. 22410646Sandreas.hansson@arm.com * @return Decompressed data for the given index. 22510646Sandreas.hansson@arm.com */ 22610646Sandreas.hansson@arm.com virtual uint64_t access(const int index) const = 0; 22710646Sandreas.hansson@arm.com 22810646Sandreas.hansson@arm.com /** 22910646Sandreas.hansson@arm.com * Get encoding. 23010646Sandreas.hansson@arm.com * 23110646Sandreas.hansson@arm.com * @return The encoding. 23210646Sandreas.hansson@arm.com */ 23310646Sandreas.hansson@arm.com uint8_t getEncoding() const; 23410646Sandreas.hansson@arm.com 23510646Sandreas.hansson@arm.com /** 23610140SN/A * Get encoding name. 23710140SN/A * 23810140SN/A * @return The encoding name. 23910146Sandreas.hansson@arm.com */ 2409243SN/A std::string getName() const; 24110619Sandreas.hansson@arm.com}; 24210619Sandreas.hansson@arm.com 24310618SOmar.Naji@arm.com/** 24410619Sandreas.hansson@arm.com * BDI compressed data containing the ZERO encoding. 24510619Sandreas.hansson@arm.com */ 24610619Sandreas.hansson@arm.comclass BDI::BDICompDataZeros : public BDICompData 24710619Sandreas.hansson@arm.com{ 24810619Sandreas.hansson@arm.com protected: 24910619Sandreas.hansson@arm.com /** 25010619Sandreas.hansson@arm.com * Calculate compressed data size using ZERO encoding. 25110619Sandreas.hansson@arm.com */ 25210619Sandreas.hansson@arm.com void calculateCompressedSize() override; 25310619Sandreas.hansson@arm.com 25410619Sandreas.hansson@arm.com public: 25510619Sandreas.hansson@arm.com /** 25610619Sandreas.hansson@arm.com * Default constructor. 25710619Sandreas.hansson@arm.com */ 25812706Swendy.elsasser@arm.com BDICompDataZeros(); 25910618SOmar.Naji@arm.com 2609243SN/A /** 2619243SN/A * Get and decompress data at given index. Must always return 0. 2629243SN/A * 26310146Sandreas.hansson@arm.com * @param index The index of the compressed data. 2649243SN/A * @return Decompressed data for the given index. 2659243SN/A */ 2669243SN/A uint64_t access(const int index) const override; 26711334Sandreas.hansson@arm.com}; 26811334Sandreas.hansson@arm.com 26911334Sandreas.hansson@arm.com/** 2709243SN/A * BDI compressed data containing the REP_VALUES encoding. 2719243SN/A */ 2729243SN/Aclass BDI::BDICompDataRep : public BDICompData 2739243SN/A{ 27411334Sandreas.hansson@arm.com private: 2759243SN/A /** 2769243SN/A * The repeated value. 2779243SN/A */ 2789243SN/A uint64_t base; 2799243SN/A 2809243SN/A protected: 2819243SN/A /** 2829243SN/A * Calculate compressed data size using REP_VALUES encoding. 28310146Sandreas.hansson@arm.com */ 2849243SN/A void calculateCompressedSize() override; 2859831SN/A 2869831SN/A public: 2879831SN/A /** 2889243SN/A * Default constructor. 2899831SN/A * 2909831SN/A * @param rep_value The repeated value. 2919243SN/A */ 2929243SN/A BDICompDataRep(const uint64_t rep_value); 2939243SN/A 29410146Sandreas.hansson@arm.com /** 2959243SN/A * Get and decompress data at given index. Must always return the same 2969831SN/A * value as data[0]. 2979831SN/A * 2989831SN/A * @param index The index of the compressed data. 2999243SN/A * @return Decompressed data for the given index. 3009243SN/A */ 30110146Sandreas.hansson@arm.com uint64_t access(const int index) const override; 30210146Sandreas.hansson@arm.com}; 30310143SN/A 3049243SN/A/** 3059669SN/A * BDI compressed data containing the UNCOMPRESSED encoding. 30610136SN/A */ 30710136SN/Aclass BDI::BDICompDataUncompressed : public BDICompData 3089243SN/A{ 3099967SN/A private: 31010245Sandreas.hansson@arm.com /** 31110245Sandreas.hansson@arm.com * Uncompressed cache line size (in bytes). 31210245Sandreas.hansson@arm.com */ 3139243SN/A const std::size_t blkSize; 31410286Sandreas.hansson@arm.com 31510286Sandreas.hansson@arm.com /** 3169831SN/A * The compressed data is the original cache line. 3179243SN/A */ 3189491SN/A const std::vector<uint64_t> _data; 3199831SN/A 32010136SN/A protected: 3219491SN/A /** 3229491SN/A * Calculate compressed data size using UNCOMPRESSED encoding. 3239831SN/A */ 3249243SN/A void calculateCompressedSize() override; 3259669SN/A 3269566SN/A public: 3279566SN/A /** 3289669SN/A * Default constructor. 3299669SN/A * 3309669SN/A * @param data The data on which compression was applied. 3319669SN/A * @param blk_size Size of a cache line in bytes. 3329669SN/A */ 3339669SN/A BDICompDataUncompressed(const uint64_t* data, 3349669SN/A const std::size_t blk_size); 3359669SN/A 3369669SN/A /** 3379669SN/A * Get and decompress data at given index. Must return the same 33811189Sandreas.hansson@arm.com * value as _data[index]. 3399669SN/A * 34010136SN/A * @param index The index of the compressed data. 34110286Sandreas.hansson@arm.com * @return Decompressed data for the given index. 34210286Sandreas.hansson@arm.com */ 34310286Sandreas.hansson@arm.com uint64_t access(const int index) const override; 3449669SN/A}; 3459669SN/A 3469669SN/A/** 34710286Sandreas.hansson@arm.com * Template class for BDI compressed data containing all the BASE_DELTA 34810286Sandreas.hansson@arm.com * encodings. TB's size must always be greater than TD's. 3499669SN/A * 3509669SN/A * @tparam TB Type of a base entry. 3519491SN/A * @tparam TD Type of a delta entry. 3529243SN/A*/ 3539243SN/Atemplate <class TB, class TD> 3549243SN/Aclass BDI::BDICompDataBaseDelta : public BDICompData 3559491SN/A{ 3569491SN/A protected: 3579243SN/A /** 3589243SN/A * Maximum number of bases. 3599243SN/A */ 36011189Sandreas.hansson@arm.com const std::size_t maxNumBases; 3619243SN/A 36210136SN/A /** 3639491SN/A * Bit mask to differentiate between the bases. 3649491SN/A */ 3659491SN/A std::vector<uint8_t> bitMask; 36610286Sandreas.hansson@arm.com 36710286Sandreas.hansson@arm.com /** 36810286Sandreas.hansson@arm.com * Bases. bases[0] is 0 and is not stored in a hardware implementation. 3699566SN/A */ 3709566SN/A std::vector<TB> bases; 3719566SN/A 3729566SN/A /** 3739566SN/A * Array of deltas (or immediate values). 3749491SN/A */ 3759491SN/A std::vector<TD> deltas; 3769243SN/A 3779243SN/A /** 3789243SN/A * Add a base to the bases vector. 3799491SN/A * 3809243SN/A * @param base The base to be added. 3819243SN/A * @return True on success, false if already used all base slots. 3829243SN/A */ 38310286Sandreas.hansson@arm.com bool addBase(const TB base); 38410286Sandreas.hansson@arm.com 3859243SN/A /** 38611189Sandreas.hansson@arm.com * Add a delta to the deltas vector. 3879243SN/A * 3889243SN/A * @param base_index Base to which the delta refers. 3899243SN/A * @param delta The delta value. 3909243SN/A */ 3919243SN/A void addDelta(const std::size_t base_index, const TD delta); 3929243SN/A 3939243SN/A /** 39410245Sandreas.hansson@arm.com * Calculate compressed data size using number of bases, the base size and 3959243SN/A * the delta size. 3969243SN/A */ 3979831SN/A void calculateCompressedSize() override; 3989243SN/A 3999243SN/A public: 4009567SN/A /** 4019567SN/A * Default constructor. 4029967SN/A * 4039967SN/A * @param encoding The encoding value for this compressor. 40410618SOmar.Naji@arm.com * @param blk_size Size of a cache line in bytes. 4059243SN/A * @param max_num_bases Maximum number of bases allowed to be stored. 4069243SN/A */ 4079243SN/A BDICompDataBaseDelta(const uint8_t encoding, const std::size_t blk_size, 40810146Sandreas.hansson@arm.com const std::size_t max_num_bases = BDI_DEFAULT_MAX_NUM_BASES); 4099243SN/A 4109243SN/A /** 4119243SN/A * Get and decompress data at given index. 4129243SN/A * 4139243SN/A * @param index The index of the compressed data. 4149831SN/A * @return Decompressed data for the given index. 4159831SN/A */ 4169831SN/A uint64_t access(const int index) const override; 4179831SN/A 4189831SN/A /** 4199831SN/A * Apply base delta compression. 4209831SN/A * 4219831SN/A * @param data The data on which compression was applied. 4229243SN/A * @param blk_size Size of a cache line in bytes. 4239831SN/A * @return True on success. 4249831SN/A */ 4259831SN/A bool compress(const uint64_t* data, const std::size_t blk_size); 4269831SN/A}; 4279831SN/A 4289831SN/A#endif //__MEM_CACHE_COMPRESSORS_BDI_HH__ 4299831SN/A