1/*
2 * Copyright (c) 2018 Inria
3 * All rights reserved.
4 *
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.
15 *
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.
27 *
28 * Authors: Daniel Carvalho
29 */
30
31/** @file
32 * Definition of "Base-Delta-Immediate Compression: Practical Data Compression
33 * for On-Chip Caches".
34 */
35
36#ifndef __MEM_CACHE_COMPRESSORS_BDI_HH__
37#define __MEM_CACHE_COMPRESSORS_BDI_HH__
38
39#include <cstdint>
40#include <memory>
41#include <vector>
42
43#include "base/types.hh"
44#include "mem/cache/compressors/base.hh"
45
46struct BDIParams;
47
48/**
49 * Default maximum number of bases in the original BDI.
50 */
51#define BDI_DEFAULT_MAX_NUM_BASES 2
52
53class BDI : public BaseCacheCompressor
54{
55  protected:
56    /**
57     * Forward declaration of comp data classes.
58     */
59    class BDICompData;
60    class BDICompDataZeros;
61    class BDICompDataRep;
62    class BDICompDataUncompressed;
63    template <class TB, class TD> class BDICompDataBaseDelta;
64
65    /**
66     * The possible encoding values. If modified, ENCODING_NAMES must be too.
67     */
68    enum ENCODING {ZERO, REP_VALUES, BASE8_1, BASE8_2, BASE8_4, BASE4_1,
69                   BASE4_2, BASE2_1, UNCOMPRESSED, NUM_ENCODINGS};
70
71    /**
72     * The respective encoding names. They are indexed by the ENCODING enum.
73     * The values are assigned in the source file, and should be modified if
74     * ENCODING is changed.
75     */
76    static const char* ENCODING_NAMES[];
77
78    /**
79     * If set, create multiple compressor instances for each possible
80     * combination of base and delta size. Otherwise, just create a
81     * compressor for each base size with the highest available delta
82     * size. This can be used to save area and power (having less
83     * compressors). True by default.
84     */
85    const bool useMoreCompressors;
86
87    /**
88     * Number of qwords in a cache line.
89     */
90    const std::size_t qwordsPerCacheLine;
91
92    /**
93     * @defgroup CompressionStats Compression specific statistics.
94     * @{
95     */
96
97    /**
98     * Number of data entries that were compressed to each encoding.
99     */
100    Stats::Vector encodingStats;
101
102    /**
103     * @}
104     */
105
106    /**
107     * Check if the cache line consists of only zero values.
108     *
109     * @param data The cache line.
110     * @return True if it is a ZERO cache line.
111     */
112    bool isZeroPackable(const uint64_t* data) const;
113
114    /**
115     * Check if the cache line consists only of same values.
116     *
117     * @param data The cache line.
118     * @return True if it is a REP_VALUES cache line.
119     */
120    bool isSameValuePackable(const uint64_t* data) const;
121
122    /**
123     * Instantiate a BaseDelta compressor with given TB and TD, and try to
124     * compress the cache line. If the compression fails, it returns a nullptr.
125     * @sa BDICompDataBaseDelta
126     *
127     * @tparam TB Type of a base entry.
128     * @tparam TD Type of a delta entry.
129     * @param data The cache line to be compressed.
130     * @param encoding Encoding value for given TB-TD combination.
131     * @return Cache line after compression or nullptr.
132     */
133    template <class TB, class TD>
134    std::unique_ptr<BDICompData> tryCompress(const uint64_t* data,
135                                             const uint8_t encoding) const;
136
137    /**
138     * Apply compression.
139     *
140     * @param data The cache line to be compressed.
141     * @param comp_lat Compression latency in number of cycles.
142     * @param decomp_lat Decompression latency in number of cycles.
143     * @param comp_size Compressed data size.
144     */
145    std::unique_ptr<BaseCacheCompressor::CompressionData> compress(
146        const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override;
147
148    /**
149     * Decompress data.
150     *
151     * @param comp_data Compressed cache line.
152     * @param data The cache line to be decompressed.
153     * @return Decompression latency in number of cycles.
154     */
155    void decompress(const BaseCacheCompressor::CompressionData* comp_data,
156                                           uint64_t* data) override;
157
158  public:
159    /** Convenience typedef. */
160    typedef BDIParams Params;
161
162    /**
163     * Default constructor.
164     */
165    BDI(const Params *p);
166
167    /**
168     * Default destructor.
169     */
170    ~BDI() = default;
171
172    /**
173     * Register local statistics.
174     */
175    void regStats() override;
176};
177
178/**
179 * Template for the BDI compression data.
180 */
181class BDI::BDICompData : public CompressionData
182{
183  private:
184    /**
185     * Data encoding.
186     * @sa BDI
187     */
188    const uint8_t _encoding;
189
190  protected:
191    /**
192     * Number of bits needed for the encoding field.
193     */
194    static const std::size_t encodingBits = 4;
195
196    /**
197     * Calculate and set compressed data size.
198     * Each BDI compressor generates compressed data with different sizes.
199    */
200    virtual void calculateCompressedSize() = 0;
201
202  public:
203    /**
204     * Default constructor.
205     *
206     * @param encoding The encoding value.
207     */
208    BDICompData(const uint8_t encoding);
209
210    /**
211     * Default destructor.
212     */
213    virtual ~BDICompData() = default;
214
215    /**
216     * Get and decompress data at given index.
217     *
218     * The index is given relative to 64-bit entries, therefore if the base
219     * size of the given compressed data is smaller than that, this function
220     * joins multiple base-delta entries to generate the respective 64-bit
221     * entry.
222     *
223     * @param index The index of the compressed data.
224     * @return Decompressed data for the given index.
225     */
226    virtual uint64_t access(const int index) const = 0;
227
228    /**
229     * Get encoding.
230     *
231     * @return The encoding.
232     */
233    uint8_t getEncoding() const;
234
235    /**
236     * Get encoding name.
237     *
238     * @return The encoding name.
239     */
240    std::string getName() const;
241};
242
243/**
244 * BDI compressed data containing the ZERO encoding.
245 */
246class BDI::BDICompDataZeros : public BDICompData
247{
248  protected:
249    /**
250     * Calculate compressed data size using ZERO encoding.
251     */
252    void calculateCompressedSize() override;
253
254  public:
255    /**
256     * Default constructor.
257    */
258    BDICompDataZeros();
259
260    /**
261     * Get and decompress data at given index. Must always return 0.
262     *
263     * @param index The index of the compressed data.
264     * @return Decompressed data for the given index.
265     */
266    uint64_t access(const int index) const override;
267};
268
269/**
270 * BDI compressed data containing the REP_VALUES encoding.
271 */
272class BDI::BDICompDataRep : public BDICompData
273{
274  private:
275    /**
276     * The repeated value.
277     */
278    uint64_t base;
279
280  protected:
281    /**
282     * Calculate compressed data size using REP_VALUES encoding.
283     */
284    void calculateCompressedSize() override;
285
286  public:
287    /**
288     * Default constructor.
289     *
290     * @param rep_value The repeated value.
291     */
292    BDICompDataRep(const uint64_t rep_value);
293
294    /**
295     * Get and decompress data at given index. Must always return the same
296     * value as data[0].
297     *
298     * @param index The index of the compressed data.
299     * @return Decompressed data for the given index.
300     */
301    uint64_t access(const int index) const override;
302};
303
304/**
305 * BDI compressed data containing the UNCOMPRESSED encoding.
306 */
307class BDI::BDICompDataUncompressed : public BDICompData
308{
309  private:
310    /**
311     * Uncompressed cache line size (in bytes).
312     */
313    const std::size_t blkSize;
314
315    /**
316     * The compressed data is the original cache line.
317     */
318    const std::vector<uint64_t> _data;
319
320  protected:
321    /**
322     * Calculate compressed data size using UNCOMPRESSED encoding.
323     */
324    void calculateCompressedSize() override;
325
326  public:
327    /**
328     * Default constructor.
329     *
330     * @param data The data on which compression was applied.
331     * @param blk_size Size of a cache line in bytes.
332     */
333    BDICompDataUncompressed(const uint64_t* data,
334                            const std::size_t blk_size);
335
336    /**
337     * Get and decompress data at given index. Must return the same
338     * value as _data[index].
339     *
340     * @param index The index of the compressed data.
341     * @return Decompressed data for the given index.
342     */
343    uint64_t access(const int index) const override;
344};
345
346/**
347 * Template class for BDI compressed data containing all the BASE_DELTA
348 * encodings. TB's size must always be greater than TD's.
349 *
350 * @tparam TB Type of a base entry.
351 * @tparam TD Type of a delta entry.
352*/
353template <class TB, class TD>
354class BDI::BDICompDataBaseDelta : public BDICompData
355{
356  protected:
357    /**
358     * Maximum number of bases.
359     */
360    const std::size_t maxNumBases;
361
362    /**
363     * Bit mask to differentiate between the bases.
364     */
365    std::vector<uint8_t> bitMask;
366
367    /**
368     * Bases. bases[0] is 0 and is not stored in a hardware implementation.
369     */
370    std::vector<TB> bases;
371
372    /**
373     * Array of deltas (or immediate values).
374     */
375    std::vector<TD> deltas;
376
377    /**
378     * Add a base to the bases vector.
379     *
380     * @param base The base to be added.
381     * @return True on success, false if already used all base slots.
382     */
383    bool addBase(const TB base);
384
385    /**
386     * Add a delta to the deltas vector.
387     *
388     * @param base_index Base to which the delta refers.
389     * @param delta The delta value.
390     */
391    void addDelta(const std::size_t base_index, const TD delta);
392
393    /**
394     * Calculate compressed data size using number of bases, the base size and
395     * the delta size.
396     */
397    void calculateCompressedSize() override;
398
399  public:
400    /**
401     * Default constructor.
402     *
403     * @param encoding The encoding value for this compressor.
404     * @param blk_size Size of a cache line in bytes.
405     * @param max_num_bases Maximum number of bases allowed to be stored.
406     */
407    BDICompDataBaseDelta(const uint8_t encoding, const std::size_t blk_size,
408        const std::size_t max_num_bases = BDI_DEFAULT_MAX_NUM_BASES);
409
410    /**
411     * Get and decompress data at given index.
412     *
413     * @param index The index of the compressed data.
414     * @return Decompressed data for the given index.
415     */
416    uint64_t access(const int index) const override;
417
418    /**
419     * Apply base delta compression.
420     *
421     * @param data The data on which compression was applied.
422     * @param blk_size Size of a cache line in bytes.
423     * @return True on success.
424     */
425    bool compress(const uint64_t* data, const std::size_t blk_size);
426};
427
428#endif //__MEM_CACHE_COMPRESSORS_BDI_HH__
429