2 * Copyright (c) 2018-2020 Inria
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.
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.
30 * Definition of a basic cache compressor.
33 #include "mem/cache/compressors/base.hh"
41 #include "base/trace.hh"
42 #include "debug/CacheComp.hh"
43 #include "mem/cache/base.hh"
44 #include "mem/cache/tags/super_blk.hh"
45 #include "params/BaseCacheCompressor.hh"
47 namespace Compressor
{
49 // Uncomment this line if debugging compression
50 //#define DEBUG_COMPRESSION
52 Base::CompressionData::CompressionData()
57 Base::CompressionData::~CompressionData()
62 Base::CompressionData::setSizeBits(std::size_t size
)
68 Base::CompressionData::getSizeBits() const
74 Base::CompressionData::getSize() const
76 return std::ceil(_size
/8);
79 Base::Base(const Params
&p
)
80 : SimObject(p
), blkSize(p
.block_size
), chunkSizeBits(p
.chunk_size_bits
),
81 sizeThreshold((blkSize
* p
.size_threshold_percentage
) / 100),
82 compChunksPerCycle(p
.comp_chunks_per_cycle
),
83 compExtraLatency(p
.comp_extra_latency
),
84 decompChunksPerCycle(p
.decomp_chunks_per_cycle
),
85 decompExtraLatency(p
.decomp_extra_latency
),
86 cache(nullptr), stats(*this)
88 fatal_if(64 % chunkSizeBits
,
89 "64 must be a multiple of the chunk granularity.");
91 fatal_if(((CHAR_BIT
* blkSize
) / chunkSizeBits
) < compChunksPerCycle
,
92 "Compressor processes more chunks per cycle than the number of "
93 "chunks in the input");
94 fatal_if(((CHAR_BIT
* blkSize
) / chunkSizeBits
) < decompChunksPerCycle
,
95 "Decompressor processes more chunks per cycle than the number of "
96 "chunks in the input");
98 fatal_if(blkSize
< sizeThreshold
, "Compressed data must fit in a block");
102 Base::setCache(BaseCache
*_cache
)
108 std::vector
<Base::Chunk
>
109 Base::toChunks(const uint64_t* data
) const
111 // Number of chunks in a 64-bit value
112 const unsigned num_chunks_per_64
=
113 (sizeof(uint64_t) * CHAR_BIT
) / chunkSizeBits
;
115 // Turn a 64-bit array into a chunkSizeBits-array
116 std::vector
<Chunk
> chunks((blkSize
* CHAR_BIT
) / chunkSizeBits
, 0);
117 for (int i
= 0; i
< chunks
.size(); i
++) {
118 const int index_64
= std::floor(i
/ (double)num_chunks_per_64
);
119 const unsigned start
= i
% num_chunks_per_64
;
120 chunks
[i
] = bits(data
[index_64
],
121 (start
+ 1) * chunkSizeBits
- 1, start
* chunkSizeBits
);
128 Base::fromChunks(const std::vector
<Chunk
>& chunks
, uint64_t* data
) const
130 // Number of chunks in a 64-bit value
131 const unsigned num_chunks_per_64
=
132 (sizeof(uint64_t) * CHAR_BIT
) / chunkSizeBits
;
134 // Turn a chunkSizeBits-array into a 64-bit array
135 std::memset(data
, 0, blkSize
);
136 for (int i
= 0; i
< chunks
.size(); i
++) {
137 const int index_64
= std::floor(i
/ (double)num_chunks_per_64
);
138 const unsigned start
= i
% num_chunks_per_64
;
139 replaceBits(data
[index_64
], (start
+ 1) * chunkSizeBits
- 1,
140 start
* chunkSizeBits
, chunks
[i
]);
144 std::unique_ptr
<Base::CompressionData
>
145 Base::compress(const uint64_t* data
, Cycles
& comp_lat
, Cycles
& decomp_lat
)
148 std::unique_ptr
<CompressionData
> comp_data
=
149 compress(toChunks(data
), comp_lat
, decomp_lat
);
151 // If we are in debug mode apply decompression just after the compression.
152 // If the results do not match, we've got an error
153 #ifdef DEBUG_COMPRESSION
154 uint64_t decomp_data
[blkSize
/8];
156 // Apply decompression
157 decompress(comp_data
.get(), decomp_data
);
159 // Check if decompressed line matches original cache line
160 fatal_if(std::memcmp(data
, decomp_data
, blkSize
),
161 "Decompressed line does not match original line.");
164 // Get compression size. If compressed size is greater than the size
165 // threshold, the compression is seen as unsuccessful
166 std::size_t comp_size_bits
= comp_data
->getSizeBits();
167 if (comp_size_bits
> sizeThreshold
* CHAR_BIT
) {
168 comp_size_bits
= blkSize
* CHAR_BIT
;
169 comp_data
->setSizeBits(comp_size_bits
);
170 stats
.failedCompressions
++;
174 stats
.compressions
++;
175 stats
.compressionSizeBits
+= comp_size_bits
;
176 if (comp_size_bits
!= 0) {
177 stats
.compressionSize
[1 + std::ceil(std::log2(comp_size_bits
))]++;
179 stats
.compressionSize
[0]++;
182 // Print debug information
183 DPRINTF(CacheComp
, "Compressed cache line from %d to %d bits. " \
184 "Compression latency: %llu, decompression latency: %llu\n",
185 blkSize
*8, comp_size_bits
, comp_lat
, decomp_lat
);
191 Base::getDecompressionLatency(const CacheBlk
* blk
)
193 const CompressionBlk
* comp_blk
= static_cast<const CompressionBlk
*>(blk
);
195 // If block is compressed, return its decompression latency
196 if (comp_blk
&& comp_blk
->isCompressed()){
197 const Cycles decomp_lat
= comp_blk
->getDecompressionLatency();
198 DPRINTF(CacheComp
, "Decompressing block: %s (%d cycles)\n",
199 comp_blk
->print(), decomp_lat
);
200 stats
.decompressions
+= 1;
204 // Block is not compressed, so there is no decompression latency
209 Base::setDecompressionLatency(CacheBlk
* blk
, const Cycles lat
)
212 assert(blk
!= nullptr);
215 static_cast<CompressionBlk
*>(blk
)->setDecompressionLatency(lat
);
219 Base::setSizeBits(CacheBlk
* blk
, const std::size_t size_bits
)
222 assert(blk
!= nullptr);
225 static_cast<CompressionBlk
*>(blk
)->setSizeBits(size_bits
);
228 Base::BaseStats::BaseStats(Base
& _compressor
)
229 : Stats::Group(&_compressor
), compressor(_compressor
),
230 ADD_STAT(compressions
, UNIT_COUNT
, "Total number of compressions"),
231 ADD_STAT(failedCompressions
, UNIT_COUNT
,
232 "Total number of failed compressions"),
233 ADD_STAT(compressionSize
, UNIT_COUNT
,
234 "Number of blocks that were compressed to this power of two "
236 ADD_STAT(compressionSizeBits
, UNIT_BIT
, "Total compressed data size"),
237 ADD_STAT(avgCompressionSizeBits
,
238 UNIT_RATE(Stats::Units::Bit
, Stats::Units::Count
),
239 "Average compression size"),
240 ADD_STAT(decompressions
, UNIT_COUNT
, "Total number of decompressions")
245 Base::BaseStats::regStats()
247 Stats::Group::regStats();
249 // Values comprised are {0, 1, 2, 4, ..., blkSize}
250 compressionSize
.init(std::log2(compressor
.blkSize
*8) + 2);
251 compressionSize
.subname(0, "0");
252 compressionSize
.subdesc(0,
253 "Number of blocks that compressed to fit in 0 bits");
254 for (unsigned i
= 0; i
<= std::log2(compressor
.blkSize
*8); ++i
) {
255 std::string str_i
= std::to_string(1 << i
);
256 compressionSize
.subname(1+i
, str_i
);
257 compressionSize
.subdesc(1+i
,
258 "Number of blocks that compressed to fit in " + str_i
+ " bits");
261 avgCompressionSizeBits
.flags(Stats::total
| Stats::nozero
| Stats::nonan
);
262 avgCompressionSizeBits
= compressionSizeBits
/ compressions
;
265 } // namespace Compressor